代码之家 › 专栏 › 技术社区 › VarunGupta

向链表添加新节点的新方法

pointers data-structures c c++

VarunGupta · 技术社区 · 17 年前

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;
}

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

6 回复 | 直到 17 年前

Michael Burr 17 年前

该漏洞在于,您依赖调用者执行将头部指针更新到列表的最后一步。

如果调用者忽略了这一点,编译器将不会抱怨,并且出于所有意图和目的,列表将看起来没有改变(并且您将泄漏节点的内存)。

Daniel Spiewak 17 年前

这就是链表在大多数函数式语言中的工作方式。例如,在ML中,你可能会做这样的事情:

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

这个 :: 语法实际上是一个接受两个参数的函数( 0 和 ls )并返回一个新列表,该列表具有 0 作为第一要素。ML中的列表实际上被定义为列表节点,因此 :: 实际上,它的写法与 addNewNode 你提出的功能。

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

Alnitak 17 年前

你的方法与以下想法不相容 addNode 是列表中的一种方法,在面向对象语言中更常用。

我个人认为

list.add(element)

这比想象中要直观得多

list = add(list, element)

几十个“收藏”图书馆不会错的。..

quinmars 17 年前

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

unwind 17 年前

这并不新鲜。正如quinmars所指出的那样,glib已经这样做了10多年。这是个好主意,所以恭喜你想出了这个主意。

不过,关于你的代码有一个小问题:不要强制转换返回值 malloc() 在C中,在使用时不要重复类型名称 sizeof 。您的分配行应如下:

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

看到了吗?更短,更紧,更容易阅读,更难搞砸。好多了! :)

sergtk 17 年前

我认为上述正确代码中没有任何问题。更改或不更改头部是一个设计问题,以及如何返回修改后的列表。 std::list<中实现了良好的接口;>作为使用OOP的示例,这种方法没有潜在的问题。head指针是隐藏的,您可以根据需要修改它,并且由于调用者没有显式存储head,因此它对列表的引用总是正确的。

有一件事看起来很难看(当你使用C++而不是C时),那就是malloc,最好使用“new”。