在条件(C)下删除链表的节点

Question

我正在使用链表进行练习,其中我需要根据条件删除一些节点.条件是''删除存储的数据小于或等于'avg''的节点.

我应该考虑三种情况: - 删除头节点 - 删除中间的节点 - 删除最后一个节点

我使用了三个指针,但这似乎不起作用.我究竟做错了什么？我不小心错过了一些指针吗？先感谢您!

void checkAvg(int avg, struct list* head_node){

   struct list* prev;
   struct list* curr;
   struct list* next;

   prev = head;
   curr = prev->link;
   next = curr->link;

   while (curr!=NULL) {
      if (prev->data <= avg) {
          head = curr;
      }

      if (curr->data <= avg) {
          prev->link = curr->link;
      }

      if (next->data <= avg) {
          curr->link = next->link;
      } 

      prev = prev->link;
      curr = curr->link;
      next = next->link;

   }

}

编辑:对不起,正如你告诉我的那样,我并不具体.程序必须这样做:1)读取链表2)生成我读取的值的平均值(值/值的总和)3)从列表中删除具有<=的数据的节点平均释放那些节点的内存.关于free()部分,我遇到了一些困难,所以我想我首先要学习如何正确使用指针.你可能已经注意到了,我并不擅长这一点,我是首发.

感谢所有回复的人,我正在检查回复

Answer 1

如果你的链表没有一些前哨头节点(我强烈建议它没有,因为这NULL是一个很好的值,表明"我是空的"),删除遍历并不是太复杂.代码中您似乎误入歧途的地方是:

• 将头指针传递给地址并将参数声明为指向指针的指针,或者如果处理旧指针则返回新的指针.
• 保持本地指针变量的一致性.你要知道肯定什么都点在所有时间.

您可以使用指针值,也可以使用实际指针本身(按地址).我更喜欢后者.在任何一种情况下,头节点指针必须通过地址传递,以允许可能修改调用者的变量(就像C中的其他所有内容一样),或者该函数可以返回潜在的新头节点地址.我更喜欢这些方法的前者,因为它让您可以选择使用函数返回值将错误状态传递给调用者.你现在没有这样做,但你应该(提示).

void checkAvg(int avg, struct list** pp)
{
    while (*pp)
    {
        if ((*pp)->data <= avg)
        {
            struct list *victim = *pp;
            *pp = victim->link;
            free(victim);
        }
        else
        {   // advance to address of next "link" pointer
            pp = &(*pp)->link;
        }
    }
}

值得注意的是,如果列表按升序排序,则可以明显更简单.如果是这种情况,则整个checkAvg功能变得非常简单.一旦检测到不再适合您的条件的值,您就可以退出循环:

void checkAvg(int avg, struct list** pp)
{
    while (*pp && (*pp)->data <= avg)
    {
        struct list *victim = *pp;
        *pp = victim->link;
        free(victim)
    }
}

在任何一种情况下,通过将头指针传递给调用者端的by-address来调用该函数:

struct list *head = NULL;

//... populate list....

checkAvg(value, &head);

这个怎么运作

链接列表就像这样:

          --------      --------      --------
head ---> | link | ---> | link | ---> | link | ---> NULL
          | val1 |      | val2 |      | val3 |
          --------      --------      --------

使用发布的方法,遍历列表使用指针指针,它执行如下操作:

pp --:
     :        --------      --------      --------
    head ---> | link | ---> | link | ---> | link | ---> NULL
              | val1 |      | val2 |      | val3 |
              --------      --------      --------

pp指向指针 ; 不是节点.最初pp保存head指针的地址(作为参数传入by-address).

那么如果第一个节点符合您的标准会发生什么？最终,这就是结果

pp --:
     :        --------      --------
    head ---> | link | ---> | link | ---> NULL
              | val2 |      | val3 |
              --------      --------

             --------
 victim ---> | link |
             | val1 |
             --------

并且受害者节点被立即丢弃(受害者的链接实际上仍然引用第二个节点,但在分离发生后在此上下文中没有意义.

那么,如果第二个节点是需要删除的节点(即我们跳过第一个节点)呢？这有点复杂:

         pp -----:
                 :
              ---:----      --------
    head ---> | link | ---> | link | ---> NULL
              | val1 |      | val3 |
              --------      --------
             --------
 victim ---> | link |
             | val2 |
             --------

这是什么想显示(当然很差)就是pp指针到指针始终认为,我们的指针的地址可能被修改.如果我们不需要修改该指针,我们将保留的地址更改pp为指向link列表中的下一个指针(通过获取pp = &(*pp)->link

当列表已经排序时,后一种情况不会发生,因此其迭代循环更简单的原因.我们只是枚举列表,抛出节点,直到找到一个不再符合我们条件的节点.

但无论如何,pp 总是保存指向我们正在使用的节点的指针的地址..最初,该地址是调用者head指针的地址.

好.我只能希望能让它更清晰.printf("pp=%p, *pp=%p\n", pp, *pp)在循环中进行一些调试可以实现最具教育意义的实际情况.在调试器中手动遍历算法将提供高度信息.