c circular double linked-list：遍历末尾节点的fwd / rev给出不同的指针地址
相关post： c circular double linked-list delete_node – iterate在删除后首次遍历已删除的节点
所有，在删除该节点之前实现搜索节点连接行号“x”，我遇到了一个问题，正向和反向搜索都识别出正确的节点，但是反向搜索报告了调用者节点地址的指针而不是前锋？ 这仅适用于最后一个节点（最高行号）。 如果仅使用转发搜索（pba_fwd_iter_test），则会正确删除最后一个节点。 但是，如果使用反向搜索（pba_rev_iter_test），那么地址设置为“（victim-> next） – > prev = victim-> prev;” 不正确，它设置“（victim-> next） – > prev =（victim-> next） – > prev”。 例如，使用反向搜索到达终端节点然后执行delete_node会导致以下结果：
49: 7 - (line to delete) This is a line of text that is somewhere around 50 to 80 characters in length 48 - prev: 0x604a80 cur: 0x604b10 next: 0x604ba0 49 - prev: 0x604b10 cur: 0x604ba0 next: 0x603010 <-- delete_node 0 - prev: 0x604ba0 cur: 0x603010 next: 0x6030a0 48 - prev: 0x604a80 cur: 0x604b10 next: 0x603010 49 - prev: 0x604b10 cur: 0x604ba0 next: 0x603010 <-- (node deleted) 0 - prev: 0x603010 cur: 0x603010 next: 0x6030a0 \_______________\______ Error (should be prev: 0x604b10) @WhosCraig慷慨地帮助了delete_node函数，它工作得很好，但是我无法弄清楚为什么在delete_node中使用反向搜索结果定位相同的节点时无法设置“（victim-> next） – > prev = victim-> prev; “ 正常。 作为反向搜索的测试，我只是将一个额外的节点向前推进，然后将一个节点转发回相关节点，然后delete_node工作正常。 （只是一个额外的：list =＆（* list） – > prev; list =＆（* list） – > next;所以这个问题与使用反向搜索到达终端节点时的指针状态有关而不是向前搜索 – 这是我需要帮助搞清楚的。这是正向和反向搜索后指针地址的输出，以及快速 – >上一步 – >下一步：
=========== pba_fwd_iter_test() =========== passing list = &(*list)->next to tstpptr (0x605b28) tstpptr(): list : 0x605b28 tstpptr(): &list : 0x7ffff14633a8 tstpptr(): *list : 0x605ba0 tstpptr(): &(*list) : 0x605b28 next : 0x605bb8 =========== pba_rev_iter_test() =========== passing list = &(*list)->next to tstpptr (0x604020) tstpptr(): list : 0x604020 tstpptr(): &list : 0x7ffff14633a8 tstpptr(): *list : 0x605ba0 tstpptr(): &(*list) : 0x604020 next : 0x605bb8 passing list = &(*list)->next to tstpptr (0x605b28) tstpptr(): list : 0x605b28 tstpptr(): &list : 0x7ffff14633a8 tstpptr(): *list : 0x605ba0 tstpptr(): &(*list) : 0x605b28 prev; &(*list)->next tstpptr(): &(*list)->next : 0x605bb8
以下是相关的代码片段，其中包含指向完整源代码的链接。 感谢您提供任何帮助：
/* full source: http://www.3111skyline.com/dl/dev/prg/src/ll-double-cir-1.c.txt */ struct record { char *line; int lineno; int linetype; struct record *prev; struct record *next; }; typedef struct record rec; void // traverse in fwd direction to find hightest line no. pba_fwd_iter_test (rec **list, int num); void // traverse in rev direction to find hightest line no. pba_rev_iter_test (rec **list, int num); void // dump the pointers for examination tstpptr (rec **list); int main (int argc, char *argv[]) { // fill struct with 50 records for testing (lineno '0' based 0-49) pba_fwd_iter_test (&textfile, 49); pba_rev_iter_test (&textfile, 49); return 0; } void pba_fwd_iter_test (rec **list, int num) { printf ("=========== %s() ===========\n",__func__); int linemax = getmaxline (*list); int iterno = 0; while (((*list)->lineno != num) && (iterno next; } printf ("passing list = &(*list)->next to tstpptr (%p)\n", list); tstpptr (list); } void pba_rev_iter_test (rec **list, int num) { printf ("=========== %s() ===========\n",__func__); int linemax = getmaxline (*list); int iterno = 0; while (((*list)->lineno != num) && (iterno prev; } printf ("passing list = &(*list)->next to tstpptr (%p)\n", list); tstpptr (list); // increment prev then next and check ptr values again list = &(*list)->prev; list = &(*list)->next; printf ("passing list = &(*list)->next to tstpptr (%p)\n", list); tstpptr (list); } void tstpptr (rec **list) { fprintf (stdout, "%s(): list : %p\n", __func__, list); fprintf (stdout, "%s(): &list : %p\n", __func__, &list); fprintf (stdout, "%s(): *list : %p\n", __func__, *list); fprintf (stdout, "%s(): &(*list) : %p\n", __func__, &(*list)); fprintf (stdout, "%s(): &(**list) : %p\n\n", __func__, &(**list)); fprintf (stdout, "%s(): &(*list)->next : %p\n\n", __func__, &(*list)->next); }
我想我看到了问题 – 我认为没有问题。 重要的值是*list ，在所有情况下都是相同的。 我认为打印列表和列表等只会让问题蒙上阴影。
在前向迭代器中， list指向项目＃48的next变量的位置。
在后向迭代器中， list指向item＃0的prev变量的位置。
在这两种情况下，* list指向正确的项目＃49。
如果他们只使用rec *而不是rec ** ，那么这两个函数都会简单得多，那么更明显的是，获取list变量的地址并不是你想要的。
我从3111skyline.com网站上获取了你的代码，但它根本没有调用删除函数（或许多其他函数）。 我添加了一个函数validate_list() ，它确认您的列表是正确构造的。 我创建了一个循环来删除列表中的行，如下所示：
static void validate_list(rec *list) { assert(list != 0); assert(list->next != 0); assert(list->prev != 0); rec *iter = list; do { assert(iter != 0); assert(iter->next != 0); assert(iter->prev != 0); assert(iter == iter->next->prev); assert(iter == iter->prev->next); printf("Node: %p (n = %p; p = %p) %2d [%s]\n", (void *)iter, (void *)iter->next, (void *)iter->prev, iter->lineno, iter->line); iter = iter->next; } while (iter != list); } int main(void) { rec *textfile = fillrecord(); validate_list(textfile); for (int i = 0; i < 49; i++) { delete_node(&textfile, (i * 13 + 31) % (50 - i)); validate_list(textfile); } return 0; }
这一切似乎对我有用。 下一步是用随机数替换表达式生成的确定性（但不是特别明显）序列，以检查它是否也能正常工作，但代码对我来说似乎很干净。