C循环双链表: rev traverse gives different list-pointer address for same node

Question

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

相关帖子2:c circular double linked-list: traverses fwd/rev for end node gives different pointer address

在使用循环双链表时，我在 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
if (node >= szlist || node < 0) {
    fprintf (stderr, "%s(), Error: record to delete is out of range (%d)\n", __func__, node);
    return;
}

// 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++)
    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
}

但是，我遇到了反向迭代的问题，其中到达所需节点时报告的指针地址与前向迭代到达时为同一节点报告的地址不同。在 related post 2 ，这是通过正向迭代将指向节点的指针保留在 (node - 1) 上和反向迭代使其指向 (node + 1) 而两个节点指针正确指向 (node) 来解释的。我不相信情况是这样。

通过反向迭代到所需节点后转储指针，然后迭代一个附加步骤 (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 的第一个 block 中，节点 30 的列表指针达到反向迭代，将其地址报告为 cur: 0x605190。这看起来很糟糕，就像代码有问题一样，但事实并非如此。然而有些问题，因为 node 30 cur: != node 29 next:。反向继续执行 list = &(*list)->prev; 给出下一个地址 block ，并且列表指针地址已更改为 cur: 0x605078。啊？但是，通过查看现在节点 29 和 28 的地址，您可以看到问题在反向迭代中继续存在。与节点 30 相同的问题现在也存在于节点 29 上(通过附加步骤 -> 上一步) .

现在使用 list = &(*list)->next; 返回到节点 30，允许使用地址 0x605078 删除节点 30，并且一切正常。但我无法理解为什么我不能反向迭代到节点 30 并进行删除工作？为什么反向交互为节点 30 0x605190 提供的地址与从正向到达节点 0x605078 的地址不同。

最后，在 ->prev,->next 步骤之后，您可以在 node 30 cur: 0x605078 和 node 31 prev: 0x605190 之间看到相同类型的问题。啊？ (这就是反向迭代到达时最初为节点 30 报告的地址？这里发生了什么？

完整source code可用。只需使用 gcc -Wall -o tlld teSTLld.com 进行编译即可。该代码创建一个 50 个节点的链表进行操作。您可以使用 ./tlld {49..0} 强制列表删除所有节点作为测试。

Answer 1

正如我在上一个线程中所说，问题在于您正在查看指针变量的地址，而不是指针变量的值(即变量指向的位置)。您也不想更新 *list ，除非要删除的条目是第一个条目。您的调用函数依赖文本文件来指向列表的开头。

这是基于我在上一个线程中提供的代码的delete_node_debug 的更新版本。我只是在循环中使用了 victim 而不是 *list，这使得 *list 指向列表的开头。然后最后，您可以检查是否要删除列表的开头 if 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);
}

总的来说，我认为任何时候在同一个术语中出现多个 & 和 * 时(例如 *&(*list))，您都需要重新考虑发生了什么。