C++ 按顺序遍历单个链表
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/17450085/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Traversing a single linked list in order
提问by Sarp Kaya
I have been trying to think a way to traverse a single linked list.
我一直在想办法遍历单个链表。
This is so far what I have done:
到目前为止，这是我所做的：
#include <iostream>
typedef struct node {
int data; // will store information
node *next; // the reference to the next node
};
int printList(node *traverse) {
if (traverse->next == NULL) {
return -1;
}
traverse=traverse->next;
printList(traverse);
cout << traverse->data << endl;
return 0;
}
int main() {
node *head = NULL;
for (int i = 0; i < 10; i++) {
node *newEntry = new node;
newEntry->data = i;
newEntry->next = head;
head = newEntry;
}
printList(head);
return 0;
}
I cannot think a way to print the last digit(9) in printList()function. How would I be able to achieve this?
My second question is, how can I traverse the same in a while loop rather than a recursive function.
我想不出在printList()函数中打印最后一位数字 (9) 的方法。我将如何能够实现这一目标？我的第二个问题是，如何在 while 循环而不是递归函数中遍历相同的函数。
As some of you tried to answer before, I am not looking to traverse this from 9 to 0, This should traverse from 0 to 9, you can see the output from http://codepad.org/ynEdGc9S
正如你们中的一些人之前试图回答的那样，我不想从 9 到 0 遍历这个，这应该从 0 到 9 遍历，您可以从http://codepad.org/ynEdGc9S看到输出
回答by
There are a few things here:
这里有几件事：
In main()the way you are creating the listis incorrect. Draw what you're doing, you'll realize that your headis the last item in the list, i.e., it will probably have a value of 9. (Print out head's value just before you call printList to verify this).
在main()将要创建的列表的方式不正确。画出你正在做的事情，你会意识到你head是列表中的最后一项，也就是说，它的值可能是 9。（在你调用 printList 之前打印出 head 的值来验证这一点）。
Let me explain (follow along in your code) with iteration of i = 1:
让我用 i = 1 的迭代来解释（跟随你的代码）：
Current state: head=[0]
当前状态： head=[0]
- A new temporary node is allocated
[ ] - Then you assign data to it
[1] - Then you set this temporary node's next to your head
[1]-->[0] ; head=[0] - Then you set head to this temporary node
[1]-->[0] ; head = [1]
- 分配了一个新的临时节点
[ ] - 然后你给它分配数据
[1] - 然后你把这个临时节点放在你的头旁边
[1]-->[0] ; head=[0] - 然后你设置 head 到这个临时节点
[1]-->[0] ; head = [1]
So, you can see what's happening here. Head should still be [0]and its next should be [1]not the other way around.
所以，你可以看到这里发生了什么。头应该仍然是[0]，它的下一个应该[1]不是相反。
You can explore and think about the correct way of doing this.
您可以探索并思考正确的方法。
printList, this is printing out the recursive stack and not the traversal. Traversal would print them in reverse order because your list is in the reverse order (check the previous section ^ for why).
printList，这是打印出递归堆栈而不是遍历。Traversal 会以相反的顺序打印它们，因为您的列表是相反的顺序（检查上一节 ^ 了解原因）。
This is the correct way to print the link in a traversal. This will print the elements of the list in the way they are. When you checked for traverse->next==NULL, traverse held the last element. Since you just ended the recursion by returned -1, the last element was never printed.
这是在遍历中打印链接的正确方法。这将按原样打印列表中的元素。 当您检查 traverse->next==NULL 时，traverse 保存了最后一个元素。由于您刚刚通过返回 -1 结束了递归，因此从未打印过最后一个元素。
int printList(node *traverse) {
if (traverse == NULL) {
return -1;
}
cout << traverse->data << endl;
printList(traverse->next);
return 0;
}
Iterative
迭代
int printList(node *traverse) {
while(traverse != NULL) {
cout << traverse->data << endl;
traverse = traverse->next;
}
}
Feel free to post questions, etc.
随意发布问题等。
回答by Chris
Instead of if (traverse->next == NULL)try if (traverse == NULL)
而不是if (traverse->next == NULL)尝试if (traverse == NULL)
This way, you print the current node if it's an actual node with data in it. You then recurse. Ultimately, at the end you will recurse into a NULLpointer, which you can easily escape.
这样，如果当前节点是包含数据的实际节点，则打印当前节点。然后你递归。最终，最后您将递归为一个NULL指针，您可以轻松地将其转义。
回答by Aswin Murugesh
Why don't you interchange these statements?
你为什么不交换这些陈述？
traverse=traverse->next;
printList(traverse);
cout << traverse->data << endl;
This should be changed to:
这应该改为：
cout << traverse->data << endl;
traverse=traverse->next;
printList(traverse);
This should work. And then, change
这应该有效。然后，改变
if(traverse->next==NULL)
to
到
if(traverse==NULL)
回答by feralin
As an answer to the second part, your code could look like this:
作为第二部分的答案，您的代码可能如下所示：
void printList_iter(node* node)
{
while (node)
{
cout << node->data << endl;
node = node->next;
}
}
This will loop through the list, printing each element until it gets to a NULL node, which signifies the end of the list. It's a pretty standard iteration algorithm.
这将遍历列表，打印每个元素，直到它到达一个 NULL 节点，这表示列表的结尾。这是一个非常标准的迭代算法。
