Strutture dati: Le liste

Le liste sono strutture dati che rappresentano un insieme finito ed ordinato di n oggetti dello stesso

tipo caratterizzate da due proprietà:

ciascun elemento della lista è contraddistinto da una posizione in base alla quale è possibile

– individuare relazioni di precedenza e di successione tra gli elementi;

la lista vuota è una lista che non presenta alcun elemento.

–

Possiamo avere due tipi di rappresentazione delle liste:

Liste concatenate: sono basate su puntatori ed allocazione dinamica della memoria, si utilizzano se

ci sono modifiche (inserimenti, cancellazioni) frequenti, ed ogni elemento della lista è una coppia

denominata Node = (Object, Node) , ovvero il tipo di dato che contiene ed il puntatore all'elemento

successivo.

Liste tramite array collegati: si basano su array monodimensionale e sono caratterizzate dalla

definizione della capacità massima, e comportano la gestione anche della lista libera, cioè

dell’insieme degli elementi dell’array che non vengono utilizzati .

Sulle liste possiamo eseguire varie operazioni tra cui inserimento in testa o in coda, ricerca di un

elemento, cancellazione di un elemento, ecc...

Liste concatenate

Ogni oggetto della lista è denominato nodo e contiene un informazione propria ed un puntatore

all'elemento successivo:

In C la lista viene è definita come una struttura del seguente tipo (che sarà la prima cosa da scrivere

nel codice prima del main):

#include <stdio.h>

struct nodo

{ datatype data; //elemento della lista (int,float,char, ecc...)

struct nodo *next; // puntatore all'elemento successivo

};

struct nodo *head=NULL; // la lista è vuota per cui il primo elemento non punta a nulla

Come però ogni cosa anche le liste hanno vantaggi e svantaggi, i vantaggi sono quelli di non dover

spostare elementi per inserimenti e cancellazioni perché basta modificare i riferimenti, non è

necessario un limite massimo di dimensioni della lista e quindi può essere gestita in modo che lo

spazio di memoria da essa occupata sia proporzionale al numero dei suoi elementi.

Di contro però le operazioni di accesso agli elementi sono costose perché bisogna scandire gli

elementi della lista che precedono quello voluto , in pratica per arrivare ad un elemento bisogna

passare per tutti gli altri.

Creazione di una lista:

Per prima cosa si crea una nuova lista che ha come elemento l'elemento da inserire:

struct nodo *crea_lista (datatype elem){ //datatype è fa riferimento a tipo di dato int,double,char,ecc

struct nodo* head;

head=(struct nodo*)malloc(sizeof(struct nodo));

// inseriamo i dati

head->data=elem;

head->next=NULL;

return head;

}

head è il primo elemento della lista quinti la testa e punta all'unico elemento inserito.

Ricerca di un elemento nella lista:

Per cercare un elemento bisogna solo scorrere la lista fino a quando non si trova oppure fino alla

alla fine:

struct nodo* Trova(struct nodo *head, datatype elem){

struct nodo *p;

p = head;

while ((p != NULL) && (p->data != elem)){

p = p->next;

}

return p;

}

Un idea per segnalare poi nel main() se si è trovato o no è creare un apposita struct nodo che

contenga l'elemento ritornato e poi vedere se era nella lista o meno.

Inserimento in testa:

Bisogna far puntare il puntatore alla testa della lista (head) all'elemento da inserire e si deve creare

un collegamento tra l'elemento inserito ed il resto della lista:

void InserisciTestaLista (struct nodo **head, datatype elem){

struct nodo *p;

p= (struct nodo *) malloc(sizeof(struct nodo));

p->data = elem;

p->next = *head;

*head = p;

}

Inserimento in coda:

Bisogna scorrere tutta la lista fino a quando non si trova l'ultimo elemento (campo next

dell'elemento uguale a NULL) e quindi si procede all'inserimento del nuovo elemento.

Se la lista è vuota inseriamo semplicemente un elemento che sarà l'unico e perciò coincide con la

testa della lista.

void InserisciCodaLista (struct nodo **head, datatype elem){

struct nodo *temp; /* puntatore usato per la scansione */

struct nodo *p; /* creazione del nuovo nodo */

p = (struct nodo *) malloc(sizeof(struct nodo));

p->data = elem;

p->next = NULL;

if(*head==NULL){ /* la lista è vuota */

*head=p;

return;

}

/* scansione della lista */

temp = *head;

while (temp->next != NULL)

temp = temp->next;

temp->next = p;

}

Inserimento ordinato:

Si scorre tutta la lista fino a quando non si trova un elemento maggiore di quello da inserire o non si

arriva alla fine della lista e quindi si effettua l’inserimento. E' necessario memorizzare un puntatore

all'elemento corrente ed uno all'elemento precedente.

Ovviamente l'elemento più grande va inserito in testa e quello più piccolo in coda quindi vale

quanto detto precedentemente.

void InserisciOrdinato (struct nodo **head, datatype elem){

struct nodo *p; /*elemento da inserire*/

struct nodo *r = *head, *q = *head; /* predecessore e successore */

p = (struct nodo *) malloc(sizeof(struct nodo));

p->data = elem;

while ((q != NULL) && (q->data < p->data)){ /* trova il punto di

inserimento */

r = q;

q = q->next;

}

if(q==*head)

/* inserimento in testa */

*head=p;

else r->next = p; //inserimento in coda

p->next = q;

//fuori dall'if

}

Cancellazione di un elemento:

Si scorre tutta la lista fino a quando non si trova l'elemento da cancellare o non si arriva alla fine

della lista. E' necessario memorizzare un puntatore all'elemento corrente ed uno all'elemento

precedente. Se l'elemento da cancellare è il primo non c'è bisogno di scorrere la lista mentre se

l'elemento non esiste non si effettua nessuna operazione.