c-从链接列表中删除元素

Question

我正在重构一些C代码，有一段时间我遇到了一个与链表数据结构有关的问题。请看下面的简化片段：

Link apply(Link first, pred_ptr cond)
{
    Link t=first->next,p=first;
    do{
        if(cond(t))
        {
            p->next=t->next;
            free(t);
            t=p;
        }
        p=t;
        t=t->next;
    }while(t!=first);
    //Check the first
    if(cond(first))
    {
        t=first->next;
        free(first);
        first=t;
        p->next=t;
    }
    return first;
}

函数apply从链表中删除函数cond返回非零值的所有元素Link是这样的：

struct node
{
    struct node* next;
    //Stuff
};
typedef struct node* Link

好吧，我唯一的问题是关于apply如何删除链表的第一个元素-first-，看起来需要循环外的额外代码才能对第一个元素求值，如果没有额外的if语句，我无法将此检查放入循环内，也许你可能知道如何从循环中删除额外代码-如果可能的话-，是吗？

谢谢，

祝你今天愉快。

Answer 1

第一个元素是一个特殊情况，因此您将为该元素编写与其他情况略有不同的代码，这并不奇怪。因此，您的替代方案是（1）按照示例中的方式进行，（2）将特殊情况代码放在主循环中，每次迭代都执行if比较，或者（3）使用指针对指针的不太容易理解的版本。

你应该问自己的第一个问题是：为什么要重构？为了清楚起见，还是因为已经证明需要更快的实施？或

Answer 2

您的代码的逻辑几乎正确，但在某些地方存在各种问题：

• 通过阅读代码，我猜测link list实际上是circular link list，因为如果不是，那么在某个节点中，某些->next将是== NULL。代码不会在任何地方检查NULL，当达到NULL时，while循环结束前的t=t->next;等行将执行Undefined Behavior。假设cond函数与NULL一起正常工作，并且不输入if语句（如果输入，则此处将执行UBp->next=t->next;）。如果link list只是一个link list而不是循环的，那么代码需要大量重构

linked list或circular linked list中的第一个元素可以单独分析，在简单的linked list的情况下，这种方式更好，因为分析其余节点的循环更可读，并且不需要处理特定的情况（将在循环外处理，并且检查第一个节点不会使其他节点的分析过载），在CCD_ 16的情况下，第一个元素可以在循环中优雅地分析，但也可以在循环外分析。

顺便说一句，如果你已经在重构中了，那么实际代码中使用的变量名会得到更好的改进（p->previor，t->test？我认为等等…）