Sistemi basati su conoscenza Conoscenza e ragionamento Prof. M.T. PAZIENZA a.a. 2013-2014.
Fondamenti di Informatica II Ingegneria Informatica / Automatica (A-I) Meccanica Prof. M.T. PAZIENZA...
-
Upload
carlotta-bono -
Category
Documents
-
view
217 -
download
0
Transcript of Fondamenti di Informatica II Ingegneria Informatica / Automatica (A-I) Meccanica Prof. M.T. PAZIENZA...
Fondamenti di Informatica IIIngegneria Informatica / Automatica (A-I)
Meccanica
Prof. M.T. PAZIENZAa.a. 2002-2003 – 3° ciclo
ListeUna lista è una struttura dati ricorsiva (formata da elementi
dello stesso tipo e collegati insieme) la cui lunghezza può variare dinamicamente.
I suoi elementi so no variabili dinamiche che vengono creati e/o distrutti a tempo di esecuzione producendo una struttura dati che cresce o diminuisce a seconda delle esigenze del programma in esecuzione.
E’ possibile implementare liste tramite array, ma ciò può avvenire solo quando si conoscono esattamente le dimensioni della lista.
Liste
Ogni elemento di una lista è definito come una struttura costituita da uno o più campi dati e da un campo puntatore contenente l’indirizzo dell’elemento successivo.
struct elem{ int info; elem * succ;};
Strutture concatenateUna struttura é detta concatenata quando é costituita, oltre che dai suoi normali membri, anche da uno o più membri aggiuntivi, dichiarati come puntatori alla struttura stessa. struct rec
{int info; rec*next; };
La definizione di una struttura concatenata é di solito accompagnata da un certo numero di funzioni, che hanno il compito di gestirla, cioè eseguire le operazioni di inserimento, di eliminazione e di ricerca di oggetti.
Liste
Ogni lista è definita da una variabile puntatore che punta al primo elemento della lista.
Nel caso di assenza di elementi (lista vuota) tale variabile puntatore assume valore NULL.
In una lista il campo puntatore dell’ultimo elemento assume sempre valore NULL.
Liste
0Dati
Puntatore alla lista
Puntatore al sucessivo
Ultimo elemento
DatiDati
struct rec { int info; rec* next;};
lis lis-> info lis->next
Tipi di Lista
Lista circolare (l’ultimo puntatore non ha valore NULL, ma punta al primo nodo)
Lista doppia (può essere visitata nei due sensi -> presenza di due puntatori per nodo)
Lista doppia circolare (il puntatore all’elemento successivo dell’ultimo nodo punta al primo elemento della lista e il puntatore all’elemento precedente del primo punta all’ultimo elemento della lista)
Allocazione dinamica di liste
L’allocazione dinamica della memoria si presta alla gestione di liste di oggetti, quando il loro numero non é definito a priori.
Queste liste possono aumentare e diminuire di dimensioni dinamicamente in base al flusso del programma, e quindi devono essere gestite in un modo più efficiente dell’allocazione di memoria permanente sotto forma di array
Liste concatenate
Una lista concatenata (linked list) é un insieme di oggetti, caratterizzati dal fatto di essere istanze di una struttura concatenata. In ogni oggetto, i membri puntatori alla struttura contengono l’indirizzo di altri oggetti della lista, creando così un “legame” fra gli oggetti e rendendo la stessa lista “percorribile”, anche se gli oggetti non sono allocati consecutivamente in memoria. Se la struttura possiede un solo membro puntatore a se stessa, la lista é detta single-linked, se ne possiede due, é detta double-linked.
Inserimento in testa
0
dato
0
dato
0
dato
tempprec* tempp= new rec;
tempp->info = dato;
tempp->next = lis;
lis = tempp;
lis
tempp
lis
tempp
lis
Estrazione dalla testa
rec* tempp= lis;
lis = lis->next;
tempp->next = NULL;
tempp
lis
tempp
lis
0
tempp
lis
Operazioni su liste
• Creazione della lista (vuota e successivi inserimenti)• Lettura di una lista• Stampa di una lista• Cancellazione di una lista
• Inserimento in lista• Estrazione da lista
Creazione della listaPer creare una lista, basta definirla, ovvero è sufficiente
creare il modo di riferirsi ad essa. L’unica cosa che esiste sempre della lista è la sua testa (o radice) ossia il puntatore al suo primo elemento.
Questa è l’unica componente allocata staticamente ed è inizializzata a NULL poiché all’inizio non punta a niente in quanto non ci sono elementi.
Es.:
rec* lis=NULL;
Puntatore alla lista
lis NULL
Creazione di un nuovo nodoLa creazione di un nuovo nodo (in qualunque fase dell’esistenza di una lista) avviene creando una nuova istanza della struttura tramite allocazione dinamica, utilizzando di solito un puntatore d’appoggio (tempp)
Es.:
rec* tempp = new rec;
tempp
info next
Assegnazione di valori ai campi datiL’assegnazione di valori ai campi dati si ottiene dereferenziando il puntatore al nodo e accedendo ai singoli dati, ovvero utilizzando direttamente l’operatore ->
Es.:
tempp->info=7;
tempp
info next
7
rec* LeggiListaR() { int val; cin >> val; if (val == 0) return NULL; else { rec* l = new rec; l->info = val; l->next = LeggiListaR(); return l; }}
Lettura listaversione ricorsiva
Nodo lista
Lettura di una listarec* LeggiListaI() { int val; cin >> val; if (val == 0) return NULL; else { rec* l = new rec; l->info = val; rec* ll = l; cin >> val; while (val != 0) { ll->next = new rec; ll = ll->next; ll->info = val; cin >> val; } ll->next = NULL; return l; }}
Lettura listaversione iterativa
void StampaListaR(rec* l){ if (l ==NULL) cout << endl; else { cout << l->info << ' '; StampaListaR(l->next); }}
Stampa listaversione ricorsiva
Nodo lista
Stampa di una listavoid StampaListaI(rec* l){ while (l != NULL) { cout << l->info << ' '; l = l->next; } cout << endl;}
Stampa listaversione iterativa
void CancellaListaR(rec*& l){ if (l != NULL) { CancellaListaR(l->next); delete l; l = NULL; }}
Cancellazione listaversione ricorsiva
Nodo lista
Cancellazione di una listavoid CancellaListaI(rec*& l){ while (l != NULL) { rec* ll = l; l = l->next; delete ll; } l = NULL;}
Cancellazione listaversione iterativa
#include <iostream.h>struct rec { int info; rec* next;};void main(){ rec* lis; lis = LeggiListaR(); StampaListaR(lis); CancellaListaR(lis); lis = LeggiListaI(); StampaListaI(lis); CancellaListaI(lis);}
Programma Chiamante
Esempio
Inserimento in lista
Le operazioni di inserimento di un elemento (ed analogamente quelle di cancellazione) possono avvenire secondo diverse modalità, (ovvero in diverse posizioni della lista) assumendo di volta in volta caratteristiche specifiche.
Inserimento di un nuovo elemento
In ogni caso l’inserimento di un nuovo elemento nella lista prevede sempre i seguenti passi:
1) Creazione di un nuovo nodo (allocazione dinamica)
2) Assegnazione di valori ai campi dati
3) Collegamento del nuovo elemento alla lista esistente
• aggiornamento del campo puntatore del nodo
• aggiornamento dei puntatori della lista
Queste due ultime operazioni caratterizzeranno la tipologia dell’ inserimento
Creazione di un nuovo nodoLa creazione di un nuovo nodo (in qualunque fase dell’esistenza di una lista) avviene creando una nuova istanza della struttura tramite allocazione dinamica, utilizzando di solito un puntatore d’appoggio (tempp)
Es.:
rec* tempp = new rec;
tempp
info next
Assegnazione di valori ai campi datiL’assegnazione di valori ai campi dati si ottiene dereferenziando il puntatore al nodo e accedendo ai singoli dati, ovvero utilizzando direttamente l’operatore ->
Es.:
tempp->info=7;
tempp
info next
7
Inserimento in testaIl caso più semplice è costituito dall’ inserimento in testa, in quanto si dispone di un riferimento esplicito a questa (il puntatore alla lista lis).
• Il campo next del nuovo nodo punterà allo stesso valore di lis
• lis punterà al nuovo nodo
tempp->next=lis;
lis=tempp;NB. Funziona anche se la lista è vuota!
Inserimento in testa
0
dato
0
dato
dato
tempp
tempp->next = lis;
lis = tempp;
lis
tempp
lis
tempp
lis 0
0
dato
0dato
0dato
tempp
lis
lis
lis
0
tempp
tempp
Inserimento in codaL’inserimento in coda è più complesso, in quanto non abbiamo un puntatore esplicito all’ultimo elemento, ma dobbiamo prima scorrere la lista per cercarlo. Supponiamo di averlo trovato e che sia il puntatore p:
Il campo next del nuovo nodo punterà a NULL (in quanto è l’ultimo)
Il campo next dell’ex ultimo nodo punterà al nuovo nodo
Es.:
tempp->next=NULL;
p->next=tempp;La lista vuota va gestita come un caso particolare!
Ricerca dell’ultimo elementoPer cercare l’ultimo elemento, possiamo scorrere la lista tramite un puntatore ausiliario p, inizializzato a lis.
Es:
rec* p= lis;
while (p->next != NULL) p=p->next;
Dove è l’errore ??
Ricerca dell’ultimo elementoLa condizione (p->next != NULL) nel caso la lista sia vuota conduce ad un errore fatale in quanto si sta dereferenziando un puntatore nullo.
Questo è un tipico errore che si fa nella gestione delle strutture dinamiche!!!
0lis 0lis
p
p->next
0p
p->next = ??
Ricerca dell’ultimo elementoLa procedura corretta è:
rec* p= lis;
while (p!=NULL && p->next != NULL) p=p->next;
0lis 0lis
p
p->next
0p
Inserimento in coda
0lis 0lis
p 0p
0datotempp 0datotempp
lis
p
0datotempp
lis
0p
0datotempp
tempp->next = p; (o NULL)
p->next = tempp; lis = tempp;
Inserimento in una posizione specifica
L’inserimento in una posizione specifica richiede preventivamente l’individuazione di tale posizione all’interno della lista e dipende dalla condizione che si vuole verificare, per cui dobbiamo prima scorrere la lista per determinarla.
Vediamo ad esempio come comportarsi per inserire i valori in ordine crescente.
Inserimento ordinato dei valori
Nel caso di inserimento in ordine crescente, la lista risultante deve rimanere in ogni momento ordinata.
Pertanto, all’inserimento di un nuovo valore, si dovrà scorrere la lista fino alla posizione corretta per l’inserimento (fin quando cioè il campo info dei nodi esistenti risulta minore del dato da inserire).
Ricerca di un elemento qualsiasi
La condizione più sicura da utilizzare in una ricerca è riferirsi direttamente al puntatore all’elemento nella condizione di scorrimento. In tal modo però si sorpassa l’elemento cercato. Per questo nella ricerca della posizione di inserimento si usano di solito due puntatori, p e q, che puntano rispettivamente all’elemento precedente e al successivo.
Es:rec* q= lis; rec* p= lis;while (q != NULL && q->info < tempp->dato) {p=q; q=q->next;}
Ricerca di una posizione specificarec* q= lis; rec* p= lis;
while (q != NULL && q->info < tempp->dato) {p=q; q=q->next;}
2lis
p
q
7tempp 8 0 10
2
0
5 0 6lis
p
q
Casi particolarirec* q= lis; rec* p= lis;
while (q != NULL && q->info < tempp->dato) {p=q; q=q->next;}
8lis
p
q
7tempp 9 0 10
0
0
0
lis
p
q
Se q==lis allora p non contiene l’elemento precedente
Inserimento ordinato dei valori
Quindi nel caso generale:
tempp-> next = q;p->next = tempp;
ma se q==lis (inserimento in testa)
lis=tempp
Inserimento ordinato dei valori
2lis
p
q
7tempp
8 0 10
2lis
p
q
7tempp
8 0 10
tempp->next =q
p->next =tempp
void instesta(rec*& lis, int a){ rec* p = new rec; p->info = a; p->next = lis; lis = p;}
Inserimento in testa
Inserimento in listavoid insfondo(rec*& lis, int a){ rec* p = lis; for (rec* q = p; q != NULL; q = q->next) p = q; q = new rec; q->info = a; q->next = NULL; if (p != NULL) p->next = q; else lis = q;}
Inserimento in coda
Inserimento in ordine crescente (info)void inscresc(rec*& lis, int a){ rec* p = lis; for (rec* q = p; q != NULL && q->info < a; q = q->next) p = q; rec* r = new rec; r->info = a; r->next = q; if (q != lis) p->next = r; else lis = r;}
Inserimento in ordine crescente
Eliminazione di un nodo dalla lista
L’eliminazione di un nodo dalla lista prevede:• Ricerca del nodo da eliminare (se necessaria)
• Salvataggio del nodo in una variabile ausiliaria (per passo 4)
• Scollegamento del nodo dalla lista (aggiornamento dei puntatori della lista)
• Distruzione del nodo (deallocazione della memoria)
In ogni caso, bisogna verificare che la lista non sia già vuota!
if (lis != NULL) …
Ricerca del nodo da eliminareDipende dalle esigenze del programma.
Come per l’inserimento, il caso più semplice è costituito dall’eliminazione del nodo di testa, in quanto esiste il puntatore lis a questo elemento.
Negli altri casi, si procede come per l’inserimento
Scollegamento del nodo dalla listaIndividuato il nodo, bisogna evitare che la sua rimozione spezzi la lista.
In generale, è necessario aggiornare il puntatore next dell’elemento precedente
lis 0
lis 0
lis 0
Eliminazione del nodo di testa
Bisogna aggiornare il puntatore alla testa lis che dovrà puntare al nodo successivo a quello da eliminare.
rec* tempp=lis; (salvataggio nodo da eliminare)
lis = tempp->next; (aggiornamento lista)
delete tempp; (distruzione nodo)
Eliminazione del nodo di codaBisogna aggiornare il campo next relativo al penultimo nodo, che ora diventa l’ultimo (e quindi assume valore NULL).Per la ricerca dell’ultimo elemento si usano due puntatori p e q, che puntano rispettivamente al penultimo e all’ultimo elemento.La condizione sarà: rec* q= lis; rec* p= lis;while (q != NULL && q->next != NULL) {p=q; q=q->next;}
Casi particolari: l’elemento da eliminare è l’unico della lista.
Eliminazione del nodo di codarec* q= lis; rec* p= lis;
while (q != NULL && q->next != NULL) {p=q; q=q->next;}
lis
p
q
0
0 lis
p
q
Se q==lis allora p non contiene l’elemento precedente
Eliminazione del nodo di coda
lis
p
q
0
tempp
lis
p
q
0 0
tempp
rec* tempp =q;
p->next =
tempp->next;oppurep->next = NULL;
Eliminazione del nodo di coda
lis
p
q
0
tempp
tempp
rec* tempp = q;
lis = tempp->next;oppurelis = NULL;
lis
p
q
0 0
BOOL esttesta(rec*& lis, int& a){ rec* p = lis; if (lis != NULL) { a = lis->info; lis = lis->next; delete p; return T; } return F;}
Estrazione dalla testa
Estrazione da lista
Estrazione da listaBOOL estfondo(rec*& lis, int& a){ rec* p = lis; if (lis != NULL) { for (rec* q = p; q->next != NULL; q = q->next) p = q; a = q->info; if (q == lis) lis = NULL; else p->next = NULL; delete q; return T; } return F;} Estrazione dal fondo
Estrazione da listaBOOLEAN togli(rec*&lis, int a){ rec* p = lis; for (rec* q = p; q != NULL && q->info != a; q = q->next) p = q; if (q != NULL) { if (q == lis) lis = p->next; p->next = q->next; delete q; return T; } return F;}
Estrazione di un elemento specifico
Inserimento in listavoid insfondoR(rec*& lis, int a){ if (lis != NULL)
insfondoR(lis->next,a); else {
rec* p = new rec;p->info = a;p->next = NULL;lis=p
}}
Inserimento in fondoversione ricorsiva
void inscrescR(rec*& lis, int a){ if (lis != NULL && lis->info < a)
inscrescR(lis->next,a); else {
rec* p = new rec;p->info = a;p->next = lis;lis=p
}}
Inserimento in ordineversione ricorsiva
Estrazione da listaBOOL estfondoR(rec*& lis, int& a){ if (lis != NULL) { if (lis->next != NULL)
return estfondoR(lis->next,a); else {
a= lis->info; delete lis; lis = NULL; return T;
} } else return F;}
Estrazione dal fondoversione ricorsiva
BOOL togliR(rec*& lis, int a){ if (lis != NULL) {
if (lis->info != a) return togliR(lis->next,a);
else { rec* p = lis; lis = lis->next; delete p; return T;
} } else return F;}
Estrazione di un elemento specificoversione ricorsiva