Basic Issues with Linked Lists

Question

I'm working on a homework assignment for CS1, and I almost have it finished but errors keep popping up in relation to a few functions I've tried to implement. The assignment is the classic addition and subtraction of big integers using linked lists. My issue isn't with any of mathematical functionality of the program, but rather getting the linked lists to print properly when finished. I'm pretty sure most of the problems reside within stripLeadingZeros(); the functions are as follows.

/*
 * Function stripLeadingZeros
 * 
 * @Parameter STRUCT** Integer
 * 
 * Step through a linked list, recursively unlinking 
 * all leading zeros and making the first
 * non-zero integer the head of the list.
 */
struct integer* stripLeadingZeros( struct integer *p )
{
    // Are we at the end of the list?
    if( p == NULL ) return NULL;

    // Are we deleting the current node?
    if( p->digit == 0 )
    {
        struct integer *pNext;

        pNext = p->next;

        // Deallocate the node
        free( p );

        // Return the pointer to the next node
        return pNext;
    }

    // Recurse to make sure next node is not 0
    p->next = stripLeadingZeros( p->next );

        return p;
}

---///---

/*
 * Function print
 *
 * @Parameter STRUCT* Integer
 *
 * Given a linked list, will traverse through
 * the nodes and print out, one at a time,
 * the digits comprising the struct integer that the
 * linked list represents.
 *
 * TODO: Print to file
 */
void print( struct integer *p )
{   
    struct integer *head = p;
    reverse( &p );
    p = stripLeadingZeros( p );

    while( p )
    {
        fprintf(outFile, "%d", p->digit);
        p = p->next;
    }

    reverse( &head );
}

---///---

/*
 * Function reverse
 * 
 * @Parameter STRUCT** Integer
 * 
 * Recursively reverses a linked list by
 * finding the tail each time, and linking the
 * tail to the node before it.
 */
void reverse (struct integer **p)
{
    /*
     * Example p: 1->2->3->4->NULL
     */
    if( (*p)->next == NULL ) return;

    struct integer *pCurr = *p, *i, *pTail;

    // Make pCurr into the tail
    while( pCurr->next )
    {
        i = pCurr;
        pCurr = pCurr->next;
    }

    // Syntactic Sugar
    pTail = pCurr;

    pTail->next = i;
    /*
     * p now looks like:
     * 1->2->3<->4
     */

    i->next = NULL;
    /*
     * p now looks like:
     * 1 -> 2 -> 3 <- 4
     *           |
     *           v
     *          NULL
     */

    reverse( p ); // Recurse using p: 1 -> 2 -> 3;
    *p = i;   
}

The output I am currently getting for the whole program is:

888888888 + 222222222 = 11111111
000000000 - 999999999 = 000000001
000000000 - 999999999 = 000000001

whereas the expected output is

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

Any help anyone could give would just be awesome; I've been working on this for so long that if I had any hair I'd have pulled it out by now.

EDIT My read_integer function is as follows:

/*
 * Function read_integer
 *
 * @Parameter CHAR* stringInt
 *
 * Parameter contains a string representing a struct integer.
 * Tokenizes the string by each character, converts each char
 * into an integer, and constructs a backwards linked list out
 * of the digits.
 *
 * @Return STRUCT* Integer
 */
struct integer* read_integer( char* stringInt )
{
    int i, n;
    struct integer *curr, *head;

    int numDigits = strlen( stringInt ); // Find the length of the struct integer
    head = NULL;

    for( i = 0; i < numDigits; i++ )
    {
        n = stringInt[i] - '0'; // Convert char to an integer

        curr = (struct integer *) malloc (sizeof( struct integer )); // Allocate memory for node
        curr->digit = n; // Digit of current node is assigned to n
        curr->next = head; // Move to the next node in the list.
        head = curr; // Move head up to the front of the list.
    }

    return head; // Return a pointer to the first node in the list.
} 

Answer 1

in your current version of stripLeadingZeros you can replace the while loop with an if statement that the result will be the same. Maybe that is the problem.

while (1) {
    /* ... */
    return 0; /* this "infinite loop" only runs once */
}

compare with

if (1) {
    /* ... */
    return 0;
}

Answer 2

Consider the control flow of this function:

struct integer* stripLeadingZeros( struct integer *p )
{
    // Are we at the end of the list?
    if( p == NULL ) return NULL;

    // Are we deleting the current node?
    if( p->digit == 0 )
    {
        struct integer *pNext;

        pNext = p->next;

        // Deallocate the node
        free( p );

        // Return the pointer to the next node
        return pNext;
    }

    // Recurse to make sure next node is not 0
    p->next = stripLeadingZeros( p->next );

    return p;
}

What happens when p starts with a zero? It enters the if statement, removes the one leading zero, and returns. It does not recurse because you've already returned within the if statement. This means that stripLeadingZeros will remove at most one zero.

Now what happens when p starts with a one? It skips the if statement, but it does recurse. This is also wrong, because once have seen a one, you want to stop removing zeroes, as they are no longer leading.

So what this function is actually doing is removing the first zero it encounters, leading or not, and then stopping. That's not what you want it to do.

You want to recurse after you have removed a zero, and only after you have removed a zero, so move the recursive call into the if statement. In other words, replace return pNext; with return stripLeadingZeros(pNext);, and remove the recursion from outside the loop.

Answer 3

Simulate stripLeadingZeros() on "0004".

It does not work. Also you ignored an edge case: what if it is only "0". You must not strip the only 0 in that case.

Correct code:

struct integer* stripLeadingZeros( struct integer *p )
{
    // Are we at the end of the list?
    if( p == NULL ) return NULL;

    // Are we deleting the current node? Also it should not strip last 0
    if( p->digit == 0 && p->next != NULL)
    {
        struct integer *pNext;

        pNext = p->next;

        // Deallocate the node
        free( p );

        // Try to strip zeros on pointer to the next node and return that pointer
        return stripLeadingZeros(pNext);
    }
    return p;
}

Answer 4

You can improve your reverse function by reversing your original list into another list:

void reverse(struct integer** p)
{
    struct integer* old = *p;
    struct integer* new = NULL;

    while(old != NULL)
    {
        struct integer* oldNext = old->next;
        old->next = new;
        new = old;

        old = oldNext;
    }
    *p = new;
}