C中的链表

Question

我正在尝试用节点结构自学链接列表，并希望有人可以帮助我。我会从命令行获取输入，它会让我成为一个嵌套列表，我可以输出它。

例子：

输入：“1 2 3 4 5”

输出：“1 2 3 4 5”

有两件事我遇到了麻烦：1）当我运行程序时，我不断收到 警告：在这个声明中忽略了’typedef’[默认启用] 我怎样才能摆脱这个？

编辑：我已将其更改为 typedef struct Node* NodePtr;

2）我的代码不能正常工作。我怎样才能解决这个问题？我正在尝试用 C++ 自学链表。

 typedef struct Node;
typedef Node* NodePtr;
struct Node{
    int x;
    NodePtr next;
};

int main ()
{
    int n;
    NodePtr head, ptr = NULL;
    head = ptr;
    while (cin >> n){
        ptr = new Node;
        ptr->x = n;
        ptr->next = NULL;
        ptr = ptr->next;
    }

    NodePtr bling = head;
    while(bling != NULL){
        cout << bling->x << endl;
        bling = bling->next;
    }
    return 0;
}

理想情况下，我想做的是制作一个如下所示的链表。

 1 -> 2 -> 3 -> NULL.

原文由 Masterminder 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

首先，关于你的结构的声明和你似乎想要的指针 typedef，有很多方法可以做到这一点。以下将在 C 或 C++ 中工作。

 // declare NodePtr as a pointer to Node, currently an incomplete type
//  C and C++ both allow you to declare a pointer to damn-near anything
//  so long as there is an understanding of what it *will* be, in this
//  case, a structure called Node.
typedef struct Node *NodePtr;

// Now declare the structure type itself
struct Node
{
    int x;
    NodePtr next;
};

也就是说，老实说，我 _不建议这样做_。大多数工程师想要一个 清晰 且语法可见的定义，让他们尖叫，“这是一个指针！”你可能不一样。我个人更喜欢这个：

 struct Node
{
    int x;
    struct Node *next; // omit the 'struct' for C++-only usage
};

只要您以及同样重要的 _其他工程师阅读您的代码_，了解您使用 NodePtr 作为指向节点的指针，然后选择最适合您的情况。指针类型声明对某些人来说几乎是宗教性的，所以请记住这一点。有些人更喜欢看到那些星号（我就是其中之一），有些人可能不喜欢（听起来像 你 =P）。

注意：有 一个 地方使用 typedef ed 指针类型有助于避免潜在错误： 多变量声明。考虑一下：

 Node* a, b;     // declares one Node* (a), and one Node (b)

拥有 typedef struct Node *NodePtr; 允许这样做：

 NodePtr a, b;   // declares two Node*; both (a) and (b)

如果您花足够的时间用 C 编写代码，那么前者会在您学会不犯该错误的情况下反复咬您一口，但它仍然会偶尔发生。

---

负载循环

关于将列表拼凑在一起的加载循环，您没有正确连接列表，坦率地说，有一百万种方法可以做到这一点，其中一种是下面的方法。这 不需要 您清除“额外的节点”。它也不需要任何 if (head){} else{} 块结构来避免上述相同的情况。考虑一下我们真正想做的事情：创建节点并将它们的地址分配给正确的指针：

 NodePtr head = NULL;     // always the head of the list.
NodePtr* ptr = &head;    // will always point to the next pointer to assign.
int n;
while (cin >> n)
{
    *ptr = new Node;
    (*ptr)->x = n;
    ptr = &(*ptr)->next;
}

// note this always terminates the load with a NULL tail.
(*ptr)->next = NULL;

---

这个怎么运作

1. 将头指针初始化为NULL
2. 初始化节点指针指针（是的指针指针）以指向头指针。该指针对指针将始终保存 目标 指针的地址，该地址将接收下一个动态分配节点的地址。最初，这将是头指针。在上面的代码中，这个指向指针的指针是变量： ptr 。
3. 开始while循环。对于读取的每个值，分配一个新节点，将其保存在 ptr 指向的指针中（因此 *ptr ）。在第一次迭代中，它保存了 head 指针的地址，因此 head 变量将获得我们的新节点分配。在所有后续迭代中，它包含 插入的最后一个节点 的 next 指针的地址。顺便说一句，保存这个新目标指针的地址是我们进入下一个分配周期之前在循环中完成的 最后一 件事。
4. 一旦循环完成， 最后 插入的节点需要将其 next 指针设置为 NULL 以确保正确终止的链表。 _这是强制性的_。我们很方便地有一个指向该指针的指针（我们一直在使用的那个指针），因此我们将它“指向”的指针设置为 NULL。我们的列表已终止，我们的加载已完成。 Brain Food：如果加载循环从未加载任何节点，它将 指向 什么指针？答案： &head ，如果我们的列表为空，这正是我们想要的（一个 NULL 头指针）。

---

设计

我希望这将有助于更好地解释它是如何通过循环的三个完整迭代来工作的。

初始配置

      head ===> NULL;
ptr --^

一次迭代后：

 head ===> node(1)
          next
ptr ------^

两次迭代后

head ===> node(1)
          next ===> node(2)
                    next
ptr ----------------^

三轮迭代后

head ===> node(1)
          next ===> node(2)
                    next ===> node(3)
                              next
ptr --------------------------^

如果我们在三个迭代中停止，最终的终止分配（ *ptr = NULL; ）给出：

 head ===> node(1)
          next ===> node(2)
                    next ===> node(3)
                              next ===> NULL;
ptr --------------------------^

注意 head 一旦第一次迭代完成就永远不会改变（它总是指向第一个节点）。另请注意， ptr 始终保存要填充的下一个指针的地址，在初始迭代之后（它从我们的头指针的地址开始），将始终是 next 添加的 最后一个 节点中的指针。

我希望这能给你一些想法。值得注意的是，将这两个指针（ head 指针和 ptr 指针）配对到它们自己的结构中并具有适当的管理功能定义了教科书 Queue ；其中一端仅用于插入（ ptr ），一端用于提取（ head ）并且容器 不允许 随机访问。如今，使用标准库容器适配器（如 std::queue<> ）已经不需要这样的东西了，但它确实提供了一个有趣的冒险，可以很好地使用指针对指针的概念。

---

完整的工作样本

这个示例只加载我们的队列，包含 20 个元素，打印它们，然后清理队列并退出。根据需要适应您的使用情况（提示：比如更改传入数据的来源）

 #include <iostream>
using namespace std;

// declare NodePtr as a pointer to Node, currently an incomplete type
//  C and C++ both allow you to declare a pointer to damn-near anything
//  so long as there is an understanding of what it *will* be, in this
//  case, a structure called Node.
typedef struct Node *NodePtr;

// Now declare the structure type itself
struct Node
{
    int x;
    NodePtr next;
};

int main()
{
    // load our list with 20 elements
    NodePtr head = NULL;
    NodePtr* ptr = &head;
    for (int n=1;n<=20;++n)
    {
        *ptr = new Node;
        (*ptr)->x = n;
        ptr = &(*ptr)->next;
    }

    // terminate the list.
    *ptr = NULL;

    // walk the list, printing each element
    NodePtr p = head;
    while (p)
    {
        cout << p->x << ' ';
        p = p->next;
    }
    cout << endl;

    // free the list
    while (head)
    {
        NodePtr victim = head;
        head = head->next;
        delete victim;
    }

    return 0;
}

输出

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

原文由 WhozCraig 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

您实际上并未将“head”变量设置为 NULL(head = ptr)。你实际上从一开始就失去了你的清单。尝试这个：

 int n;
NodePtr head, ptr;
ptr = new Node;
head = ptr;
while (cin >> n){
    ptr->x = n;
    ptr->next = new Node;
    ptr = ptr->next;
}

然后您可能想要删除最后一个 ptr->next 并将其设置为 0 以节省内存并避免打印出额外的值。

原文由 Sinkingpoint 发布，翻译遵循 CC BY-SA 3.0 许可协议