C ++中的链接列表 [英] Linked lists in C++

查看：196
本文介绍了C ++中的链接列表的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我想教自己链接列表与节点结构，并希望有人可以帮助我这个。



例如：











b

输入：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  - >空值。


解决方案

首先， typedef你似乎想要，有很多方法这样做。 

  //将NodePtr声明为指向Node的指针，目前是一个不完整的类型
 // C和C ++都允许你声明一个指向dam-near的任何东西
 //的指针，只要有一个理解它的*将*，在
 //情况下，一个结构称为Node。 
 typedef struct Node * NodePtr; 
 
 //现在声明结构类型本身
 struct Node 
 {
 int x; 
 NodePtr next; 
};

说实话，不建议这样做。大多数工程师想要一个清除和语法可见的定义，向他们尖叫，这是一个指针！你可能不同。我，个人只会更喜欢这个：

  struct Node 
 {
 int x; 
 struct Node * next; //为C ++省略'struct' - 只使用
};

只要您同样重要， ，了解您对 NodePtr 作为指针节点的使用，然后在您的情况下使用最有效的方法。指针类型声明是一些接近宗教的，所以只要记住这一点。有些人更喜欢看到这些星号（我是一个），有些可能不会（听起来像你 = P）。



注意： >一个，使用 typedef ed指针类型可以有助于避免潜在错误：多个变量声明。考虑这个：

  Node * a，b; //声明一个Node *（a）和一个节点（b）

$ c> typedef struct Node * NodePtr; 允许这样：

  NodePtr a，b; //声明两个Node *; （a）和（b）

如果你花了足够的时间在C中写代码，





加载循环



有关将列表拼接在一起的加载循环，您无法正确布线您的列表，坦率地说是一个百万的方法来做，一个是下面的一个。这不要要求您清除额外的节点。也不需要任何 if（head）{} else {} 块结构，以避免所述相同的条件。考虑我们真正想做什么：创建节点并将它们的地址分配给正确的指针：

  NodePtr head = NULL; //总是列表的头。 
 NodePtr * ptr =& head; //将总是指向要分配的下一个指针。 
 int n; 
 while（cin>> n）
 {
 * ptr = new Node; 
（* ptr） - > x = n; 
 ptr =&（* ptr） - > next; 
} 
 
 //注意这总是用NULL尾端来终止加载。 
（* ptr） - > next = NULL;





工作原理


  1. 将头指针初始化为NULL

  2. 初始化节点指针指针）指向头指针。这个指针到指针将总是保存要接收下一个动态分配节点的地址的目标指针的地址。最初，这将是头指针。在上面的代码中，这个指针指针是变量： ptr 。

  3. 开始while循环。对于每个读取的值，分配一个新的节点，保存在 ptr 指向的指针中（因此 * ptr ）。在第一次迭代时，它保存头指针的地址，因此 head 变量将获得我们的新节点分配。在所有后续迭代中，它包含所插入的最后一个节点的下指针的地址。顺便说一下，保存这个新目标指针的地址是在我们转到下一个分配周期之前在循环中完成的最后一个事情。

  4. 完成后，插入的最后一个节点需要将其下一个指针设置为NULL，以确保正确终止的链表。 这是必须的。我们方便地有一个指向该指针的指针（我们一直使用的同一个指针），因此我们将指针指向设置为NULL。我们的列表终止，我们的负载完成。 Brain Food：如果加载循环从未加载任何节点，它将指向 什么指针？回答：& head ，如果我们的列表是空的，这正是我们想要的（一个 NULL 头指针）





设计

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



初始配置

  head ===>空值; 
 ptr  -  ^

一次迭代后：

  head ===>节点（1）
 next 
 ptr ------ ^

两次迭代后

  head ===> node（1）
 next ===> node（2）
 next 
 ptr ---------------- ^

三次迭代后

  head ===> node（1）
 next ===> node（2）
 next ===> node（3）
 next 
 ptr -------------------------- ^ 
  * ptr = NULL;   
 
 $ b < ），给出：
  head ===> node（1）
 next ===> node（2）
 next ===> node（3）
 next ===>空值; 
 ptr -------------------------- ^ 
  
请注意，第一次迭代完成后， head 不会改变（它总是指向第一个节点）。还要注意， ptr 始终保存要填充的下一个指针的地址，在初始迭代（其开始作为头指针的地址）之后，始终是添加的最后一个节点中下一个指针的地址。
 
 
 
 I希望给你一些想法。值得注意的是，将这两个指针（ head 指针和 ptr 指针）配对到自己的结构中，适当的管理功能定义教科书 队列 ;其中一端仅用于插入（ ptr ）一个用于提取（ head ），容器会执行不是允许随机访问。这些日子对于标准库容器适配器，如  std :: queue<>  ，但它确实提供了一个有趣的冒险，可以很好地利用指针到指针的概念。
 
 
 
 
 
 
 完成工作示例 
 
 
 
 20个元素，打印它们，然后清除队列并退出。根据需要调整您的使用（提示：例如可能更改传入数据的来源）
  #include< iostream& 
 using namespace std; 
 
 //将NodePtr声明为指向Node的指针，目前是一个不完整的类型
 // C和C ++都允许你声明一个指向dam-near的任何东西
 //的指针只要有一个理解什么是*将*，在这
 //情况下，一个称为节点的结构。 
 typedef struct Node * NodePtr; 
 
 //现在声明结构类型本身
 struct Node 
 {
 int x; 
 NodePtr next; 
}; 
 
 int main（）
 {
 //加载包含20个元素的列表
 NodePtr head = NULL; 
 NodePtr * ptr =& head; 
 for（int n = 1; n <= 20; ++ n）
 {
 * ptr = new Node; 
（* ptr） - > x = n; 
 ptr =&（* ptr） - > next; 
} 
 
 //终止该列表。 
 * ptr = NULL; 
 
 //遍历列表，打印每个元素
 NodePtr p = head; 
 while（p）
 {
 cout<< p  - > x< ''; 
 p = p-> next; 
} 
 cout<< endl; 
 
 //释放列表
 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 
  
 
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.



Example:



Input: "1 2 3 4 5" 

Output:"1 2 3 4 5"



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?



EDIT: I have changed this to typedef struct Node* NodePtr;



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.



 解决方案 
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
};

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).



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)

Having a typedef struct Node *NodePtr; allows this:
NodePtr a, b;   // declares two Node*; both (a) and (b)

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.






The Load Loop



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;







How It Works
    

  1. Initialize the head pointer to NULL
    2. 

  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. 

  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. 

  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.
    5. 







Design



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



Initial configuration
      head ===> NULL;
ptr --^

After one iteration:
head ===> node(1)
          next
ptr ------^

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

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

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 --------------------------^

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.



I hope that gives you some ideas. It is worth noting that pairing these two pointers (the head pointer and the ptr pointer) into their own structure and having the appropriate management functions defines the textbook Queue; where one end is only for insertions (ptr) one is for extractions (head) and the container does not allow random access. There isn't much need for such a thing these days with the standard library container adapters like std::queue<>, but it does provide an interesting adventure into a good use of pointer-to-pointer concepts.






Complete Working Sample



This sample just loads our queue with 20 elements, prints them, then cleans out the queue and exits. Adapt to your usage as needed (hint: like change the source of the incoming data perhaps)
#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;
}

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



                        
这篇关于C ++中的链接列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
相关文章
C/C++开发最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆