Adding and Subtracting Bigints Using Linked Lists

Question

I'm almost done with this assignment, and it's killing me. This is my THIRD post about three different sections of this, and I'm honestly embarrassed that I'm struggling this much with the assignment.

The assignment itself is to make a program that performs addition and subtraction of big integers using linked lists (and I'm slowly starting to hate linked lists, outside of Lisp). Everything seems to be working now, save for the actual addition and subtraction. I'm not sure if it is the arithmetic functions, because they were sort of working before (but never 100%), but it doesn't hurt to check with the S/O community (normally I wouldn't ask for this much help on an assignment because I prefer to figure things out on my own, but this has been an awful and hectic week, and the deadline is fast approaching).

The arithmetic functions I've written are as follows, can anyone help me pick out what is wrong?

/*
 * 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;
}

---

---

The sample output should look like this:

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

but instead, it looks like this:

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

EDIT The entire program, in its current form as of 3:30PM EST, is available here for reference, or in case these functions are not the issue.

Answer 1

else q->digit = 0;
You are changing the argument inside the function.

Try changing your functions to accept const arguments and recompile.

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

Answer 2

The part that reads

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

looks a bit out of place. From the code above, dCurr->next is set to be the digits we've already calculated in earlier loops, so it is only NULL on the first digit. I think you meant to check p->next instead.

I am assuming that the condition len(p) >= len(q) holds for this function. If not, you will have to do something about handling where it doesn't hold (running out of p nodes before you run out of q nodes). I also assume the digits are in the list from least significant digit to most significant one. If not, you may need to reverse p and q before you process them.

One other thing I can't figure out is how you handle negative numbers. Or even if you are supposed to handle them. It is not easy to add to a structure like this, because a naive approach of adding something to the end would not work when subtracting: when q is negative, you will go to all the trouble of subtracting q from p, and then discover that you should have added instead.

Answer 3

In function compare() you "walk" p and afterwards try to walk it again.

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

p is now NULL

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

The while loop never runs.