将节点添加到c中双循环链表的开头

Question

我正在尝试将 '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;

密码是运行。我无法理解这两种说法之间的区别。

Answer 1

下一段代码假定 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;   */
    }
 }

Answer 2

(*head)->prev->next=newnode;
...
newnode->prev->next=newnode;
I am not able to understand what is the difference between the two statement.

newnode->prev已经正确设置为head之前的节点。相比之下，此时的(*head)->prev已经被newnode->next->prev=newnode改变了，因为newnode->next=*head。因此(*head)->prev不再指向head之前的节点，而是指向新的节点。这就是区别。

Answer 3

在添加新节点之前，当列表包含单个节点时，原始代码出错。我们将该节点称为 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;

列表已损坏，因为更改了错误的 link 指针。它可以通过使用临时变量 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;

将节点添加到c中双循环链表的开头

adding node to the beginning of double circular linked list in c

c

circular-list