добавление узла в начало двойного кругового связного списка в c - PullRequest
Новая
       18

добавление узла в начало двойного кругового связного списка в c

2 голосов
/ 27 февраля 2020

Я пытаюсь добавить 'n' количество узлов в начало двойного кругового связанного списка. Вот функция для добавления узла: 

//the **head is assigned the address of the original head pointer which is being passed from the main function.

void insert(struct node**head,int n){
 while(n-- >0){
    int num;
    //to input the data for the linked list
    scanf("%d",&num);
    struct node* newnode=(struct node*)malloc(sizeof(struct node));
    newnode->data=num;

    if(*head==NULL){
        newnode->next=newnode;
        newnode->prev=newnode;

        *head=newnode;
    }
    else{

        newnode->next=*head;
        newnode->prev=(*head)->prev;

        //to make the previously first node point to the new first node
        newnode->next->prev=newnode;
        //to make the last node point to the new first node
        (*head)->prev->next=newnode;
        *head=newnode;

    }
 }
}

, когда я выполняю его, он не показывает никаких вывод, но когда я изменяю 

//to make the last node point to the new first node
            (*head)->prev->next=newnode;

эту строку на 

newnode->prev->next=newnode;

, код работает. Я не могу понять, в чем разница между этими двумя утверждениями.

Ответы [ 3 ]

1 голос
/ 27 февраля 2020 
(*head)->prev->next=newnode;
...
newnode->prev->next=newnode;

Я не могу понять, в чем разница между этими двумя утверждениями.

newnode->prev было правильно установлено на узел до head . Напротив, (*head)->prev в это время уже было изменено на newnode->next->prev=newnode, так как newnode->next=*head. Следовательно, (*head)->prev больше не указывает на узел перед головой , но на новый узел. В этом разница.

0 голосов
/ 27 февраля 2020

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

/* List with single node. */
(*head) = &A;
A.next = &A;
A.prev = &A;

Давайте назовем узел, на который указывает newnode B: 

newnode = &B;

Код для добавления newnode в настоящее время выглядит следующим образом (с добавленными комментариями //>): 

    newnode->next=*head;         //> B.next=&A;
    newnode->prev=(*head)->prev; //> B.prev=&A;

    //to make the previously first node point to the new first node
    newnode->next->prev=newnode; //> A.prev=&B;
    //to make the last node point to the new first node
    (*head)->prev->next=newnode; //> B.next=&B; !!! want A.next = &B;
    *head=newnode;

Ситуация после вышеуказанной кодовой последовательности: 

(*head) = &B;
B.next = &B; // !!! want B.next = &A;
B.prev = &A;
A.next = &A; // !!! want A.next = &B;
A.prev = &B;

Список был разорван из-за неправильного указателя ссылки был изменен. Это можно исправить с помощью временной переменной lastnode, установленной на старое значение (*head)->prev. Обновленный код выглядит следующим образом: 

    struct node *lastnode;
    lastnode=(*head)->prev;      //> lastnode=&A;
    newnode->next=*head;         //> B.next=&A;
    newnode->prev=lastnode;      //> B.prev=&A;

    //to make the previously first node point to the new first node
    newnode->next->prev=newnode; //> A.prev=&B;
    //to make the last node point to the new first node
    lastnode->next=newnode;      //> A.next=&B;
    *head=newnode;

Ситуация после обновленной последовательности кодов: 

(*head) = &B;
B.next = &A;
B.prev = &A;
A.next = &B;
A.prev = &B;
0 голосов
/ 27 февраля 2020

Следующий код предполагает, что head определяется как: struct node* head;. Я только что удалил некоторые дополнительные операторы разыменования (*).

Он не может быть напрямую проверен, так как минимально воспроизводимый пример не был предоставлен. 

 while(n-- >0){
    int num;
    //to input the data for the linked list
    scanf("%d",&num);
    struct node* newnode=(struct node*)malloc(sizeof(struct node));
    newnode->data=num;

    if(head==NULL){              /*   was: if(*head==NULL){   */
        newnode->next=newnode;
        newnode->prev=newnode;

        head=newnode;{              /*   was: *head=newnode;{   */
    }
    else{

        newnode->next=head;              /*   was: newnode->next=*head;   */
        newnode->prev=(*head)->prev;

        //to make the previously first node point to the new first node
        newnode->next->prev=newnode;
        //to make the last node point to the new first node
        (*head)->prev->next=newnode;
        head=newnode;              /*   was: *head=newnode;   */
    }
 }
...