Strutture dati in C
dispense del corso di
Laboratorio di Algoritmi e Strutture Dati A.A. 2001/2002
prima parte
(versione molto ma molto draft)
Gianfranco Ciaschetti
127 maggio 2002
1
Dipartimento di Matematica Pura e Applicata, Universitµ a degli Studi di
L'Aquila, via Vetoio, Coppito, I-67010 L'Aquila; e-mail: ciasc@univaq.it
Indice
1 Insiemi e oggetti 2
2 Liste 6
2.1 Inserimento . . . . 7
2.2 Ricerca . . . . 9
2.3 Cancellazione . . . 10
3 Code e Pile 13 3.1 Implementazione con array . . . 13
3.1.1 Pile . . . 15
3.1.2 Code . . . 16
3.2 Implementazione con liste . . . 18
3.2.1 Pile . . . 18
3.2.2 Code . . . 19
4 Alberi 22 4.1 Visita di un albero in profonditµa . . . 24
4.2 Visita di un albero in ampiezza . . . 27
4.3 Inserimento e cancellazione . . . 30
1
Capitolo 1
Insiemi e oggetti
Nella progettazione di algoritmi spesso si ha bisogno di rappresentare oggetti e insiemi di oggetti. Ogni oggetto µe descritto all'interno di un calcolatore da un set di informazioni che ne rappresentano le proprietµa e/o le caratter- istiche. Possiamo allora pensare a un oggetto come a una generica porzione di memoria in cui le sue informazioni sono archiviate. A seconda del numero e del tipo di informazioni che intendiamo associare a ogni oggetto, esso puµo occupare piµ u o meno spazio in memoria. L'oggetto x puµo essere indicato tramite il contenuto o l'indirizzo delle locazioni di memoria in cui le sue in- formazioni sono memorizzate. In C, nel primo caso l'oggetto µe rappresentato da una variabile, nel secondo caso da un puntatore.
Il linguaggio C mette a disposizione un certo numero di tipi prede¯niti per la rappresentazione di oggetti con una singola informazione (interi, reali, caratteri, ecc.), oltre a un tipo array per l'aggregazione di oggetti dello stesso tipo e un tipo struct per l'aggregazione di oggetti di tipo diverso. Sia gli array che le strutture hanno l'e®etto di de¯nire locazioni di memoria contigue nelle quali gli oggetti sono memorizzati.
Ad esempio, se vogliamo de¯nire un oggetto di tipo intero basta dichiarare una variabile di tipo intero o puntatore a intero, come
int o;
int *po;
oppure, se vogliamo de¯nire un insieme omogeneo di 10 interi, dichiariamo una variabile
int A[10];
2
o ancora, per realizzare una struttura con un intero e un carattere, struct ascii
{
int code;
char c;
}
I nomi o, po, A e ascii sono nomi di variabili, e come tali possono essere de¯niti come stringhe arbitrarie.
Array e strutture sono collezioni statiche di oggetti, in quanto non perme- ttono di inserire o cancellare altri oggetti oltre quelli speci¯cati all'atto della dichiarazione (o dell'allocazione, se un array µe de¯nito come un puntatore).
Tuttavia molto spesso si richiede di disporre di una struttura dati che rappresenti un insieme dinamico, il cui numero di elementi puµo variare nel tempo. Per incrementare il numero n di elementi di un'array, una volta che esso µe allocato in memoria, occorre allocare una nuova porzione di memoria per n + 1 oggetti e copiare l'intero contenuto dell'array precedente nel nuo- vo. Ad esempio, per poter aggiungere un elemento all'array A dell'esempio precedente, si puµo , de¯nita una funzione Reallocate che prende in ingresso un array di interi (tramite due parametri, il nome dell'array e la sua dimen- sione) e il numero di elementi da aggiungere, e®ettuare la seguente chiamata di funzione:
int* Reallocate(int *p, int cur_dim, int grow_factor) {
int *A_primo = (int*)malloc((cur_dim + grow_factor)*sizeof(int));
for (int i=0; i<cur_dim; i++) A_primo[i] = A[i];
return A_primo;
}
A = Reallocate(A, 10, 1);
Gli insiemi dinamici di oggetti hanno diverse caratteristiche a seconda del
tipo di operazioni che su di esso si intendono fare. Un tipo di dato astratto
(TDA) rappresenta un insieme dinamico e il set di operazioni che su di esso
si intendono eseguire. Le operazioni tipiche sono di interrogazione (ricerca
di un oggetto, numero di oggetti presenti, ecc.) o di modi¯ca dell'insieme
(inserimento, cancellazione, modi¯ca di un oggetto, ecc.). Il mantenimen- to in memoria di un TDA per la rappresentazione di insiemi dinamici puµo richiedere che in un oggetto siano presenti, oltre alle informazioni che lo iden- ti¯cano, un certo numero di informazioni aggiuntive che permettono la sua aggregazione nell'insieme. Ad esempio, la struttura
struct nodo {
int info;
struct nodo *next;
}
puµo essere usata per realizzare una lista lineare di oggetti, ognuno collegato al proprio successore nella lista. Le liste saranno presentate nel x??.
La scelta del TDA da utilizzare per rappresentare insiemi dinamici dipende principalmente dal tipo di operazione che si intende fare sull'insieme, e ha in°uenza sull'e±cienza di un eventuale algoritmo che deve usare tale in- sieme di informazioni. Ad esempio, la ricerca di un elemento speci¯co in una lista richiede che tutti gli elementi vengano esaminati linearmente, e perciµo richiede un tempo computazionale pari a O(n). Se l'operazione di ricerca di un elemento µe ripetuta molte volte in un algoritmo, si potrebbe scegliere di utilizzare strutture (TDA) piµu e±cienti per questa operazione, come ad esempio alberi bilanciati. In questo contesto, a meno che non sia esplicita- mente detto il contrario, utilizziamo un'analisi asintotica del caso peggiore per determinare l'e±cienza di un'operazione in una struttura dati.
Riprendendo l'esempio precedente, se anzich¶e un solo intero volessimo memorizzare per ogni oggetto della lista tutte le informazioni relative a un impiegato, potremmo dichiarare un oggetto del tipo:
struct object {
int matricola;
char nome[20];
char cognome[20];
char sesso;
long stipendio;
struct object *next;
};
Alternativamente, per mantenere la struttura lista collegata piµ u leggera, possiamo memorizzare in essa solo il puntatore all'oggetto anzich¶e l'oggetto stesso. In questo caso, dovremmo de¯nire l'oggetto impiegato con le sue sole informazioni, cio¶e senza il campo next, e dichiarare un nuovo oggetto per la nostra lista
struct my_object {
struct object* o;
struct my_object *next;
};
Le liste che vengono realizzate con le due diverse dichiarazioni sono rap- presentate in ¯gura 1.1.
nome cognome
sesso stipendio
nome cognome
sesso stipendio
nome cognome
sesso stipendio
nome cognome
sesso stipendio
nome cognome
sesso stipendio
nome cognome
sesso stipendio
nome cognome
sesso stipendio
nome cognome
sesso stipendio
Figura 1.1: Una lista di oggetti di tipo impiegato una di puntatori a oggetti di
tipo impiegato
Capitolo 2 Liste
Una lista (o lista collegata o lista lineare) µe una struttura dati in cui gli oggetti sono organizzati in un ordine lineare. Ogni oggetto della lista contiene informazioni proprie piµ u un puntatore all'oggetto successivo.
A di®erenza degli array, la dimensione di una lista non µe nota a priori (negli array, ricordiamo, la dimensione µe speci¯cata all'atto della dichiarazione o dell'allocazione esplicita di memoria), ma varia nel tempo man mano che gli oggetti sono inseriti o cancellati dalla lista.
Una lista µe univocamente determinata mediante una variabile di tipo puntatore che contiene l'indirizzo del primo oggetto della lista. Gli altri oggetti possono essere individuati scorrendo la lista mediante i puntatori agli elementi successivi. In quanto segue, supponiamo senza perdita di generalitµa che ogni oggetto contenga una sola informazione di tipo intero, come nella dichiarazione che segue:
struct elem {
int info;
struct elem *next;
}
Per il TDA lista lineare, de¯niamo le seguenti operazioni:
² inserimento
² cancellazione
² ricerca
6
Ognuna di queste operazioni µe implementata in modo diverso a seconda che la lista sia mantenuta ordinata (rispetto al campo info oppure no.
2.1 Inserimento
Se la lista non µe ordinata, scegliamo di inserire un elemento in testa alla lista, in modo da minimizzare il numero di operazioni elementari da compiere.
Siano de¯nite, oltre all'oggetto elem, le seguenti variabili:
elem *piniz; /* puntatore al primo oggetto della lista */
elem *p; /* puntatore a un oggetto generico */
15 10 7 21
12
piniz
15 10 7 21
piniz
12 p
Figura 2.1: Inserimento in testa a una lista lineare
Tutto quello che occorre fare, una volta creato il nuovo elemento da in- serire, e allocata memoria per esso, µe aggiornare opportunamente i puntatori come mostrato in ¯gura 2.2, cio¶e eseguire le seguenti istruzioni:
/* alloca memoria per il nuovo oggetto e inserisci dati di informazione */
p = (elem*) malloc (sizeof(elem));
p->info = 12;
/* aggiorna puntatori */
p->next = piniz;
piniz = p;
Se invece la lista µe ordinata, allora l'inserimento richiede che il nuovo oggetto venga collocato nella posizione opportuna nella lista. Senza perdi- ta di generalitµa , supponiamo che la lista non possa presentare ripetizioni (elementi con stessa informazione).
3 10 13 21
12
piniz
3 10 13 21
piniz
12
r q
p
Figura 2.2: Inserimento in una lista lineare ordinata
Bisogna prima trovare il punto di inserimento del nuovo oggetto (imme- diatamente prima dell'elemento che contiene l'informazione maggiore della sua) e poi e®ettuare la modi¯ca dei puntatori.
/* alloca memoria per il nuovo oggetto e inserisci dati di informazione */
p = (elem*) malloc (sizeof(elem));
p->info = 12;
/* trova il punto di inserimento */
struct elem *q = piniz, *r = piniz;
while (q->info < p->info) {
r = q;
q = q->next;
}
/* aggiorna puntatori */
/* r e q sono il predecessore e il successore del nuovo elemento p*/
r->next = p;
p->next = q;
Si noti che abbiamo dovuto utilizzare due variabili di tipo puntatore perch¶e altrimenti, una volta identi¯cato l'elemento q, non abbiamo modo di recuperare la locazione di memoria dove scrivere il puntatore all'elemento da inserire. Questo problema non si presenta se al posto di liste lineari uti- lizziamo liste doppie, contenenti sia il puntatore all'oggetto successivo sia il puntatore all'oggetto precedente. In questo caso, la struttura dell'oggetto diventa la seguente:
struct elem {
int info;
struct elem *next;
struct elem *prev;
}
e le istruzioni per l'inserimento in una lista ordinata diventano le seguenti (si veda la ¯gura 2.3):
struct elem *q = piniz;
/* trova il punto di inserimento */
while (q->info < p->info) q = q->next;
/* aggiorna puntatori */
q->prev->next = p;
p->prev = q->prev->next;
p->next = q;
q->prev = p;
A partire da una lista doppia, si possono de¯nire liste circolari facendo puntare il predecessore del primo elemento all'ultimo elemento della lista, e il successore dell'ultimo al primo.
2.2 Ricerca
La ricerca di un elemento in una lista viene fatta scandendo tutti gli elementi
della lista ¯no a trovare quello che contiene l'informazione interessata, se
esiste, o ¯no alla ¯ne della lista. Nel codice che segue, supponiamo ancora che
p sia il puntatore all'elemento da inserire, e piniz il puntatore all'elemento
iniziale della lista.
12
piniz
piniz
3 10 13 21
3 10 13 21
12
q q->prev
p
Figura 2.3: Inserimento in una lista doppia ordinata struct elem* Ricerca(int k)
{
struct elem *q = piniz;
while (q != NULL) if (q->info != k)
q = q->next;
else break;
return q;
La procedura di ricerca restituisce un puntatore all'elemento cercato, se es- so µe presente nella lista, altrimenti il puntatore nullo NULL. Qui descrivi- amo la procedura generale nel caso delle liste lineari, lasciando per esercizio l'implementazione dell'operazione di cancellazione nel caso delle liste doppie o circolari.
2.3 Cancellazione
La cancellazione di un elemento, come per l'inserimento in una lista ordi-
nata, prevede due fasi: prima si deve identi¯care l'elemento da cancellare,
e poi modi¯care opportunamente i puntatori (ed eventualmente cancellare
l'elemento dalla memoria, se non serve piµu ). Il procedimento µe illustrato in
Fugura 2.4
void Delete(int k) {
/* trova l'elemento da cancellare */
struct elem *q = piniz, *r = piniz;
while (q->info != p->info) {
r = q;
q = q->next;
}
/* aggiorna puntatori */
r->next = q;
/* cancella oggetto dalla memoria */
free p;
3 10 13 21
piniz
3 10 13 21
piniz
r q
p
Figura 2.4: Cancellazione di un elemento da una lista lineare
La procedura di cancellazione descritta non considera il caso in cui l'elemento da cancellare non µe presente nella lista. Si lascia allo studente per esercizio il compito di descrivere la procedura completa.
Solitamente, si usa inserire all'inizio della lista un oggetto ¯ttizio (dum-
my) per evitare di eseguire i controlli necessari per i casi particolari in
cui l'elemento da cancellare si trovi all'inizio o alla ¯ne della lista. Tut-
tavia, la presenza di un oggetto dummy non riduce la complessitµa asintotiva
dell'operazione.
A titolo di esempio, presentiamo il codice per la costruzione di una lista lineare di 10 elementi.
#include<stdio.h>
#include<stdlib.h>
struct elem { int info;
struct elem *next;
}
void main() {
struct elem *p, *piniz;
int k, i;
for(i=0; i<10; i++) {
printf("\n%d -esimo elemento", i);
scanf("%d", &k);
p = (struct elem *)malloc(sizeof(elem));
p->info = k;
p->next = piniz;
piniz = p;
}
}
Capitolo 3 Code e Pile
Code e pile sono particolari struture dati astratte che permettono di inserire ed estrarre elementi solo in determinate posizioni. In particolare, una coda µe gestita in modo FIFO (¯rst-in-¯rst-out), mentre una pila µe getita in modo
LIFO (last-in-¯rst-out).
Le operazioni consentite in queste strutture sono le seguenti:
push inserimento pop estrazione
Per le code l'inserimento avviene in coda alla struttura, e l'estrazione in testa, mentre per le pile si inserisce e si estrae sempre in testa alla struttura.
Code e pile possono essere realizzate sia tramite array che tramite liste.
Discuteremo l'implementazione delle funzioni push e pop in entrambi i casi.
3.1 Implementazione con array
Se pile e code vengono implementate tramite array, occorre che il numero di elementi presenti nella pila o nella coda sia sempre inferiore alla dimensione dell'array, a meno di riallocazioni di memoria. Come mostrato in ¯gura 3.2, occorre mantenere due indici head e tail per rappresentare la coda con un array, mentre basta solo l'indice head per la pila.
13
push pop pop
push
LIFO FIFO
Figura 3.1: Pile e Code
top
head
tail
pile code
1 3 4 8 1 1
1
4 1 1
3 5 7
Figura 3.2: Implementazione di pile e code tramite array
3.1.1 Pile
Per descrivere le operazioni di inserimento e cancellazione in una pila, sup- poniamo di costruirire una pila utilizzando un array A con 100 posizioni, e di chiamare top l'indice di testa della pila. Vediamo di seguito le istruzioni C che creano l'array, allocano memoria per esso, inizializzano l'indice
tt top, e realizzano le funzioni push e pop.
int A[100];
int top;
for(int k=0; k<100; k++) A[k] = 0;
top = -1;
void push(int i) {
if (top < 99) A[++top] = i;
else
printf("errore: pila piena");
}
int pop() {
if (top > 0)
return A[top--];
else
printf("errore: pila vuota");
}
Si puµo osservare che sia l'operazione di inserimento che quella di cancellazione aggiornano l'indice top al valore precedente o successivo. Se si vuole scandire l'intera pila, basta e®etture un ciclo for partendo da 0 ¯no al valore di top.
Se la lista µe vuota, nessuna istruzione interna al ciclo viene eseguita.
for(int k=0; k<top; k++)
...
3.1.2 Code
Anche per una coda, l'inserimento di un elemento comporta l'aggiornamento degli indici. In particolare, un inserimento aggiorna l'indice di testa, men- tre l'estrazione aggiorna l'indice di coda. Per descrivere queste oeprazioni, supponiamo di costruire una coda utilizzando un array A con 100 posizioni.
Vediamo di seguito le istruzioni C che creano l'array, allocano memoria per esso, inizializzano gli indici head e tail, e realizzano le funzioni push e pop.
int A[100];
int tail, head;
for(int k=0; k<100; k++) A[k] = 0;
head = -1;
tail = -1;
void push(int i) {
if (tail < 99) A[++tail] = i;
}
int pop() {
if (head > 0)
return A[--head];
}
Se si vuole scandire una coda, basta partire da uno dei due indici (ad esempio quello di testa) e raggiungere l'altro in un ciclo while, come nella seguente istruzione:
while(head < tail) {
int p = head;
...
p++;
}
Un modo pratico di realizzare liste µe tramite array circolari. In un array circolare, la coda della struttura coda rappresenta il primo elemento libero dell'array, secondo l'ordine circolare, come mostrato in ¯gura 3.3.
1 5 3 8
1 1 4 0
1 2
4 5 6
7 8 9 11 10
head = 3 3
tail = 9
Figura 3.3: Implementazione di code tramite array circolari
In questo caso, supponendo che l'array A ha n posizioni, le operazioni push e pop possono essere codi¯cate come segue:
head = 0;
tail = 0;
void push(int i) {
if (head == (tail+1)%n)
printf("errore: coda piena");
else {
A[tail] = i;
tail = (tail+1)%n;
} }
int pop() {
if (head == tail)
printf("errore: coda vuota");
else {
int k = A[head];
head = (head+1)%n;
return head;
} }
3.2 Implementazione con liste
Se invece che interi volessimo realizzare una pila o una coda di oggetti generici con piµu di un'informazione, ci potrebbe essere utile realizzare pile e code con delle liste collegate. Ogni elemento della lista contiene tutte le informazioni relative all'oggetto, e un puntatore all'oggetto successivo. Senza perdita di generalitµa , supponiamo per ora che ci sia solo un'informazione di tipo intero associata a ogni oggetto.
3.2.1 Pile
Una pila realizzata tramite una lista ha il puntatore top corrispondente al puntatore iniziale della lista, e le operazioni di inserimento e cancellazione vengono e®ettuate solo in testa alla lista.
struct elem { int info;
struct elem *next;
}
struct elem *top; /* come piniz */
void create() {
top = NULL;
}
void push(struct elem *p)
{
p->next = top;
top = p;
}
struct elem *pop() {
if (top != NULL) {
struct elem *p = top;
top = top->next;
return p;
else
printf("errore: pila vuota");
}
Si noti che nella implementazione di pile tramite liste non occorre e®etuare il controllo di pila piena, in quanto usiamo una struttura dati dinamica.
3.2.2 Code
Una coda realizzata tramite una lista ha il puntatore head corrispondente al puntatore iniziale della lista, mentre il puntatore tail punta all'ultimo elemento della lista.
struct elem { int info;
struct elem *next;
}
struct elem *head, *tail;
void create() {
head = NULL;
tail = NULL;
}
void push(struct elem *p) {
if (head == NULL) head = p;
else
tail->next = p;
tail = p;
}
struct elem *pop() {
if (head == NULL)
printf("errore: coda vuota");
else {
struct elem *p = head;
head = head->next;
return p;
} }
Come nell'implementazione tramite array, µe possibile de¯nire liste circo- lari come quella rappresentata in ¯gura 3.4, dove si illustra l'inserimento di un elemento.
In questo caso, le inizializzazioni sono le stesse che per le liste lineari, mentre le operazioni push e pop vanno riscritte come segue:
void push(struct elem *p) {
if (head == NULL) head = p;
else {
p->next = head;
tail->next = p;
tail = p;
}
}
15 10 7 21
tail head
8
Figura 3.4: Inserimento di un elemento in una coda implementata con lista circolare
struct elem *pop() {
if (head == NULL)
printf("errore: coda vuota");
else {
struct elem *p = head;
head = head->next;
tail->next = head;
return p;
}
}
Capitolo 4 Alberi
Un albero rappresenta la generalizzazione di una lista lineare, in cui un el- emento puµo avere piµu di un successore. Ogni elemento si chiama nodo e dispone dei puntatori ai suoi successori, ed eventualmente al predecessore.
Seguendo una terminologia genealocica, il predecessore del nodo in un albero si chiama padre, i successori ¯gli, e cosµ³ via. Il nodo che non ha predecessori µe detto la radice dell'albero, mentre quelli che non hanno successori sono detti foglie. In un albero ogni elemento ha un solo predecessore.
Un albero µe detto n-ario se ogni elemento ha al piµ u n ¯gli. In fugura 4.1 sono mostrati un esempio di albero binario (4.1-a) e uno n-ario generico (4.1- b). Un albero µe identi¯cato per mezzo della propria radice, ossia il puntatore all'oggetto che µe in tale posizione.
Se l'albero µe binario, allora basta usare due variabili di tipo puntatore per memorizzare i ¯gli di ogni nodo. Supponendo ancora, senza perdita di generalitµa , di memorizzare una sola informazione per nodo, descriviamo l'implementazione del tipo nodo.
struct nodo { int info;
struct nodo *left;
struct nodo *right;
struct nodo *parent;
}
Per ogni nodo, il puntatore left punta al suo ¯glio sinistro (eventual- mente NULL se si tratta di una foglia), right al suo ¯glio destro e parent al genitore. L'informazione sul genitore non µe sempre necessaria.
22
(a)
(b)
Figura 4.1: Alberi binari e n-ari
Se invece l'albero puµo avere piµu successori per ogni nodo, e il numero µe variabile, dobbiamo memorizzare i puntatori ai ¯gli in un array e speci¯carne le dimensioni. La dichiarazione del tipo nodo sarµa allora del tipo:
struct nodo { int info;
struct nodo **sons;
int numsons;
}
Si potrµa in questo caso indicare l'i-esimo ¯glio del nodo puntato da p con l'espressione p->sons[i-1].
Si de¯nisce altezza di un nodo x dell'albero il numero massimo di archi (puntatori) che occorre percorrere, a partire da x, per raggiunge una sua foglia. Si de¯nisce inoltre altezza dell'albero l'altezza della sua radice.
In generale, gli alberi sono usati perch¶e , a di®erenza delle liste, per- mettono di avere piµ u successori per ogni elemento, ma anche perch¶e , se organizzati opportunamente, danno luogo a operazioni piµ u e±cienti. In par- ticolare, un albero bilanciato di n elementi ha altezza log
2n e si vedrµa come µe possibile in alberi bilanciati realizzare operazioni di ricerca, inserimento e cancellazione in un tempo proporzionale all'altezza dell'albero, cio¶e in O(n).
Se l'albero non gode di particolari proprietµa , occorre in genere visitare
l'intero albero per cercare un dato elemento. Esistono due modi diversi per
visitare un albero:
² visita in profonditµa
² visita in ampiezza
4.1 Visita di un albero in profonditµ a
La visita di un albero in profonditµa prevede che, dato un nodo corrente x, si visiti successivamente il proprio sottoalbero sinistro (l'albero che ha come radice il ¯glio sinistro di x, x->left) e poi il proprio sottoalbero destro (l'albero che ha come radice il ¯glio destro di x, x->right). Nel caso di alberi n-ari, si visitano nell ordine i ¯gli del nodo corrente (x), x->sons[0], x->sons[1], ..., x->sons[numsons-1].
Questa strategia si puµo applicare ricorsivamente, a partire dalla radice, per tutti i nodi dell'albero. Mostriamo di seguito il codice per ricerca di un elemento di un albero binario e n-ario mediante visita in profonditµa . Per completezza, presentiamo sia la versione ricorsiva che quella iterativa.
struct b_nodo { int info;
struct b_nodo *left;
struct b_nodo *right;
}
struct n_nodo { int info;
struct n_nodo *left;
struct n_nodo **sons;
int numsons;
}
/* creazione degli alberi */
...
struct b_nodo *b_root;
struct n_nodo *n_root;
...
struct b_nodo* BRecDepthFirstSearch(int key)
{
struct nodo *p = b_root;
if (p->info == key) return p;
if (p->left != NULL)
DepthFirstSearch(p->left);
if (p->right != NULL)
DepthFirstSearch(p->right);
}
struct n_nodo* NRecDepthFirstSearch(int key) {
int i;struct nodo *p = b_root;
if (p->left != NULL)
for (i=0; i<p->numsons; i++) DepthFirstSearch(p->sons[i]);
if (p->info == key) return p;
}
struct b_nodo* BDepthFirstSearch(int key) {
char found = 0;
struct nodo *p = b_root;
if ((p->info == key) && (found != 0)) {
found = 1;
return p;
}
while ((p->left != NULL) && (found != 0)) {
p = p->left;
if (p->info == key) {
found = 1;
return p;
} }
while ((p->right != NULL) && (found != 0))
{
p = p->right;
if (p->info == key) {
found = 1;
return p;
} } }
struct b_nodo* NDepthFirstSearch(int key) {
char found = 0;
int i;
struct nodo *p = b_root;
if ((p->info == key) && (found != 0)) {
found = 1;
return p;
}
for (i=0; i<p->numsons; i++) {
p = p->sons[i];
if ((p->info == key) && (found != 0)) {
found = 1;
return p;
} } }
A titolo di esempio, si riporta in ¯gura 4.2 la sequenza di visita in pro-
fonditµa prodotta con le due funzioni date. Come si puµo notare, la ver-
sione ricorsiva della visita in ampiezza µe piµu agevole, poich¶e la struttura
oggetto-puntatore lista successivi si presta naturalmente alla de¯nizione
di funzioni ricorsive.
1
4
8 5
3
9
1, 3, 9, 4, 5, 8
1
10 5 7
11
8 2
13 6
3
1, 7, 11, 3, 13, 6, 8, 2, 10, 5
Figura 4.2: Visita in profonditµ a di un albero
4.2 Visita di un albero in ampiezza
La visita di un albero in ampiezza procede, a partire dalla radice (livello 0), visitando in sequenza tutti i nodi di uno stesso livello, per poi passare a tutti quelli del livello successivo. Nella ¯gura 4.3 si mostra la sequenza di visita in ampiezza di un albero.
Per realizzare questa operazione abbiamo bisogno, ogni volta che ci trovi- amo a un nodo corrente x, di memorizzare gli elementi successivi da visitare.
Mentre si visita il nodo padre di x, possiamo memorizzare i puntatori ai
¯gli in una sequenza, che verrµa visitata solo dopo che tutti i nodi al livello di x siano stati visitati. Mediante l'uso di una coda si realizza facilmente questa operazione: l'elemento corrente x µe in testa alla coda, poi ci sono tutti gli elementi dello stesso livello, e in¯ne vengono accodati i ¯gli di x. Il procedimento µe illustrato in ¯gura 4.3 per alberi binari.
Di seguito presentiamo il codice per la visita in ampiezza di un albero binario e un albero n-ario, nella sola versione iterativa.
struct b_nodo { int info;
struct b_nodo *left;
struct b_nodo *right;
}
1
4
8 5
3
9
1, 3, 4, 9, 5, 8
1 1 3 4
3 4 3 4 9
4 9 4
9 9 5 8
5 8 5 8 8
