一个有趣的C链表习惯用法 [英] An interesting C linked list idiom

问题描述

我在接受C职位面试时，他们给了我一个我以前从未遇到过的成语.这是一个技巧，可以简化涉及链表的各种算法的实现，我想知道是否还有其他人遇到过这种情况.

I was at an interview for a C position in which they presented me with an idiom that I haven't previously encountered. This is a trick that simplifies implementation of various algorithms involving linked lists and I'm wondering if anybody else has encountered this.

假设我们有一个链接列表记录，其定义如下:

Say we have a linked list record defined so:

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

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

We need a function that inserts a new record so that the entire list remains sorted with respect to the value's in the records. The following implementation is simpler than anything I would have used, albeit less readable.

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 字段，这很酷.

When the function is called, r points to the head pointer of the list. During the while loop, r is updated to point to the next field of the record that comes just before the point where we want to put the new record in. The last line of the function either updates the head pointer of the list (if the insertion happens at the beginning) or the next field of the previous record, which is quite cool.

几个问题:

• 这个成语有名字吗?在任何文献中都有提及吗?

• Does this idiom have a name or is it mentioned in any literature?

是否有其他人喜欢C语言?

Are there others like it in the C language?

我以为我很了解C，并且很清楚地知道了指针和间接寻址，但是这一步花了我一段时间才能完全理解.

I thought I knew C pretty well and had pointers and indirection pretty well figured out, but this one took me a while to fully understand.

推荐答案

我已经使用类似的方法将其插入到二叉树中.因为在迭代树时，通常会在指针变为 NULL (从树上跑出)时停止.

I've used similar to this to insert into a binary tree. Because when iterating the tree, you usually stop when your pointer becomes NULL (you ran off the tree).

要插入，您有3个选项

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

1: use a variable which tracks the previous value of your iterating pointer.

2:在您要遵循的指针为NULL时停止，然后停止工作，但我认为它稍差一些.

2: stop when the pointer you would follow is NULL before you follow it, works but slightly less elegant in my opinion.

3:或更简单的解决方案是简单地使用指向指针的指针，因此您可以执行以下操作: * it = new_node(); 并将其添加到NULL 曾经在您的树中.

3: or a more elegant solution is simply use a pointer to a pointer, so you can just do: *it = new_node(); and it'll add it where the NULL used to be in your tree.

对于链表，虽然这段代码很好用，但我通常只使用双链表，这样就可以在任何位置插入它.

For a linked list, while this code works nicely, I usually just use a doubly linked list which makes it trivial to insert at any location.

这篇关于一个有趣的C链表习惯用法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！