6

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

例子：

输入：“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.
4

4 回答 4

9

首先，关于你的结构的声明和你似乎想要的指针 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）。

注意：有一个地方使用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。我们的列表已终止，我们的加载已完成。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 --------------------------^

如果我们在 3 次迭代中停止，最终的终止赋值 ( *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
于 2013-01-27T05:31:27.403 回答
3

您实际上并未将“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 以节省内存并避免打印出额外的值。

于 2013-01-27T04:58:20.327 回答
1

您没有连接列表。每个新项目都将为->nextNULL。

你说ptr = ptr->next（它是NULL）但是下一次迭代用新分配的节点覆盖ptr。您需要重新排列代码以将节点串在一起......

一种方法是ptr->next = head让你的新节点指向旧的头。然后head = ptr将头部移动到新节点。例如：

在开头插入（例如对于 LIFO，后进先出）：

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

在末尾插入（对于 FIFO）：

while (cin >> n){
    if(!head) {
        head = new Node;
        ptr = head;
    }
    else
    {
        ptr->next = new Node;
        ptr = ptr->next;
    }
    ptr->next = NULL;
    ptr->x = n;
}
于 2013-01-27T04:56:48.223 回答
1

首先，您的 typedef :typedef struct Node;不正确。您使用 sintaxe 声明一个结构：

struct st_Name{
    int field1;
    double field2;
};

typedef 就像一个名称归属函数。您应该（为了便于阅读/工作）更改结构的名称，这是可能的，在声明它之后，使用：

typedef struct Node_st Node;

或者，全部在一个声明中：

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

在上面的段中，请注意我也将 更改NodePtr为struct node_st *Next，原因是：如果你在一个段中完成所有操作，因为 c++ 代码是线性读取的 top->down(kinda)，如果你尝试在结构声明之前创建NodePtr一个指针Node你会得到一个错误，如果你稍后再做并NodePtr在结构中使用你也会有一个错误。编译器还不知道该结构存在，因此它会说您正在尝试命名不存在的东西。

然后，您的指针操作是错误的。

...
while (cin >> n){
    ptr = new Node;
    ptr->x = n;
    ptr->next = NULL;  // You're making the next slot inexistent/NULL
    ptr = ptr->next;   // You're just setting ptr to NULL
}
...

我认为您想要的是继续添加到末尾，将头部保持在第一个数字中。对于第一种情况，您可以简单地使用 if/else 语句来执行此操作：

 while (cin >> n){
     if(head == NULL){
        ptr = new Node;
        ptr->x = n;
        ptr->next = NULL;
        head = ptr;
     }else{ 
        ptr->next = new Node;
        ptr = ptr->next;
        ptr->x = n;
        ptr->next = NULL; 
     }
}

这样，您的插入最终会发生，因此您的打印循环应该可以工作。

希望这可以帮助。

于 2013-01-27T05:20:57.317 回答