[C] stack con liste

[lucas87]

Scrivere una funzione che restituisca una nuova pila che contiene i valori di una pila in ingresso in ordine inverso. La pila originale non deve essere modificata.

Qualcuno di voi ha un idea di base su cui poi lavoro io di come non modificare lo stack iniziale?

Perchè passando i valori da una pila all'altra e man mano cancellare la pila iniziale funge, ma così modifico la pila iniziale e non devo farlo

grazie per l'aiuto

[cionci]

Sai il significato di visita anticipata e visita posticipata (di solito si applica agli alberi, ma può andare bene anche per le liste) ?

Qui hai due alternative:
- fai una visita anticipata della lista originale e crei quella nuova con l'inserimento in testa
- fai una visita posticipata della lista originale e crei quella nuova con l'inserimento in coda

[lucas87]

Mhh...mi dovresti spiegare questa faccenda della vista che non la conosco.

graize

[cionci]

Visita...non vista ;)
La visita è la valutazione del campo informazione del nodo...

Avendo una lista la classica struttura di una funzione ricorsiva che scorre la lista può assumere queste due forme:

funzione(lista l)
{
(condizione di arresto)
funzione(l->next);
(elaborazione del campo informazioni del nodo)
}


funzione(lista l)
{
(condizione di arresto)
(elaborazione del campo informazioni del nodo)
funzione(l->next);
}

La prima è una visita posticipata in quanto la valutazione del campo informazioni del nodo avviene a ritroso, cioè prima si arriva all'ultimo elemento della lista e poi si torna indietro valutando il campo informazioni partendo dall'ultimo.
La seconda è una visita anticipata in quanto si valuta prima il campo informazioni e poi si fa la ricorsione.

Se provi a sostituire (elaborazione del campo informazioni del nodo) con printf("%d\n", l->info); chiaramente nel primo caso verranno stampati gli interi a partire dall'ultimo, mentre nel secondo caso a partire dal primo.

Il modo più logico per gestire uno stack con le liste è fare in modo che push faccia un inserimento in testa e pop faccia un'estrazione dalla testa.

Quindi è chiaro che nella lista che rappresenta lo stack l'elemento che si trova in fondo dovrà essere rappresentato per primo nella lista risultante che dovrai produrre.