一个有趣的 C 链表习惯用法

Question

我参加了一个 C 职位的面试，他们向我展示了一个我以前从未遇到过的习语。 这是一个简化涉及链表的各种算法的实现的技巧，我想知道是否有其他人遇到过这个。

假设我们有一个这样定义的链表记录：

typedef struct _record
{
    char* value;
    struct _record* next;
} record;

我们需要一个插入新记录的函数，以便整个列表根据记录中的值保持排序。 以下实现比我使用的任何实现都更简单，尽管可读性较差。

void insert_sorted(record** r, const char* value)
{
    record* newrec = NULL;
    while(*r && strcmp(value, (*r)->value) > 0)
        r = &((*r)->next); /* move r to point to the next field of the record */
    newrec = malloc(sizeof(record));
    newrec->value = strdup(value);
    newrec->next = *r;
    *r = newrec;
}

当函数被调用时，r指向链表的头指针。 在 while 循环期间，r 被更新为指向记录的 next 字段，该字段位于我们要放入新记录的点之前。函数的最后一行要么更新 head列表的指针（如果插入发生在开头）或上一条记录的下一个字段，这非常酷。

有几个问题：

• 这个习语有名字或者在任何文献中提到过吗？

• C 语言中还有其他类似的吗？

我以为我很了解 C，并且很好地理解了指针和间接，但是我花了一段时间才完全理解。

Answer 1

我用类似的方式插入二叉树。 因为在迭代树时，通常会在指针变为 NULL 时停止（您跑出了树）。

因此，要插入，您有 3 个选项，

1：使用一个变量来跟踪迭代指针的前一个值。

2：当你要跟随的指针为 NULL 时停止，然后再跟随它，可以工作，但在我看来稍微不太优雅。

3：或更优雅的解决方案是简单地使用指向指针的指针，因此您可以执行：*it = new_node();，它会将其添加到NULL的位置code> 曾经在你的树中。

对于链表，虽然此代码运行良好，但我通常只使用双向链表，这使得在任何位置插入都很简单。

Answer 2

我想说的成语是“那种给‘c’带来坏名声的代码”

• 毫无根据地聪明
• 毫无根据地紧凑
• 对调用者产生令人惊讶的副作用
• malloc 上没有错误处理
• 只适用于美国英语字符串

Answer 3

我没有看到任何我称之为习语本身的东西。 它看起来像是在 C 中处理数据结构时的标准编码。

我唯一的抱怨是调用者指针 (*r) 被修改了。 根据该功能的使用，我预计这会产生意想不到的副作用。 除了消除意外的副作用之外，使用局部变量来扮演 *r 的角色还可以使代码更具可读性。

Answer 4

这里的习语是什么？ 肯定不是链表的实现。
指针结构的用法？
紧凑的循环？

就我个人而言，我会使用指针返回值而不是对输入值进行操作。
因为看到这个输入数据类型会敲响警钟，这让我在将值传递给您的函数之前复制它。

Answer 5

这是众所周知的事情——双指针迭代（这是我给它起的名字，我不知道正式名称）。 目标是能够在单个链表中找到一个位置，然后在该位置之前插入（在该位置之后插入是微不足道的）。 简单地实现，这需要两个指针（current 和 prev）和用于列表开头的特殊代码（当 prev == NULL 时）。

我通常编写的代码类似于

void insertIntoSorted(Element *&head, Element *newOne)
{
  Element **pp = &head;
  Element *curr;
  while ((curr = *pp) != NULL && less(curr, newOne)) {
    pp = &(pp->next);
  }
  newOne->next = *pp;
  *pp = newOne;
}

更新：

我忘记了这个技巧的另一个目的 - 一个更重要的目的。 它用于从单链表中删除元素：

// returns deleted element or NULL when key not found
Element *deleteFromList(Element *&head, const ElementKey &key)
{
  Element **pp = &head;
  Element *curr;
  while ((curr = *pp) != NULL && !keyMatches(curr, key)) {
    pp = &(pp->next);
  }
  if (curr == NULL) return NULL;
  *pp = (*pp)->next; // here is the actual delete
  return curr;
}

Answer 6

我不知道这是否有一个名称，或者即使它是一些特殊的习语，但是，由于现在内存相对充足，我的链接列表（语言库不让它们可用）是一个特殊的变体，它大大简化了代码。

首先，它们始终是双向链接的，因为这使得处理和插入/删除操作的两个方向的遍历都更容易。

“空”列表实际上由两个节点组成：头节点和尾节点。 通过这样做，插入和删除不需要担心它们要删除的节点是头节点还是尾节点，他们可以假设它是中间节点。

在节点 x 之前插入新节点 y 就变得很简单：

x -> prev -> next = y
y -> next = x
y -> prev = x -> prev
x -> prev = y

删除节点 x 也很简单：

x -> prev -> next = x -> next
x -> next -> prev = x -> prev
free x

调整遍历以忽略无关的头和尾：

n = head -> next
while n != tail
    process n
    n = n -> next

这一切都使代码更容易理解，而无需进行所有特殊处理边缘情况，以几个内存节点为代价。

Answer 7

最好不要将新节点的值作为输入/输出参数返回，而是将其作为函数的返回值。 这简化了调用代码和函数内部的代码（您可以摆脱所有那些丑陋的双重间接寻址）。

record* insert_sorted(const record* head, const char* value)

顺便说一句，您缺少对 malloc/strdup 失败案例的错误处理。

Answer 8

这个习惯用法在《C 语言指针》第 12 章中给出。它用于将节点插入到没有链表头的链表中。

Answer 9

为了回答最初的问题，这被称为以指针为中心的方法，而不是朴素的以节点为中心的方法。 Rex Barzee 的《高级编程技术》第 3 章可在 amazon.com 获取包括一个更好的以指针为中心的方法的示例实现。

Answer 10

我也想出了双指针的这种用法，我已经使用过它，但我不太喜欢它。 我想出的代码有这个内核来搜索某些对象并将它们从列表中删除：

Element** previous = &firstElement, *current;
while((current = *previous)) {
    if(shouldRemove(current)) {
        *previous = current->next;  //delete
    } else {
        previous = ¤t->next;  //point to next
    }
}

我不喜欢我的代码的原因是两个 if 子句之间的细微差别：语法几乎相同，但效果是完全不同的。 我不认为我们应该编写如此微妙的代码，但以不同的方式做会让代码变得非常冗长。 因此，无论哪种方式都不好 - 您可能会追求简洁或可读性，这是您的选择。

Answer 11

尽管有这些技巧，变量“r”的作用不是改变了吗？ 呼叫者在呼叫后如何知道“*r”的含义？ 或者执行后，列表的标题是什么？

我不敢相信这可以被举例说明（甚至在某些书中？！）。
我错过了什么吗？

如果您不返回任何指针（就像其他人建议的那样），那么我建议进行以下更改以保留输入的角色。

void insert_sorted(record** head, const char* value)
{
    record** r = head;
    bool isSameHead = false;
    record* newrec = NULL;
    while(*r && strcmp(value, (*r)->value) > 0) {
        r = &((*r)->next); isSameHead = true; }
    newrec = malloc(sizeof(record));
    newrec->value = strdup(value);
    newrec->next = *r;
    *r = newrec;
    if (!isSameHead) *head = newrec;
}

实际上，另一种更好的方法可能是使用“虚拟头节点”，它将其下一个节点链接到列表的开头。

    void insert_sorted(record** head, const char* value)
    {
        record dummyHead;
        dummyHead.next = *head;
        record* r = &dummyHead;
        while(r->next) {
           if(strcmp(value, r->next->value) < 0) 
              break;
           r = r->next;}
        newrec = malloc(sizeof(record));
        newrec->value = strdup(value);
        newrec->next = r->next;
        r->next = newrec;
        *head = dummyHead.next;
    }