Основные проблемы со связанными списками

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

Имитация stripLeadingZeros () на "0004".

Не работает.Также вы проигнорировали крайний случай: что, если это только «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;
}

Answer 2

Рассмотрим поток управления этой функции:

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

Что происходит, когда p начинается с нуля?Он вводит оператор if, удаляет начальный ноль и возвращает.Это не рекурсивно, потому что вы уже вернулись в операторе if.Это означает, что stripLeadingZeros удалит не более одного нуля.

Что теперь происходит, когда p начинается с единицы?Он пропускает оператор if, но регрессирует .Это также неправильно, потому что, увидев один, вы хотите прекратить удалять нули, так как они больше не являются ведущими.

Итак, что на самом деле делает эта функция, так это удаляет первый ноль, с которым она сталкивается, ведущий или нет, а затем останавливаясь.Это не то, что вы хотите.

Вы хотите выполнить рекурсию после того, как вы удалили ноль, и только после того, как вы удалили ноль, поэтому переместите рекурсивный вызов в if заявление.Другими словами, замените return pNext; на return stripLeadingZeros(pNext); и удалите рекурсию из-за пределов цикла.

Answer 3

stripLeadingZeros( nodeptr s )
{
if(s!=NULL)
    stripLeadingZeros(s->next);
       if((s!=NULL)&&s->data==0&&on)
       flg=1;
       if((s!=NULL)&&(s->data!=0)&&flg)
       on=0,flg=0,s->next=NULL;
       if(flg)
 s->next=NULL;
}

вот мой код для удаления начальных нулей, начальные значения on и flg равны 1 и 0 соответственно.

http://programmingconsole.blogspot.in/2013/10/all-basic-calculator-functions-on-large.html

Answer 4

Вы можете улучшить свою функцию реверса, перевернув исходный список в другой список:

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

Answer 5

в вашей текущей версии stripLeadingZeros вы можете заменить цикл while на выражение if, что результат будет таким же. Может быть, в этом проблема.

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

сравнить с

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