链接列表的基本问题

Question

我正在为CS1做一个家庭作业,我几乎完成了它,但是我试图实现的一些功能的错误不断出现.赋值是使用链表的大整数的经典加法和减法.我的问题不在于程序的任何数学功能,而是在完成时使链接列表正确打印.我很确定大多数问题都存在于其中stripLeadingZeros(); 功能如下.

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

我目前获得的整个程序的输出是:

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

而预期的产出是

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

任何人都可以提供的任何帮助都会令人敬畏; 我一直在研究这个问题已经很长时间了,如果我有任何头发,我现在已经把它拉了出来.

编辑我的read_integer功能如下:

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

在"0004"上模拟stripLeadingZeros().

这是行不通的.你也忽略了一个边缘情况:如果它只是"0"怎么办.在这种情况下,您不能剥离唯一的0.

正确的代码:

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