c++ - 如何使用结构创建链表？

Question

我已经看过一些关于链表的主题，并且我已经阅读了足够多的资料来了解一般情况下如何做，但我想确保我没有错误地解释我收集到的信息。

假设我有:

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

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

我还了解到，您需要某种“绑定(bind)”，这样您就不会丢失您的列表。我的教授将其描述为一串气球，如果您没有“领带”，您的 list 可能会丢失。

所以我开始创建“绑定(bind)”指针:

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

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

有了这样的辅助结构，跟踪列表大小并保持指向最后一个元素的指针以进行快速追加也很简单。这些都是以每个列表操作的一些额外指令为代价的。