Добавление и вычитание Bigints с использованием связанных списков

Question

Я почти закончил с этим заданием, и оно меня убивает.Это мой ТРЕТИЙ пост о трех разных его разделах, и я, честно говоря, смущен тем, что так много борюсь с заданием.

Само назначение состоит в создании программы, которая выполняет сложение и вычитание большихцелые числа, использующие связанные списки (и я постепенно начинаю ненавидеть связанные списки за пределами Lisp).Кажется, теперь все работает, за исключением фактического сложения и вычитания.Я не уверен, что это арифметические функции, потому что они работали раньше (но никогда не на 100%), но это не помешает проверить с сообществом S / O (обычно я бы не стал так много проситьпомочь с заданием, потому что я предпочитаю выяснить все самостоятельно, но это была ужасная и беспокойная неделя, и крайний срок быстро приближается).

Арифметические функции, которые я написал, следующие:Может кто-нибудь помочь мне определить, что не так?

/*
 * Function add
 *
 * @Paramater STRUCT* Integer
 * @Parameter STRUCT* Integer
 *
 * Takes two linked lists representing
 * big integers stored in reversed order,
 * and returns a linked list containing
 * the sum of the two integers.
 *
 * @Return STRUCT* Integer
 * 
 * TODO Comment me
 */
struct integer* add( struct integer *p, struct integer *q )
{
    int carry = 0;

    struct integer *sHead, *sCurr;
    struct integer *pHead, *qHead;

    pHead = p;
    qHead = q;

    sHead = NULL;

    while( p )
    {
        sCurr = ( struct integer* ) malloc (sizeof(struct integer));
        sCurr->digit = p->digit + q->digit + carry;
        sCurr->next = sHead;
        sHead = sCurr;

        carry = 0;

        /*
         * If the current digits sum to greater than 9,
         * create a carry value and replace the current
         * value with value mod 10.
         */
        if( sCurr->digit > 9 )
        {
            carry = 1;
            sCurr->digit = sCurr->digit % 10;
        }

        /*
         * If the most significant digits of the numbers
         * sum to 10 or greater, create an extra node
         * at the end of the sum list and assign it the
         * value of 1.
         */
        if( carry == 1 && sCurr->next == NULL )
        {
            struct integer *sCarry = ( struct integer* ) malloc (sizeof(struct integer));
            sCarry->digit = 1;
            sCarry->next = NULL;
            reverse( &sCurr );
            sCurr->next = sCarry;
            reverse( &sCurr );
        }

        p = p->next;
        if( q->next ) q = q->next; 
        else q->digit = 0; 
    }

    return sHead;
}

---

/*
 * Function subtract
 *
 * @Parameter STRUCT* Integer
 * @Parameter STRUCT* Integer
 *
 * Takes two linked lists representing struct integers.
 * Traverses through the lists, subtracting each
 * digits from the subsequent nodes to form a new
 * struct integer, and then returns the newly formed
 * linked list.
 *
 * @Return STRUCT* Integer
 * 
 * TODO Comment me
 */
struct integer* subtract( struct integer *p, struct integer *q )
{
    int borrow = 0;

    struct integer *dHead, *dCurr;
    struct integer *pHead, *qHead;

    pHead = p;
    qHead = q;

    dHead = NULL;

    while( p )
    {
        dCurr = (struct integer*) malloc (sizeof(struct integer));
        if( q )
        {
            dCurr->digit = p->digit - q->digit - borrow;
        }
        else
        {
            dCurr->digit = p->digit - borrow;
        }
        dCurr->next = dHead;

        if( dCurr->digit < 0 )
        {
            dCurr->digit += 10;
            borrow = 1;
        }

        dHead = dCurr;

        p = p->next;
        if( q->next) q = q->next;
    }

    return dHead;
}

---

---

Пример вывода должен выглядеть следующим образом:

8888888888 + 2222222222 = 11111111110
10000000000 – 9999999999 = 1
10000000000 – 9999999999 = 1

, но вместо этого, это выглядит так:

8888888888 + 2222222222 = 1111111110
10000000000 - 9999999999 = 10000000001
10000000000 - 9999999999 = 10000000001

РЕДАКТИРОВАТЬ Вся программа в ее текущей форме по состоянию на 15:30 EST доступна здесь для справки, илив случае, если эти функции не являются проблемой.

Answer 1

Часть, которая читает

if( dCurr->next == NULL && carry == 1 )
{
    struct integer *dCarry = (struct integer*) malloc (sizeof(struct integer));
    dCarry->digit = -1;
    dCarry->next = NULL;
    dCurr->next = dCarry;
}

, выглядит немного неуместно.Исходя из приведенного выше кода, dCurr->next задается цифрами, которые мы уже вычислили в предыдущих циклах, поэтому в первой цифре оно равно NULL.Я думаю, что вы хотели проверить p->next.

Я предполагаю, что условие len(p) >= len(q) выполняется для этой функции.Если нет, вам придется что-то делать с обработкой, если она не сохраняется (из-за отсутствия p-узлов перед тем, как закончится q-узлов).Я также предполагаю, что цифры находятся в списке от наименее значимой цифры до самой значимой.Если нет, возможно, вам придется поменять местами p и q, прежде чем обрабатывать их.

Еще одна вещь, которую я не могу понять, это как вы обрабатываете отрицательные числа.Или даже если вы должны справиться с ними.Нелегко добавить к структуре, подобной этой, потому что наивный подход добавления чего-либо к концу не сработает при вычитании: когда q отрицательно, вы пойдете на все проблемы вычитания q из p, а затем обнаружите, чтоВы должны были добавить вместо этого.

Answer 2

В функции compare() вы "гуляете" p, а затем пытаетесь пройти его снова.

int compare( struct integer *p, struct integer *q )
{
    /* ... */
    while( p )
    {
        pCount++;
        p = p->next;
    }

p теперь NULL

    /* ... */
    while( p )
    {
        /* ... */
    }

Цикл while никогда не запускается.

Answer 3

else q->digit = 0;
Вы меняете аргумент внутри функции.

Попробуйте изменить свои функции, чтобы они принимали const аргументы и перекомпилировали.

struct integer* add( const struct integer *p, const struct integer *q )
struct integer* subtract( const struct integer *p, const struct integer *q )