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.

Answer 1

首先,关于结构的声明和你似乎想要的指针类型,有很多方法可以做到这一点.以下内容适用于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).

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

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.我们的列表已终止,我们的负载已完成.健脑食物:会是什么指针指向到如果负载循环永远不会加载任何节点？答案:如果列表为空&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