views:

150

answers:

3

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.

+1  A: 

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 )
pmg
As part of the assignment, I can't change the function definitions. :/
Andrew
Ok, but change anyway, compile with `const` until you get no errors, then remove the `const` :)
pmg
@pmg It turns out that the biggest issue WAS `else q->digit = 0` in terms of one of the wonky errors, thanks for pointing that out.
Andrew
Thank you for the feedback Andrew. I knew it! LOL! But I didn't want to have too much of the "hunt the bug" fun. It's your bug, you should get the fun :)
pmg
+1  A: 

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.

Dysaster
Luckily, the program only deals with non-negative integers. Also, I do have it set up so that `subtract()` is never called with `p < q`.
Andrew
+1  A: 

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.

pmg
Good find, thank you. Now the only issue left is the `subtract()` function. :(
Andrew
What happens if the lengths of the numbers to subtract are different? Let's say `12` - `8` ... What's the first digit operation the function does?
pmg
Well, the numbers are stored in reverse, so it should do `2 - 8 = -6`, and then `-6 + 10 = 4`.
Andrew
Hmm ... I forgot about the reverse thing. But what happens to `q` in `12` - `8`? `q->digit` is 8, `q->next` is NULL. Pay attention to the last statement in the `while`
pmg
@pmg I changed it to `if( qCurr->next ) qCurr = qCurr->next; else qCurr->digit = 0;`. I'm getting really weird results, as evidenced by this http://pastebin.com/LqLdDSHH
Andrew
Hmmm ... I may have been wrong with that `q` thing before. Sorry. Is the `reverse` function ok? Print the argument (dereferenced) right at the beginning and end of the function. What's the reverse of `04`?
pmg
@pmg I rewrote `reverse` using some guidance from the internet and ended up with this: http://pastebin.com/ZL8S9ZRs It didn't really affect the outcome at all.
Andrew
So ... LOL ... you can change the function definitions. You need to pay attention to the `subtract` routine. The result of subtracting `21 reversed` and `8 reversed` is not `04 reversed`: it's `4 reversed`
pmg
@pmg Yeah, I just finished the assignment! It also turns out that in the `stripLeadingZeros` function, I was calling it recursively but the first step involved reversing the list so it never stripped all of the zeros. That, combined with me changing the value of `q->digit` in the function, led to the wonky errors. Thank you SO much for all of your help here.
Andrew