Linguaggio C by Brian W. Kernighan & Dennis M. Ritchie

autore:Brian W. Kernighan & Dennis M. Ritchie [Kernighan, Brian W. & Ritchie, Dennis M.]
La lingua: ita
Format: epub
pubblicato: 2012-04-23T19:09:41+00:00

Supponiamo di volere gestire il programma più generale di contare le occorrenze di tutte le parole presenti in un particolare input. Poiché la lista delle parole non è nota a priori, non siamo in grado di ordinarla e di utilizzare la ricerca binaria.

Non possiamo neppure effettuare una ricerca lineare su ogni parola in input, per vedere se essa è già stata letta in precedenza: il programma risulterebbe troppo lungo (in particolare, il suo tempo d’esecuzione cre-scerebbe quadraticamente rispetto al crescere delle parole in input). Come possiamo organizzare i dati, in modo da gestire con efficienza una lista di parole arbitrarie?

Una soluzione consiste nel tenere sempre ordinato l’insieme delle parole lette fino ad un certo istante, collocando nella posizione corretta ogni parola in arrivo. Ciò non può essere fatto spostando le parole all’interno di un vettore lineare, perché anche questo procedimento risulterebbe eccessivamente lungo. Useremo invece una struttura dati detta albero binario.

L’albero contiene un “nodo” per ogni parola diversa; ogni nodo contiene: un puntatore al testo della parola

un contatore del numero di occorrenze

un puntatore al nodo figlio di sinistra

un puntatore al nodo figlio di destra

Ogni nodo può avere zero, uno o due figli, ma non di più.

I nodi vengono ordinati in modo che, per ognuno di essi, il sottoalbero di sinistra contenga parole lessicograficamente minori della parola contenuta nel nodo stesso, mentre il sottoalbero di destra contiene soltanto parole maggiori di quest’ultima.

Nella figura che segue è illustrato l’albero corrispondente alla frase “now is the time for all good men to come to the aid of their party”, costruito inserendo ogni parola non appena è stata letta: now

is

the

for

men of

time

all

good

party their to

108

aid

come

Per scoprire se una parola si trova già nell’albero, iniziamo dalla radice e confrontiamo la nuova parola con quella contenuta in quel nodo. Se esse sono uguali, la risposta al nostro quesito è affermativa. Se la nuova parola è minore di quella contenuta nel nodo in esame, la ricerca prosegue nel sottoalbero di sinistra, altrimenti in quello di destra. Se, nella direzione in cui dovrebbe proseguire la ricerca, non esistono ulteriori no-di, la nuova parola non è nell’albero, e la posizione vuota trovata è proprio quella in cui essa dev’essere inserita. Questo procedimento è ricorsivo, poiché la ricerca su ogni nodo è legata a quella su uno dei suoi figli.

Di conseguenza, le funzioni più adatte per l’inserimento e la stampa di elementi dell’albero sono di tipo ricorsivo.

Tornando alla descrizione di un nodo, possiamo dire che esso è ben rappresentato da una struttura avente quattro componenti:

struct tnode {

/* il nodo dell’albero */

char *word;

/* punta al testo */

int count;

/* numero di occorrenze */

struct tnode *left;

/* figlio di sinistra */

struct tnode *right;

/* figlio di destra */

};

La dichiarazione ricorsiva di un nodo può sembrare pericolosa, ma è corretta. Non è possibile dichiarare una struttura che contenga un’istanza di se stessa, ma

struct tnode *left;

dichiara che left è un puntatore ad un oggetto tnode, non un tnode stesso.

A volte, può essere necessario utilizzare una variante delle strutture ricorsive: due strutture che si riferiscono l’una all’altra. Il modo per gestire questi oggetti è il seguente: struct t {

….

scaricare

Disconoscimento:
Questo sito non memorizza alcun file sul suo server. Abbiamo solo indice e link                                                  contenuto fornito da altri siti. Contatta i fornitori di contenuti per rimuovere eventuali contenuti di copyright e inviaci un'email. Cancelleremo immediatamente i collegamenti o il contenuto pertinenti.