C循环双链表: traverses fwd/rev for end node gives different pointer address

Question

相关帖子:c circular double linked-list delete_node - iterate traverses deleted node on first pass after delete

所有，在删除该节点之前实现对包含行号“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->上一页；”适本地。作为反向搜索的测试，我只是简单地向开头添加一个节点，然后向前一个节点返回到有问题的节点，然后 delete_node 工作正常。 (只需附加:list = &(*list)->prev; list = &(*list)->next;。因此，问题与通过反向搜索到达结束节点时的指针状态有关而不是正向搜索——这就是我需要帮助弄清楚的。这是正向和反向搜索以及快速 ->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 : 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);
}

Answer 1

我想我看到了问题所在 - 我认为不存在这个问题。重要的值是*list，它在所有情况下都是相同的。我认为打印列表和 &list 等只会使问题变得模糊。

在前向迭代器中，list 指向项目 #48 的 next 变量的位置。

在向后迭代器中，list 指向项目 #0 的 prev 变量的位置。

在这两种情况下，*list 都指向正确的项目 #49。

如果这两个函数只采用 rec * 而不是 rec **，那么它们会更简单，那么采用list 变量不是您想要的。