Fondamenti di Informatica IIIngegneria Informatica

Prof. M.T. PAZIENZAa.a. 2003-2004 – 3° ciclo

Liste concatenate

Una lista concatenata (linked list) è una sequenza lineare di oggetti connessi attraverso dei puntatori detti link.

L’acceso ad una lista concatenata avviene per mezzo di un puntatore al suo primo nodo; ai successivi si accede con il link all’elemento successivo immagazzinato in ogni nodo.

Gli elementi di una lista concatenata sono creati e memorizzati dinamicamente (solo quando necessario).

Si possono avere liste ramificate i cui elementi puntano ad intere liste.

Tutti gli elementi di una qualunque lista sono strutture dello stesso tipo per rendere agevoli le operazioni di scorrimento; il tipo del puntatore dipende infatti dal tipo dell’elemento puntato.

Code e pile

Le code e le pile sono anch’esse delle strutture dati lineari; possono essere considerate come liste concatenate con alcune restrizioni sulle modalità di accesso agli elementi (FIFO, LIFO).

Gli alberi sono strutture dati non lineari.

Coda (queue)

In una coda (queue) gli elementi sono gestiti esclusivamente con una politica FIFO (first-in, first-out), (es. coda allo sportello), ovvero si può eliminare un elemento

solo dalla testa della coda

e si può inserire

solo in fondo alla coda.

Coda

L'estremità della lista in cui è consentita l'estrazione è chiamata testa, o cima mentre l’estremità in cui avviene l’inserimento è chiamata coda, o fondo.

5 35-281-6

testa coda

Operazioni primitive sulla Coda

VUOTA(S): coda boolean. Test di CODA vuota.

  INCODA(S,x): coda, valore coda. Inserimento dell'elemento x in fondo alla coda.

Se S è la CODA a1, a2,…, an, INCODA(S,x) restituisce a1, a2,…, an, x e il nuovo elemento di coda è x.

  OUTCODA(S): coda coda. Eliminazione dell'elemento in testa alla coda.

Se S è la CODA a1, a2,…, an, OUTCODA(S) restituisce a2,a3,…, an e la nuova testa è rappresentata dalla posizione dell'elemento a2.

PRIMO(S) coda valore. Lettura dell'elemento in testa alla CODA.

Pile (stack)

Una pila o stack è una lista concatenata sulla quale i nuovi elementi possono essere aggiunti e/o rimossi soltanto dalla sua sommità (top), ovvero l’ultimo elemento ad entrare è anche il primo ad uscire (last-in, first-out LIFO)(es. pila di libri)

Le altre caratteristiche di lista restano inalterate: si punta ad una pila mediante un puntatore all’elemento in cima alla pila ed il membro di link dell’ultimo elemento è impostato a null per indicare la fine della pila.

Pila

L'estremità della lista in cui è consentito

l'inserimento e

l'estrazione

è chiamata top, o cima. 5

3

5

-2

8

1

-6

top

Operazioni primitive sulla Coda

VUOTA(S): coda boolean. Test di CODA vuota.

  INCODA(S,x): coda, valore coda. Inserimento dell'elemento x in fondo alla coda.

Se S è la CODA a1, a2,…, an, INCODA(S,x) restituisce a1, a2,…, an, x e il nuovo elemento di coda è x.

  OUTCODA(S): coda coda. Eliminazione dell'elemento in testa alla coda.

Se S è la CODA a1, a2,…, an, OUTCODA(S) restituisce a2,a3,…, an e la nuova testa è rappresentata dalla posizione dell'elemento a2.

PRIMO(S) coda valore. Lettura dell'elemento in testa alla CODA.

Inserimento di un nuovo elemento

L’inserimento di un nuovo elemento nella coda o nella pila prevede sempre i seguenti passi:

1) Creazione di un nuovo nodo (allocazione dinamica)2) Assegnazione di valori ai campi dati3) Collegamento del nuovo elemento alla struttura esistente

• aggiornamento del campo puntatore del nodo• aggiornamento dei puntatori della lista

Queste due ultime operazioni caratterizzeranno la tipologia dell’ inserimento in coda o in pila.

Creazione di un nuovo nodo

La creazione di un nuovo nodo 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 dati

L’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 testa alla pila (push)

Le operazioni di collegamento per l’inserimento in testa (push) alla pila, utilizzano il riferimento esplicito al top della pila (il puntatore alla pila lis).

• Il campo next del nuovo elemento punterà allo stesso valore di lis

• lis punterà al nuovo elemento

tempp->next=lis;lis=tempp;

Inserimento in testa alla pila (push)

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

Eliminazione di un elemento dalla testa della coda (dequeue)

L’eliminazione di un elemento dalla coda prevede:

• Salvataggio dell’elemento in una variabile ausiliaria (per passo 3)

• Scollegamento dell’elemento dalla testa della coda (aggiornamento dei puntatori della coda)

• Distruzione dell’elemento (deallocazione della memoria)

In ogni caso, bisogna verificare che la coda non sia già vuota!

if (lis != NULL) …

Eliminazione del nodo di testa della pila (pop)

Bisogna aggiornare il puntatore alla testa lis che dovrà puntare all’elemento successivo a quello da eliminare.

rec* tempp=lis; (salvataggio elemento da eliminare)

lis = tempp->next; (aggiornamento lista)

delete tempp; (distruzione elemento)

Eliminazione dell’elemento di testa della coda (dequeue)

Bisogna aggiornare il puntatore alla testa lis che dovrà puntare all’elemento successivo, ovvero a quello che ora è il secondo.

rec* tempp=lis; (salvataggio elemento da eliminare)

lis = tempp->next; (aggiornamento coda)

delete tempp; (distruzione elemento)

void instesta(rec*& lis, int a){ rec* p = new rec; p->info = a; p->next = lis; lis = p;}

push

Inserimento in pila e in codavoid 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;}

inqueue

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

Pop / Dequeue

Alberi

• Un albero è una struttura dati non lineare i cui nodi contengono due o più link.

• I nodi di un albero binario contengono esattamente due link.

• Il primo nodo di ogni albero si chiama radice e per definizione non discende da nessun altro nodo.

• Un nodo da cui non discende nessun altro nodo si chiama foglia.

Alberi

In ogni albero: • tutti i nodi ad eccezione delle foglie sono detti nodi

padre; • Tutti i nodi ad eccezione della radice sono detti nodi

figlio.

Ogni nodo padre può avere 0, 1,2,…n figli

Ogni nodo figlio può avere un solo padre.

Gli alberi n-ari possono avere un numero qualsivoglia di figli per ciascun nodo.

Gli alberi binari possono avere 0, 1, o al più 2 figli per ciascun nodo

Albero binario (def. ricorsiva)

Un albero binario è un insieme finito di nodi che:

• o è vuoto

• o è costituito da un nodo speciale detto radice e da due sottoinsiemi (disgiunti) di nodi che sono a loro volta alberi binari (sottoalbero sinistro e sottoalbero destro)

Albero binario

Un albero binario in C++ può essere rappresentato associando ad ogni nodo una struttura avente un campo informazione e due campi puntatore.

Il tipo di ogni nodo si può definire come:

struct nodo{ char inf; nodo* sin; nodo* des;

};

Albero binario ordinato per contenuto (inserimento)

Se l’albero è vuoto,

crea il nodo radice e inserisci l’informazione,

altrimenti

considera l’inserimento nel sottoalbero sinistro o destro a seconda che l’informazione da inserire sia minore o maggiore di quella contenuta nella radice (se l’informazione ha valore uguale a quello della radice, non viene effettuato l’inserimento).

Albero binario ordinato per contenuto (inserimento)

nodo* inserisci (nodo* r, int d){ if (r==0){ r=new nodo; r->inf=d; r->sin=0; r->des=0; }else if (d<r->inf) r-> sin=inserisci (r->sin,d);else if (d>r->inf) r-> des=inserisci (r->des,d);return r;

};

Visita di un albero

Per estrarre il valore di ciascun elemento (nodo) dell’albero binario, si effettua una operazione di visita, ovvero si esaminano tutti i nodi dell’albero in un certo ordine.

Le visite più significative sono:

visita in preordine

visita in postordine

visita in ordine simmetrico

Visita in preordine

Se l’albero non è vuoto,

visita la radice, visita in preordine il sottoalbero sinistro, visita in preordine il sottoalbero destro

void voa(nodo* r){if (r!=0)

{ cout << r->inf; voa(r->sin); voa(r->des); }};

Visita in postordine

Se l’albero non è vuoto,

visita in postordine il sottoalbero sinistro, visita in postordine il sottoalbero destro, visita la radice.

void vod(nodo* r){if (r!=0)

{ vod(r->sin); vod (r-> des);

cout << r->inf;}};

Visita in ordine simmetrico

Se l’albero non è vuoto,

visita in ordine simmetrico il sottoalbero sinistro, visita la radice , visita in ordine simmetrico il sottoalbero destro.

void vos(nodo* r){if (r!=0)

{vos(r->sin); cout << r->inf;

vos(r->des); }};