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

関数の最後の桁(9)を出力する方法が思いつきませんprintList()。どうすればこれを達成できますか？私の 2 番目の質問は、再帰関数ではなく 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. 次に、この一時ノードに頭を設定します[1]-->[0] ; head = [1]

ですから、ここで何が起こっているかを見ることができます。頭はまだあるべきで[0]あり、その次はその逆であってはなり[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;
   }
}

質問等、お気軽にどうぞ。

于 2013-07-03T21:48:18.513 に答える
1

if (traverse->next == NULL)試す代わりにif (traverse == NULL)

このように、現在のノードがデータを含む実際のノードである場合は、現在のノードを出力します。その後、再帰します。最終的には、NULL簡単にエスケープできるポインターに再帰します。

于 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

2 番目の部分に対する答えとして、コードは次のようになります。

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

これはリストをループし、リストの終わりを示す NULL ノードに到達するまで各要素を出力します。これはかなり標準的な反復アルゴリズムです。

于 2013-07-03T14:05:18.667 に答える