La Struttura Dati Astratta (adt) Lista



Scaricare 130.23 Kb.
29.12.2017
Dimensione del file130.23 Kb.

Prof.Ing.Salvatore Cavalieri

L’ADT Lista in Linguaggio C a.a.2009/2010


La Struttura Dati Astratta (ADT) Lista




Introduzione


Nella definizione di un programma mirato alla risoluzione di un determinato problema, la scelta delle strutture dati è di fondamentale importanza per un’efficiente risoluzione del problema, almeno tanto quanto la scelta dell'algoritmo risolutore. Molto spesso, anzi, l'algoritmo in grado di risolvere il problema stesso dipende strettamente dalle strutture dati adottate. Ciò implica che i tempi necessari per la risoluzione di un problema (ossia la complessità computazionale dell'algoritmo) è strettamente legata alla struttura dati adottata.

Le liste rappresentano una struttura dati flessibile ed efficiente per la gestione delle informazioni. In questo documento introdurremo il concetto della struttura dati astratta (ADT) Lista, la sua rappresentazione sequenziale e collegata e l’implementazione delle primitive di gestione di una lista in linguaggio C.



1 Definizione di ADT Lista


Le liste rappresentano una tra le più semplici strutture dati utilizzate per la memorizzazione e la gestione di informazioni. Il vantaggio del loro utilizzo è la semplicità della gestione. Di contro le prestazioni delle operazioni necessarie a gestire tali strutture dati non sono eccelse. Se n è il numero di informazioni contenute, la complessità computazionale (ossia i tempi di esecuzione) degli algoritmi necessari alla loro gestione è O(n), ossia direttamente proporzionale al numero di informazioni da gestire. Esistono altre strutture dati, come ad esempio alberi, che possono offrire prestazioni superiori (O(log n)), ma a costo di una più difficile gestione.

Particolari liste che trovano un utilizzo molto frequente sono le PILE e le CODE. Le prime permettono di realizzare politiche di gestione delle informazioni del tipo Last In First Out (LIFO); una tipica applicazione di tale politica è quella relativa allo stack in un computer. La struttura CODA realizza una politica di gestione di tipo First In First Out (FIFO), che trova innumerevoli applicazioni quando si vogliano realizzare algoritmi che processano informazioni in base, ad esempio, ad un ordine temporale della loro generazione.

Un ADT Lista è una sequenza di elementi, aventi le seguenti caratteristiche:


  • Tutti gli elementi della lista sono omogenei, ossia appartengono allo stesso tipo.

  • Ciascun elemento della lista è contraddistinto da una posizione. In base alla posizione di ciascun elemento nella lista, è possibile individuare relazioni di precedenza e di successione tra gli elementi. Particolari elementi sono quello di testa che occupa la prima posizione e quello di coda che occupa l'ultima posizione. È ovvio che il primo elemento della lista non ha predecessore, e l'ultimo elemento non ha successore.

Un ADT lista viene solitamente rappresentato come sequenza degli elementi che la compongono, disposti in accordo alla loro posizione. Sia ai un generico elemento e sia i la sua posizione nella lista. Una lista composta da n elementi dello stesso tipo di ai, può essere rappresentata da:

a1, a2, a3,…, an

Si chiama lunghezza della lista il numero n di elementi che la compongono. Una lista è individuata dall'elemento in prima posizione. Una Lista Vuota non presenta alcun elemento.



2 Operazioni Primitive sull’ADT Lista


Una lista è caratterizzata da alcune operazioni fondamentali. Da ora in poi si consideri la seguente simbologia:

  • sia l una lista,

  • sia p la generica posizione di un elemento della lista,

  • sia x un generico elemento dello stesso tipo degli elementi presenti nella lista. Il tipo di appartenenza verrà nel seguito indicato con TipobaseList.

Per fissare le idee si consideri la seguente lista di numeri interi:

l={12, 43, 21, 17, 19, 54, 3, 21}

e si supponga che la posizione di ciascun elemento della lista sia espressa sempre da numeri interi a partire dallo 0. Così, il primo elemento della lista ha posizione 0, e l'ultimo, nell'esempio, ha posizione 7.



Le seguenti operazioni primitive vengono definite sulla struttura dati lista:

  • End(l): Restituisce la posizione successiva alla posizione dell’ultimo elemento della lista. Tale posizione è quella in cui verrà inserito un elemento che si vuole diventi il successore dell’ultimo elemento della lista. Se la lista è vuota, End(l) ritorna la prima posizione della lista. Per esempio, se l è la lista prima vista, la funzione End(l) restituirà 8 (visto che l'ultimo elemento, il 21, ha posizione 7).

  • First(l): Restituisce la posizione del primo elemento della lista l. Nel caso in cui la lista è vuota ritorna End(l). Per esempio, considerando la lista l vista prima, First(l) restituirà 0.

  • InsertList(l,p,x): Inserisce l’elemento x in posizione p, spostando di una posizione più alta tutti gli elementi di posizione p e superiori. Per esempio, considerando la lista l dell'esempio, la chiamata InsertList(l,1,-5) modificherà la lista in questo modo: l={12, -5, 43, 21, 17, 19, 54, 3, 21}. La funzione InsertList(l,p,x) non è definita quando p non esiste nella lista (ad esempio se volessi inserire l'elemento -5 in posizione 10 nella lista precedentemente considerata).

  • DeleteList(l,p): Elimina l’elemento della lista di posizione p, spostando di una posizione in basso tutti gli elementi di posizione superiore a p. Per esempio, considerando la lista precedente, la chiamata DeleteList(l,4) modificherà la lista in questo modo: l={12, 43, 21, 17, 54, 3, 21}. La funzione non è definita quando p non esiste o quando p coincide con End(l).

  • Locate(l,x): Restituisce la posizione dell’elemento x; se x compare nella lista più di una volta, allora viene restituita la posizione della prima occorrenza di x. Se x non compare nella lista allora viene restituita la posizione fornita dalla funzione End(l). Per esempio, nell'esempio di lista prima considerato, la chiamata alla funzione Locate(l,21) restituisce 2, mentre la chiamata Locate(l, 52) restituisce 8.

  • Retrieve(l,p): Restituisce l’elemento della lista di posizione p. La funzione non è definita quando p non esiste o p coincide con End(l). Per esempio, se l è la lista prima vista, la chiamata Retrieve(l,3) restituisce 17.

  • MakeNullList(l): Restituisce una lista vuota. Attenzione, la funzione MakeNullList(l) è intesa a inizializzare una lista, ponendo il suo valore a lista vuota. La funzione MakeNullList(l) non è concepita per eliminare tutti gli elementi di una lista già esistente. Per far ciò si può utilizzare la funzione DeleteList(l,p) applicandola a tutte le posizioni esistenti. La funzione MakeNullList(l) servirà, come si vedrà più avanti, ad inizializzare variabili di tipo lista.

  • EmptyList(l): Restituisce il valore booleano vero se la lista l è vuota. Restituisce il valore falso altrimenti.

  • FullList(l):Restituisce il valore booleano vero se la lista è piena, ossia non è possibile inserire nuovi elementi. Restituisce il valore falso altrimenti.

  • Next(l,p):Restituisce la posizione dell’elemento successivo all’elemento di posizione p. Per esempio, considerando la lista dell'esempio, la chiamata alla funzione Next(l,2) restituisce il valore di posizione 3. La funzione non è definita quando p non esiste o p coincide con End(l).



3 Realizzazione di un ADT Lista in Linguaggio C


La realizzazione della struttura dati lista, consiste nella sua rappresentazione attraverso i tipi di dati disponibili nei linguaggi di programmazione, ed in particolare in C. Esistono tra le altre, due modalità realizzative di una Lista: Sequenziale e Collegata.

La realizzazione sequenziale prevede che la sequenzialità degli elementi della lista venga rappresentata dalla adiacenza delle locazioni di memoria utilizzate per contenere ciascun elemento della lista. Una tipica realizzazione sequenziale è attraverso un tipo di dato vettore.

La realizzazione collegata si basa sull'idea di rappresentare la sequenzialità degli elementi della lista attraverso l'uso di locazioni di memoria ciascuna delle quali contiene due informazioni: un elemento della lista e l'indicazione della locazione di memoria contenente l'elemento successivo. In tal caso le locazioni di memoria non sono per forza contigue in RAM, ma possono occupare spazi di memoria sparpagliati nella porzione RAM riservata al programma.

3.1.Rappresentazione Sequenziale


Come detto prima, la più tipica rappresentazione sequenziale di una lista avviene tramite l'uso di un vettore. Nel seguito verrà mostrata la realizzazione sequenziale della lista tramite il tipo vettore reso disponibile dal linguaggio C.

Come già detto, il tipo di appartenenza di ciascun elemento della lista verrà chiamato tipobaseList. Ad esempio se ciascun elemento della lista fosse di tipo float, il tipobaseList coinciderebbe con il tipo float. In linguaggio C, si può scrivere allora:


typedef float tipobaseList;
Visto che molte funzioni primitive della lista restituiscono il valore booleano (ad esempio EmptyList(l) e FullList(l)), che non è definito in C, possiamo definirlo equivalente ad un tipo short nella seguente maniera:
typedef short boolean;
Nella rappresentazione sequenziale di una lista, la posizione di ogni elemento della lista è rappresentata dall'indice del vettore in cui l'elemento stesso è memorizzato. Dunque la posizione di ogni elemento della lista nella rappresentazione sequenziale è un intero. Possiamo allora definire un alias di un intero, che chiameremo position, per rappresentare in C la posizione di ogni elemento della lista. In C, ciò si può scrivere:
typedef int position;
Allo scopo di rappresentare la sequenzialità degli elementi della lista, gli elementi della lista devono occupare componenti adiacenti del vettore. In questo modo, preso un qualunque elemento della lista, posso accedere al suo successore o predecessore considerando uno dei due componenti adiacenti (se esistono) del vettore. Ciò può essere realizzato in due modi.

Il primo consiste nel memorizzare ciascun elemento a partire dall'ultimo componente del vettore, in cui viene memorizzato il primo elemento della lista. Il secondo elemento viene memorizzato nel penultimo componente del vettore e così via. Utilizzando la rappresentazione in C vista precedentemente, il primo elemento della lista ha posizione N-1, il secondo N-2 e così via. Preso un elemento la cui posizione sia i, il suo successore ha posizione i-1 e il suo predecessore ha posizione i+1. Il primo elemento della lista ha posizione N-1 e ha solo il successore che ha posizione N-2.

L'altra possibilità è quella di memorizzare ciascun elemento della lista a partire dal primo componente del vettore. Utilizzando la rappresentazione della lista in C vista prima, l'elemento in testa alla lista viene memorizzato nel componente del vettore di indice 0 del vettore (ossia ha posizione 0), il secondo elemento della lista viene memorizzato nel componente di indice 1 (ossia la sua posizione è 1) e così via. In base a ciò, preso il generico elemento della lista in posizione i, il suo successore (se esiste) ha posizione i+1, mentre il suo predecessore (se esiste) ha successore i-1. L'elemento in testa ha posizione 0 e il suo successore ha posizione 1.

Nel seguito verrà scelta la seconda modalità di memorizzazione. In questa rappresentazione, la posizione del primo elemento della lista è sempre la stessa ed è la posizione 0, mentre la posizione dell'ultimo elemento della lista dipende dalla lunghezza della lista. Allo scopo di individuare la posizione dell'ultimo elemento della lista, viene utilizzato una variabile che individua la posizione dell'ultimo elemento della lista. Tale variabile viene chiamata last.

La struttura di nome list, dunque, contiene due campi. Il primo è il vettore a N componenti, mentre il secondo è il puntatore last. Il campo last è di tipo position, ossia intero, visto che la posizione di ciascun elemento è un intero. Il tipo di dato lista, viene realizzato con la struttura composta da un array di N componenti (dove N è una costante) e da una variabile last.
#define N 10
typedef struct {

tipobaseList info[N];

position last;

} list;
Per realizzare la lista secondo la rappresentazione sequenziale, ci serve una costante, che chiameremo LISTAVUOTA. Essa serve ad indicare che la lista è vuota. Visto che si è assunto di indicare con last la posizione dell'ultimo elemento della lista, la condizione di lista vuota, può essere rappresentata da un valore della variabile last inferiore a 0 (che indica la presenza di un solo elemento nella lista, in posizione 0). Ad esempio il valore last=–1 può esere utilizzato per indicare la presenza di 0 elementi nella lista. Dunque, la rappresentazione della costante LISTAVUOTA può essere fatta attraverso una definizione di costante in C:


#define LISTAVUOTA -1

Rappresentazione delle funzioni Primitive della Lista


Nel seguito vengono implementate le funzioni definite per la lista:
position End(list l) {

return(l.last+1);

}
position First(list l){

return(0); /*ritorna End(l) se la lista è vuota*/

}

void MakeNullList(list *l){



l->last=LISTAVUOTA;

}
boolean EmptyList(list l){

return(l.last==LISTAVUOTA);

}
boolean FullList(list l){

return(l.last==N-1);

}

void InsertList(list *l, position p, tipobaseList x){



position i;
if (!FullList(*l))

if (p>=0 && p<=l->last+1) {

for (i=l->last; i>=p; i--)

l->info[i+1]=l->info[i];

l->last++;

l->info[p]=x;

}

}
void DeleteList(list *l, position p){



position i;
if (!EmptyList(*l))

if (p>=0 && p<=l->last) {

for (i=p;ilast; i++)

l->info[i]=l->info[i+1];

l->last--;

}

}


position Locate(list l, tipobaseList x){

position i;


if (!EmptyList(l))

for (i=0; i<=l.last; i++)

if (!Confronta(l.info[i],x)) return(i);
return(l.last+1);

}
tipobaseList Retrieve(list l, position p){

if (!EmptyList(l))

if (p>=0 && p<=l.last) return(l.info[p]);

}
position Next(list l, position p){

if (!EmptyList(l))

if (p>=0 && p<=l.last) {

p++;


return(p);

}

}


Nelle precedenti funzioni primitive, ed in particolare nella funzione Locate, si è fatto uso della funzione definita dall’utente, chiamata Confronta. Essa riceve in ingresso due parametri tipobaseList a e b:
int Confronta (tipobaseList a, tipobaseList b)
e restituisce:

  • 0, se a e b sono identici

  • Un numero negativo se a è minore di b

  • Un numero positivo se a è maggiore di b

Il motivo dell’uso di tale funzione è che nell’inserimento in lista è necessario utilizzare espressioni che realizzano confronti logici (uguale, maggiore e minore). Nella funzione locate, ad esempio, serve il confronto tra due elementi al fine di capire se essi sono uguali. Come si sa, gli operatori ==, < e > non possono essere applicati a tutti i tipi di dati (ad esempio non si possono applicare a struct). Dunque per avere delle funzioni che effettuino confronti logici e che valgano per qualunque TipobaseList, faremo uso di funzioni astratte, che implementeremo in modo diverso per ciascun TipobaseList.

3.2.Rappresentazione Collegata


Come detto precedentemente, la rappresentazione collegata di una struttura dati lista si basa sul principio di memorizzare gli elementi della lista in modo da non essere adiacenti, ossia da occupare posizioni in memoria RAM non contigue. La sequenzialità tipica della lista è mantenuta memorizzando accanto all'elemento generico ai, la posizione del successivo elemento ai+1.

La rappresentazione collegata può essere realizzata sia con vettori che con puntatori. Nel seguito verrà illustrata solo l’implementazione con puntatori.



Rappresentazione collegata con Puntatori


La rappresentazione collegata con puntatori si basa sull'idea di considerare elementi allocati dinamicamente in memoria RAM, ciascuno dei quali è rappresentato da due campi. Un campo memorizza il generico elemento della lista, mentre l'altro campo memorizza la posizione del successivo elemento.

La posizione di un elemento coincide con l'indirizzo di memoria della locazione in cui è memorizzato un elemento della lista, e dunque è una variabile puntatore. Il problema è decidere la corrispondenza tra le posizioni degli elementi della lista e gli indirizzi di memoria.

Intuitivamente potrebbe essere assunto che la posizione di un elemento ai sia l'indirizzo di memoria RAM della locazione in cui l'elemento stesso è memorizzato. Se fosse così verrebbero a crearsi dei problemi nella gestione della lista. Si consideri il seguente esempio, in cui ciascun rettangolo corrisponde ad un elemento dinamicamente allocato, caratterizzato da un puntatore, mostrato sotto ciascun rettangolo, che corrisponde al suo indirizzo di memoria RAM.

In questo esempio tre elementi della lista, gli elementi ai-1, ai e ai+1, sono memorizzati nelle locazioni di memoria RAM caratterizzate dai valori di indirizzo pai-1, pai, pai+1, rispettivamente. Tali indirizzi rappresentano, per quanto detto, le posizioni dei tre elementi. Come si vede ciascuna locazione dinamica, oltre a contenere l'elemento della lista, contiene l'indicazione dell'indirizzo della locazione di memoria in cui è memorizzato l'elemento successivo, ossia contiene la posizione dell'elemento successivo. Le frecce, rappresentano il collegamento che si instaura tra i vari elementi della lista. A partire da un qualunque elemento della lista è possibile accedere solo al suo successore tramite il campo puntatore.

Supponiamo di voler cancellare l'elemento ai, di cui è nota la posizione pai. Il seguente disegno mostra le operazioni da compiere:

Come si vede la cancellazione dell'elemento di posizione pai, comporta la modifica dell'elemento di posizione pai-1, in quanto è necessario modificare il puntatore alla posizione del successivo elemento. Ma accedendo all'elemento di posizione pai, non è possibile conoscere la posizione dell'elemento precedente a ai, ossia di ai-1.

Analogo esempio per l'inserimento di un nuovo elemento in posizione pai.

Questi esempi evidenziano la necessità di ricorrere ad una diversa scelta della rappresentazione della posizione degli elementi della lista. Allo scopo di poter effettuare la cancellazione e l'inserimento in modo semplice, la scelta più ovvia è quella di far coincidere la posizione dell'elemento ai con l'indirizzo della locazione di memoria contenente l'elemento ai-1.

La seguente figura evidenzia che adesso la posizione dell'elemento ai è sempre indicata con pai, ma questa volta coincide con l'indirizzo della locazione di memoria in cui è memorizzato ai-1.

In questo modo, è possibile effettuare la cancellazione dell'elemento ai a partire dalla conoscenza della posizione di ai, ossia pai. Attraverso questa posizione si può accedere alla locazione di memoria che contiene ai-1 e pai+1, e modificare quest'ultimo campo in pai+2, come mostrato nella seguente figura:

Analogo discorso può essere fatto per l'inserimento.

In base a questa scelta è chiaro che la posizione dell'ultimo elemento della lista, an è rappresentato dall'indirizzo della locazione di memoria contenente an-1, mentre la posizione successiva all'ultimo elemento della lista è fornita dall'indirizzo della locazione di memoria che contiene an.

Per quanto riguarda il secondo elemento della lista, a2, analogamente la sua posizione è quella del puntatore alla locazione che contiene a1.

Nasce a questo punto il problema di assegnare un valore alla posizione del primo elemento della lista a1. A tal fine sono possibili due soluzioni:
Soluzione 1

Viene assunto che la posizione di a1 è rappresentata dal valore NULL, che è assolutamente distinguibile dai rimanenti valori di posizione. La seguente figura riassume la convenzione scelta.


Soluzione 2

Viene considerato come primo elemento della lista un elemento fittizio, che non contiene cioè alcun elemento della lista da rappresentare. L'unica informazione che tale elemento contiene è relativa all'indirizzo di memoria in cui è memorizzato il primo elemento della lista. La seguente figura riassume la convenzione scelta. Il vantaggio di tale rappresentazione è quello di poter scrivere le procedure di inserimento, cancellazione e ricerca senza espressamente codificare la gestione del primo elemento. Il codice di tali procedure è molto semplice e considera il primo elemento della lista come un qualunque elemento.

In accordo a questa convenzione, se la lista è vuota, allora l'elemento fittizio conterrà il valore NULL, ossia la condizione di lista vuota è rappresentata dalla seguente figura:

Nel seguito verrà mostrata la rappresentazione della Lista con puntatori in C, unicamente in base alla soluzione 1.



3.2.1. Rappresentazione Collegata basata sulla Soluzione 1


Come fatto in precedenza, definiremo con tipobaseList il tipo di appartenenza di ciascun elemento della lista. Ad esempio se ciascun elemento fosse di tipo int, l’implementazione del tipo tipobaseList risulterebbe:
typedef int tipobaseList;
Inoltre, la presenza di funzioni booleane ci suggerisce la possibilità di definire un tipo boolean, come alias del tipo short.
typedef short boolean;
Ciascun elemento della lista viene memorizzato in una locazione di memoria contente una struttura, composta da due campi: info che contiene il generico elemento della lista, e la posizione dell'elemento successivo, campo next. La lista è individuata dal puntatore alla locazione di memoria contenente il primo elemento della lista. L'ultimo elemento della lista è riconoscibile per il fatto che possiede il valore NULL nel campo relativo alla posizione del successivo elemento.

L'implementazione di ciascun elemento della lista in C, è:


typedef struct nodoList {

tipobaseList info;

struct nodoList *next;

} *list;


La posizione di ciascun elemento della lista è un puntatore di tipo list. Definiremo, per comodità, un tipo position:
typedef list position;
L'unica costante che ci serve per realizzare la lista con puntatori, è la costante LISTAVUOTA che corrisponde ad una lista vuota. Se la lista è vuota il puntatore al primo elemento della lista è NULL. Dunque, la costante LISTAVUOTA può essere rappresentata in C nella seguente maniera:
#define LISTAVUOTA NULL

Rappresentazione di Operazioni Primitive


Le seguenti procedure e funzioni realizzano le operazioni primitive di una lista:
position End(list l){

if (l==LISTAVUOTA) return(LISTAVUOTA);

while (l->next!=LISTAVUOTA)

l=l->next;

return(l);

}
position First(list l) {

return(LISTAVUOTA); /*se la lista è vuota torna END(l) */

}
void MakeNullList(list *l){

*l=LISTAVUOTA;

}
boolean EmptyList(list l){

return(l==LISTAVUOTA);

}
boolean FullList(list l){

return(0);

}
void InsertList(list *l, position p, tipobaseList x){

struct nodoList * temp;
if (!FullList(*l)) {

temp=(struct nodoList *) malloc(sizeof(struct nodoList));

temp->info=x;

if (p==LISTAVUOTA) {

temp->next=*l;

*l=temp;


} else {

temp->next=p->next;

p->next=temp;

}

}



}

void DeleteList(list *l, position p){

struct nodoList * tmp;
if (!EmptyList(*l) && p!=End(*l)) {

if (p==LISTAVUOTA) {

tmp=(*l)->next;

free (*l);

*l=tmp;

} else {


tmp=p->next;

p->next=tmp->next;

free (tmp);

}

}



}

position Locate(list l, tipobaseList x){


if (!EmptyList(l)) {

if (!Confronta(l->info,x)) return(LISTAVUOTA);

while (l->next!=LISTAVUOTA) {

if (!Confronta(l->next->info,x)) return(l);

l=l->next;

}

return(l);



}

}
tipobaseList Retrieve(list l, position p) {

if (!EmptyList(l) && p!=End(l)) {

if (p==LISTAVUOTA) return(l->info);

else return(p->next->info);

}

}


position Next(list l, position p) {

if (p!=End(l)) {

if (p==LISTAVUOTA) return(l);

else return(p->next);

}

}
Nelle precedenti funzioni primitive, ed in particolare nella funzione Locate, si è fatto uso della funzione definita dall’utente, chiamata Confronta. Essa riceve in ingresso due parametri tipobaseList a e b:


int Confronta (tipobaseList a, tipobaseList b)
e restituisce:

  • 0, se a e b sono identici

  • Un numero negativo se a è minore di b

  • Un numero positivo se a è maggiore di b

Il motivo dell’uso di tale funzione è che nell’inserimento in lista è necessario utilizzare espressioni che realizzano confronti logici (uguale, maggiore e minore). Ad esempio nella funzione Locate si deve verificare se due elementi sono uguali tra loro. Come si sa, gli operatori ==, < e > non possono essere applicati a tutti i tipi di dati (ad esempio non si possono applicare a struct). Dunque per avere delle funzioni che effettuano confronti logici e che valgano per qualunque TipobaseList, faremo uso di funzioni astratte, che implementeremo in modo diverso per ciascun TipobaseList.

4.Un'Applicazione dell’ADT Lista:Visita e Inserimento Ordinato


Esistono alcuni algoritmi di rilevante importanza per la gestione delle liste. Alcuni di questi sono: la visita di una lista e l'inserimento ordinato. Essi verranno definiti nel seguito sempre in formato astratto a prescindere dall’implementazione della Lista.

4.1. Visita di una Lista


L'algoritmo di visita di una lista consiste nella visualizzazione di tutti gli elementi della lista a partire da quello di posizione iniziale. Ovviamente la visita può essere realizzata solo se la lista non è vuota. Nel seguito viene riportata la codifica dell’algoritmo di visita in termini di funzioni e tipi astratti, a prescindere dall’implementazione dell’ADT Lista.
void visita(list l){

position p,u;

tipobaseList x;
p=First(l);

u=End(l);

while (p!=u) {

x=Retrieve(l,p);

VisualizzaElemento(x);

p=Next(l,p);

}

}


4.2. Inserimento Ordinato in una Lista


L'algoritmo di inserimento ordinato consiste nell'inserire, a partire da una lista vuota, elementi nella lista, disponendo ciascun elemento nella posizione opportuna secondo l'ordinamento prescelto.

Ad esempio, data una lista di interi e scelto l'inserimento in ordine crescente, ciascun elemento che viene inserito viene messo in modo che l'elemento di posizione iniziale sia il più piccolo e quello di posizione finale sia il più grande.

Nel seguito viene riportata la codifica dell’algoritmo di ordinamento in termini di funzioni e tipi astratti, a prescindere dall’implementazione dell’ADT Lista.
void insord(list *l, tipobaseList x)

{

position p,u;



tipobaseList tmp;
if (EmptyList(*l)) InsertList(l,First(*l),x);

else {


p=First(*l);

u=End(*l);

while (p!=u) {

tmp=Retrieve(*l,p);

if (Confronta(tmp,x)<0) p=Next(*l,p);

else break;

}

InsertList(l,p,x);



}

}
Nella precedente funzione di inserimento ordinato si è fatto uso della funzione Confronta. Come già detto, essa riceve in ingresso due parametri tipobaseList a e b:


int Confronta (tipobaseList a, tipobaseList b)
e restituisce:

  • 0, se a e b sono identici

  • Un numero negativo se a è minore di b

  • Un numero positivo se a è maggiore di b

Il motivo dell’uso di tale funzione è che nell’inserimento ordinato in lista è necessario utilizzare espressioni che realizzano confronti logici (maggiore e minore in particolare). Come si sa, gli operatori < e > non possono essere applicati a tutti i tipi di dati (ad esempio non si possono applicare a struct). Dunque per avere delle funzioni che effettuano confronti logici e che valgano per qualunque TipobaseList, facciamo uso di funzioni astratte, che verranno implementate in modo diverso per ciascun TipobaseList.

5.Un Esempio Applicativo dell’ADT Lista


Il seguente programma si riferisce alla gestione di un ADT Lista. Si suppone l’esistenza di un file di nome “Lista.h” contenente l’implementazione della lista (sequenziale con vettore o collegata con puntatore, come spiegato in precedenza) e la definizione del tipobaseList.

Come si vede il programma utilizza delle funzioni per leggere ciascun elemento dell’ADT Lista dalla tastiera (LeggiElemento, CercaElementoe e ModificaElemento) e visualizzare ciascun elemento dell’ADT Lista sul video (VisualizzaElemento). Queste funzioni sono strettamente legate alla definizione del tipobaseList, visto che le funzioni di input/output del linguaggio C dipendono dai tipi delle variabili da leggere/scrivere. Tali funzioni sono dunque definite nel file Lista.h, in dipendenza della codifica del tipobaseList.


#include
void flush(void);
#include "Lista.h"
void visita(list );

void insord(list *, tipobaseList );


list lt;
main(){

short s;


tipobaseList elem;

position pos;


MakeNullList(<);
do {

printf("\n\nMenu di Operazioni ");

printf("\n1-Inserimento Ordinato ");

printf("\n2-Ricerca ");

printf("\n3-Cancellazione ");

printf("\n4-Visita Lista ");

printf("\n5-Modifica Elemento ");

printf("\n6-Fine ");

printf("\nInserisci la scelta ---> ");

scanf("%d",&s);

flush();

switch(s) {

case 1 :

if (FullList(lt)) printf("\nLista piena ");

else {

LeggiElemento(&elem);



insord(<,elem);

}

break;


case 2 :

if (EmptyList(lt)) printf("\nLista Vuota ");

else {

CercaElemento(&elem);



pos=Locate(lt,elem);

if (pos!=End(lt)){

printf("\nElemento Trovato ");

VisualizzaElemento(Retrieve(lt,pos));

}else printf("\nElemento non Trovato ");

}

break;


case 3 :

if (EmptyList(lt)) printf("\nLista Vuota ");

else {

CercaElemento(&elem);



pos=Locate(lt,elem);

if (pos!=End(lt)) {

DeleteList(<,pos);

printf("\nElemento Eliminato ");

}

else printf("\nElemento non Trovato ");



}

break;
case 4 :

if (EmptyList(lt)) printf("\nLista Vuota ");

else visita(lt);

break;
case 5 :

if (EmptyList(lt)) printf("\nLista Vuota ");

else {

CercaElemento(&elem);



pos=Locate(lt,elem);

if (pos!=End(lt)) {

elem=Retrieve(lt,pos);

ModificaElemento(&elem);

DeleteList(<,pos);

insord(<,elem);

printf("\nElemento Modificato ");

} else printf("\nElemento non Trovato ");

}

}

} while (s<6);



}

void flush(void){

while (getchar()!='\n');

}
void visita(list l){

position p,u;

tipobaseList x;


p=First(l);

u=End(l);

while (p!=u) {

x=Retrieve(l,p);

VisualizzaElemento(x);

p=Next(l,p);

}

}
void insord(list *l, tipobaseList x)



{

position p,u;

tipobaseList tmp;
if (EmptyList(*l)) InsertList(l,First(*l),x);

else {


p=First(*l);

u=End(*l);

while (p!=u) {

tmp=Retrieve(*l,p);

if (Confronta(tmp,x)<0) p=Next(*l,p);

else break;

}

InsertList(l,p,x);



}

}

5.1. Implementazione Sequenziale con Vettore


Nel caso di Rappresentazione Sequenziale, supponendo che il tipobaseList sia un float, il file Lista.h è:
#define LISTAVUOTA -1
typedef float tipobaseList;
typedef short boolean;
typedef int position;
#define N 10
typedef struct {

tipobaseList info[N];

position last;

} list;


void LeggiElemento(tipobaseList * x){

printf("\nInserisci l'Elemento ");

scanf("%f",x);

flush();


}
void CercaElemento(tipobaseList * x){

printf("\nInserisci l'Elemento ");

scanf("%f",x);

flush();


}
void VisualizzaElemento(tipobaseList x){

printf("\nElemento %f ",x);

}
void ModificaElemento(tipobaseList * x){

printf("\nModifica l'elemento = % f ",*x);

printf("\nInserisci il nuovo elemento ");

scanf("%f",x);

flush();

}
int Confronta(tipobaseList a, tipobaseList b){

if (a

else if (a>b) return 1;

else return 0;

}
position End(list l) {

return(l.last+1);

}
position First(list l){

return(0); /*ritorna End(l) se la lista è vuota*/

}
void MakeNullList(list *l) {

l->last=LISTAVUOTA;

}
boolean EmptyList(list l){

return(l.last==LISTAVUOTA);

}
boolean FullList(list l){

return(l.last==N-1);

}


void InsertList(list *l, position p, tipobaseList x){

position i;


if (!FullList(*l))

if (p>=0 && p<=l->last+1) {

for (i=l->last; i>=p; i--)

l->info[i+1]=l->info[i];

l->last++;

l->info[p]=x;

}

}
void DeleteList(list *l, position p){



position i;
if (!EmptyList(*l))

if (p>=0 && p<=l->last) {

for (i=p;ilast; i++)

l->info[i]=l->info[i+1];

l->last--;

}

}


position Locate(list l, tipobaseList x){

position i;


if (!EmptyList(l))

for (i=0; i<=l.last; i++)

if (!Confronta(l.info[i],x)) return(i);
return(l.last+1);

}

tipobaseList Retrieve(list l, position p){



if (!EmptyList(l))

if (p>=0 && p<=l.last) return(l.info[p]);

}
position Next(list l, position p){

if (!EmptyList(l))

if (p>=0 && p<=l.last) {

p++;


return(p);

}

}




5.2. Implementazione Collegata con Puntatori


Nel caso di rappresentazione collegata, supponendo che il tipobaseList sia uno struct contenente i campi: cognome, nome ed età, il file Lista.h è:

#include


#define LISTAVUOTA NULL
#define S 15
typedef struct {

char cognome[S], nome[S];

unsigned short eta;

}tipobaseList;


typedef short boolean;
typedef struct nodoList {

tipobaseList info;

struct nodoList *next;

} *list;
typedef list position;

void LeggiStringa(char s[],unsigned short dim){

unsigned short i;

for (i=0; (s[i]=getchar())!='\n' && i

s[i]='\0';

}
void LeggiElemento(tipobaseList * x){

printf("\nInserisci l'Elemento ");

printf("\nInserisci il Cognome ");

LeggiStringa(x->cognome, S);

printf("\nInserisci il Nome ");

LeggiStringa(x->nome, S);

printf("\nInserisci l'eta' ");

scanf("%d",&x->eta);

flush();

}
void CercaElemento(tipobaseList * x){

printf("\nRicerca per Cognome e Nome ");

printf("\nInserisci il Cognome ");

LeggiStringa(x->cognome, S);

printf("\nInserisci il Nome ");

LeggiStringa(x->nome, S);

}
void VisualizzaElemento(tipobaseList x){

printf("\n\nElemento ");

printf("\nCognome = %s ", x.cognome);

printf("\nNome = %s ", x.nome);

printf("\nEta' = %d \n\n",x.eta);

}
void ModificaElemento(tipobaseList * x){

printf("\nModifica l'Eta' = % d ",x->eta);

printf("\nInserisci la nuova Eta' ");

scanf("%d",&x->eta);

flush();

}
int Confronta(tipobaseList a, tipobaseList b){

if (!strcmp(a.cognome,b.cognome)) return strcmp(a.nome,b.nome);

else return strcmp(a.cognome,b.cognome);

}
position End(list l){

if (l==LISTAVUOTA) return(LISTAVUOTA);

while (l->next!=LISTAVUOTA)

l=l->next;

return(l);

}
position First(list l) {

return(LISTAVUOTA); /*se la lista è vuota torna END(l) */

}
void MakeNullList(list *l){

*l=LISTAVUOTA;

}
boolean EmptyList(list l){

return(l==LISTAVUOTA);

}
boolean FullList(list l){

return(0);

}
void InsertList(list *l, position p, tipobaseList x){

struct nodoList * temp;
if (!FullList(*l)) {

temp=(struct nodoList *) malloc(sizeof(struct nodoList));

temp->info=x;

if (p==LISTAVUOTA) {

temp->next=*l;

*l=temp;


} else {

temp->next=p->next;

p->next=temp;

}

}



}

void DeleteList(list *l, position p){

struct nodoList * tmp;
if (!EmptyList(*l) && p!=End(*l)) {

if (p==LISTAVUOTA) {

tmp=(*l)->next;

free (*l);

*l=tmp;

} else {


tmp=p->next;

p->next=tmp->next;

free (tmp);

}

}



}
position Locate(list l, tipobaseList x){
if (!EmptyList(l)) {

if (!Confronta(l->info,x)) return(LISTAVUOTA);

while (l->next!=LISTAVUOTA) {

if (!Confronta(l->next->info,x)) return(l);

l=l->next;

}

return(l);



}

}
tipobaseList Retrieve(list l, position p)

{

if (!EmptyList(l) && p!=End(l)) {



if (p==LISTAVUOTA) return(l->info);

else return(p->next->info);

}

}
position Next(list l, position p)



{

if (p!=End(l)) {

if (p==LISTAVUOTA) return(l);

else return(p->next);



}

}





: users -> scava -> dispense -> FdINO
FdINO -> 1. Definizione di Albero
users -> La montagna incantata, IL Purgatorio di Dante e IL pellegrino–viator alla rovescia, cioè lo statico residente Hans Castorp
users -> La geografia (giochi di tragitti, di percorsi, di territori e confini, cacce al tesoro, idee di distanze, di lunghezze) La psicomotricità
users -> Una possibile sequenza di attività (anche di tipo ludico) su questo tema può essere la seguente, sperimentata in una classe 5
users -> Le indagini più recenti del Ministero dell’Istruzione sui dati della dispersione scolastica arrivano a concludere che la dispe
users -> Lezione 2 L'italiano d'oggi: le varietà funzionali, situazionali e strutturali
users -> Distinguiamo tra dimostrazione ed argomentazione; la prima ha carattere di certezza e di incontrovertibilità è usata nella ri
FdINO -> Struttura dati Coda
FdINO -> Abstract Data Type (adt) pila
dispense -> Università degli studi di catania facoltà di Ingegneria




©astratto.info 2017
invia messaggio

    Pagina principale