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.

Please follow and like us: