0

我试图了解链表节点是什么。传递给构造函数的是什么？特别是什么是node* head？它是指向结构本身的指针。链表如何适应这种结构？

struct node {
    node* next;
    int data;
    explicit node(int data) : node(nullptr, data) {}
    node(node* head, int data) : next(head), data(data) {}
}

编辑：：

我应该更清楚我的问题。我知道我可以手动定义每个节点并初始化它们并继续这样做以创建一个列表。但是我如何从节点实现一个列表而不指定我每次想要什么？我想我得到的是我不确定如何从刚刚给定节点定义的节点构建列表。

4

5 回答 5

1

我们先关注单个节点：

--------
| data |
--------
| next |
--------

显然，datamember 保存了当前节点的数据。因此，节点只是一对data持有者，以及指向列表中下一个元素的指针 ( next)。现在，“链表”这个名称告诉你，这种数据结构是由一些链接连接起来的。所以你可能有多个节点，链接在一起，像这样：

--------     --------       --------
| 5    |     | 3    |     | 6       |
--------     --------      --------
| next | --->| next | --->| nullptr |
--------     --------      --------

很容易找到列表中的最后一个节点是哪个节点——next指针的值为 的nullpointer那个节点，表示列表中没有更多节点。

但是，我们如何找到列表的第一个元素呢？我们将通过保持head指针 - 指向内存中某处列表的第一个元素的指针来做到这一点：

--------     --------       --------
| 5    |     | 3    |     | 6       |
--------     --------      --------
| next | --->| next | --->| nullptr |
--------     --------      --------

  ^
  |
 head

通过存储head指针，我们可以像这样轻松地遍历列表：

node *tmp = head; // tmp is our "iterator" through the list
while(tmp != nullptr) 
{
   // Print the data
   cout << tmp->data;

   // Move iterator to the next element
   // Note that when we print the last element,
   // tmp will become nullptr, and the loop will break!
   tmp = tmp->next;
}

我应该更清楚我的问题。我知道我可以手动定义每个节点并初始化它们并继续这样做以创建一个列表。但是我如何从节点实现一个列表而不指定我每次想要什么？我想我得到的是我不确定如何从刚刚给定节点定义的节点构建列表。

有一个聪明的技巧可以做到这一点 - 您可以将last指针保存在某个地方，并且您可以创建一个辅助函数，例如：

void insert(int data)
{
    node* n = new node(data);

    // If the list is empty:
    if(head == nullptr)
    {
       // This element becomes the first!
       head = n;
    }
    else
    {
       // Append this element to the end of the
       // list
       last->next = n;
    }

    // Update last, as this is the last
    // element in the list
    last = n;
}
于 2013-09-09T14:15:50.540 回答
0

node* headnode是您显然保留了引用/句柄的第一个实例化。随后的实例化形成链表。

于 2013-09-09T14:09:53.743 回答
0

也许维基百科有助于澄清问题： http ://en.wikipedia.org/wiki/Linked_list#Basic_concepts_and_nomenclature

命名法说：头是第一个元素，而尾巴是指其余的。

于 2013-09-09T14:14:40.783 回答
0

链表是一系列事物一个接一个地连接在一起。列表中的每个事物都是（或由其持有）一个“节点”，因此链表节点是链表中的一个条目。在示例中，您给出的节点是一个结构，其中包含值（“数据”）空间以及指向下一个列表节点的指针空间。

您的示例中的第一个构造函数初始化一个节点，但没有将其链接到列表中。第二个创建一个节点并使其成为列表的头部。您的列表是通过将新节点推到其头部来构建的。头是列表中的第一个节点，所有其他节点都可以通过从头开始的“下一个”指针到达。

于 2013-09-09T14:12:22.837 回答
0

链表节点实际上是链表的一个节点，它具有数据字段和指向下一个节点的指针。就像您的代码已经显示的那样。

struct node {
    node* next;
    int data;
    explicit node(int data) : node(nullptr, data) {}
    node(node* head, int data) : next(head), data(data) {}
}

如果node *head放在一个linkedlist结构中就更清楚了，这使得linkedlist操作更方便。例如：

struct linkedlist {
   node *head;
   linkedlist();
   node *getHead();
   node *getNext();
   void traverse_list();
   ......
}
于 2013-09-09T14:12:36.450 回答