C++中的链表

Linked lists in C++(C++中的链表)

问题描述

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

I am trying to teach myself linked-lists with node structs and was hoping someone could help me with this. I would take input from the command line and it would make me a nested list and I could output it.

示例:

输入:1 2 3 4 5"
输出:1 2 3 4 5"

Input: "1 2 3 4 5"
Output:"1 2 3 4 5"

我遇到了两件事:1) 当我运行程序时，我不断收到警告:此声明中忽略了typedef"[默认启用]我怎样才能摆脱这个?

There are two things I am having trouble with: 1) When I run the program I keep getting warning: ‘typedef’ was ignored in this declaration [enabled by default] How can I get rid of this?

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

2) 我的代码工作不正常.我怎样才能解决这个问题?我正在尝试在 C++ 中自学链表.

2) My code is not working properly. How can I fix this? I am trying to teach myself linked lists in 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;
}

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

Ideally what I want to do is to make a linked-list like the following.

1 -> 2 -> 3 -> NULL.

推荐答案

首先，关于结构的声明和您似乎想要的指针 typedef，有多种方法可以做到这一点.以下内容适用于 C 或 C++.

First, regarding the declaration of your structure and the pointer typedef you seem to want, there are a number of ways of doing this. The following will work in C or 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;
};

也就是说，老实说，我不建议这样做.大多数工程师想要一个清晰和语法可见的定义，向他们尖叫:这是一个指针！"你可能不一样.我个人更喜欢这个:

That said, I honestly do not recommend doing this. Most engineers want a clear and syntax-visible definition that screams to them, "THIS IS A POINTER!" You may be different. I, personally would simply prefer this:

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

只要您和同样重要的其他工程师阅读您的代码，了解您将 NodePtr 作为指向节点的指针的用法，然后使用有效的方法最适合你的情况.指针类型声明对某些人来说近乎宗教，所以请记住这一点.有些人更喜欢看到这些星号(我就是其中之一)，有些人可能不喜欢(听起来像 you =P).

So long as you, and equally important, other engineers reading your code, understand your usage of NodePtr as a pointer-to-node, then go with what works best in your situation. Pointer type declaration is near-religious to some, so just keep that in mind. Some prefer seeing those asterisks (I being one), some may not (sounds like you =P).

注意:有一个一个地方，使用typedefed 指针类型有助于避免潜在错误:多个变量声明.考虑一下:

Note: there is one place that using a typedefed pointer-type can be beneficial in avoiding potential errors: multiple variable declarations. Consider this:

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 you spend enough time writing code in C the former of these will come back to bite you enough times you learn to not make that mistake, but it can still happen once in awhile.

负载循环

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

Regarding the load-loop for piecing together your list, you're not wiring up your list correctly, and frankly there are a million ways to do it, one being the one below. This does not require you to clean out "an extra node". Nor does it require any if (head){} else{} block structure to avoid said-same condition. Consider what we're really trying to do: create nodes and assign their addresses to the right pointers:

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

1. Initialize the head pointer to NULL
2. Initializer a Node pointer-pointer (yes a pointer to a pointer) to point to the head pointer. This pointer-to-pointer will always hold the address of the target pointer that is to receive the address of the next dynamic-allocated node. Initially, that will be the head pointer. In the above code, this pointer-to-pointer is the variable: ptr.
3. Begin the while-loop. For each value read, allocate a new node, saving it in the pointer that is pointed-to by ptr (thus the *ptr). On the first iteration this holds the address of the head pointer, so the head variable will get our new node allocation. On all subsequent iterations, it contains the address of the next pointer of the last node inserted. Incidentally, saving the address of this new target pointer is the last thing that is done in the loop before we move to the next allocation cycle.
4. Once the loop is complete, the last node inserted needs to have its next pointer set to NULL to ensure a properly terminated linked list. This is mandatory. We conveniently have a pointer to that pointer (the same one we've been using all this time), and thus we set the pointer it "points to" to NULL. Our list is terminated and our load is complete. Brain Food: What pointer will it be pointing to if the load loop never loaded any nodes? Answer: &head, which is exactly what we want (a NULL head pointer) if our list is empty.

<小时>

设计

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

I hope this will help better explain how it works through three full iterations of the loop.

初始配置

      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;)，给出:

If we stopped at three iterations, the final termination assignment (*ptr = NULL;), gives:

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

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

Notice that head never changes once the first iteration is finished (it always points to the first node). Also notice that ptr always holds the address of the next pointer that is to be populated, which after the initial iteration (where it started as the address of our head pointer), will always be the address of the next pointer in the last node added.

我希望这能给你一些想法.值得注意的是，将这两个指针(head 指针和ptr 指针)配对成它们自己的结构并具有相应的管理函数定义了教科书队列;其中一端仅用于插入(ptr)，一端用于提取(head)，容器不允许随机访问.如今，使用标准库容器适配器(例如 std::queue<>，但它确实提供了一个有趣的冒险，可以很好地使用指针到指针的概念.

#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