Gli alberi strutture Dati Astratte alberi Generali



Scaricare 166.93 Kb.
Pagina3/3
17.11.2017
Dimensione del file166.93 Kb.
1   2   3


succ(oggi) gio

prec(oggi)  mar

ord(oggi)  2

Si noti solo che i numeri d’ordine partono da 0 (non da 1) e che l’elenco non è ciclico, per cui succ(dom) non è lun, ma produce una segnalazione di errore.

----------
Possiamo ora tornare al nostro programma. Esso comprende tre procedure:


  1. La locate trova un nodo (data l’etichetta) nell’albero costruito fino ad ora (è quella che trova sempre lo stesso ‘z’, anche se ce ne sono più d’uno)

  2. La addDaughter, dato un nodo genitore e un nodo figlio, inserisce il figlio (se il genitore non ne ha già 10)

  3. La readTree, che fa la vera e propria lettura (usando la locate per trovare il genitore, la new per allocare lo spazio nello heap per il nuovo figlio e la addDaughter per legare il genitore al figlio).

La locate ricalca esattamente la lettura in preordine di un albero. Ho solo aggiunto la variabile booleana found, che dice quando, in un sottoalbero, è stata trovata l’etichetta cercata, per evitare l’inutile ricerca negli altri sottoalberi (questo, ovviamente, non ha senso nella preorder, poiché in quel caso tutti i sottoalberi vanno percorsi per effettuare la stampa).


La addDaughter cerca, nella array di puntatori del padre, il primo puntatore NIL e lo sostituisce con il puntatore al nuovo figlio. Se tutti i puntatori sono diversi da NIL, segnala un errore (manyDaughters).
La readTree è un ciclo while di lettura da file. Suppongo che nel file di input ogni riga corrisponda a un arco. La funzione eof(f) dà True se siamo in fondo al file (eof sta per End Of File), e quindi not eof(f) è vero se ci sono ancora righe da leggere. Le righe del file sono nella forma:

x y


in cui x è l’etichetta del genitore e y quella del figlio. Questo comporta un piccolo problema di lettura, perché lo spazio che separa x da y è un carattere come tutti gli altri. Se io faccio

readln (f, upLabel, downLabel);

la readln, che sa che upLabel e downLabel sono di tipo char, assegna ‘x’ a upLabel e ‘ ‘ (cioè lo spazio) a downLabel. Per evitare che questo succeda, possiamo fare due cose: o inserire i dati nella forma

xy

e cioè senza spazio (ma questo non sembra molto leggibile), oppure far leggere tre caratteri, il secondo dei quali (lo spazio) non sarà più usato. Io ho adottato la seconda soluzione, facendo leggere anche la variabile blank. A questo punto si crea il figlio (new) inserendo la nuova etichetta e mettendo a NIL tutti i puntatori. Questa è un’operazione importante, perché altrimenti i puntatori non hanno un valore e non si può controllare se sono NIL. Si controlla poi se upLabel è ‘*’. In questo caso si sta introducendo la radice. Questo comporta l’assegnazione alla variabile root (passata per riferimento, per cui l’assegnazione viene in realtà effettuata su una variabile del main) del nodo appena creato, dopo aver verificato che root non abbia già un valore (nel qual caso, nel file, c’è più di una radice). Se upLabel non è ‘*’, si cerca il nodo con etichetta upLabel nell’albero (locate) e si aggiunge il nuovo figlio (addDaughter).


Le varie procedure effettuano vari controlli, fanno delle stampe intermedie che permettono di seguire quello che succede nel corso dell’esecuzione e, se necessario, impostano la variabile error. Il main richiama readTree, stampa ‘Lettura terminata’ e poi, se non ci sono stati errori (la variabile error ha ancora il valore originale ok) stampa in preordine l’albero letto.
program alberi;
const maxDaughters = 10;
type nodePointer = ^treeNode;

treeNode = record

nodeLabel: char;

daughters: array[1..maxDaughters] of nodePointer;

father: nodePointer

end;


errorCode = (ok, manyroots, nofather, manydaughters);
var treeroot: nodePointer; error: errorCode;
function locate (tree: nodePointer; nlabel: char): nodePointer;

var found: boolean; i: integer; temp, nextd: nodePointer;

begin

found := false;



if tree = NIL

then locate := NIL

else

begin


if tree^.nodeLabel = nlabel

then locate := tree

else

begin


locate := NIL;

i := 1;


while (i <= maxDaughters) and

(tree^.daughters[i] <> NIL) and

(not found) do

begin


temp := locate (tree^.daughters[i], nlabel);

if temp <> NIL

then

begin


found := true;

locate := temp

end

else i := i+1



end

end


end

end;
procedure addDaughter (father, daughter: nodePointer; var err: errorCode);

var i: integer; done: boolean;

begin


i:= 0;

done := false;

while (i <= maxDaughters) and (not done) do

begin


if i=maxDaughters

then


begin

writeln (father^.nodelabel, ' ha troppi figli');

err:= manydaughters;

i := i+1;

readln

end


else

begin


i := i+1;

if father^.daughters[i] = NIL

then

begin


done:= true;

father^.daughters[i] := daughter

end

end


end

end;
procedure readtree (var root: nodePointer; var error: errorCode);

var f: text; nextNode: nodePointer; upLabel, downLabel, blank: char;

i: integer;

begin

assign (f, 'treedata.dat');



reset (f);

while not eof(f) do

begin

readln (f, upLabel, blank, downLabel);



readln;

writeln ('Genitore:', upLabel, ' ; figlio: ', downLabel);

new (nextNode);

for i := 1 to maxDaughters do nextNode^.daughters[i] := NIL;

nextNode^.nodeLabel := downLabel;

if uplabel = '*'

then

if root = NIL



then

begin


nextNode^.father := NIL;

root := nextNode

end

else


begin

writeln ('Errore: più' di 1 radice');

error := manyroots;

readln


end

else


begin

nextnode^.father := locate (root, upLabel);

if nextNode^.father = NIL

then


begin

writeln ('Errore: figlio definito prima del padre');

error := nofather;

readln


end

else


begin

writeln ('locate; trovato padre di ', downLabel);

addDaughter (nextNode^.father, nextNode, error)

end


end

end


end;
procedure preorder (root: nodePointer);

var i: integer;

begin

if root <> NIL then



begin

i := 1;


writeln (root^.nodeLabel);

while (i <= maxDaughters) and (root^.Daughters[i] <> NIL) do

begin

preorder (root^.Daughters[i]);



i := i+1

end


end

end;
begin

error := ok;

readtree (treeRoot, error);

writeln ('Lettura terminata');

readln;


if error = ok then

begin


writeln ('Risultato lettura in preordine:');

preorder (treeRoot)



end;

readln


end.


1 Di norma per Struttura Dati Astratta si intende l’organizzazione dei dati unitamente alle operazioni fondamentali definite sui dati stessi.

2 Questo non è del tutto preciso. In realtà, i vari programmi di Merge Sort sono realizzazioni di ‘specializzazioni’ diverse dell’algoritmo fondamentale: ad un certo livello di dettaglio (astrazione) sono lo stesso algoritmo, ad un altro livello sono algoritmi differenti.

3 Si ricordi che nelle definizioni ‘astratte’ non è previsto nessun massimo! Il vincolo che io sto utilizzando dipende solo dal fatto che abbiano deciso di utilizzare, per la memorizzazione dei figli, una array di puntatori.

4 Vi suggerisco di leggere attentamente le poche righe che seguono. Il problema si pone per strutture dati anche più complesse degli alberi e, in un certo senso, anche per sistemi applicativi quali le basi di dati.



1   2   3


©astratto.info 2017
invia messaggio

    Pagina principale