如何使用结构体创建链表

Question

我看过一些关于链表的主题，我已经阅读了足够多的内容来收集如何使用链表，但是我想确保我没有错误地解释我所收集的信息。

假设我有:

struct element 
{
    int       val;
    element   *next;
};

元素*next是指向另一个元素的指针，用于将元素连接在一起以形成链表。

我还收集到，你需要有某种"领带"，这样你就不会丢失你的清单。我的教授把它描述成一串气球，如果你不系上领带，你的清单就会迷路。

我从创建"tie off"指针开始:

element first;
first -> *next = 0; // or null

这就是我迷路的地方…如何添加到链表的头部?排序在这里并不重要，我只需要从一个无序列表开始，稍后我会变得更复杂。

像这样?

element addMe;
addMe -> val = 100;
first -> next = *addMe;

对吗?

如何向非空列表添加内容?

感谢您的宝贵时间!

编辑:这不是家庭作业。我们已经复习了链表，并做了一个关于它们的作业。这次作业我的成绩不是很好，所以我在下次作业前努力加强自己的理解。我们将再次使用链表。

Edit2:谢谢!

我不知道这是否会被认为是"家庭作业"。我个人不这么认为，考虑到我不会使用我在这里发布的代码。

Answer 1

对于单链表，添加新元素的有效方法是将它们放在列表的开头。对于您的设计，这将是:

element newHead;
newHead.next = &list;

你会注意到newHead现在是第一个元素，而list不再代表整个列表。这导致了一种更函数式的编程风格，在这种风格中，你总是在创建新的列表(参见:Lisp中的cons函数)。

像c++这样的过程语言通常使用这样的包装结构:

struct list
{
    element * first;
    void prepend(element * elt)
    {
        elt->next = first;
        first = elt;
    }
}

so列表前缀表示为更改现有列表而不是创建新列表。

有了这样一个辅助结构，跟踪列表大小和保持指向最后一个元素的指针用于快速追加也很简单。

Answer 2

通常存储指向第一个节点的指针:

element* first = &first_node; // this "ties" it off
first->val = 5; // set first node value to 5
first->next;    // pointer to next node

如果你的列表是空的，那么首先应该设置为NULL。

另外，列表中的最后一个节点应该将next设置为NULL。

Answer 3

你必须有一个第一个指针或者头指针，或者随便你怎么叫它。当链表为空时，指针为NULL。但是，当您向链表添加第一个元素时，也将该元素的节点地址添加到hear/first指针中。并且从第二个节点开始，将新节点的地址附加到列表的末尾(下一个指针为NULL的节点)，或者通过先更改头/然后将当前头添加到新头的下一个。

我不知道这样的理论是否有帮助。只需遵循示例或编写自己的代码。如果遇到错误，请将其张贴在SO上。我想链表、队列、堆栈等在所有c或c++书籍中都是可用的。

或在SO中搜索链表。

简单c++链表

Answer 4

如果你想添加到列表的头部

struct element *el = (element *) malloc(sizeof(struct element));
el->val = 100;
el->next = first;

现在el是第一个元素，first是第二个元素

在您的示例中，您使用新元素覆盖下一个元素的第一个元素。您可以剪切列表并插入新元素作为第二个元素。first之后的所有内容现在都从列表中删除了(这也是一个列表，但是您无法访问它，因为您覆盖了指向第三个元素的指针)。

要添加到列表的末尾，迭代

struct element *e;
e = first;
while (e->next !=0)
  e = e->next;
// here e is the last element. Allocate a new one and point e->next to it. And set this new one next to 0.