一个有趣的C链表成语
我正在接受一个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并且很好地指出了指针和间接，但是这个让我花了一些时间来完全理解。
我已经使用类似的东西插入到二叉树中。 因为在迭代树时，通常在指针变为NULL （你跑掉树）时停止。
所以要插入，你有3个选项，
1：使用跟踪迭代指针的先前值的变量。
2：当你跟随它之前你所遵循的指针是NULL时停止，在我看来工作但稍微不那么优雅。
3：或者更优雅的解决方案是简单地使用指向指针的指针，所以你可以这样做： *it = new_node(); 并且它会将NULL添加到您的树中的NULL 。
对于链表，虽然这段代码工作得很好，但我通常只使用一个双向链表，这使得在任何位置插入都很简单。
我会说成语是“那种给’c’起个坏名字的代码”
- 毫无根据的聪明
- 无根据的紧凑
- 令人惊讶的呼叫者副作用
- 在malloc上没有error handling
- 仅适用于美国英语字符串
我没有看到任何我称之为成语的东西。 当您在C中处理数据结构时，它看起来像标准编码。
我唯一的抱怨是调用者指针（* r）被修改。 根据function的用途，我预计这会产生意想不到的副作用。 除了消除意外的副作用外，使用局部变量扮演* r的角色会使代码更具可读性。
这里的成语是什么？ 肯定不是链表的实现。 使用指针构造指针？ 紧凑的循环？
就个人而言，我会使用指针返回值而不是对输入值进行操作。 因为看到这个输入数据类型会响铃，这使我在将它交给你的函数之前复制我的值。
这是一个众所周知的事情 – 双指针迭代（这是我的名字，我不知道正式名称）。 目标是能够在单个链表中找到一个位置，然后在该位置之前插入（在它之后插入是微不足道的）。 天真地实现，这需要两个指针（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; }
我不知道这是否有一个名字，或者它是否是一些特殊的习惯用法但是，由于现在内存相对丰富，我的链表（语言库不能使它们可用）是一种特殊的变体，它大大简化了代码。
首先，它们总是双重链接，因为这使得处理和插入/删除操作的两个方向的遍历变得更容易。
“空”列表实际上由两个节点组成，即头部和尾部。 通过这样做，插入和删除不需要担心他们正在删除的节点是头还是尾，他们可以假设它是一个中间节点。
在节点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
这一切都有助于使代码更容易理解，而无需对边缘情况进行所有特殊处理，代价是几个内存节点。
不是将新节点的值作为输入/输出参数返回，而是最好将其作为函数的返回值。 这简化了调用代码和函数内部的代码（你可以摆脱所有那些丑陋的双重间接）。
record* insert_sorted(const record* head, const char* value)
你错过了malloc / strdup失败案例btw的error handling。
这个成语在“C指针”的第12章中给出。这用于将节点插入到没有列表头的链表中。
为了回答原始问题，这被称为以指针为中心的方法而不是以天真节点为中心的方法。 由amazon.com提供的Rex Barzee的“高级编程技术”第3章包含了一个更好的以指针为中心的方法实现示例。
我也想出了这个双指针的用法，我已经习惯了，但我并不喜欢它。 我想出的代码有这个内核来搜索某些对象并从列表中删除它们：
Element** previous = &firstElement, *current; while((current = *previous)) { if(shouldRemove(current)) { *previous = current->next; //delete } else { previous = ¤t->next; //point to next } }
我不喜欢我的代码的原因是两个if子句之间的细微差别：语法几乎相同，但效果完全不同。 我不认为，我们应该像这样编写代码，但是以不同的方式执行代码会使代码变得非常冗长。 所以，无论哪种方式都很糟糕 – 你可能只是为了简洁或可读性，这是你的选择。
尽管有伎俩，变量“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; }