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

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 

Любая помощь, которую может оказать любой человек, будет просто потрясающей; Я так долго работал над этим, что, если бы у меня были волосы, я бы сейчас его вытащил.

EDIT Моя 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

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

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

сравнить с

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

Answer 3

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

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, удаляет один ведущий ноль и возвращает. Это не recurse, потому что вы уже вернулись в заявлении if. Это означает, что stripLeadingZeros удалит не более одного нуля.

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

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

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

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

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

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