[C] Invertire i valori all'interno di una lista

[^EvAmPiReS^]

Ciao, ci ho pensato per diverso tempo ma non mi viene propio in mente come realizzare una funzione che inverta i valori(es. 1-2-3-4, 4-3-2-1) all'interno di una lista con i nodi siffatti:

struct cella {

int valore;

struct cella *next;

}

Non mi interessa il codice (mi serve per esercitarmi), ma vorrei sapere a livello concettuale come devo gestire i puntatori...ho provato a mantenere un puntatore all'elemento successivo ed uno al precedente, ma a mio avviso non sono sufficienti, non mi viene in mente come risalire la lista dal fondo (con un puntatore) visto che in questo tipo di lista inserisco gli elementi in testa ed ho solo un puntatore a next...uffi!

Grazie per ogni suggerimento penso che sia una cosa "banale" ma proprio non mi viene.

[^EvAmPiReS^]

up

[Dr_House]

Ti rispondo in termini concettuali senza pensare minimamente al codice come hai chiesto tu.

Tu vuoi realizzare da quel che ho potuto capire, una lista bidirezionale, allora, se vuoi effettuare l'inserimento in testa soltanto, devi ricordarti di inserire due puntatori comunque.

facciamo vari casi:

1.La lista è vuote
Vai ad inserire un elemento nella lista quindi dovrai ricordarti che, essendo il primo, next non punterà a nulla dato che non c'è nulla dopo di lui, ugualmente prew. Questo elemento lo chiameremo L1

2.Inderimento secondo elemento
Nella lista adesso supponiamo ci sia L1, tu adesso vai ad inserire L2. Om questo caso, L2 prima di lui non avrà nessuno, quindi il campo prew non deve puntare a nulla, mentre il campo next deve puntare ad L1.
Ugualmente L1 precedentemente non aveva nessuno prima di lui, adesso ha L2, quindi L1.prew deve indicare L2.

3,Caso iterativo
Un generico elemento L(n+1) avrà il campo next che punta all'elemento L(N) primo nella lista ed L(n) all'inserimento di un nuovo elemento avrà un elemento L(n+1) a cui puntare il campo prew

[LeleFT]

La puoi pensare in modo ricorsivo, che viene più facile.
Hai 1 caso base e un passo induttivo:

1) Caso base: ho un solo elemento -> Ho finito
2) Passo induttivo: ho N+1 elementi -> Applico l'ipotesi induttiva sui primi N elementi e attacco in testa l'ultimo elemento.


Ciao.

[^EvAmPiReS^]

Grazie per la risposta ma mi sa che senza codice non riesco a spiegarmi

La versione ricorsiva mi è venuta (ed è più facile):

void invertiListaricorsiva (struct cella **t)  //inversione della lista ricorsiva

{

	struct cella *paux;

	if ((*t)->next !=NULL)
	{
		paux = *t;

		*t = (*t)->next;

		invertiListaricorsiva(t);

		paux->next->next = paux;

		paux->next = NULL;

	}


}

Il fatto è che la versione ricorsiva comincia a risolvere le istanze della funzione madre che le ha create dall'ultima (quindi dalla fine della coda fino alla testa) cosa non valida per la versione iterativa in cui devo cominciare a fare le modifiche dalla testa.
Ho pensato di introdurre due puntatori ausiliari:
- paux1 sostituisce ciò che è puntato dalla testa
- paux1->next = testa
- paux1->next->next = paux2

In modo da avere uno schema del tipo:


testa->struct1.next->struct2.next->struct3.next->NULL

Da qui in poi ho perso ore pensando a come ribaltare questa lista :master:



P.S. Non voglio mantenere una lista doppiamente linkata in cui ogni struct ha un puntatore alla struct precedente ed a quella successiva vorrei cavarmela con un solo puntatore a next per ogni casella...

[{Bl4d3}]

void inverti(struct cella **lista)
{
  struct cella *temp = *lista;
  struct cella *next = (*lista)->next;
  temp->next = NULL;
  struct cella *temp2 = temp;
  while (next != NULL)
  {
    temp = next;
    next = next->next;
    temp->next = temp2;
    temp2 = temp;
  }
  *lista = temp2;
}

non l'ho provata, vedi un pò se funziona...
(la lista passata inizialmente deve avere almeno un elemento)

[^EvAmPiReS^]

Funziona
Ancora sono in tempo a cambiare uni