0

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

到目前为止,这是我所做的:

#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的输出

4

4 回答 4

4

这里有几件事:


您创建列表main()的方式不正确。画出你在做什么,你会发现你是列表中的最后一项,也就是说,它的值可能是 9。(在你调用 printList 之前打印出 head 的值来验证这一点)。head

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

当前状态:head=[0]

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

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

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


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

这是在遍历中打印链接的正确方法。这将按原样打印列表的元素。 当您检查 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;
   }
}

随时发布问题等。

于 2013-07-03T21:48:18.513 回答
1

Instead of if (traverse->next == NULL) try 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 NULL pointer, which you can easily escape.

于 2013-07-03T14:03:38.857 回答
0

你为什么不交换这些陈述?

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)
于 2013-07-03T14:05:10.560 回答
0

作为对第二部分的回答,您的代码可能如下所示:

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

这将遍历列表,打印每个元素,直到它到达一个 NULL 节点,这表示列表的结尾。这是一个非常标准的迭代算法。

于 2013-07-03T14:05:18.667 回答