c++ - 按顺序遍历单链表

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 之前打印出 head 的值来验证这一点)。

让我用 i = 1 的迭代来解释(在你的代码中):

当前状态:head=[0]

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

所以，您可以看到这里发生了什么。 Head 应该仍然是 [0] 而它的 next 应该是 [1] 而不是相反。

您可以探索和思考这样做的正确方法。

---

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

这是在遍历中打印链接的正确方法。这将按原样打印列表的元素。当您检查 traverse->next==NULL 时，traverse 持有最后一个元素。由于您刚刚通过返回 -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;
   }
}

---

有问题可以留言等