Вставка связанного списка в C с использованием двойного указателя - PullRequest
Новая
       15

Вставка связанного списка в C с использованием двойного указателя

0 голосов
/ 17 ноября 2018

Привет, я новичок в изучении Связанного списка, я создал этот пример программы, но он не заполняет весь список, заполняются только последние два (или они перезаписывают первые связанные элементы)

Может кто-нибудь, пожалуйста, помогите мне, что вызывает проблему? 

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

struct node {
    int data;
    struct node *link;
};  

void appendNode(int data, struct node **ptr) {

    struct node *newnode = (struct node*)malloc(sizeof(struct node));

    newnode->data = data;
    newnode->link = NULL;

    if(*ptr == NULL) {
         *ptr = newnode;
    } else {
        while((*ptr)->link != NULL ) {
            *ptr = (*ptr)->link;
        }
        (*ptr)->link = newnode;
    }

}

void printList(struct node *node) 
{ 
  while (node != NULL) 
  { 
     printf(" %d ", node->data); 
     node = node->link; 
  } 
} 

int main() {

    struct node *head = NULL ;

    appendNode(23,&head);
    appendNode(45,&head);
    appendNode(32,&head);
    appendNode(11,&head);
    appendNode(98,&head);
    printList(head);

}

ИК-отпечатки 

 11  98

Что является причиной проблемы здесь?

Ответы [ 2 ]

0 голосов
/ 17 ноября 2018

Ваша проблема в том, что вы итерируете с сам указатель в appendNode [1] .Это меняет адрес списка каждый раз, когда вы назначаете что-то на *ptr, например, 

     *ptr = newnode;
     ...
        *ptr = (*ptr)->link;

Каждый раз, когда *ptr назначается, адрес списка меняется (как видно на appendNode и main())

Ваши операции со списком верны, все, что вам нужно сделать, это использовать временный указатель для перебора списка (iter ниже) 

void appendNode (int data, struct node **ptr) {

    struct node *newnode = malloc (sizeof *newnode),
        *iter = *ptr;

    if (!newnode) { /* VALIDATE every allocation */
        perror ("malloc-newnode");
        exit (EXIT_FAILURE);
    }

    newnode->data = data;
    newnode->link = NULL;

    if (iter == NULL) {
        *ptr = newnode;
    }
    else {
        while (iter->link != NULL) {
            iter = iter->link;
        }
        iter->link = newnode;
    }
}

( note использование разыменованного указателя, используемого с sizeof для установки размера шрифта. Если вы используете разыменованный указатель для установки размера, вы устраняете любую ошибку при установкетребуется фактический тип. Кроме того, если вы выделяете - вы должны проверять - каждый раз)

С этим изменением (и следующим изменением на printList) 

void printList (struct node *node) 
{ 
    while (node != NULL) 
    { 
        printf(" %d ", node->data); 
        node = node->link; 
    }
    putchar ('\n');     /* tidy up with newline */
}

Ваш список работаетпросто отлично, например

Пример использования / Вывод 

$ ./bin/lllast2
 23  45  32  11  98

сноски:

1. Хотя это и не ошибка, C обычно избегает использования camelCase или MixedCase имен переменных в пользу всех строчных букв при резервировании заглавные имена для использования с макросами и константами.Это вопрос стиля - так что это полностью зависит от вас, но если вы не будете следовать ему, то в некоторых кругах может произойти неправильное первое впечатление.

0 голосов
/ 17 ноября 2018

Заменить: 

while((*ptr)->link != NULL ) {
    *ptr = (*ptr)->link;
}
(*ptr)->link = newnode;

На: 

struct node* last = *ptr;
while (last->link) {
    last = last->link;
}
last->link = newnode;

Хотя было бы неплохо извлечь это в свою собственную функцию: 

struct node* findLastNode(struct node* ptr) {
    while (ptr->link) {
        ptr = ptr->link;
    }
    return ptr;
}

Затем внутриappendNode: 

struct node* last = findLastNode(*ptr);
last->link = newnode;
...