c - 在条件 (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)
    }
}

在任何一种情况下，该函数都是通过在调用者端按地址传递头指针来调用的:

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 的地址指针(通过地址作为参数传入)。

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

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) 进行一些调试在循环中使实际发生的事情最具教育意义。在调试器中手动遍历算法将提供大量信息。