Kthimi i një liste të lidhur në mënyrë rekursive në c

Algoritmi i përgjithshëm rekurziv për këtë është:

1. Divide lista në 2 pjesë - nyja e parë dhe pjesa tjetër e listës.
2. Thirrni në mënyrë rekursive reverse për rest të listës së lidhur.
3. Lidhni rest me first.
4. Rregulloni treguesin head

Këtu është kodi me komente inline:

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

Shpresoj që kjo foto t'i bëjë gjërat më të qarta:

_{(burimi: geeksforgeeks.org)}
.

Zgjidhja alternative:

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

Kryesisht, thirrni reverse (NULL, kokë);

Le të jetë lista e lidhur 1-> 2 -> 3 ->4

funksioni në c është--

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

tani ekzekuton funksionin për listën e lidhur 1-> 2-> 3 -> 4

• brenda reverse(&1) kodi funksionon derisa rev_head=reverse(&2); // këtu &1 është adresa e 1.

lista e funksionit është
1(i pari)->2(e dyta) -> 3 -> 4

• brenda kodit reverse(&2) ekzekutohet derisa rev_head=reverse(&3); lista e funksionit
  2(i pari)->3 (i dyti)-> 4

• kodi brenda reverse(&3) shkon derisa rev_head=reverse (&4); lista nëse funksioni
  3(i pari)-> 4 (i dyti)

• brenda kushtit përfundimtar reverse(&4) second==NULL është e vërtetë kështu që kthimi ekzekutohet dhe adresa e 4 kthehet.

lista e funksionit

4 (e para) -> NULL (e dyta)

• kthimi në listën reverse(&3) të funksionit është
  NULL‹-3(first) 4 (e dyta)
  dhe vlera e rev_head=&4 e cila u kthye

pas ekzekutimit second->next=first; lista bëhet

NULL‹- 3 (e para) ‹-4 (e dyta)

kthimi (rev_head); ekzekutohet i cili kalon &4 sepse rev_head=&4

• kthehu në kthim (&2)

lista në funksion është

NULL‹-2(e para) 3(e dyta)‹-4

dhe rev_head është &4 që u kthye nga rev(&3)

pas ekzekutimit second->next=first, lista bëhet

NULL‹-2(e para)‹-3(e dyta)‹-4

kthimi (rev_head); ekzekutohet i cili kthen &4 në rev(&1);

• kthehu në kthim (&1)

lista në funksion është

NULL‹-1(e para) 2(e dyta)‹-3‹-4

dhe vlera e rev_head është &4 e cila u kalua me reverse(&3)

tani second->next =first ekzekutohet dhe lista bëhet

NULL‹-1(e para) ‹- 2(e dyta)‹-3‹-4

kthimi (rev_head); ekzekutohet // rev_head=&4 i cili u kthye me reverse(&2) dhe vlera e rev_head i kalohet funksionit kryesor.

shpresoj se kjo ndihmon. M'u desh mjaft kohë për ta kuptuar këtë dhe gjithashtu për të shkruar këtë përgjigje.

Një zgjidhje tjetër:

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

}

Kjo është një qasje e bukur që mund të ndiqet për të kthyer SLL në mënyrë rekursive:

1.    struct node* head; // global head
2.    void rec_reverse(struct node* prev, struct node* cur)
3.    {
4.        if (cur)
5.        {
6.            rec_reverse(cur, cur->next);
7.            cur->next = prev;
8.        }
9.        else
10.            head = prev;
11.    }

Thirrni funksionin në këtë mënyrë:

rec_reverse(NULL, head);

Qasja:

• Duke thirrur funksionin në mënyrë rekursive (rreshti 6) shkojmë në nyjen e fundit të listës së lidhur.
• Më pas përditësojmë kokën me adresën e nyjës së fundit (rreshti 10).
• Së fundi, ne drejtojmë lidhjen e secilës nyje me nyjen e saj të mëparshme (rreshti 7).

Më duket se askush nuk ka sugjeruar një algoritëm që është rekurziv i bishtit. Në parim, një algoritëm rekurziv i bishtit mund të kompilohet pa një pirg (me kusht që përpiluesi të jetë mjaftueshëm i zgjuar), duke prodhuar kështu kodin që konsumon më pak memorie.

Supozoni se TList është një tip i personalizuar i të dhënave për listën me një lidhje të vetme, është një tregues drejt një strukture që si fushë link për të hyrë në elementin tjetër në listë.

Algoritmi është si më poshtë:

```

TList reverse_aux(TList l, TList solution) {
    if (l == NULL) {
        return solution;
    } else {
        TList tmp = l->link;
        l->link = solution;
        return reverse_aux(tmp, l);
    }
}

TList reverse(TList l) {
    return reverse_aux(l, NULL);
}

```

ll *rev_list(ll *prev, ll *cur)
{
    if (!cur) {
        return prev;
    }

    ll *tmp = cur;
    cur = cur->next;
    tmp->next = prev;
    prev = tmp;
    return rev_list(prev, cur);
}

Gjeni kodin e plotë: https://github.com/vijaythreadtemp/Data-Structures-And-Algorithms/blob/master/rev_link_list_rec.cxx