相关帖子： 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 <- caller's address reported tstpptr(): &(**list): 0x605ba0 with forward search tstpptr(): &(*list)->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 <- caller's address reported tstpptr(): &(**list): 0x605ba0 with reverse search tstpptr(): &(*list)->next : 0x605bb8 passing list = &(*list)->next to tstpptr (0x605b28) tstpptr(): list : 0x605b28 tstpptr(): &list : 0x7ffff14633a8 tstpptr(): *list : 0x605ba0 tstpptr(): &(*list) : 0x605b28 <- caller's address reported after tstpptr(): &(**list): 0x605ba0 &(*list)->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[]) { // <snip> 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 <= linemax)) { iterno++; list = &(*list)->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 <= linemax)) { iterno++; list = &(*list)->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); }related post: c circular double linked-list delete_node - iterate traverses deleted node on first pass after delete
All, implementing a search for node contianing line number 'x' prior to deleting that node, I ran across a problem where both forward and reverse searches identify the proper node, but the pointer for the caller's node address is reported differently by the reverse search than for the forward? This applies to the last node (hightest line number) only. If only the forwrd search is used (pba_fwd_iter_test), then the last node is deleted properly. However, if the reverse search is used (pba_rev_iter_test), then the address set by "(victim->next)->prev = victim->prev;" is incorrect, it sets "(victim->next)->prev = (victim->next)->prev". For example, arriving at the end node with a reverse search and then preforming the delete_node results in the following:
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 graciously helped with the delete_node function which works fine, but I cannot figure out why when locating the same node with the reverse search results in the delete_node failing to set "(victim->next)->prev = victim->prev;" properly. As a test of the reverse search, I simply stepped one additional node toward the beginning and then went forward one node back to the node in question and then the delete_node worked fine. (simply an additional: list = &(*list)->prev; list = &(*list)->next;. So the issue has something to do with the pointer state when arriving at the end-node with a reverse search rather than a forward seach -- that is what I need help figuring out. Here is the output of the pointer addresses following both forward and reverse searchs, as well as following the quick ->prev ->next:
=========== pba_fwd_iter_test() =========== passing list = &(*list)->next to tstpptr (0x605b28) tstpptr(): list : 0x605b28 tstpptr(): &list : 0x7ffff14633a8 tstpptr(): *list : 0x605ba0 tstpptr(): &(*list) : 0x605b28 <- caller's address reported tstpptr(): &(**list): 0x605ba0 with forward search tstpptr(): &(*list)->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 <- caller's address reported tstpptr(): &(**list): 0x605ba0 with reverse search tstpptr(): &(*list)->next : 0x605bb8 passing list = &(*list)->next to tstpptr (0x605b28) tstpptr(): list : 0x605b28 tstpptr(): &list : 0x7ffff14633a8 tstpptr(): *list : 0x605ba0 tstpptr(): &(*list) : 0x605b28 <- caller's address reported after tstpptr(): &(**list): 0x605ba0 &(*list)->prev; &(*list)->next tstpptr(): &(*list)->next : 0x605bb8The following are the relevant code snippets with the link to the full source at the beginning. Thank you for any help you can provide:
/* 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[]) { // <snip> 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 <= linemax)) { iterno++; list = &(*list)->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 <= linemax)) { iterno++; list = &(*list)->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变量的地址并不是你想要的。
I think I see the problem - I don't think there is one. The important value is *list, which is the same in all cases. I think printing out list and &list etc is just clouding the issue.
In your forward iterator, list is pointing to the location of item #48's next variable.
In your backward iterator, list is pointing to the location of item #0's prev variable.
In both cases *list is pointing to the correct item #49.
Both functions would be much simpler if they just took a rec *, rather than a rec **, then it would be more obvious that taking the address of the list variable isn't what you want.
更多推荐
发布评论