c循环双向链表删除节点-删除后第一次迭代遍历删除的节点

Question

所有，在 GNU c 中，我有一个循环双向链表，我正试图在其上实现 delete_node 函数。它适用于除节点 0 以外的所有节点。它确实删除 (free()) 节点 0，但是在删除节点 0 后第一次遍历列表时，它仍然存在于第一遍，导致条件停止迭代到失败。实现的基础是:

struct record
{
    char *line;
    int lineno;
    int linetype;
    struct record *prev;
    struct record *next;
};

typedef struct record rec;

void
iterfwd (rec *list) {

    rec *iter = list;   // second copy to iterate list

    if (iter ==  NULL) {
        fprintf (stdout,"%s(), The list is empty\n",__func__);
    } else {
        do {
            printf ("%2d - prev: %p  cur: %p  next: %p\n", iter->lineno, iter->prev, iter, iter->next);
        iter = iter->next;
        } while (iter != list);
    }
}

void
delete_node (rec *list, int num) {

    rec *iter = list;   // second copy to iterate list
    int cnt = 0;
    int found = 0;

    if (iter ==  NULL) {
        fprintf (stdout,"%s(), The list is empty\n",__func__);
    } else {
        // traverse list forward (check cnt == num, else if end -> Out Of Range)
        do {
            if (cnt == num) {
                found=1;
                (iter->prev)->next = iter->next;
                (iter->next)->prev = iter->prev;
                free (iter);
                break;
            }
            iter = iter-> next;
            cnt++;
            } while (iter != list);

            if (found != 1) {
            fprintf (stderr, "%s(), Error: record to delete is out of range (%d)\n", __func__, num);
        }
    }
}

int main (int argc, char *argv[]) {
    struct record *textfile = NULL; // instance of record, pointer to list
    int node = 0;
    node = (argc >= 2) ? atoi (argv[1]) : 0;
    textfile = fillrecord ();  // fill textfile circular linked-list
    iterfwd (textfile);
    delete_node (textfile, node);
    iterfwd (textfile);
    return 0;
}

完整列表在这里:http://www.3111skyline.com/dl/dev/prg/src/ll-double-cir.c.txt

列表中填满了50条测试数据，我插入了printf语句来确认指针操作。删除节点 0 以外的任何节点都按预期工作(以下是 iter->prev、iter、iter->next 的指针地址，用于删除节点 10 的受影响行[删除前和删除后]):

 9 - prev: 0x603490  cur: 0x603520  next: 0x6035b0
10 - prev: 0x603520  cur: 0x6035b0  next: 0x603640  <-- delete_node
11 - prev: 0x6035b0  cur: 0x603640  next: 0x6036d0

 9 - prev: 0x603490  cur: 0x603520  next: 0x603640
10 - prev: 0x603520  cur: 0x6035b0  next: 0x603640  <-- (node deleted)
11 - prev: 0x603520  cur: 0x603640  next: 0x6036d0

在列表的下一次遍历中，一切都按预期工作:

 7 - prev: 0x603370  cur: 0x603400  next: 0x603490
 8 - prev: 0x603400  cur: 0x603490  next: 0x603520
 9 - prev: 0x603490  cur: 0x603520  next: 0x603640
11 - prev: 0x603520  cur: 0x603640  next: 0x6036d0
12 - prev: 0x603640  cur: 0x6036d0  next: 0x603760

但是，如果节点 0 被删除，delete_node 会正确处理指针:

49 - prev: 0x604b10  cur: 0x604ba0  next: 0x603010
 0 - prev: 0x604ba0  cur: 0x603010  next: 0x6030a0  <-- delete_node
 1 - prev: 0x603010  cur: 0x6030a0  next: 0x603130

49 - prev: 0x604b10  cur: 0x604ba0  next: 0x6030a0
 0 - prev: 0x604ba0  cur: 0x603010  next: 0x6030a0  <-- (node deleted)
 1 - prev: 0x604ba0  cur: 0x6030a0  next: 0x603130

但是在删除后第一次尝试遍历列表时，节点 0 出现在第一次遍历中，导致迭代器条件 'while (iter != list)' 失败并陷入循环:

 0 - prev: 0x604ba0  cur: 0x603010  next: 0x6030a0
 1 - prev: 0x604ba0  cur: 0x6030a0  next: 0x603130
 2 - prev: 0x6030a0  cur: 0x603130  next: 0x6031c0
 3 - prev: 0x603130  cur: 0x6031c0  next: 0x603250
 4 - prev: 0x6031c0  cur: 0x603250  next: 0x6032e0
<snip>
47 - prev: 0x6049f0  cur: 0x604a80  next: 0x604b10
48 - prev: 0x604a80  cur: 0x604b10  next: 0x604ba0
49 - prev: 0x604b10  cur: 0x604ba0  next: 0x6030a0
 1 - prev: 0x604ba0  cur: 0x6030a0  next: 0x603130
 2 - prev: 0x6030a0  cur: 0x603130  next: 0x6031c0
 3 - prev: 0x603130  cur: 0x6031c0  next: 0x603250

如上所示，迭代器遍历0-49后，被删除的节点0消失，重新开始正常遍历1-49，但此时处于循环中，因为条件(iter != list)总是true(节点 0 消失，阻止 iter 永远等于列表)。这是一个纯循环列表，没有HEAD和TAIL节点设置为null，end->next指向列表的开头，first->prev指向结尾。让 delete_node() 函数对节点 0 起作用，以便删除后的第一次迭代从 1 开始而不是随后消失的旧 0 的技巧是什么？

Answer 1

当请求它指向的节点作为删除请求时，您并没有修改调用者的指针。下面是您的一些代码的简化版本，演示了一种执行此操作的方法:

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

typedef struct record rec;
struct record
{
    int data;
    rec *prev, *next;
};

void delete_node (rec ** pp, int num)
{
    if (!*pp)
        return;

    // find the num'th node
    while (num-- && *pp)
        pp = &(*pp)->next;

    // setup victim
    rec *victim = *pp;

    // non-self-reference node means just rewire
    if (victim && (victim != victim->next))
    {
        victim->prev->next = victim->next;
        victim->next->prev = victim->prev;
        *pp = victim->next;
    }
    else
    {   // deleted node was self-referenced. last node
        *pp = NULL;
    }
    free(victim);
}

void iterfwd(const rec* list)
{
    const rec *p = list;
    printf("list: %p\n", list);
    if (p)
    {
        for (; p; p = (p->next != list ? p->next : NULL))
            printf("prev: %p, self:%p, next:%p, data = %d\n", p->prev, p, p->next, p->data);
    }
    puts("");
}

void insert(rec **pp, int data)
{
    // setup new node
    rec *newp = malloc(sizeof(*newp));
    newp->data = data;

    if (!*pp)
    {
        newp->next = newp->prev = newp;
        *pp = newp;
    }
    else
    {   // insert between prev and head.
        newp->next = *pp;
        (*pp)->prev->next = newp;
        newp->prev = (*pp)->prev;
        (*pp)->prev = newp;
    }
}

int main()
{
    rec *list = NULL;
    int i;

    for (i=1; i<=5; ++i)
        insert(&list, i);
    iterfwd(list);

    // delete fourth node (0-based)
    delete_node(&list, 3);
    iterfwd(list);

    // delete first node (0-based)
    delete_node(&list, 0);
    iterfwd(list);

    // delete first node (0-based)
    delete_node(&list, 0);
    iterfwd(list);

    // delete first node (0-based)
    delete_node(&list, 0);
    iterfwd(list);

    // delete first node (0-based)
    delete_node(&list, 0);
    iterfwd(list);

    return 0;
}

输出(显然取决于系统)

请注意在请求删除 0 元素时如何修改传入的指针(按地址传递)。

list: 0x100103af0
prev: 0x100103b70, self:0x100103af0, next:0x100103b10, data = 1
prev: 0x100103af0, self:0x100103b10, next:0x100103b30, data = 2
prev: 0x100103b10, self:0x100103b30, next:0x100103b50, data = 3
prev: 0x100103b30, self:0x100103b50, next:0x100103b70, data = 4
prev: 0x100103b50, self:0x100103b70, next:0x100103af0, data = 5

list: 0x100103af0
prev: 0x100103b70, self:0x100103af0, next:0x100103b10, data = 1
prev: 0x100103af0, self:0x100103b10, next:0x100103b30, data = 2
prev: 0x100103b10, self:0x100103b30, next:0x100103b70, data = 3
prev: 0x100103b30, self:0x100103b70, next:0x100103af0, data = 5

list: 0x100103b10
prev: 0x100103b70, self:0x100103b10, next:0x100103b30, data = 2
prev: 0x100103b10, self:0x100103b30, next:0x100103b70, data = 3
prev: 0x100103b30, self:0x100103b70, next:0x100103b10, data = 5

list: 0x100103b30
prev: 0x100103b70, self:0x100103b30, next:0x100103b70, data = 3
prev: 0x100103b30, self:0x100103b70, next:0x100103b30, data = 5

list: 0x100103b70
prev: 0x100103b70, self:0x100103b70, next:0x100103b70, data = 5

list: 0x0