按顺序遍历单个链表

Question

我一直在想一种遍历单个链表的方法。

这就是到目前为止我所做的：

#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;
}

我想不出打印printList()函数中最后一个数字（9）的方法。我怎样才能做到这一点？我的第二个问题是，如何在while循环中遍历相同的函数，而不是递归函数。

正如你们中的一些人之前试图回答的那样，我不想从9遍历到0，这应该从0遍历到9，你可以看到http://codepad.org/ynEdGc9S

Answer 1

这里有一些东西：

---

在main()中，创建列表的方式不正确。画出你正在做的事情，你会意识到你的head是列表中的最后一项，也就是说，它的值可能为9。（在调用printList进行验证之前，打印出打印头的值）。

让我用i=1:的迭代来解释（在你的代码中跟随）

当前状态：head=[0]

1. 分配一个新的临时节点[ ]
2. 然后将数据分配给它[1]
3. 然后将这个临时节点设置在头部[1]-->[0] ; head=[0]旁边
4. 然后将头设置到此临时节点[1]-->[0] ; head = [1]

所以，你可以看到这里发生了什么。头应该仍然是[0]，它的下一个应该是[1]，而不是相反。

你可以探索并思考正确的方法。

---

printList，这是打印递归堆栈，而不是遍历。Traversal会以相反的顺序打印它们，因为您的列表是以相反的次序打印的（请查看上一节^了解原因）。

这是在遍历中打印链接的正确方法。这将按列表中的元素的实际方式打印它们。当您检查遍历->next==NULL时，遍历保留了最后一个元素。由于您刚刚通过返回-1结束了递归，所以从未打印最后一个元素

int printList(node *traverse) {
   if (traverse == NULL) {  
       return -1;
    }
    cout << traverse->data << endl;
    printList(traverse->next);
    return 0;
}

---

迭代

int printList(node *traverse) {
   while(traverse != NULL) {  
    cout << traverse->data << endl;
    traverse = traverse->next;
   }
}

---

请随意发布问题等。

Answer 2

尝试if (traverse == NULL) 而不是if (traverse->next == NULL)

通过这种方式，如果当前节点是一个包含数据的实际节点，则打印该节点。然后递归。最终，在结束时，您将递归到一个NULL指针中，您可以轻松地对其进行转义。

Answer 3

作为第二部分的答案，您的代码可能如下所示：

void printList_iter(node* node)
{
    while (node)
    {
        cout << node->data << endl;
        node = node->next;
    }
}

这将在列表中循环，打印每个元素，直到它到达一个NULL节点，这表示列表的结束。这是一个非常标准的迭代算法。

Answer 4

为什么不交换这些语句？

traverse=traverse->next;
printList(traverse);
cout << traverse->data << endl;

应将其更改为：

cout << traverse->data << endl;
traverse=traverse->next;
printList(traverse);

这应该行得通。然后，更改

if(traverse->next==NULL)

至

if(traverse==NULL)