一个有趣的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字段。该函数的最后一行要么更新列表的头指针（如果插入发生在开头），要么更新先前记录的next字段，这非常棒。

几个问题：

• 这种惯用法有没有名称或是否在任何文献中提到？

• 在C语言中是否有其他类似的方法？

我认为我对C语言和指针以及间接性非常了解，但是这个问题花了我一些时间才完全理解。

- gooli

---

char* value 而不是 char *value？呃，不要在那里工作。 - finnw

@finnw 这是个人（或工作场所）风格的问题。对我来说，它也将是 char* value。 - zentrunix

@JoséX。像大多数C程序员一样，我也犯过几次写char* pointer1, pointer2;的错误。没有空格的'char*'会让人们更容易以与编译器不同的方式解读它（从而增加这种错误的可能性）。 - finnw

这种技术在Steve Maguire的《编写可靠代码》一书中被讨论，但没有给出名称。有些人批评这本书（请参见ACCU评论），我认为它是合理的，尽管在某些地方现在已经过时了（主要是因为它是在标准C编译器普遍可用之前编写的）。 - Jonathan Leffler

Answer 1

我曾经使用类似的方法来插入二叉树。因为在遍历树时，通常当指针变为NULL（超出了树的范围）时停止。

所以要插入，你有3个选项，

1: 使用一个变量来跟踪你迭代的指针的上一个值。

2: 在跟随指针之前检查该指针是否为空，虽然可行但我认为不太优雅。

3: 或更优雅的解决方案是简单地使用指向指针的指针，这样你只需执行：*it = new_node();它就会将其添加到你树中原来的NULL位置。

对于链表，虽然这段代码非常好用，但我通常只使用双向链表，这使得在任何位置进行插入变得轻而易举。

- Evan Teran

---

这正是我一直在寻找的——既能识别模式，又能在二叉树中应用它。谢谢！ - elifiner

Answer 2

我认为这个成语是“那种让‘c’声名狼藉的代码”

• 过度聪明
• 过度紧凑
• 对调用者产生意外副作用
• 在malloc上没有错误处理
• 仅适用于美式英语字符串

- Will Dean

---

这段代码看起来很简单，没有什么“聪明”的地方，是一个典型的例子，忽略了错误检查并使用了一个显而易见的库函数。 - Paul Nathan

哇，迪恩真的很讨厌C语言。它并不足够聪明或紧凑，是典型的C代码。它确切地为调用者做了调用者想要的事情。在这里发布时省略错误处理以避免混淆重点是一个好的实践。 - buti-oxa

@Tim，我喜欢你说的“2001年我误打误撞地接了一份工作”的那句话——难道你只是路过他们公司的大门，不小心摔进去然后签了接受表格吗？ :-) - paxdiablo

传入的指针没有标记为const，所以当然会向调用者发出可能被更改的信号？ - unwind

同意最后两点。强烈反对第三点。这是在C语言中模拟按引用传递的传统（也是最简单）方法。如果类似的C#方法被定义为void InsertSorted(ref Record r, string value)，你不会抱怨“意外”的副作用，对吧？从函数签名中可以明显看出它可以修改r。 - finnw

Answer 3

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

我唯一的抱怨是调用者指针（*r）被修改了。根据函数的使用情况，我认为这是一个意外的副作用。除了消除意外的副作用外，使用一个本地变量来扮演*r的角色将使代码更易读。

- Frank Schwieterman

---

更新*r会返回指向新节点的指针。这是有意为之的，否则如果值不唯一，则没有明确的方法来访问新节点。 - ConcernedOfTunbridgeWells

为什么不让函数将记录*返回到新节点呢？ - Adam Jaskiewicz

r 用于修改链表的头指针，以防为空。record *newlist = NULL; insert_sorted(&newlist, "value"); 现在 newlist 指向一个单元素链表。 - aib

AIB，这是一个不错的情景/想法。但是当新元素没有成为列表的头部时，调用者的指针就会指向除头部以外的其他位置。如果目的是告诉调用者头部，那么它应该只做这件事。 - Frank Schwieterman

你说得对，我忽略了最后一个*r=的赋值是无条件的。它只应该在需要更新头指针时才会发生。 - aib

Answer 4

这里应该用什么惯用语呢？肯定不是链表的实现。

使用指向指针的构造方式？

简洁的循环？

个人建议使用返回指针值的方式，而不是操作输入值。因为看到这种输入数据类型会让我想起什么，让我在将其传递给你的函数之前先复制我的值。

- hydroes

Answer 5

这是一个众所周知的技巧 - 双指针迭代（这是我给它起的名字，我不知道官方名称）。其目的是能够定位单链表中的一个位置，并在该位置之前插入（在之后插入很容易）。实现上，需要两个指针（当前和前一个）以及特殊代码处理列表开头（当 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;
}

- user3458

---

C语言没有引用，pp的类型应该是Element **，而不是Element *。 - Evan Teran

好的，所以我在这里允许自己有些自由。这个技巧在C++和C中同样有价值。 - user3458

Answer 6

我不知道这种方法是否有名字或者是否是某种特殊的习语，但在现今内存相对充足的情况下，我的链表（在编程语言库中没有提供的情况下）是一种特殊变体，可以极大地简化代码。

首先，它们始终是双向链表，因为这使得遍历和处理以及插入/删除操作都更加容易。

实际上，“空”列表由两个节点组成：头结点和尾结点。这样做的好处是，插入和删除操作无需考虑要删除的节点是头节点还是尾节点，它们只需要假设它是中间节点即可。

将新节点 y 插入到节点 x 之前变得非常简单：

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

这些都有助于使代码更易于理解，而无需处理边缘情况的特殊处理，代价是多使用了几个节点的内存。

- Pax

---

你的遍历不允许修改指向n的指针，以完成插入。 - Frank Schwieterman

哎呀，谢谢@Frank，我已经有一段时间没有做这个了，因为我现在主要做Java，它几乎已经实现了太阳下的所有数据结构。我已经修复了它。 - paxdiablo

AmigaOS 广泛使用这种双向链表。 - user52898

一个有用的模式，但这并没有回答问题。 - finnw

@finnw，这个问题有两个部分：（1）“这个习语有名称吗？或者在任何文献中提到过吗？”（2）“C语言中是否还有其他类似的习语？”- 我认为你会发现我回答了第二部分。当然，这是模糊的记忆，一年半前的事情 :-) - paxdiablo

这在 Knuth 中提到过。您也可以使用相同的节点作为头部和尾部。 - Paul Hankin

Answer 7

回答原问题，这被称为指针中心方法而不是天真的节点中心方法。 Rex Barzee 的《高级编程技术》第3章在amazon.com提供了指针中心方法的更好示例实现。

- Rex Barzee

---

高级编程技术目前是2011年版。这项技术已经存在很长时间了。例如，在1993年S Maguire的《编写可靠代码》中有所讨论（虽然只是略带一笔）。 （WSC的声誉参差不齐；它并不是一个推荐，尽管我认为它比批评者允许的要好；相反，它只是先前出版物的“例子”。我会感到惊讶如果WSC是第一个提出这个技术的。我只是碰巧知道它。） - Jonathan Leffler

Answer 8

这个成语出现在《C语言指针》第12章中。它用于在没有链表头的情况下向链表中插入节点。

- placebo

Answer 9

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

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

顺便提一下，你缺少malloc/strdup失败情况的错误处理。

- Greg Rogers

---

我认为 *head 不应该是 const，因为这个函数可能需要修改它的 next 指针。 - finnw

Answer 10

我也想到了使用双指针，我用过它，但我并不是很喜欢。我编写的代码有这个核心来搜索特定的对象并将它们从列表中删除：

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

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

- cmaster - reinstate monica