删除列表中的节点，并在C中通过引用传递

Given the following code for deletion of an element in a doubly linked list:

给出以下代码删除双向链表中的元素：

struct list
{
    int info;
    struct list *prev;
    struct list *next;
};

struct list *insert(struct list *top,int k)
{
    struct list *tmp=NULL;
    if(!top)
    {
        tmp=(struct list *)malloc(sizeof(struct list));
        if(tmp)
        {
            tmp->info=k;
            tmp->next=NULL;
            tmp->prev=NULL;
            top=tmp;
        }
        else
            printf("error\n");
    }
    else 
    {
        top->next=insert(top->next,k);
        if(top->next)
            top->next->prev=top;
    }
    return top;
}



void delete(struct list **top,int k)
{
    struct list *tmp=NULL;
    if(*top)
    {
        if((*top)->info==k)
        {
            tmp=*top;
            if((*top)->next)
            {
                (*top)->next->prev=(*top)->prev;
            }

            if((*top)->prev)
            {
                (*top)->prev->next=(*top)->next;
            }

            *top=(*top)->next;

            free(tmp);
        }
        else
            delete(&((*top)->next),k);
    }
}
/* correct function
void delete(struct list **top,int k)
{
    struct list *tmp=NULL;
    if(*top)
    {
        if((*top)->info==k)
        {
            tmp=*top;
            if((*top)->next)
            {
                (*top)->next->prev=(*top)->prev;
            }

            if((*top)->prev)
            {
                (*top)->prev->next=(*top)->next;
            }
            else
                *top=(*top)->next;

            free(tmp);
        }
        else
            delete(&((*top)->next),k);
    }
}*/

int main()
{
    int i,k;
    struct list *top=NULL;
    for(i=1;i<11;i++)
       top=insert(top,i);

    printf("insert a key\n");
    scanf("%d",&k);
    delete(&top,k);
    // ...
}

The problem is that when the node k is deleted, the field next of the previous node of k does not point to successor of k but to successor of the successor of k.

问题在于，当删除节点k时，k的前一节点的下一个字段不指向k的后继，而是指向k的后继的后继。

For example:

例如：

Given the following sequence : 1 2 3 4 5 6 7 8 9 10.

给出以下顺序：1 2 3 4 5 6 7 8 9 10。

Delete node 5;

删除节点5;

Result : 1 2 3 4 7 8 9 10.

结果：1 2 3 4 7 8 9 10。

Why is this happening?

为什么会这样？

EDIT: I added in the comment the function delete in which the pointer advance only when *top is the head, and it works now. But the question is always open, that it, why changing the value of *top is modified also the value of (*top)->prev->next=(*top)->next changed before.

编辑：我在评论中添加了函数delete，其中指针仅在* top为头部时前进，并且现在可以正常工作。但问题始终是开放的，它为什么改变* top的值也被修改了（* top） - > prev-> next =（* top） - > next的值之前改变了。

1 个解决方案

#1

Working code

I've not checked the chat room, but here's my working solution with the test code I used. It uses an iterative rather than recursive approach. I didn't change the insert() code (though I moved it after the delete() function), though I would remove the recursion were it to become 'my' code.

我没有检查聊天室，但这是我使用的测试代码的工作解决方案。它使用迭代而不是递归方法。我没有更改insert（）代码（虽然我在delete（）函数之后移动它），虽然我会删除递归它是否成为'我的'代码。

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

struct list
{
    int info;
    struct list *prev;
    struct list *next;
};

static
void delete(struct list **top, int k)
{
    struct list *node = *top;
    while (node)
    {
        if (node->info == k)
        {
            if (node->next)
                node->next->prev = node->prev;
            if (node->prev)
                node->prev->next = node->next;
            if (node == *top)
                *top = node->next;
            free(node);
            return;
        }
        node = node->next;
    }
}

static
struct list *insert(struct list *top, int k)
{
    struct list *tmp = NULL;
    if (!top)
    {
        tmp = (struct list *)malloc(sizeof(struct list));
        if (tmp)
        {
            tmp->info = k;
            tmp->next = NULL;
            tmp->prev = NULL;
            top = tmp;
        }
        else
            printf("error\n");
    }
    else
    {
        top->next = insert(top->next, k);
        if (top->next)
            top->next->prev = top;
    }
    return top;
}

static void dump_list_fwd(const char *tag, struct list *top)
{
    printf("List %p: %s\n", (void *)top, tag);
    while (top != 0)
    {
        printf("  Item %p: %2d (next %p, prev %p)\n", (void *)top,
               top->info, (void *)top->next, (void *)top->prev);
        top = top->next;
    }
}

static void free_list(struct list *top)
{
    while (top != 0)
    {
        struct list *next = top->next;
        free(top);
        top = next;
    }
}

int main(void)
{
    struct list *top = NULL;

    for (int i = 1; i < 11; i++)
        top = insert(top, i);
    dump_list_fwd("After insert", top);

    for (int i = 1; i < 11; i++)
    {
        int k = (i * 3 + 5) % 10 + 1;
        printf("Delete %d\n", k);
        delete(&top, k);
        dump_list_fwd("After delete", top);
    }

    free_list(top);
    return 0;
}

This compiles cleanly using the command line:

这使用命令行干净地编译：

gcc -O3 -g -std=c11 -Wall -Wextra -Wmissing-prototypes -Wstrict-prototypes \
    -Wold-style-definition -Werror dellink.c -o dellink

The functions apart from main() are static to satisfy the -Wmissing-prototypes option. If the functions were going to be used outside this source file, they'd be declared in a header — but there is no other source file and there is no header, so I made them static.

除main（）之外的函数是静态的，以满足-Wmissing-prototypes选项。如果函数将在此源文件之外使用，则它们将在标头中声明 - 但是没有其他源文件且没有标头，因此我将它们设置为静态。

The delete() function is rewritten as an iterative function. The key observation (fix) is that address stored in the pointer passed to the function should only change when that is the node that is deleted. This is harder to handle when the code is recursive. I also avoided using (*top) everywhere by copying it into a local variable; that simplifies the code a little.

delete（）函数被重写为迭代函数。关键观察（修复）是存储在传递给函数的指针中的地址只应在删除的节点时更改。当代码递归时，这很难处理。我还避免在任何地方使用（* top）将其复制到局部变量中;这简化了代码。

The print and free functions are straight-forward bits of code. I almost always pass a tag string to printing functions so that the different locations where it is called can be simply identified. Were I doing the job thoroughly, I'd use uintptr_t and the PRIXPTR macro from <inttypes.h> to avoid 0x0 being printed for null pointers (I'd use "0x%.12" PRIXPTR to print the addresses, perfectly aware that pointers could need 16 bytes but not often running into that as a problem).

打印和*功能是直接的代码位。我几乎总是将标记字符串传递给打印函数，以便可以简单地识别调用它的不同位置。如果我彻底完成这项工作，我会使用uintptr_t和 中的PRIXPTR宏来避免为空指针打印0x0（我使用“0x％.12”PRIXPTR打印地址，完全清楚指针可能需要16个字节，但不会经常遇到问题）。

The main() code serially adds entries 1..10. The deleting loop deals with the entries in a different sequence (9, 2, 5, 8, 1, 4, 7, 10, 3, 6) so that the 'remove from start' and 'remove from end' are both executed as well as 'remove from middle'.

main（）代码按顺序添加条目1..10。删除循环处理不同序列（9,2,5,8,1,4,7,10,3,6）中的条目，以便'从开始删除'和'从结尾删除'都执行为以及'从中间移除'。

Sample run

List 0x7f9460c03180: After insert
  Item 0x7f9460c03180:  1 (next 0x7f9460c031a0, prev 0x0)
  Item 0x7f9460c031a0:  2 (next 0x7f9460c031c0, prev 0x7f9460c03180)
  Item 0x7f9460c031c0:  3 (next 0x7f9460c031e0, prev 0x7f9460c031a0)
  Item 0x7f9460c031e0:  4 (next 0x7f9460c03200, prev 0x7f9460c031c0)
  Item 0x7f9460c03200:  5 (next 0x7f9460c03220, prev 0x7f9460c031e0)
  Item 0x7f9460c03220:  6 (next 0x7f9460c03240, prev 0x7f9460c03200)
  Item 0x7f9460c03240:  7 (next 0x7f9460c03260, prev 0x7f9460c03220)
  Item 0x7f9460c03260:  8 (next 0x7f9460c03280, prev 0x7f9460c03240)
  Item 0x7f9460c03280:  9 (next 0x7f9460c032a0, prev 0x7f9460c03260)
  Item 0x7f9460c032a0: 10 (next 0x0, prev 0x7f9460c03280)
Delete 9
List 0x7f9460c03180: After delete
  Item 0x7f9460c03180:  1 (next 0x7f9460c031a0, prev 0x0)
  Item 0x7f9460c031a0:  2 (next 0x7f9460c031c0, prev 0x7f9460c03180)
  Item 0x7f9460c031c0:  3 (next 0x7f9460c031e0, prev 0x7f9460c031a0)
  Item 0x7f9460c031e0:  4 (next 0x7f9460c03200, prev 0x7f9460c031c0)
  Item 0x7f9460c03200:  5 (next 0x7f9460c03220, prev 0x7f9460c031e0)
  Item 0x7f9460c03220:  6 (next 0x7f9460c03240, prev 0x7f9460c03200)
  Item 0x7f9460c03240:  7 (next 0x7f9460c03260, prev 0x7f9460c03220)
  Item 0x7f9460c03260:  8 (next 0x7f9460c032a0, prev 0x7f9460c03240)
  Item 0x7f9460c032a0: 10 (next 0x0, prev 0x7f9460c03260)
Delete 2
List 0x7f9460c03180: After delete
  Item 0x7f9460c03180:  1 (next 0x7f9460c031c0, prev 0x0)
  Item 0x7f9460c031c0:  3 (next 0x7f9460c031e0, prev 0x7f9460c03180)
  Item 0x7f9460c031e0:  4 (next 0x7f9460c03200, prev 0x7f9460c031c0)
  Item 0x7f9460c03200:  5 (next 0x7f9460c03220, prev 0x7f9460c031e0)
  Item 0x7f9460c03220:  6 (next 0x7f9460c03240, prev 0x7f9460c03200)
  Item 0x7f9460c03240:  7 (next 0x7f9460c03260, prev 0x7f9460c03220)
  Item 0x7f9460c03260:  8 (next 0x7f9460c032a0, prev 0x7f9460c03240)
  Item 0x7f9460c032a0: 10 (next 0x0, prev 0x7f9460c03260)
Delete 5
List 0x7f9460c03180: After delete
  Item 0x7f9460c03180:  1 (next 0x7f9460c031c0, prev 0x0)
  Item 0x7f9460c031c0:  3 (next 0x7f9460c031e0, prev 0x7f9460c03180)
  Item 0x7f9460c031e0:  4 (next 0x7f9460c03220, prev 0x7f9460c031c0)
  Item 0x7f9460c03220:  6 (next 0x7f9460c03240, prev 0x7f9460c031e0)
  Item 0x7f9460c03240:  7 (next 0x7f9460c03260, prev 0x7f9460c03220)
  Item 0x7f9460c03260:  8 (next 0x7f9460c032a0, prev 0x7f9460c03240)
  Item 0x7f9460c032a0: 10 (next 0x0, prev 0x7f9460c03260)
Delete 8
List 0x7f9460c03180: After delete
  Item 0x7f9460c03180:  1 (next 0x7f9460c031c0, prev 0x0)
  Item 0x7f9460c031c0:  3 (next 0x7f9460c031e0, prev 0x7f9460c03180)
  Item 0x7f9460c031e0:  4 (next 0x7f9460c03220, prev 0x7f9460c031c0)
  Item 0x7f9460c03220:  6 (next 0x7f9460c03240, prev 0x7f9460c031e0)
  Item 0x7f9460c03240:  7 (next 0x7f9460c032a0, prev 0x7f9460c03220)
  Item 0x7f9460c032a0: 10 (next 0x0, prev 0x7f9460c03240)
Delete 1
List 0x7f9460c031c0: After delete
  Item 0x7f9460c031c0:  3 (next 0x7f9460c031e0, prev 0x0)
  Item 0x7f9460c031e0:  4 (next 0x7f9460c03220, prev 0x7f9460c031c0)
  Item 0x7f9460c03220:  6 (next 0x7f9460c03240, prev 0x7f9460c031e0)
  Item 0x7f9460c03240:  7 (next 0x7f9460c032a0, prev 0x7f9460c03220)
  Item 0x7f9460c032a0: 10 (next 0x0, prev 0x7f9460c03240)
Delete 4
List 0x7f9460c031c0: After delete
  Item 0x7f9460c031c0:  3 (next 0x7f9460c03220, prev 0x0)
  Item 0x7f9460c03220:  6 (next 0x7f9460c03240, prev 0x7f9460c031c0)
  Item 0x7f9460c03240:  7 (next 0x7f9460c032a0, prev 0x7f9460c03220)
  Item 0x7f9460c032a0: 10 (next 0x0, prev 0x7f9460c03240)
Delete 7
List 0x7f9460c031c0: After delete
  Item 0x7f9460c031c0:  3 (next 0x7f9460c03220, prev 0x0)
  Item 0x7f9460c03220:  6 (next 0x7f9460c032a0, prev 0x7f9460c031c0)
  Item 0x7f9460c032a0: 10 (next 0x0, prev 0x7f9460c03220)
Delete 10
List 0x7f9460c031c0: After delete
  Item 0x7f9460c031c0:  3 (next 0x7f9460c03220, prev 0x0)
  Item 0x7f9460c03220:  6 (next 0x0, prev 0x7f9460c031c0)
Delete 3
List 0x7f9460c03220: After delete
  Item 0x7f9460c03220:  6 (next 0x0, prev 0x0)
Delete 6
List 0x0: After delete

The code is given a clean bill of health by valgrind — no access errors and no unfreed memory.

valgrind为代码提供了一个干净的健康状况 - 没有访问错误，没有不同的内存。

Why does the original code skip a node?

Let's draw a picture — ASCII art to the fore!

让我们画一幅画 - ASCII艺术脱颖而出！

Before deleting Node 2:

  +-----+
  | top |
  +-----+
     |
     v
+--------+     +--------+     +--------+     +--------+
|        |---->|        |---->|        |---->|        |
| Node 1 |     | Node 2 |     | Node 3 |     | Node 4 |
|        |<----|        |<----|        |<----|        |
+--------+     +--------+     +--------+     +--------+

Recursive call:

The top in the recursive call is actually stored in 'Node 1'->next!

递归调用中的顶部实际存储在“节点1” - >下一个！

                 +-----+
                 | top |
                 +-----+
                    |
                    v
+--------+     +--------+     +--------+     +--------+
|        |---->|        |---->|        |---->|        |
| Node 1 |     | Node 2 |     | Node 3 |     | Node 4 |
|        |<----|        |<----|        |<----|        |
+--------+     +--------+     +--------+     +--------+

Non-null (*top)->next:

Assigning: (*top)->next->prev=(*top)->prev;

分配：（* top） - > next-> prev =（* top） - > prev;

                 +-----+
                 | top |
                 +-----+
                    |
                    v
+--------+     +--------+     +--------+     +--------+
|        |---->|        |---->|        |---->|        |
| Node 1 |     | Node 2 |     | Node 3 |     | Node 4 |
|        |<-------------------|        |<----|        |
+--------+     +--------+     +--------+     +--------+

Non-null (*top)->prev:

Assigning: (*top)->prev->next=(*top)->next;

分配：（* top） - > prev-> next =（* top） - > next;

Note that because top is actually a pointer to 'Node 1'->next, the assignment (*top)->prev->next = (*top)->next also changes (*top).

注意，因为top实际上是指向'Node 1' - > next的指针，所以赋值（* top） - > prev-> next =（* top） - > next也会改变（* top）。

                                +-----+
                                | top |
                                +-----+
                                   |
                                   v
+--------+     +--------+     +--------+     +--------+
|        |------------------->|        |---->|        |
| Node 1 |     | Node 2 |     | Node 3 |     | Node 4 |
|        |<-------------------|        |<----|        |
+--------+     +--------+     +--------+     +--------+

Assign *top and free

Assigning (*top) = (*top)->next;

分配（*顶部）=（*顶部） - >下一个;

Because *top is also 'Node 1'->next, the assignment to *top also changes where 'Node 1'->next points to, skipping 'Node 3'. Note that a backwards traverse would still go through 'Node 3'.

因为* top也是'Node 1' - > next，所以* top的赋值也会改变'Node 1' - > next指向的地方，跳过'Node 3'。请注意，向后遍历仍将通过“节点3”。

                                               +-----+
                                               | top |
                                               +-----+
                                                  |
                                                  v
+--------+                    +--------+     +--------+
|        |---------------------------------->|        |
| Node 1 |                    | Node 3 |     | Node 4 |
|        |<-------------------|        |<----|        |
+--------+                    +--------+     +--------+

The reason for the damage is now explained.

现在解释损坏的原因。