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