c循环双链表：rev遍历为同一节点提供不同的列表指针地址 [英] c circular double linked-list: rev traverse gives different list-pointer address for same node

问题描述

相关文章1： c圆形双链表delete_node-删除后迭代遍历已删除的节点

相关文章2：c圆形double-linked-list：遍历fwd / rev以结束节点给出了不同的指针地址

在使用循环双链表时，我在stackoverflow的帮助下创建了一个delete_node函数，该函数同时使用两个或在列表上进行反向迭代以到达要删除的节点。该函数将链接列表的地址作为参数来简化删除操作（与指向列表的指针引用相反）。正向和反向迭代的混合仅是为了提高效率，以防止遍历整个列表在正向迭代时到达末尾附近的节点，而在反向迭代时避免到达起始节点。

 完整源代码：
 http://www.3111skyline.com/dl/dev/prg/src/testlld.c.txt 
编译为：gcc -Wall -o tlld testlld.com 
 
 void 
 delete_node（rec ** list，int node）
 {
 
 //测试列表是否存在
 if（！* list）{
 fprintf（stdout，％s（），列表为空\n，__ func__）; 
的回报； 
} 
 
 //获取列表的大小
 int szlist = getszlist（* list）; 
 
 //测试节点< szlist 
 if（节点> = szlist ||节点< 0）{
 fprintf（stderr，％s（），错误：要删除的记录超出范围（％d）\n ，__ func__，节点）； 
的回报； 
} 
 
 //通过均衡搜索找到第一个节点
 //搜索fwd以查找0-> szlist / 2，rev end-> szlist / 2 
 if（node！= 0&& => = szlist / 2）{
而（szlist-node ++）
 list =&（** list）-> prev; 
 
 list =&（** list）->上一个; //删除
 list =&（** list）-> next;之前先获取正确的列表ptr //当反向遍历list时
}否则
而（node--）
 list =&（** list）-> next; 
 
 //创建指向节点的指针以删除
 rec * victim = * list; 
 
 //非自引用节点意味着如果（受害者！=受害人->下一个）{
（受害者->上一个）->下一个=受害者->下一个； 
（受害者->下一个）->上一个=受害者->上一个; 
 * list =受害人-> next; 
} else {//删除的节点是自引用的。最后一个节点
 * list = NULL; 
} 
 
免费（受害者）； //删除节点
} 
  

但是，我遇到了一个反向迭代的问题其中到达期望节点时报告的指针地址与通过正向迭代到达时针对同一节点报告的地址不同。在相关文章2中，这可以通过向前迭代将poiter-to-the-node-pointer保留在（node-1）上，而反向迭代则将其指向（node + 1）来解释，而两个节点指针都正确指向了（node） 。我不认为是这种情况。

在反向迭代所需节点后转储指针，然后又迭代一个步骤（节点），可以很容易地看到问题。 ->上一个）再次转储指针，然后在向前方向上退回到所需的节点（node-> next）并再次转储指针。为节点报告的地址更改。这是节点30的示例：

 反向迭代到节点后的列表指针状态：30 
 29-上一页： 0x605070 cur：0x605100 next：0x605078 
 30-上一页：0x605100 cur：0x605190 next：0x605108 
 31-prev：0x605190 cur：0x605108 next：0x605198 
 
 next之后的列表指针状态步骤到节点：29 
 28-上一页：0x604fe0 cur：0x605070下一页：0x604fe8 
 29-上一页：0x605070 cur：0x605100下一页：0x605078 
 30-上一页：0x605100 cur：0x605078下一页：0x605108 
 
前进到节点后的列表指针状态：30 
 29-上一页：0x605070 cur：0x605100 next：0x605078 
 30-prev：0x605100 cur：0x605078 next：0x605108 
 31-上一页：0x605190 cur：0x605108 next：0x605198 
  

我不明白！在上面的3的第一个块中，节点30的列表指针达到反向迭代，并将其地址报告为 cur：0x605190 。这看起来很糟，就像代码有问题，但没有。但是出了点问题，因为 node 30 cur：！=节点29 next：。反向继续执行下一步 list =&（** list）-> 给出下一个地址块，并且列表指针地址已更改为 cur：0x605078 。 ?？然而，通过查看现在节点29和29的地址，您可以看到问题在反向迭代中继续存在。 28.对于节点30来说，同样的问题现在存在于节点29（通过使用额外的步骤-> prev）。

现在移回节点 list =&（** list）-> next; 允许使用地址 0x605078 删除节点30一切正常。但是我无法理解为什么我不能只反向迭代节点30并执行删除操作？为什么反向插入节点30 0x605190 会比从正向 0x605078 到达要赋予不同的地址。 / p>

最后，在执行->上一步，->接下来的步骤之后，您可以看到 node 30 cur：0x605078 和 node 31 prev：0x605190 。 ?？ （这是最初到达节点30反向反向迭代时报告的地址？这是怎么回事？

完整的源代码可用。只需使用 gcc -Wall -o进行编译tlld testlld.com 。该代码创建了一个可运行的50节点链接列表。您可以使用 ./ tlld {49。 .0} 。

解决方案

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

这是基于我在上一个线程中提供的代码的delete_node_debug的更新版本。只是在循环中使用受害者而不是 * list ，这留下了 * list 指向列表的开头。然后最后，如果 victim == * list

<$，您可以检查是否要删除列表的开头p $ p> void
delete_node_debug（rec ** list，int node）
{

//测试列表是否存在
if（ ！* list）{
fprintf（stdout，％s（），列表为空\n，__ func__）;
的回报；
}

//获取列表的大小
int szlist = getszlist（* list）;

//测试节点< szlist
if（节点> = szlist ||节点< 0）{
fprintf（stderr，％s（），错误：要删除的记录超出范围（％d）\n ，__ func__，节点）；
的回报；
}

rec *受害者= *名单；
//用平衡搜索找到第一个节点
//搜索fwd 0-> szlist / 2，rev end-> szlist / 2
if（node！= 0 &&节点> = szlist / 2）{
而（szlist-node ++）
受害人=受害人->上一个；
fprintf（stderr，向节点反向迭代后的 nlist指针状态：％d\n，
受害人-> lineno）；
psurround（&受害者）;
} else
而（节点-）
受害者=受害人->下一个；

//非自引用节点意味着如果（受害者！=受害人->下一个）{
（受害者->上一个）->下一个=受害者->下一个；
（受害者->下一个）->上一个=受害者->上一个;
//如果我们要删除第一项，则需要更改传入的指针
if（受害者== *列表）
*列表=受害人-> next;
} else {//删除的节点是自引用的。最后一个节点
* list = NULL;
}

免费（受害者）； //删除节点
}


此外，更改调试输出函数psurround进行打印指针值，而不是指针变量的地址：

  void 
 psurround（rec ** list）{ 
 
 fprintf（stderr，％2d-上一个：％p cur：％p下一个：％p，n，
（*列表）->上一个-> lineno， 
（* list）->上一个-> prev，
（* list）-> prev，
（* list）->上一个-> next）; 
 fprintf（stderr，％2d-上一个：％p cur：％p下一个：％p\n，
（* list）-> lineno，（* list）-> prev ，* list，（* list）-> next）; 
 fprintf（stderr，％2d-上一页：％p cur：％p下一个：％p\n\n，
（* list）-> next-> lineno，
（* list）-> next-> prev，
（* list）-> next，
（* list）-> next-> next）; 
} 
  

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

related post 1: c circular double linked-list delete_node - iterate traverses deleted node on first pass after delete

related post 2: c circular double linked-list: traverses fwd/rev for end node gives different pointer address

In working with a circular double linked-list, I have, with help from stackoverflow, created a delete_node function that uses both forward or reverse iterations on the list to arrive at the node to be deleted. The function takes the address of the linked-list as the argument to facillitate the deletion (as opposed to a pointer reference to the list). The mix of forward and reverse iteration is simply for efficiency to prevent traversing the entire list to reach a node near the end when iterating in the forward direction or the beginning when iterating in reverse.

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
}

However, I have run across a problem iterating in reverse where the pointer address reported upon reaching the desired node is different from the address reported for the same node when reached with forward iteration. In related post 2, this was explained by forward iteration leaving the poiter-to-the-node-pointer on (node - 1) and reverse iteration leaving it pointing (node + 1) while both node-pointers correctly pointed to (node). I'm not convinced that is the case.

The problem is easily seen by dumping the pointers after iterating in reverse to the wanted node, then iterating one additional step (node->prev) dumping the pointers again, then stepping back to the wanted node in the forward direction (node->next) and dumping the pointers again. The address reported for the node changes. Here is an example for node 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

I do not get it! In the first block of 3 above, the list pointer for node 30 reached iterating in reverse reports its address as cur: 0x605190. This looks broken, like there is some problem with the code, but there isn't. Something is wrong however, because node 30 cur: != node 29 next:. Continuing one more step in reverse list = &(*list)->prev; gives the next block of addresses and the list pointer address has changed to cur: 0x605078. Huh? However, you can see the problem continues in reverse iteration by looking at the addresses for now nodes 29 & 28. The same issue that was a problem for node 30, now exists at node 29 (by virture of the additional step->prev).

Now moving back to node 30 with list = &(*list)->next; allows node 30 to be deleted using address 0x605078 and everything works fine. But I cannot get my head around why I can't just iterate to node 30 in reverse and have the delete work? Why does interating in reverse give a different address for node 30 0x605190 than if reaching it from the forward direction 0x605078.

Lastly, after the ->prev,->next steps, you can see the same type of problem between node 30 cur: 0x605078 and node 31 prev: 0x605190. Huh? (and that is the address originally reported for node 30 when reached iterating in reverse?? What is going on here?

The full source code is available. Simply compile with gcc -Wall -o tlld testlld.com. The code creates a 50 node linked-list to operate on. You can force the list to delete all nodes as a test with ./tlld {49..0}.

解决方案

As I said in the last thread, the problem is that you are looking at the address of the pointer variables, rather than the value of the pointer variables (i.e. where the variables are pointing). You also don't want to update *list unless the entry being deleted is the first one. Your calling function is relying on textfile to point to the start of the list.

Here is an updated version of delete_node_debug based on the code I offered on the last thread. I just used victim instead of *list in the loop, which leaves *list pointing to the start of the list. Then at the end, you can check if you are removing the start of the 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
}

Also, change your debugging output function psurround to print out the pointer values, rather than the addresses of the pointer variables:

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);
}

In general, I think any time you have multiple &s and *s in the same term (like *&(*list)), you need to rethink what is going on.

这篇关于c循环双链表：rev遍历为同一节点提供不同的列表指针地址的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！