23: Liste – Nozioni utili (Riassunto)
Se volete sapere come funzionano le liste e quali sono le principali operazioni che si possono svolgere, vi rimando ai due articoli precendenti: 22 e 21. Qui invece vi propongo un riassunto/ “bigino” delle tipiche richieste o problemi che si possono presentare nell’utilizzare delle liste (le librerie e la dichiarazione di variabili è implicita). Sarà un articolo un po’ lungo, ma è per una questione di completezza. Ricordo comunque che ci sono mille modi diversi per soddisfare le richieste, quindi non è detto che se voi risolvete il problema in un’altra maniera sia sbagliato.
Definire una lista e un suo elemento
struct elem { //elemento di una lista int inf; //è un esempio, qui tutti i vari campi che voglio che l'elemento abbia struct elem *next; //mi serve per poter puntare a elemento successivo nella lista } typedef struct elem *Tipolista; //definisco con la typedef il tipo della lista Tipolista lista=NULL; //inizializzo la lista
Stampare una lista
void stampalista (Tipolista lista) //dichiarazione di funzione di stampa { if (lista==NULL) return; //se la lista è vuota non fare niente while (lista!= NULL) //finché non si arriva alla fine della lista { printf ("%d - - >", lista->valore); //stampa l'elemento lista=lista->next; //passa all'elemento successivo (è come se fosse un i++ dei cicli) } }
Inserire un elemento in testa a una lista
void inseriscitesta (Tipolista *lista) { Tipolista temp=malloc(sizeof (struct elem)); //alloco spazio per creare un nuovo elemento if (temp!=NULL) { //se ho creato l'elemento temp->info='Ciao' //qui inserisco tutti gli attributi che voglio che il mio elemento abbia temp->next=NULL); } else return; //se la malloc non è andata a buon fine mi fermo if (*lista==NULL) // se la lista è vuota { *lista=temp; return; } //do alla lista il nuovo (unico) elemento temp->next=*lista; //se la lista non è vuota con questi due passaggi... *lista=temp; //...attacco la lista dietro all'elemento creato }
Inserire un elemento in coda a una lista
void inseriscicoda (Tipolista *lista) { Tipolista temp=malloc(sizeof (struct elem)); //alloco spazio e creo il nuovo elemento if (temp!=NULL) {//se ho creato l'elemento temp->cazzi= mazzi; //metto tutti i campi e le caratteristiche che voglio che il mio elemento abbia temp->next=NULL; } else return; //se la malloc non è andata a buon fine mi fermo Tipolista iter=NULL; //mi servirà anche un altro elem di appoggio per scorrere la lista if(*lista==NULL) { //se la lista è vuota *lista=temp; return; } //inserisco il mio unico elemento iter=*lista; //se la lista non è vuota attacco l'elemento di supporto alla lista while (iter->next!=NULL) iter=iter->next; //scorro tutta la lista fino ad arrivare all'ultimo elemento iter->next=temp;//attacco il nuovo elemento in coda alla lista }
Ricerca di un elemento in una lista
Tipolista cercaelemento(Tipolista lista, char c) //c è il carattere cercato { Tipolista temp=NULL; //di supporto int i=0; while (lista!=NULL) //finché non si arriva alla fine della lista { if(lista->codice==c) { printf("Elemento trovato"); i++; /*se nel campo della lista che volevo trovo l'elemento che cercavo, allora faccio le istruzioni conseguenti al ritrovamento */ if (i==1) temp=lista; } //se ho trovato l'elemento che cercavo lo metto nella lista di supporto lista=lista->next; }//altrimenti continuo a scorrere la lista if(i==0) return NULL; // se i=0 vuol dire che non ho trovato quel che cercavo if(i!=0) return temp; // altrimenti temp contiene l'elemento cercato }
Eliminare un elemento di una lista
void (Tipolista *lista, char c) //voglio eliminare un determinato elemento che abbia codice c { Tipolista prec=NULL; //mi servirà di supporto per vedere qual è l'elemento precedente a quello puntato Tipolista temp=*lista; //faccio puntare temp al primo elemento della lista if (temp==NULL) return; //se la lista è vuota non faccio nulla; while (temp!=NULL) //se la lista non è vuota allora la scorro ed elimino tutti gli elementi avente codice c { if (temp->codice==c) //se trovo l'elemento che cerco { if (prec==NULL) //se l'elemento precedente a quello cercato è nullo, vuol dire che siamo in testa alla lista { *lista=temp->next; free(temp); //cancello l'elemento temp=*lista; } else //se non mi trovo in testa alla lista { prec->next=temp->next; free(temp); //cancello l'elemento temp=prec->next; } } else //se non trovo l'elemento { prec=temp; temp=temp->next; //scorro la lista } } //fine while }
Inserimento successivo a un elemento cercato
Tipolista inserimento(Tipolista nuovo, Tipolista lista, int elem) /*"elem" è l'elemento cercato, mentre "nuovo" è quello da inserire nella lista */ { Tipolista attuale=NULL; //sempre di supporto attuale=lista; //faccio puntare la lista attuale al primo elemento di lista if (attuale==NULL) return nuovo; // se la lista è vuota, avrò solo l'elemento nuovo //inutile che metta "else", se if è vero il return non permetterà che le successive righe vengano eseguite while (( attuale->next!=NULL) && (attuale->info!=elem)) /*finché non arrivo alla fine della lista o finché non trovo l'elemento*/ attuale=attuale->next; //scorro la lista //se non trovo "elem" all'interno della lista nuovo è inserito in coda nuovo->next=attuale->next; attuale->next=nuovo; return lista; //ritorno la nuova lista }
Inserimento prima di un elemento cercato
Tipolista inserimento (Tipolista nuovo, Tipolista lista, int elem) /*"nuovo" è l'elemento da inserire, "elem" è quello cercato nella lista*/ { Tipolista attuale, prec=NULL; attuale=lista; //attuale punta al primo elemento if (attuale==NULL) return nuovo; //se la lista è vuota, allora avrò solo il mio elemento "nuovo" else//se non è vuota, potrei omettere questo else e togliere le parentesi, se l'if precedente è vero //il return termina tutto e il resto non viene eseguito { while ((attuale!=NULL) && (attuale->info!=elem)) //finché non arrivo alla fine della lista o trovo l'elemento { prec=attuale; attuale=attuale->next;//scorro le liste (scorro attuale e muovo prec di conseguenza) } if (prec==NULL)//se siamo in testa alla lista { nuovo->next=lista; lista=nuovo; } else { //se non trovo l'elemento "elem" inserisco nuovo in coda nuovo->next=attuale; prec->next=nuovo; } } retutn lista; //ritorno la lista aggiornata }
Inserimento ordinato degli elementi
Tipolista insOrdinato (Tipolista nuovo, Tipolista lista) //nuovo è l'elemento da inserire, lista è la lista ordinata { Tipolista attuale, prec=NULL; attuale=lista; //attuale punta al primo elemento di lista while ((attuale !=NULL) && (attuale->info< nuovo-> info)) /* l'ordinamento avverà seconodo l'informazione del campo info delle nostre info. Eseguo il ciclo finché non arrivo alla fine della lista oppure l'info di attuale è minore di quella di nuovo... */ { prec=attuale; attuale=attuale->next; //..scorro la lista } if (prec==NULL) //se siamo in testa alla lista { nuovo->next=lista; lista=nuovo; } else //se non siamo in testa alla lista { nuovo->next=attuale; prec->next=nuovo; } return lista; //ritorno la lista modificata }
Inserire un elemento in una lista circolare (dinamica)
Tipolista Circ (Tipolista nuovo, Tipolista lista) { Tipolista temp=lista; if (temp==NULL) //se la lista è vuota { nuovo->next=nuovo; return nuovo;//la lista avrà un solo elemento } else //se la lista non è vuota { while (temp->next!=lista) temp=temp->next;//scorro lista fino alla fine //inserisco il nuovo elemento che punterà alla "testa" della nostra lista circolare temp->next=nuovo; nuovo->next=lista; } return lista; }
Ovviamente se avete dubbi o non vi è chiaro qualcosa, chiedete pure.
Commenti recenti