2

私の再帰スキルはかなり錆びています。私はこの問題について考えていて、長い間フォーラムを検索しましたが、まだ理解できません。今、私はスタンフォード CS ed ライブラリからリンクされたリスト コードを再帰的に逆に見ています。

#include <stdio.h> 

struct Node {
  int x;
  struct Node *next;
};

void Reverse(struct Node ** headRef){
    struct Node* first;
    struct Node* rest;

    if(*headRef==NULL)
       return;

    first= *headRef;
    rest= first->next;  

    if(rest==NULL)
        return; 

    Reverse(&rest);
    printf("Rest%d\n", (rest)->x); // I added this line to print rest
    first->next->next=first;
    first->next=NULL;
    *headRef=rest;
}

void printList(struct Node* head){

    if(!head)
       return;
    else{
       printf("%d ", head->x);
       printList(head->next);   
    }
}

void main(){
    struct Node *head;
    struct Node * node1= (struct Node*) malloc(sizeof(struct Node));
    struct Node * node2= (struct Node*) malloc(sizeof(struct Node));
    struct Node * node3= (struct Node*) malloc(sizeof(struct Node));
    struct Node * node4= (struct Node*) malloc(sizeof(struct Node));
    head= node1;
    node1->next=node2;
    node1->x=1;
    node2->x=2;
    node3->x=3;
    node4->x=4;
    node2->next=node3;
    node3->next=node4;
    node4->next=NULL;
    Reverse(&head);
}

ここで、リンクされたリスト 1->2->3->4 があるとします。私が理解できないのは、最終的に headRef を 4 に設定する最後の行です。headRef を 2 に設定する必要があると思います。関数を実行しようとすると、次のように出力されました。

4
4
4

変数残りの場合。

ただし、Reverse 関数の最後の行をコメントアウトすると、リストは逆になりますが、出力されます。

4
3
2.

2 番目の結果は理解できますが、最初の結果はかなり混乱しているように見えました。「*headRef=rest」というステートメントは、変数 rest に対して何かを行いますか? 4 を指し続けるのは何ですか?

また、**headRef の代わりに *headRef を渡すと (最後の行はコメントアウトされていません)、結果が出力されます。

4
3
2

それも。

誰かが記憶の中で何が起こったのか説明してもらえますか? どうもありがとう。

4

2 に答える 2

2

再帰呼び出しの前に、次のようReverseになります。

first---|  
        |  
        v  
        1->2->3->4->NULL
           ^
           |
           |
  rest------

の再帰呼び出しの後、次のようReverseになります。

first---|
        |
        v
        1->2<-3<-4
           |     ^
           v     |
         NULL    |
  rest------------

次に、で修正する必要が2->NULLあり2->1ますfirst->next->next=first。

first---|
        |
        v
        1<-2<-3<-4
        |  ^     ^
        |--|     |
                 |
  rest------------

次に、で修正する必要が1->2あり1->NULLますfirst->next=NULL。

first---|
        |
        v
  NULL<-1<-2<-3<-4
                 ^
                 |
                 |
  rest------------

最後に 、ではなくを指すよう*headRef=restになります。*headRef41

于 2012-09-01T20:05:17.243 に答える
0

ここで何が起こるかというと、再帰呼び出しが残りのアドレスをローカル変数 headRefに渡すためです。各再帰呼び出しが戻ると、ステートメント *headRef=rest は、実行フローで次に来るステートメントの残りポインターのアドレスを既に変更しています。

リンクされたリスト 1->2->3->4 の場合:

100番地に1、200番地に2、300番地に3、400番地に4が格納されているとします。

パート 1: Reverse(&rest) の呼び出し [rest はアドレス 400 を指す]

最初 = 400 残り = NULL

rest は NULL であるため、実行は Reverse(400) 呼び出しの後にポイントに戻ります

パート 2: ここでは、first->next->next=first および first->next=NULL の実行後、first = 300 および rest = 400 です

*headRef=rest [残りは 400 を指します]

しかし、この headRef には、rest=300 のアドレスが渡されました。実行の次のステップでは、rest は 400 を指しています。

パート 3: 実行は Reverse(300) 呼び出しの後にポイントに戻ります

ただし、フォワード コール中 [最初は 200、レストは 300] とリターン中 [レスト = 400] です。ここにトリックがあります!!!

first->next->next=first および first->next=NULL の実行後

*headRef=rest [残りは 400 を指します]

しかし、この headRef には、rest=200 のアドレスが渡されました。実行の次のステップでは、rest は 400 を指しています。

パート 4: 実行は Reverse(200) 呼び出しの後にポイントに戻ります

ただし、転送呼び出し中 [最初は 100、残りは 200] と戻り中 [残り = 400] です。

first->next->next=first および first->next=NULL の実行後

*headRef=rest [残りは 400 を指します]

これは最初の呼び出しであるため、関数は 400 の値を持つ *headRef を返します。

ジョブ完了！

于 2014-09-22T20:51:17.610 に答える