c circular double linked-list delete_node – iterate在删除后首次遍历已删除的节点
全部，在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 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消失，防止它等于列表）。 这是一个纯循环列表，没有HEAD或TAIL节点设置为null，end-> next指向列表的开头，first-> prev指向结尾。 使delete_node（）函数适用于节点0的技巧是什么，以便删除后的第一次迭代以1开始而不是旧的0然后消失？
在请求它指向的节点作为删除请求时，您不会修改调用者的指针。 以下是一些代码的简化版本，演示了一种方法：
#include #include 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