20

次のコードは、 head がパラメーターとして送信されると正常に機能します。私は C に慣れていないので、それがどのように機能するのか理解できませんでした。助けてください。

struct node *recursiveReverseLL(struct node *list)
{
    struct node *revHead;
    if (list == NULL || list->link == NULL)
    {
        return list;
    }

    revHead = recursiveReverseLL(list->link);
    list->link->link = list;
    list->link = NULL; 

    return revHead;
}

これらの再帰呼び出しを使用してリンクがどのように提供されるかはわかりません。ie) リンクが次のようである場合、

1 -> 2 -> 3 -> 4

次に、どのように変更されますか、

4 -> 3 -> 2 -> 1
4

9 に答える 9

68

このための一般的な再帰アルゴリズムは次のとおりです。

  1. Divideリストの2一部 - 最初のノードと残りのリスト。
  2. restリンクされたリストのに対して reverse を再帰的に呼び出します。
  3. にリンクrestしfirstます。
  4. headポインタを修正

インラインコメント付きのコードは次のとおりです。

struct node* recursiveReverseLL(struct node* first){

   if(first == NULL) return NULL; // list does not exist.

   if(first->link == NULL) return first; // list with only one node.

   struct node* rest = recursiveReverseLL(first->link); // recursive call on rest.

   first->link->link = first; // make first; link to the last node in the reversed rest.

   first->link = NULL; // since first is the new last, make its link NULL.

   return rest; // rest now points to the head of the reversed list.
}

この写真が物事をより明確にすることを願っています：

画像
(ソース: geeksforgeeks.org )
.

于 2012-12-29T10:35:48.160 に答える
6

代替ソリューション:

struct node *head;
void reverse(struct node *prev, struct node *cur)
{
   if(cur){
      reverse(cur,cur->link);
      cur->link = prev;
    }
    else{
      head = prev;
    }
}

main では、reverse(NULL,head) を呼び出します。

于 2016-01-08T05:56:38.093 に答える
2

別の解決策：

struct node *reverse_recur(struct node *temp)
{
    if(temp->link==NULL)
    {
        return temp;
    }

    struct node *temp1=temp->link;

    temp->link=NULL;

    return (reverse_recur(temp1)->link=temp);

}
于 2014-07-19T04:44:37.837 に答える
2

リンクされたリストを 1-> 2 -> 3 ->4 とします。

cの関数は--

struct linked_node * reverse_recursive(struct linked_node * head)
{
struct linked_node * first;/*stores the address of first node of the linked
list passed to function*/
struct linked_node * second;/* stores the address of second node of the
linked list passed to function*/
struct linked_node * rev_head;/*stores the address of last node of initial 
linked list. It also becomes the head of the reversed linked list.*/
//initalizing first and second
first=head;
second=head->next;
//if the linked list is empty then returns null
if(first=NULL)
   return(NULL);
/* if the linked list passed to function contains just 1 element, then pass
address of that element*/
if(second==NULL)
   return(first);
/*In the linked list passed to function, make the next of first element 
 NULL. It will eventually (after all the recursive calls ) make the
 next of first element of the initial linked list NULL.*/
first->next=NULL;
/* storing the address of the reverse head which will be passed to it by the
 condition if(second==NULL) hence it will store the address of last element
 when this statement is executed for the last time. Also here we assume that 
the reverse function will yield the reverse of the rest of the linked 
list.*/
rev_head=reverse(second);
/*making the rest of the linked list point to the first element. i.e. 
 reversing the list.*/
second->next=first;

/*returning the reverse head (address of last element of initial linked 
list) . This condition executes only if the initial list is 1- not empty 
2- contains more than one element. So it just relays the value of last 
element to higher recursive calls.  */
return(rev_head);
}

リンクされたリスト 1-> 2-> 3 -> 4 の関数を実行中

  • reverse(&1) 内では、コードは rev_head=reverse(&2); まで実行されます。// ここで &1 は 1 のアドレスです。

関数のリストは
1(最初)->2(2番目) -> 3 -> 4

  • reverse(&2) 内のコードは rev_head=reverse(&3); まで実行されます。関数のリスト
    2(最初)->3 (2番目)-> 4

  • reverse(&3) 内のコードは rev_head=reverse (&4); まで実行されます。関数
    3(1 つ目)-> 4 (2 つ目)の場合のリスト

  • reverse(&4) 終了条件の中で second==NULL が真なので return を実行して 4 のアドレスを返します。

機能一覧

4(1番目)-> NULL(2番目)

  • back to reverse(&3) 関数のリストは
    NULL<-3 (最初) 4 (2番目)
    で、返された rev_head=&4 の値

second->next=first; を実行した後。リストになります

NULL<- 3(1 回目) <-4 (2 回目)

戻ります (rev_head ); rev_head=&4 であるため、&4 を渡すと実行されます

  • rev(&2)に戻る

関数内のリストは

NULL<-2(最初) 3(秒)<-4

rev_head は rev(&3) によって返された &4 です。

second->next=first を実行すると、リストは次のようになります

NULL<-2(1 回目)<-3(2 回目)<-4

戻ります (rev_head); &4 を rev(&1) に返すが実行されます。

  • rev(&1)に戻る

関数内のリストは

NULL<-1(最初) 2(秒)<-3<-4

rev_head の値は、reverse(&3) によって渡された &4 です。

今 second->next =first が実行され、リストは次のようになります

NULL<-1(1 回目) <- 2(2 回目)<-3<-4

戻ります (rev_head); が実行されます // rev_head=&4 は reverse(&2) によって返され、rev_head の値がメイン関数に渡されます。

お役に立てれば。これを理解し、この回答を書くのにもかなりの時間がかかりました。

于 2017-03-21T03:14:59.443 に答える