中间插入双链表

Question

我正在尝试为以下问题编写代码：

Insert an element(sum of neighbors) between every pair of consecutive elements?

Example: if input is
12 23 34 45 for n=4 
Output should be:
12 35 23 57 34 79 45

我写的代码是：

struct node *InsBet(node *head) {
    node *i,*j,*t;
    i=head;
    while(i->next!=NULL) {
        t = (node*)malloc(sizeof(node));
        t->data = i->data + i->next->data;
        i->next = t;t->prev = i;
        t->next = i->next;i->next->prev = t;
        i = i->next;
    }
    return head;
}

打印数组后我的终端崩溃了。

我的打印程序是：

void PrintList(node *head) {
    node *i;
    i=head;
    while(i!=NULL) {
        printf("%d ",i->data);
        i=i->next;
    }
}

Answer 1

第一个问题 是您在将 i->next 复制到 t->next

之前覆盖了它

调换顺序

    i->next = t;t->prev = i;
    t->next = i->next;i->next->prev = t;

进入

    t->next = i->next; i->next->prev = t; 
    i->next = t; t->prev = i;

为了详细说明，假设您的列表中有一个由 2 个元素组成的链：A-->B，并且您想要在它们之间添加临时元素，因此您创建了 t，但是由于第一件事你所做的是覆盖第一个元素的前向指针（在本例中为 A），你将失去任何再次访问 B 的机会。相反，您将创建无限循环的 itself 地址分配给临时元素的前向指针。

第二个问题是你将当前指针(i)提前一个link，这意味着它现在指向临时您刚刚添加的元素，您将尝试在 t 和 B 之间添加一个额外的临时元素。这将导致无限循环 - 而不是将 i 提前 -

i = t->next;

Answer 2

上面的答案解释得很好，但只是为了给你一个工作代码，给你：

PS，您不需要 return 头指针，因为它是通过引用传递的，return 对它

没有用处

void InsBet(node *head) {
    node *i,*t;
    i=head;
    while(i->next!=NULL) {
        t = (node*)malloc(sizeof(node));
        t->data = i->data + i->next->data;
        t->prev = i;
        t->next = i->next;
        i->next = i->next->next;
        i->prev = t;

        i = t->next;
    }
}

中间插入双链表

Double Linked List Insertion in Between

algorithm

data-structures

linked-list

doubly-linked-list