Невозможно добавить два номера с помощью связанных списков

Я пытаюсь добавить два числа, хранящиеся в виде связанного списка.

В приведенном ниже коде указатели на первую цифру каждого числа передаются методу метода addListNumbers(). При этом вызывается метод addNumbers() для добавления k младших значащих битов каждого числа и метод addRemaining() для добавления оставшихся цифр большего числа. количество.

#include <stdio.h>
#include <stdlib.h>

struct Node{
    int data;
    struct Node *next;
};

struct Node* addNode(struct Node* head, int data){
    struct Node *node = (struct Node*)malloc(sizeof(struct Node));
    node->data=data;
    if(head!=NULL)
        head->next=node;
    node->next=NULL;
    return node;
}

void addRemaining(struct Node *num1, struct Node **result, int *carry, int diff){
    int sum=0;
    if(!num1||diff==0)
        return;
    addRemaining(num1->next, result, carry, diff-1);
    sum=num1->data+*carry;
    *carry=sum/10;
    sum=sum%10;
    struct Node *temp=(struct Node *)malloc(sizeof(struct Node));
    temp->data=sum;
    temp->next=*result;
    *result=temp;   
    return;
}

void addNumbers(struct Node *num1, struct Node *num2, struct Node **result, int *carry){
    int sum;
    if(!num1)
        return;
    addNumbers(num1->next, num2->next,result,carry);
    struct Node* temp=(struct Node*)malloc(sizeof(struct Node));
    // printf("sum=num1->data+num2->data+(*carry)----- %d",*carry);
    sum=num1->data+num2->data+(*carry);
    // printf("sum is:%d ",sum);
    *carry=sum/10;
    // printf("carry is:%d ",*carry);
    sum=sum%10;
    temp->data=sum;
    temp->next=*result;
    *result=temp;
    return;
}

void addListNumbers(struct Node *num1, struct Node *num2, struct Node **result, int *carry){
    int l1Length=0, l2Length=0, diff=0;
    struct Node *current=num1;
    while(current!=NULL){
        current=current->next;
        l1Length++;
    }
    current=num2;
    while(current!=NULL){
        current=current->next;
        l2Length++;
    }
    if(l1Length<l2Length){
        current=num1;
        num1=num2;
        num2=current;
    }
    diff=abs(l1Length-l2Length);
    current=num1;
    while(diff){
        current=current->next;
        diff--;
    }
    addNumbers(current, num2, result, carry);
    diff=abs(l1Length-l2Length);
    addRemaining(num1, result, carry, diff);
    // if(*carry){
    //     struct Node *temp=(struct Node*)malloc(sizeof(struct Node));
    //     temp->next=*result;
    //     temp->data=temp->data+*carry;
    //     *result = temp;
    // }
}

void printList(struct Node* list){
    struct Node *current=(struct Node *)malloc(sizeof(struct Node));
    current=list;
    if(current==NULL)
        return;
    printf("%d", current->data);
    printList(current->next);
}

int main(){
    struct Node *num1 = addNode(NULL,6);
    struct Node *n2 = addNode(num1,2);
    struct Node *n3 = addNode(n2,7);
    // struct Node *n4 = addNode(n3,4);
    // struct Node *n5 = addNode(n4,5);
    printf("Num 1:: ");
    printList(num1);
    printf("\n");
    struct Node *num2 = addNode(NULL,8);
    struct Node *n22 = addNode(num2,1);
    struct Node *n23 = addNode(n22,6);
    struct Node *n24 = addNode(n23,4);
    struct Node *n25 = addNode(n24,7);
    printf("Num 2:: ");
    printList(num2);
    printf("\n");
    struct Node *result=(struct Node*)malloc(sizeof(struct Node));
    int carry=0;
    addListNumbers(num1, num2, &result, &carry);
    printf("After Adding:");
    printList(result);
    printf("\n");
    return 0;
}

Два числа хорошо складываются, но результат также имеет ноль в конце. Для двух добавленных выше чисел это дает следующий результат:

Num 1:: 627
Num 2:: 81647
After Adding:822740

тогда как фактический ответ 82274.

Любая помощь приветствуется :)


person Divij Sehgal    schedule 26.11.2016    source источник


Ответы (1)


Ваша функция addNumbers рекурсивно вычисляет сумму двух цифр и помещает результат перед списком, доступ к которому осуществляется через параметр result. Перед вызовом addListNumbers вы уже подготовили начальную последнюю цифру для результирующего списка, выделив память для первого узла:

struct Node *result=(struct Node*)malloc(sizeof(struct Node));
...
addListNumbers(num1, num2, &result, &carry);

Вы не можете установить result->next = NULL, но случайно выделенный вами узел заполнен нулями. Это предотвратит получение SEGFAULT и т. д. В общем, вы должны правильно инициализировать выделенную память. Но в этом случае вообще ничего не нужно выделять, а вместо этого установить result в NULL.

Кстати: в printList вы выделяете память для копии вашего связанного списка. Впоследствии это больше не используется и вызывает утечку памяти. В этой функции нет необходимости выделять что-либо. Просто используйте list вместо current.

person Gerhardh    schedule 26.11.2016
comment
Спасибо. Около часа ломал голову над этим. Теперь работает как шарм :) - person Divij Sehgal; 26.11.2016