Lezione XX             frames      noframes

 

Strutture dati: Liste parte I

 

Il linguaggio C non possiede il tipo di dato lista, ne tanto meno il tipo di dato albero, ma si possono implementare in tale linguaggio introducendo il concetto di:  tipo di dato astratto;

 

Cenni sui  tipi di dati astratti

 

Un tipo astratto di dato e’ uno strumento che si utilizza per esprimere i dati, in maniera indipendente dal linguaggio di programmazione.

Un tipo astratto di dato e’ un oggetto matematico composto da tre componenti:

a)    un insieme di valori detto il DOMINIO DEL TIPO

b)    un insieme di OPERAZIONI che vengono applicate ai valori del dominio oppure che hanno come risultato valori del dominio

c)     un insieme di COSTANTI, che rappresentano dei valori del dominio.

 

Tutte e tre le componenti di un tipo astratto, sono indipendenti dalla rappresentazione e dall’uso del tipo stesso nei linguaggi di programmazione.

Noi distinguiamo tra tipi astratti e tipi concreti, intendendo con quest’ultimo i tipi di dato resi disponibili direttamente nel linguaggio C, come ad esempio il tipo  array , il tipo struttura, i puntatori,  i file eccetera.

 

Notare che per caratterizzare in modo completo un tipo concreto, necessita specificare non soltanto le proprieta’ astratte (dominio, operazioni e costanti) ma anche i vincoli che il linguaggio impone sulla definizione ed uso del tipo stesso.

Ad esempio il tipo concreto di dato  array  necessita per essere definito nel linguaggio C, di specificare il modo in cui le variabili di tipo array sono dichiarate nel programma, i vincoli sul tipo degli indici e sulle dimensioni, i metodi per accedere alle componenti dell’array eccetera.

int  nome_array[10]; e’ una istruzione in cui definiamo un array di 10 elementi di tipo intero che e’ identificato dal nome nome_array; si accede alla i-esima componente nel seguente modo: nome_array[i-1]  .

Una definizione piu’ precisa di un tipo di dato astratto e’ la seguente:

 

Definizione [1]

Un tipo astratto di dato e’ una tripla < D, O, C > dove :

   D e’ un insieme di domini {Vi1, Vi2,…,Vin} fra cui si individua un dominio particolare detto “dominio di interesse”, che rappresenta l’insieme di valori del tipo che si sta definendo;

   O e’ un insieme di funzioni od operazioni  {Fi1, Fi2,…,Fim}; ogni Fi e’ del tipo:

Fi:   Vi1 X Vi2 X…X Vih} àVik

           (X indica il prodotto cartesiano)

Dove ogni elemento di { Vi1, Vi2,…,Vih, Vik} e’ un elemento di D, ed almeno uno tra i precedenti domini e’ il dominio di interesse.

Ossia il dominio ed il condominio di ciascuna Fi sono formati da domini contenuti in D, con il vincolo che il dominio di interesse o e’ il condominio di Fi oppure appare tra gli insiemi che definiscono il suo dominio;

 

   C e’ un insieme di elementi che denotano valori del dominio di interesse.

 

La rappresentazione dei tipi astratti

 

Quello che a noi interessa e’ trovare una rappresentazione del tipo di dato astratto, che ci serve definire, in termini di un altro tipo di dato, disponibile fra i tipi primitivi del linguaggio di programmazione che utilizziamo.

Per trovare tale rappresentazione bisogna fornire le regole  per poter rappresentare:

1)    il dominio di interesse e tutti gli altri domini in D

2)    le operazione in O

3)    le costanti in C

 

Esempio

Il punto 1) riguarda rappresentazione dei domini su cui il tipo astratto e’ definito.

Se intendiamo definire il tipo astratto INSIEME SU V nel linguaggio C, dove V={0,1,2,3,4,5,6,7,8,9}, potremmo far corrispondere, al generico elemento I di tipo INSIEME, un array A con indici da 0 fino a 9, i cui elementi sono di tipo booleano TRUE e FALSE, definiti come costanti di valore 1 e 0 rispettivamente;

la corrispondenza sara’ la seguente: il valore del generico  elemento i dell’array A cioe’ A[i] sara’ TRUE se i appartiene all’insieme I altrimenti sara’ A[i] uguale a FALSE.

 

Se il nostro  insieme I  vale  I={1,5,8,9}

avremo il seguente array A che lo puo’ rappresentare perfettamente:

 

tabella 20.1

         A

indice  valore  

0	FALSE
1	TRUE
2	FALSE
3	FALSE
4	FALSE
5	TRUE
6	FALSE
7	FALSE
8	TRUE
9	TRUE

 

Abbiamo creato una corrispondenza biunivoca, fra il tipo astratto INSIEME SU V 

con V={0,1,2,3,4,5,6,7,8,9}, e l’insieme dei valori di tipo array con 10 componenti di tipo booleano;

in generale possiamo dire che un metodo di rappresentazione di un tipo T1 mediante un altro tipo T2 definisce una corrispondenza rapp tra i valori dei domini di T1 ed i valori dei domini di T2.

Il punto 2) richiede che ogni operazione primitiva del tipo astratto T1 venga realizzata attraverso una operazione sul tipo di dato concreto, del linguaggio C, che si e’ scelto, per rappresentare T1.

Nel linguaggio C le operazioni primitive del tipo astratto T1 si realizzano attraverso l’uso delle funzioni.

 

Il punto 3) richiede che le costanti definite per il tipo T1 siano codificate opportunamente nel linguaggio C.

 

Le liste

 

La lista e’ un tipo astratto di dato che consente di trattare sequenze di elementi di un determinato tipo; noi introduciamo in questa lezione i metodi per la sua rappresentazione, applicandoli alle liste semplici.

 

 

Le liste semplici

 

Una lista semplice e’ un tipo di dato astratto avente una struttura lineare; con struttura lineare intendiamo dire che gli elementi della lista possono essere messi in relazione con i numeri naturali.

 

 

Una definizione piu’ rigorosa di lista semplice e’ la seguente:

 

Definizione[2]

Il tipo lista semplice e’ un tipo astratto di dato  < D, O, C >  dove:

1)    D={List, atomo,booleano};

List e’ il dominio di interesse; atomo e’ il dominio degli elementi che formano la lista;

“esempio di atomo: interi , reali, caratteri, array, strutture”

booleano sono le costanti TRUE e FALSE ( 1 od 0)

2)    O={Cons, Car, Cdr, Null} dove:

Cons: atomo X List à List

Car  : List à atomo

Cdr  : List à List

Null : List à booleano

3)    C={lista_vuota}

lista_vuota e’ la costante che indica la lista che non contiene elementi

 

Le quattro operazioni introdotte al punto 2) vengono cosi’ descritte:

 

Cons ha come dominio il prodotto cartesiano fra atomo e List e come condominio List

Essa consente l’inserimento di un dato elemento in testa alla lista.

Cons e’ quindi sinonimo di inserimento in testa

 

Esempio

 

Se L e’ un valore appartenente al dominio List  ed X un valore appartenente al dominio atomo la operazione Cons(X,L) mi da la lista semplice costituita da X seguita da tutti gli elementi precedentemente contenuti in L.

 

Se ho una L = (5,6,18); l’operazione Cons(3,L) mi restituisce la lista L’=(3,5,6,18).

 

Car consente di individuare il primo elemento della lista .

 

Car(L) restituisce il valore 5 mentre Car(L’) restituisce il valore 3

 

 

L’operazione Cdr restituisce la lista che si ottiene da un’altra lista quando viene ignorato il primo elemento di quest’ultima.

 

Cdr(L) = L*=(6,18)  mentre  Cdr(L’)=L

 

Nel caso la lista dominio di Cdr sia la lista vuota la Cdr non e’ definita.

 

L’operazione Null verifica se la lista e’ vuota

Ha come codominio, valore restituito, un booleano, ossia restituisce TRUE se la lista e’ vuota altrimenti restituisce False se la lista contiene elementi.

 

La rappresentazione delle liste tramite le parentesi tonde e’ detta rappresentazione parentetica.

 

( ) questa e’ la lista vuota

(12, 55, 12, 55) questa e’ una lista contenente 4 elementi di tipo intero.

 

Rappresentazione di una lista semplice

 

Le liste semplici noi le rappresentiamo effettuando una distinzione tra due categorie:

1)    rappresentazione sequenziale

2)    rappresentazione collegata o concatenata

 

Rappresentazione sequenziale

 

Si possono usare gli array monodimensionali in cui ogni valore della lista viene rappresentato attraverso un valore dell’array.

Si utilizzano due variabili di nome first e length, poiche’ il numero di elementi della lista puo’ variare.

first mi indica l’indice dell’array, in cui e’ memorizzato il  primo elemento della lista

lenght mi da la lunghezza della lista ossia il numero dei suoi elementi.

 

Volendo rappresentare attraverso un array A di 10 elementi interi la seguente lista:

L = (12, 2, 33, 4 ,1), in cui il primo elemento della lista lo si trova nella IV componente dell’array A, avremo per le variabili first il valore 3 e per length il valore 5.

 

Tabella 20.2   A

4	0	first=3
3	1	length=5
-2	2
12	3
2	4
33	5
4	6
1	7
1	8
2	9

 

 

 

 

 

 

 

Realizzazione delle operazioni

 

Le operazioni primitive definite per il tipo lista semplice :

 

Cons: atomo X List à List

Car  : List à atomo

Cdr  : List à List

Null : List à booleano

C={lista_vuota}

 

 possono essere cosi tradotte in linguaggio  C, facendo uso del tipo di dato array.

 

Vediamo una bozza di programma che utilizza tali operazioni, in cui definiamo un array di interi che contiene al max 10 elementi, per rappresentare la lista semplice:

 

#include<stdio.h>

#define DIM_LIS  10

 

typedef int tipo_atomi;

typedef enum{TRUE=1,FALSE=0}booleano;

typedef struct

          {

           tipo_atomi elementi[DIM_LIS];

           int first, length;

          }tipo_lista;

 

tipo_lista Cons(tipo_atomi elem, tipo_lista lis);

tipo_atomi Car(tipo_lista lis);

tipo_lista Cdr(tipo_lista lis);

booleano Null(tipo_lista lis);

 

tipo_lista lista;

 

/*funzione che verifica se la lista semplice lis e' vuota

lis e' di tipo tipo_lista*/

booleano Null(tipo_lista lis)

{

if(lis.length==0)

return(TRUE);

else return(FALSE);

}

 

 

/*inserimento in lista*/

tipo_lista Cons(tipo_atomi elem, tipo_lista lis)

{

if(lis.length==DIM_LIS)

 {

 printf("\nLista piena");

 exit(1);

 }

 else

 {

 if(Null(lis)) /*se la lista e' vuota*/

  lis.first=0;

  else

   if(lis.first==0)

    lis.first=DIM_LIS-1;

   else

   lis.first=lis.first-1;

 

  lis.elementi[lis.first]=elem;

  lis.length=lis.length+1;

 }

return(lis);

}

 

/*restituisce il primo elemento della lista*/

tipo_atomi Car(tipo_lista lis)

{

if(Null(lis)) /*se la lista e' vuota*/

 {

 printf("\nL'operazione non puo' effettuarsi");

 exit(1);

 }

 else

  return(lis.elementi[lis.first]);

}

 

 

tipo_lista Cdr(tipo_lista lis)

{

if(Null(lis))

 printf("\nOperazione Cdr non eseguibile");

 else

  {

  if(lis.length==1)

   lis.first=0;

   else

   lis.first=(lis.first%(DIM_LIS-1))+1;

 

   lis.length=lis.length-1;

 

  }

 return(lis);

}

 

 

 

 

 

 

main()

{

int e,i;

tipo_atomi testa_lista;

lista.length=0;

lista.first=-1;

…

…

…

}

 

Il primo elemento inserito viene collocato in posizione di indice 0 nell'array, il secondo in posizione DIM_LIS-1, il terzo in posizione DIM_LIS-2 e cosi di seguito..."array gestito in modo circolare"  “vedi operazione Cons”.  Abbiamo scelto le dimensioni dell’array pari alle dimensioni della lista, ma puo’ essere l’array di dimensioni anche maggiori.

 

Con la rappresentazione sequenziale si possono effettuare anche altre operazioni.

 

L’inconveniente principale e’ costituito dal fatto che le dimensioni dell’array sono fisse.

 

Vi e’ un notevole spreco di memoria in questo tipo di rappresentazione.

 

Difficoltà sorgono per l’inserimento e cancellazione di un elemento, che si trovi in una posizione diversa dalla prima e dall’ultima, in quanto questo comporterebbe lo spostamento di elementi dell’array.

In concreto la rappresentazione sequenziale si rivela inefficiente al punto che ha solo degli scopi  didattici e nella pratica si utilizza la rappresentazione collegata tramite puntatori.

 

 

Rappresentazione collegata delle liste semplici

 

In una lista collegata gli elementi vengono memorizzati associando ad ognuno di essi un “riferimento”, ossia un indirizzo di memoria che permette di localizzare il successivo elemento nella memoria.

Si perde la sequenzialita’ degli elementi,  ma si hanno notevoli vantaggi nella implementazione delle operazioni primitive e non.

 

La notazione che si usa per rappresentare tali liste e’ quella grafica illustrata in Fig. 20.1 dove sono presenti dei nodi, in cui si memorizzano gli elementi; i riferimenti (puntatori ad esempio)  sono rappresentati mediante archi che collegano tali nodi.

Gli elementi successivi nella lista, non necessariamente sono in indirizzi di memoria successivi.

 

Fig. 20.1

 

L

 

 

 

Abbiamo un riferimento al primo elemento della lista “riferimento iniziale” e si usa il simbolo null  Æ , per indicare il riferimento all’ultimo nodo.

 

Se la lista non contiene elementi, il simbolo null compare nel riferimento iniziale.

 

Con questa nuova rappresentazione delle liste semplici vediamo come possiamo eseguire le operazioni primitive introdotte:

 

Supponiamo di avere la seguente lista : L=(3, 7, 2, 9) con riferimento iniziale di nome piniz.

 

Fig. 20.2

 

piniz

 

 

 

L’operazione Cons(1,L) ossia l’inserimento in testa dell’elemento 1, avviene aggiornando il riferimento iniziale piniz, che lo facciamo puntare all’elemento 1, facendo puntare il riferimento di questo nodo al 3 ed eliminando il riferimento  piniz al 3.

 

Fig. 20.3

piniz

 

 

 

 

 

 

L’operazione Cdr(L) applicata alla nostra lista di Fig.20.1, si effettua facendo puntare il riferimento iniziale non piu’ al primo nodo ma al secondo nodo (ed eliminando il piniz precedente), che contiene il secondo elemento della lista.

 

Fig. 20.4

 

piniz

 

 

 

 

 

Nel caso si volessero effettuare delle operazioni di inserimento e cancellazione di un elemento, che non sia il primo della lista, possiamo vedere che con questo metodo, si realizzano abbastanza facilmente:

 

 

Inserimento dell’elemento 5 in seconda posizione nella lista 

L=(3, 7, 9) ottenendo L’=(3,5,7,9)

 

Fig. 20.5

 

      piniz

 

                                            

Volendo effettuare la cancellazione dell’elemento 7 nella lista L=(3,7,9) basta aggiornare il riferimento del nodo 3 e farlo puntare al nodo 9.

 

Fig. 20.6

piniz

 

 

  

Uso di tipi di dati in C per la rappresentazione collegata

 

Si puo’ utilizzare sia il tipo di dato array che i puntatori.

Mediante gli array si associa un elemento della lista ad una componente dell’array;

la componente dell’array questa volta e’ formata da : il valore del corrispondente elemento della lista e dal riferimento all’elemento successivo (“indice dell’array in cui e’ memorizzato l’elemento successivo della lista).

Esempio

La lista (14,5,7,21,45)  ha uno schema di rappresentazione collegata mediante array data dalla seguente tabella:  Tabella 20.2

  

Tabella 20.2

inizio=2	dato	next
0	-	-
1	21	3
2	14	5
3	45	Æ
4	-	-
5	5	7
6	-	-
7	7	1
8	-	-
9	-	-

 

Dalla variabile inizio capiamo, che il primo elemento della lista si trova all’indice 2 dell’array, il quale ha come valore il 21 e come riferimento al successivo elemento il 5, indice dell’array dove si trova memorizzato il secondo elemento della lista che ha valore 5 .. e cosi di seguito fino ad incontrare nel campo next il valore 3 che mi da l’ultimo elemento della lista il 45, che nel campo next ha il valore NULL (lista terminata).

 

Per quanto riguarda le operazioni, che si possono realizzare con la rappresentazione collegata tramite array, le lasciamo come riflessione per chi lo volesse fare.

 

Invece ci interesseremo con maggiore enfasi della rappresentazione collegata tramite puntatori e delle operazioni primitive e non realizzabili con essa.

 

Rappresentazione collegata tramite puntatori

 

Attraverso l’uso di strutture e puntatori, si realizza la rappresentazione collegata di una lista. Si fa corrispondere ad ogni elemento della lista una struttura, e si collegano i vari elementi della lista attraverso un campo della struttura “next” di tipo puntatore. Il riferimento iniziale della lista sara’ rappresentato da una variabile di tipo puntatore.

 

Vediamo una dichiarazione di tipi che ci consenta di rappresentare una lista.

 

#include<stdio.h>

typedef int Tipo_atomi;

 

 struct Struct_lista{

                    Tipo_atomi info;

                    struct Struct_lista *next;

                    };

typedef struct Struct_lista Tipo_nodo_lista;

typedef Tipo_nodo_lista *Tipo_lista;

main()

{

…..

}

                   

 

 

Nella dichiarazione, notiamo che la struttura e’ formata da due campi; il campo info, di tipo Tipo_atomi che nel nostro caso e’ un intero ed il campo next, che e’ un puntatore alla prossima struttura.

 

Fig. 20.7

 

 

Allo stesso modo di come abbiamo fatto per le liste semplici, realizzate con gli array, si possono definire le 4 operazioni primitive per le liste collegate. Notare che oltre alle operazioni primitive ci necessitano altre operazioni non primitive per gestire i problemi risolubili attraverso l’uso di liste. Avendo le seguenti definizioni preliminari:

 

#include<stdio.h>

#include<stdlib.h> /*contiene la malloc*/

 

typedef enum{TRUE=1,FALSE=0}booleano;

typedef int Tipo_atomi;

 

 struct Struct_lista{

                    Tipo_atomi info;

                    struct Struct_lista *next;

                    };

typedef struct Struct_lista Tipo_nodo_lista;

typedef Tipo_nodo_lista *Tipo_lista

 

/*le operazioni Null, Cons, Car, e Cdr si realizzano in C nel seguente modo:*/

 

/*prototipi delle funzioni che useremo*/

 

booleano Null(Tipo_lista lis);

Tipo_lista Cons(Tipo_lista *lis, Tipo_atomi elem);

Tipo_atomi Car(Tipo_lista lis);

Tipo_lista Cdr(Tipo_lista *lis);

void Inizializza_lista(Tipo_lista *lis);

 

/*definizione delle funzioni*/

void Inizializza_lista(Tipo_lista *lis)

{

(*lis)=NULL;

}

 

booleano Null(Tipo_lista lis)

{

/*Restituisce TRUE se lis e' la lista vuota, FALSE  altrimenti */

if(lis==NULL)

return TRUE;

 else return FALSE;

}

Tipo_lista Cons(Tipo_lista *lis,Tipo_atomi elem)

{

/*inserimento dell'elemento elem in testa alla lista lis*/

Tipo_lista punt_aux;

punt_aux=malloc(sizeof(Tipo_nodo_lista));

punt_aux->info=elem;

punt_aux->next=*lis;

*lis=punt_aux;

return(*lis);

}

 

Fig. 20.8

 

lis

 

  

 

Notare che lis e’ un puntatore ad un puntatore di tipo Tipo_lista.

Volendo dichiarare un puntatore ad puntatore di tipo intero, ad esempio si userebbe la seguente dichiarazione:

 

int **punt_intero;

 

 

Il contenuto di lis, punta alla lista che stiamo costruendo con l’operazione Cons cioe’: *lis contiene l’indirizzo del primo elemento di Struct_lista se la lista non e’ vuota.

 

 

Tipo_atomi Car(Tipo_lista lis)

{

/*Funzione che restituisce il primo elemento della lista*/

Tipo_lista piniz;

Tipo_atomi elem_iniz;

if(lis!=NULL)

elem_iniz=(lis)->info;

return elem_iniz;

}

 

Tipo_lista Cdr(Tipo_lista *lis)

{

/*aggiorna lis al resto della lista, la memoria

occupata dal primo elemento non viene rilasciata*/

if(*lis!=NULL)

(*lis)=(*lis)->next;

 

return(*lis);

}

 

 

 

esempio di main che possiamo usare per chiamare le funzioni introdotte:

 

int main()

{

int i=0;

char car;

Tipo_lista *lista,piniz;

Inizializza_lista(lista);

if(Null(*lista))

 {

 piniz=Cons(lista,i);

 printf("\nIl primo elemento inserito nella lista e': %d \n",(piniz)->info);

 i=1;

 }

 

 while(i<5)

 {

 piniz=Cons(lista,i);

 printf("\nelemento %d = %d ",i,((piniz)->info));

 i++;

 }

 Cdr(lista);

 printf("\nl'elemento restituito da Car e' : %d ",Car(piniz));

 printf("\ninserite un carattere per stampare la lista restituita da Cdr ");

 scanf("\n%c",&car);

while(*lista!=NULL)

 {

 printf("\n%d ",(*lista)->info);

 *lista=(*lista)->next;

 }

 return(0);

}

 

esercizio