PDA

Visualizza la versione completa : [C++] Invertire i nodi di una lista in modo ricorsivo


Squall1988
05-11-2005, 21:43
Ho un simpatico problema: sto cercando disperatamente di invertire l'ordine dei nodi di una lista semplicemente concatenata, però non nel modo classico iterativo, bensì ricorsivo... Ci sto provando da un po' ma mi pare abbastanza infattibile.
Cosa ne pensate???

(3->5->9->2 deve diventare 3<-5<-9<-2)

oregon
05-11-2005, 21:49
Con quale codice ci stai provando ?

Squall1988
06-11-2005, 13:58
ah come codice sinceramente non riesco neanche a capire dove partire, è per quello che ho chiesto aiuto, anche come pensare ricorsivamente l'algoritmo mi pare quasi impossibile.

unomichisiada
06-11-2005, 14:14
Originariamente inviato da Squall1988
ah come codice sinceramente non riesco neanche a capire dove partire, è per quello che ho chiesto aiuto, anche come pensare ricorsivamente l'algoritmo mi pare quasi impossibile.
L'ultimo deve diventare il primo o cosa? Beh magari non è semplice ma impossibile forse è esagerato.

Squall1988
06-11-2005, 15:10
infatti ho detto quasi :fighet: :fighet:
comunque si, deve risultare invertita, ma non cambiando i dati ma i puntatori ai nodi successivi.

unomichisiada
06-11-2005, 16:27
Non era poi così difficile!!Il codice sensibile è nella funzione FlipList, il resto è brodo.


#include <stdio.h>
#include <stdlib.h>

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

typedef struct Node Node;
void * myalloc(int n);
Node *ListCreate(Node *head,int el); //inserisce in coda
Node* FlipList(Node *head,Node* prev);
void PrintList(Node *head);
int main()
{
Node *head = NULL;
int v[10]={8,-5,-7,2,0,6,33,5,-45,-12},i,n=10;
for(i=0;i<n;i++)
{
head=ListCreate(head,v[i]);
}

printf("\n\nLista : ");
PrintList(head);
printf("\n\nLista invertita: ");
head = FlipList(head,NULL);
PrintList(head);
fflush(stdin);
getchar();
return 0;
}

void * myalloc(int n)
{
void * p=malloc(n);
if(!p)
{
printf("Memoria insufficiente!!");
exit(1);
fflush(stdin);
getchar();
}
return p;
}

Node *ListCreate(Node *head,int el)
{
//inserisce in coda
Node * p=(Node*)myalloc(sizeof(Node)),*t;
p->el=el;
p->next=NULL;
t=head;
if(!t) return p;
while(t->next) t=t->next;
t->next=p;
return head;
}

void PrintList(Node *head)
{
while(head)
{
printf("%d ",head->el);
head=head->next;
}
}

//Come vedi non era impossibile!!!
Node* FlipList(Node *head,Node* prev)
{
Node *p;
if(!head)
{
return prev;
}
p = FlipList(head->next,head);
head->next = prev;
return p;
}
:ciauz:

unomichisiada
07-11-2005, 02:50
Mi sono accorto che avevi messo C++ nel titolo e che io ti ho dato una soluzione in c, scusa ma dalla richiesta ho dato invece per scontato il c. Comunque convertirlo è abbstanza semplice... :ciauz:

Squall1988
07-11-2005, 15:48
no cioè, sei un genio :yuppi: :yuppi: :yuppi: grazie mille :D :D

Loading