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

Question

给定以下删除双向链表中元素的代码:

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);
    // ...
}

问题是当节点k被删除时，k的前一个节点的next字段并不指向k的后继者，而是指向k的后继者的后继者。

例如:

给定以下序列:1 2 3 4 5 6 7 8 9 10。

删除节点5；

结果:1​​ 2 3 4 7 8 9 10。

为什么会这样？

编辑:我在评论中添加了 delete 函数，其中只有当 *top 是头部时指针才会前进，现在它可以工作了。但问题总是悬而未决，即，为什么更改 *top 的值也会修改 (*top)->prev->next=(*top)->next 之前更改的值。

Answer 1

工作代码

我没有检查 chat room ，但这是我使用的测试代码的工作解决方案。它使用迭代而不是递归方法。我没有更改 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;
}

使用命令行可以干净地编译:

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

除main()以外的功能是 static满足-Wmissing-prototypes选项。如果要在这个源文件之外使用这些函数，它们将在 header 中声明——但是没有其他源文件也没有 header ，所以我将它们设为 static .

delete()函数被重写为迭代函数。关键观察(修复)是存储在传递给函数的指针中的地址应该仅在该节点被删除时才会更改。当代码是递归时，这更难处理。我也避免使用 (*top)通过将其复制到局部变量中无处不在；这稍微简化了代码。

print 和 free 函数是简单的代码。我几乎总是通过 tag字符串打印函数，以便可以简单地识别调用它的不同位置。如果我彻底完成这项工作，我会使用 uintptr_t和 PRIXPTR来自 <inttypes.h> 的宏避免 0x0为空指针打印(我会使用 "0x%.12" PRIXPTR 打印地址，完全意识到指针可能需要 16 个字节，但不经常遇到这个问题)。

main()代码连续添加条目 1..10。删除循环以不同的顺序处理条目(9、2、5、8、1、4、7、10、3、6)，因此“从开始删除”和“从结束删除”都执行为以及“从中间移除”。

sample 运行

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

valgrind 为代码提供了健康证明— 没有访问错误，也没有未释放的内存。

为什么原代码会跳过一个节点？

让我们画一幅画——ASCII 艺术脱颖而出!

删除节点2之前:

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

递归调用:

top在递归调用中实际存储在'Node 1'->next !

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

非空 (*top)->next :

分配:(*top)->next->prev=(*top)->prev;

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

非空 (*top)->prev :

分配:(*top)->prev->next=(*top)->next;

请注意，因为 top实际上是指向'Node 1'->next的指针,作业 (*top)->prev->next = (*top)->next也改变 (*top) .

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

分配*top免费

正在分配 (*top) = (*top)->next;

因为 *top也是'Node 1'->next , 分配给 *top也改变了'Node 1'->next指向，跳过'Node 3' .请注意，向后遍历仍会经过 'Node 3' .

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

现在解释损坏的原因。