c - 一个有趣的 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列表的指针(如果插入发生在开头)或上一条记录的 next 字段，这很酷。

几个问题:

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

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

我以为我非常了解 C，并且对指针和间接寻址非常了解，但是我花了一段时间才完全理解。

Answer 1

我用类似的方法插入到二叉树中。因为在迭代树时，您通常会在指针变为 NULL(您跑出树)时停止。

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

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

2:当你要跟随的指针为 NULL 时停止，然后再跟随它，有效但在我看来稍微不那么优雅。

3:或者更优雅的解决方案是简单地使用指向指针的指针，所以你可以这样做:*it = new_node(); 它会将它添加到 的位置NULL 曾经在你的树中。

对于链表，虽然这段代码工作得很好，但我通常只使用双向链表，这使得在任何位置插入变得微不足道。