2 
void addNewNode (struct node *head, int n)
{
    struct node* temp = (struct node*) malloc(sizeof(struct node));
    temp -> data = n;
    temp -> link = head;
    head = temp;
}

上面给出的代码是在链表头部添加新节点的函数的普遍错误版本。通常正确的版本是这样的，

void addNewNode (struct node **head, int n);
void addNewNode (struct node * &head, int n);

为此，我制定了另一个但简单的功能，效果很好。

struct node* addNewNode (struct node *head, int n)
{
    struct node* temp = (struct node*) malloc(sizeof(struct node));
    temp -> data = n;
    temp -> link = head;
    return temp;
}

但是我还没有看到在代码和教程中使用或讨论过这种方法，因此我很想知道这种方法是否存在缺陷。

4

6 回答 6

17

缺陷是您依赖调用者执行更新头指针到列表的最后一步。

如果调用者忽略了这样做，编译器将不会抱怨，并且出于所有意图和目的，列表似乎没有改变（并且您会泄漏节点的内存）。

于 2008-11-02T19:49:26.720 回答
4

这就是链表在大多数函数式语言中的工作方式。例如，在 ML 中，您可能会执行以下操作：

val ls = [1, 2, 3, 4]
val newList = 0 :: ls

::语法实际上是一个函数，它接受两个参数 (和0)ls并返回一个新列表，该列表具有0作为第一个元素。ML 中的列表实际上被定义为列表节点，因此实际上与您提出的函数::非常相似。addNewNode

换句话说：恭喜，您已经在 C 中创建了一个不可变的链表实现！理解这一点实际上是函数式语言相当重要的第一步，所以知道这真的是一件好事。

于 2008-11-02T19:50:33.503 回答
2

您的方法与列表中的方法的想法不兼容，addNode在 OO 语言中更常用。

我个人认为

list.add(element)

比直观得多

list = add(list, element)

几十个“收藏”库不会错……

于 2008-11-02T19:50:33.177 回答
1

Afaik，这就是 glib 中列表的工作方式，我相信 gtk 人不是第一个使用这种方式的人，所以我不会称之为新方法。我个人更喜欢有一个基本结构，它保存节点计数、第一个和最后一个指针。

于 2008-11-03T15:56:23.053 回答
1

这并不新鲜。正如 quinmars 所指出的，glib 已经这样做了 10 多年。这是一个好主意，所以恭喜你弄清楚了。

但是，关于您的代码的一个挑剔：不要malloc()在 C 中强制转换返回值，也不要在使用sizeof. 您的分配行应如下所示：

struct node* temp = malloc(sizeof *temp);

看？更短，更紧凑，更容易阅读，更难搞砸。更好的！:)

于 2008-11-03T16:10:35.803 回答
0

我在任何提到的正确代码中都没有发现任何问题。改变或不改变头部是设计问题 - 以及如何返回修改后的列表。std::list<> 中实现了良好的接口，作为使用 OOP 的示例，这种方法没有潜在问题。head 指针是隐藏的，您可以根据需要对其进行修改，并且由于调用者没有显式存储 head，因此它对列表的引用始终是正确的。

看起来丑陋的一件事（当你使用 C++，而不是 C 时）是 malloc，最好使用“新”。

于 2008-11-02T19:50:18.060 回答