c circular double linked-list：rev traverse为同一节点提供不同的列表指针地址
相关post1： c循环双链表list_node – 删除后第一遍遍历删除节点
相关post2： c循环双链表：遍历结尾节点的fwd / rev给出不同的指针地址
在使用循环双链表时，我在stackoverflow的帮助下创建了一个delete_node函数，该函数使用列表上的正向或反向迭代来到达要删除的节点。 该函数将链接列表的地址作为参数来实现删除（而不是对列表的指针引用）。 正向和反向迭代的混合仅仅是为了有效地防止遍历整个列表以在向前方向迭代时或在反向迭代时开始到达接近结束的节点。
full source: http://www.3111skyline.com/dl/dev/prg/src/testlld.c.txt compile with: gcc -Wall -o tlld testlld.com void delete_node (rec **list, int node) { // test that list exists if (!*list) { fprintf (stdout,"%s(), The list is empty\n",__func__); return; } // get size of list int szlist = getszlist (*list); // test node = szlist || node szlist/2, rev end->szlist/2 if (node != 0 && node >= szlist/2) { while (szlist - node++) list = &(*list)->prev; list = &(*list)->prev; // hack to get correct list ptr before delete list = &(*list)->next; // when traversing list in reverse } else while (node--) list = &(*list)->next; // create pointer to node to delete rec *victim = *list; // non-self-reference node means just rewire if (victim != victim->next) { (victim->prev)->next = victim->next; (victim->next)->prev = victim->prev; *list = victim->next; } else { // deleted node was self-referenced. last node *list = NULL; } free (victim); // delete the node } 但是，我遇到了一个反向迭代的问题，其中到达所需节点时报告的指针地址与通过前向迭代到达时为同一节点报告的地址不同。 在相关的post2中 ，这通过前向迭代解释，将节点到节点指针留在（节点-1）上，反向迭代使其指向（节点+ 1），同时两个节点指针正确指向（节点） 。 我不相信是这样的。
通过在反向迭代到有用节点之后转储指针，然后迭代一个额外的步骤（node-> prev）再次转储指针，然后在正向方向上退回到所需节点（node-> next），很容易看出这个问题。并再次转储指针。 报告的节点地址发生了变化。 以下是节点30的示例：
list pointer state after reverse iteration to node: 30 29 - prev: 0x605070 cur: 0x605100 next: 0x605078 30 - prev: 0x605100 cur: 0x605190 next: 0x605108 31 - prev: 0x605190 cur: 0x605108 next: 0x605198 list pointer state after next step to node: 29 28 - prev: 0x604fe0 cur: 0x605070 next: 0x604fe8 29 - prev: 0x605070 cur: 0x605100 next: 0x605078 30 - prev: 0x605100 cur: 0x605078 next: 0x605108 list pointer state after forward step to node: 30 29 - prev: 0x605070 cur: 0x605100 next: 0x605078 30 - prev: 0x605100 cur: 0x605078 next: 0x605108 31 - prev: 0x605190 cur: 0x605108 next: 0x605198
我不明白！ 在上面3的第一个块中，节点30的列表指针在反向迭代时报告其地址为cur: 0x605190 。 这看起来很糟糕，就像代码有一些问题，但没有。 然而有些事情是错误的，因为node 30 cur: != node 29 next: . 在反向list = &(*list)->prev;继续一步list = &(*list)->prev; 给出下一个地址块，列表指针地址已更改为cur: 0x605078 。 咦？ 但是，通过查看现在节点29和28的地址，您可以看到问题在反向迭代中继续。同样的问题是节点30的问题，现在存在于节点29处（通过附加步骤 – >上一步的优点） 。
现在用list = &(*list)->next;回到节点30 list = &(*list)->next; 允许使用地址0x605078删除节点30，一切正常。 但我无法理解为什么我不能反向迭代到节点30并删除工作？ 为什么反向交互给出节点30 0x605190的不同地址， 0x605190不是从正向0x605078到达它。
最后，在 – > prev， – >后续步骤之后，您可以在node 30 cur: 0x605078和node 31 prev: 0x605190之间看到相同类型的问题。 咦？ （当达到反向迭代时，这是最初为节点30报告的地址??这里发生了什么？
完整的源代码可用。 只需使用gcc -Wall -o tlld testlld.com编译gcc -Wall -o tlld testlld.com 。 该代码创建了一个50节点链接列表来进行操作。 您可以强制列表将所有节点删除为./tlld {49..0}的测试。
正如我在最后一个post中所说，问题是你正在查看指针变量的地址，而不是指针变量的值（即变量指向的位置）。 您也不想更新* list，除非删除的条目是第一个。 您的调用函数依赖于textfile指向列表的开头。
这是基于我在最后一个线程上提供的代码的delete_node_debug的更新版本。 我只是在循环中使用victim而不是*list ，这使得*list指向*list的开头。 然后，最后，如果victim == *list ，您可以检查是否要删除列表的开头
void delete_node_debug (rec **list, int node) { // test that list exists if (!*list) { fprintf (stdout,"%s(), The list is empty\n",__func__); return; } // get size of list int szlist = getszlist (*list); // test node < szlist if (node >= szlist || node < 0) { fprintf (stderr, "%s(), Error: record to delete is out of range (%d)\n", __func__, node); return; } rec *victim = *list; // find the node'th node with balanced search // search fwd for 0->szlist/2, rev end->szlist/2 if (node != 0 && node >= szlist/2) { while (szlist - node++) victim = victim->prev; fprintf (stderr, "\nlist pointer state after reverse iteration to node: %d\n", victim->lineno); psurround (&victim); } else while (node--) victim = victim->next; // non-self-reference node means just rewire if (victim != victim->next) { (victim->prev)->next = victim->next; (victim->next)->prev = victim->prev; // If we are deleting the first item, then we need to change the passed in pointer if (victim == *list) *list = victim->next; } else { // deleted node was self-referenced. last node *list = NULL; } free (victim); // delete the node }
另外，更改调试输出函数psurround以打印出指针值，而不是指针变量的地址：
void psurround (rec **list) { fprintf (stderr, "%2d - prev: %p cur: %p next: %p\n", (*list)->prev->lineno, (*list)->prev->prev, (*list)->prev, (*list)->prev->next); fprintf (stderr, "%2d - prev: %p cur: %p next: %p\n", (*list)->lineno, (*list)->prev, *list, (*list)->next); fprintf (stderr, "%2d - prev: %p cur: %p next: %p\n\n", (*list)->next->lineno, (*list)->next->prev, (*list)->next, (*list)->next->next); }
一般来说，我认为只要你在同一个词中有多个＆s和* s（比如*＆（* list）），你需要重新考虑发生的事情。