[C] Chiarimento liste concatenate

[Capua]

Qualcuno può commentarmi questo esercizio riga per riga in cui creo una lista concatenata in cui gli elementi sono dati in input fino all'inserimento di 9999? Vorrei cercare di capire meglio l'esercizio visto che non è completamente opera mia...Vi ringrazio anticipatamente..

/* STRUTTURA GLOBALE */

typedef struct lista {
int val;
struct lista *next;
} LISTA;


/* FUNZIONE MAIN */

int main (void){

LISTA *testa,*nuovo,*coda;

testa=NULL;
int elemento;

while (elemento!=9999){
printf("inserisci elemento, (9999 per terminare) " );
scanf("%d",&elemento);

if (elemento!=9999){

/* CREAZIONE LISTA */

nuovo=(LISTA*)malloc (sizeof(LISTA));
nuovo->val=elemento;
if(testa==NULL){

testa=nuovo;
nuovo->next=NULL;
coda=nuovo;
}

else {
nuovo->next=NULL;
coda->next=nuovo;
coda=nuovo;

}
}
}

printf("gli elementi dati in input sono: ");
stampa_lista(testa);
printf("\n");

return 0;
}

[sottovento]

typedef struct lista {
int val;
struct lista *next;
} LISTA;

Qui dichiari il tipo LISTA, il quale e' adatto a contenere un valore intero e ad avere un puntatore ad un eventuale elemento successivo, il quale e' dello stesso tipo.
Come avrai ben capito, questa struttura si utilizza quando non sai a priori il numero di elementi che puoi avere. Ovviamente ha vantaggi e svantaggi, non e' questa la sede.
In generale, per utilizzare una struttura del genere, avrai bisogno di memorizzare il puntatore al primo elemento della lista. Da questo, poi, potrai facilmente scorrere tutta la lista seguendo i puntatori next.


LISTA *testa,*nuovo,*coda;

Eccoli qui! I nomi non sono stati scelti a caso. Anzi, sono ben scelti. Stando ai nomi, ti aspetterai che testa memorizzi sempre l'indirizzo del primo elemento della lista (i.e. quello da cui potrai sempre scandire tutta la lista seguendo i next).
Potrai gia' immaginare che nuovo sara' l'elemento nuovo che vuoi inserire nella lista, e coda sara' il puntatore all'ultimo elemento.
Perche' ti serve il puntatore all'ultimo elemento, visto che con il puntatore "testa" posso scandire tutta la lista? Evidentemente perche' il programma vorra' inserire i nuovi elementi in coda, e scandire tutte le volte la lista potrebbe essere piuttosto oneroso (devi sempre far passare tutti gli elementi....). Meglio ricordarsi qual e' l'ultimo elemento, no?


testa=NULL;

All'inizio la lista e' vuota, ed il puntatore alla testa e' ovviamente NULL.


while (elemento!=9999){
printf("inserisci elemento, (9999 per terminare) " );
scanf("%d",&elemento);

Qui possiamo vedere il primo errore. Il programmatore aveva intenzione di fare un ciclo che fosse eseguito fintanto che elemento non assume il valore 9999. Prima di entrare in questo ciclo e' percio' necessario dare un valore ad elemento che sia diverso da 9999. Il programmatore se l'e' dimenticato. Siccome se non dai alcun valore il contenuto e' indeterminato (potrebbe esserci dentro qualsiasi cosa) c'e' buona probabilita' che non sia 9999, pertanto il programma SEMBRA funzionare correttamente.
Non funzionera' correttamente quando dovrai farlo vedere al cliente finale :D


if (elemento!=9999){

Certo, se elemento == 9999 non fai niente. Alla prossima iterazione, uscirai


nuovo=(LISTA*)malloc (sizeof(LISTA));
nuovo->val=elemento;

Qui possiamo vedere il secondo, subdolo, errore.
La malloc() ti alloca memoria dinamica. Signfica che, quando questa operazione si conclude con successo, la variabile nuovo assumera' un nuovo valore: puntera' ad un'area di memoria valida e sufficientemente grande per contenere il numero di bytes che hai specificato nel parametro.
Per esempio,

char *p;
p = (char *)malloc(3);

hai la certezza che, se l'operazione si conclude con successo, p conterra' l'indirizzo di un'area di memoria che puo' contenere almeno 3 byte.
La scrittura (LISTA *) oppure (char *) si chiama type cast ed e' una semplice conversione di tipo. Siccome la malloc() non puo' sapere come utilizzerai quella memoria, ti riporta un puntatore "neutro" (la maggior parte dei nuovi sistemi riporta un puntatore a void, quelli vecchi a char).
Con questo type cast semplicemente dici: "utilizzo questa memoria per puntare ad un tipo LISTA", che poi e' il tipo della variabile a cui assegni.

Si parlava di errore: infatti ho sempre detto "se l'operazione si conclude con successo". Nel caso non si concluda con successo, la malloc() ti riporta NULL, pertanto l'istruzione

nuovo->val=elemento;

mandera' in crash l'applicazione. Questo e' un "red-eyes crash", nel senso che spesso, nei programmi piuttosto grandi, ti obbliga a far la nottata a cercarlo.
Metti sempre il controllo: se non si riesce ad allocare memoria, piuttosto che niente, stampa un messaggio di errore ed esci.


if(testa==NULL){

testa=nuovo;
nuovo->next=NULL;
coda=nuovo;
}

OK! E' la prima volta che esegui il ciclo. La lista e' ancora vuota, pertanto l'elemento che hai inserito e' la testa della lista. testa (puntatore al primo elemento) pertanto ha lo stesso indirizzo del nuovo elemento (i.e. testa=nuovo).
D'altronde anche coda ha lo stesso indirizzo del nuovo elemento, in quanto la lista e' composta da un solo elemento (i.e. coda=nuovo).
L'elemento successivo? Non esiste, hai inserito un solo elemento, pertanto nuovo->next e' messo a NULL


else {
nuovo->next=NULL;
coda->next=nuovo;
coda=nuovo;

}

Abbiamo detto che si vuole inserire in coda. Questa e' la conferma. Siccome abbiamo visto che l'if stabilisce se stai inserendo il primo elemento, l'else significa che la tua lista ha almeno gia' un elemento. Esiste almeno la testa.
Quindi, siccome vogliamo inserire in coda, possiamo mettere:
- nuovo->next a NULL (e' l'ultimo, dietro di lui il vuoto);
- coda->next (cioe' quello che prima era l'ultimo elemento) ora punta a questo qui, appena inserito.
- coda = nuovo (questo e' il nuovo ultimo dei fratelli).

Scusa se sono stato prolisso

[Capua]

Grazie mille, me l'hai commentato alla perfezione! :D :D