11

我在一个 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 非常了解，并且很好地理解了指针和间接寻址，但是这个我花了一段时间才完全理解。

4

11 回答 11

8

我会说成语是“那种给'c'起坏名声的代码”

  • 莫名其妙的聪明
  • 毫无根据地紧凑
  • 对来电者的惊人副作用
  • malloc 上没有错误处理
  • 仅适用于美国英语字符串
于 2008-12-01T22:38:43.070 回答
6

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

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

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

2：当你要遵循的指针在你遵循它之前为 NULL 时停止，在我看来，它可以工作但稍微不那么优雅。

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

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

于 2008-12-01T23:52:49.693 回答
4

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

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

于 2008-12-01T22:29:28.487 回答
3

这里的成语是什么？肯定不会执行链表。指针结构的指针的用法？紧凑的循环？

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

于 2008-12-01T22:29:55.977 回答
3

这是众所周知的事情-双指针迭代（这是我的名字，我不知道正式名称）。目标是能够在单个链表中定位一个位置，然后在该位置之前插入（在它之后插入是微不足道的）。天真地实现，这需要两个指针（当前和上一个）和用于列表开头的特殊代码（当 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;
}
于 2008-12-01T23:07:52.950 回答
2

我不知道这是否有名字，或者即使它是一些特殊的习语，但由于现在内存相对丰富，我的链表（语言库不提供它们）是一个特殊的变体，它大大简化了代码.

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

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

在节点 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

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

于 2008-12-01T22:32:10.917 回答
1

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

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

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

于 2008-12-01T22:52:22.687 回答
1

为了回答最初的问题，这被称为以指针为中心的方法，而不是简单的以节点为中心的方法。amazon.com上 Rex Barzee 的“高级编程技术”第 3 章包含一个更好的以指针为中心的方法的示例实现。

于 2008-12-10T02:29:21.913 回答
1

这个习语在“C 上的指针”的第 12 章中给出。这用于将节点插入到没有链表头的链表中。

于 2013-09-01T14:22:46.413 回答
0

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

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

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

于 2013-09-01T15:03:29.490 回答
0

尽管有这些技巧，变量“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;
    }
于 2014-02-02T17:20:00.487 回答