Algoritmi E Strutture Dati Alberi N Ari

ANALISI

Alberi n-ari:

Albero<Tipoelem> acquisisciFile(FILE *F), che applica a ciascun rigo del file di testo F il metodo

acquisisciElementoFile(F)

Albero<Tipoelem> acquisisciTastiera(), che applica a ciascun rigo letto da tastiera (fino a quando

l'utente non decide di finire) il metodo acquisisciElementoTastiera()

e generano un albero n-ario, in cui la radice dell'albero è fittizia (non contiene informazione), i nodi

intermedi sono caratteri dei campi Desinenza organizzati in modo da raggruppare i caratteri comuni,

e le foglie contengono i campi Radice, Uscita e POS associati alla desinenza corrispondente al

percorso che le lega alla radice. Ad esempio, il file:

(>=1)ar(e) "v-inf/pres"

(>=1)er(e) "v-inf/pres"

(=1)at(o,i) "s-m/sing,m/pl"

(=1)at(a,e) "s-f/sing,s/pl"

(>1)at(o,a,i,e) "v-part/pass"

genera l'albero:

*

+ r

| + a

| + {Radice: (> = 1); Uscita: (e); POS: (v - i n f / p r e s)}

| + e

| + {Radice: (> = 1); Uscita: (e); POS: (v - i n f / p r e s)}

+ t

+ a

+ {Radice: (= 1); Uscita: (o , i); POS: (s - m / s i n g , m / p l)}

+ {Radice: (= 1); Uscita: (a , e); POS: (s - f / s i n g , f / p l)}

+ {Radice: (> 1); Uscita: (o , a , i , e); POS: (v - p a r t / p a s s)}

void traduci(Albero<Tipoelem> A, FILE *F), che dato un albero A prodotto dal metodo

acquisisciFile(FILE *F) o acquisisciTastiera() ne stampa il contenuto su un file di testo F secondo la

sintassi del costrutto switch del C

Ad esempio, l'albero dell'esempio precedente viene tradotto in:

switch (c) {

case 'r': switch (c) {

case 'a': {

printf("Radice: (>=1); Uscita: (e); POS: (v-inf/pres)\n");

}

case 'e': {

printf("Radice: (>=1); Uscita: (e); POS: (v-inf/pres)\n");

}

}

case 't': switch(c) {

case 'a': {

printf("Radice: (=1); Uscita: (o,i); POS: (s-m/sing,m/pl)\n");

printf("Radice: (=1); Uscita: (a,e); POS: (s-f/sing,f/pl)\n");

printf("Radice: (>1); Uscita: (o,a,i,e); POS: (v-part/pass)\n");

}

}

}

Il problema proposto si suddivide in due sottoproblemi:

• Realizzare una funzione che preso in input un file composto da un numero non definito di

righe, ne restituisca una struttura gerarchica. Il file potrà contenere un qualsiasi numero di

stringhe di qualsiasi tipo.

• Realizzare una funzione che preso in input un numero di righe non definito, digitate da

tastiera dall’utente ne restituisca una struttura gerarchica. Le righe prese in input saranno

formate da una qualsiasi successione di caratteri.

In entrambe le funzioni le strutture gerarchiche restituite saranno composte dai seguenti valori:

• Nodo Radice della struttura : conterrà un valore fittizio (valore non rilevante al fine della

risoluzione del problema)

• Nodi Intermedi : considerando il formato della stringa conforme (OpNum)Suff(Fin), e che la

stringa sarà analizzata e scomposta nelle parti RADICE, DESINENZA, USCITA e POS, i

nodi intermedi conterranno i caratteri presenti in DESINENZA. I caratteri però saranno

organizzati in maniera tale che non ci saranno nodi intermedi uguali (si raggrupperanno i

caratteri comuni)

• Nodi Foglia : conterranno le restanti parti della stringa conforme (OpNum)Suff(Fin), ossia

RADICE, USCITA, e POS, in modo tale da essere gerarchicamente inferiori al carattere

della DESINENZA che congiunge quest’ultima alla radice.

Analizzando la prima funzione emergono i seguenti punti:

1. Cosa fare se il file da leggere risulta inesistente.

2. Cosa fare se il file risulta essere vuoto.

3. Cosa fare se nel file vi sono solo stringhe non conformi.

4. Come interpretare la fine di un rigo del file.

5. Come interpretare la fine del file.

Questi punti saranno cosi risolti:

1. Sarà avvisato l’utente tramite opportuno messaggio.

2. Visto che la stringa vuota risulterà essere conforme non vi saranno messaggi di errore

nel caso di file vuoto.

3. a

4. a

5. a

Analizzando la seconda funzione risultano i seguenti interrogativi:

1. Cosa succede se l’utente decide di non inserire nessuna stringa.

2. Come capire quando l’utente non vuole più inserire altre stringhe.

Altri problemi riguardanti entrambe le funzioni riguarderanno per lo più la struttura gerarchica

restituita in output e sono:

1. Come comportarsi in caso di struttura gerarchica vuota.

2. Come raggruppare i caratteri uguali, ossia se raggruppare le desinenze se sono

completamente uguali oppure per singolo carattere.

3. Quale simbologia adottare per mostrare all’utente il risultato della funzione.

PROGETTAZIONE

Specifica sintattica

TIPI:

albero

boolean

nodo

file

OPERATORI:

CREAALBERO: ( ) albero

ALBEROVUOTO: (albero) boolean

INSRADICE: (nodo, albero) albero

RADICE: (albero) nodo

PADRE: (nodo, albero) nodo

FOGLIA: (nodo, albero) boolean

PRIMOFIGLIO: (nodo, albero) nodo

ULTIMOFRATELLO: (nodo, albero) boolean

SUCCFRATELLO: (nodo, albero) nodo

INSPRIMOSOTTOALBERO: (nodo,albero,albero) albero

INSSOTTOALBERO: (nodo, albero, albero) albero

CANCSOTTOALBERO: (nodo, albero) albero

OPERATORI DI SERVIZIO

ACQUISISCIFILE (file) albero

ACQUISISCITASTIERA ( ) albero

TRADUCI (file, albero) file

Specifica semantica

TIPI:

albero = insieme degli alberi ordinati T=<N,A> in cui ad ogni nodo n in N è associato il

livello(n);

boolean = insieme dei valori di verità;

nodo = insieme qualsiasi (non infinito)

file = sequenza di caratteri delimitata da un valore booleano che ne contrassegna la fine

OPERATORI:

CREAALBERO = T'

Post: T' = L (albero vuoto)

ALBEROVUOTO (T) = b

Post: b = true se T=L; b=false altrimenti

INSRADICE (u, T) = T'

Pre: T = L

Post: T' = (N,A), N = {u}, LIVELLO(u) = 0, A = Ø

RADICE (T) = u

Pre: T != L

Post: u Radice di T LIVELLO(u) = 0

PADRE (u, T) = v

Pre: T != L, u appartenente a N, LIVELLO(u) > 0

Post: v è padre di u, <v,u> appartenente ad A, LIVELLO(u) = LIVELLO(v) + 1

FOGLIA (u, T) = b

Pre: T != L, u appartenente a N

Post: b = true se ¬∃, v appartenente a N tale che <u,v> appartente ad A &&

LIVELLO(v) = LIVELLO(u) + 1; b = false altrimenti

PRIMOFIGLIO (u, T) = v

Pre: T != L, u appartenente N, FOGLIA (u, T) = false

Post: <u,v> appartenente ad A, LIVELLO(v) = LIVELLO(u) + 1, v è primo secondo

la relazione d’ordine stabilita tra i figli di u

ULTIMOFRATELLO (u, T) = b


Post: b = true se non esistono altri fratelli di u che lo seguono nella relazione

d’ordine, b = false altrimenti

SUCCFRATELLO (u, T) = v

Pre: T != L, u appartenente a N, ULTIMOFRATELLO (u, T) = false

Post: v è il fratello di u che lo segue nella relazione d’ordine

INSPRIMOSOTTOALBERO (u, T, T') = T''

Pre: T != L, T' != L, u appartenente a N

Post: T'' è ottenuto da T aggiungendo l’albero T’ la cui radice r’ è il nuovo albero

primofglio di u

INSSOTTOALBERO (u, T, T') = T''

Pre: T != L, T' =! L, u appartenente a N, u non è radice di T

Post: T'' è l’albero ottenuto da T aggiungendo il sottoalbero T’ di radice r’ (cioè r’

diventa il nuovo fratello che segue u nella relazione d’ordine)

CANCSOTTOALBERO (u, T) = T'


Post: T' è ottenuto da T togliendovi il sottoalbero di radice u (cioè u e tutti i suoi

discendenti)

OPERATORI DI SERVIZIO

ACQUISISCIFILE (f) = T

Post: Albero creato prendendo in input da un file più righe di caratteri e ne crea una

gerarchia

ACQUISISCITASTIERA ( ) = T

Post: Albero creato prendendo in input da tastiera più righe di caratteri e ne crea una

gerarchia

TRADUCI (f, T) = f’

Post: Prende un file in input ed un albero e fa visualizzare l’albero in un file con il

costrutto Switch/Case

ALGORITMO RISOLUTIVO

ACQUISISCI FILE

Crea una Coda<char> di nome C;

Crea suffisso con nome Temp;

Crea un char di nome Carattere;

Crea una stringa di nome N;

Crea un albero di tipoelem di nome Alb;

Crea un puntatore ad un nodo di nome Attuale;

Crea un puntatore ad un nodo di nome Scan;

Crea un puntatore ad un nodo di nome Nuovo;

Crea un albero di tipoelem di nome NuovoAlb;

Crea un booleano di nome Trovato impostato a falso;

Fintantoche non hai finito il file

C ACQUISISCIELEMENTOFILE(F);

Stampa ( C );

Se (NOT codavuota( C ) )

Allora

Temp trasferisci ( C );

Carattere getDesinenza( Temp );

Se ( alberovuoto ( Alb ) )

Allora

Setnodoetichetta ( Nuovo, *, null, null );

Insradice ( Alb, Nuovo );

Scan Radice ( Alb );

Fintantoche (Carattere NOT = ‘ \0 ‘)

Setnodoetichetta ( Nuovo, Carattere, null, null );

Insradice ( NuovoAlb, Nuovo );

Insprimosottoalbero ( Scan, Alb, NuovoAlb );

Scan Nuovo;

Carattere getDesinenza( Temp );

Fine-fintantoche

N ‘ Radice: ( ‘;

Carattere getRadice ( Temp );


N N + Carattere;


Fine-fintantoche

N N + ‘ ); Uscita: ( ‘;

Carattere getUscita ( Temp );


N N + Carattere;


Fine-fintantoche

N N + ‘ ); Pos: ( ‘;

Carattere getPos ( Temp );


N N + Carattere;


Fine-fintantoche

N N + ‘ ) ‘;

Setnodoetichetta ( Nuovo, N, null, null );


Insprimosottoalbero ( Nuovo, Scan, NuovoAlb);

Altrimenti

Attuale Radice ( Alb );

Fintantoche ( Carattere NOT = ‘ \0 ‘ )

Trovato false;

Scan Primofiglio ( Alb, Attuale );

Ripeti

Se ( Legginodo ( Alb, Scan) == Carattere )

Allora

Trovato true;

Attuale Scan;

Carattere getDesinenza (

Temp );

Altrimenti

Se (NOT Ultimofratello ( Alb,

Scan)

Allora

Scan

Succfratello ( Alb, Scan );

Fine-SE

Fine-Se

Finche (NOT Ultimofratello ( Alb, Scan ) AND NOT

Trovato );

Se ( Trovato == false )

Allora


Setnodoetichetta ( Nuovo,

Carattere, null, null );


Insprimosottoalbero ( Attuale,

Alb, NuovoAlb );

Attuale Nuovo;

Carattere getDesinenza( Temp

);

Fine-fintantoche

Fine-Se

Fine-fintantoche

N ‘ Radice: ( ‘;



N N + Carattere;


Fine-fintantoche

N N + ‘ ); Uscita: ( ‘;



N N + Carattere;


Fine-fintantoche

N N + ‘ ); Pos: ( ‘;



N N + Carattere;


Fine-fintantoche

N N + ‘ ) ‘;

Setnodoetichetta ( Nuovo, N, null, null );


Insprimosottoalbero ( Nuovo, Attuale,

NuovoAlb);

Fine-Se

Prendi il carattere dal file;

Fine-Se

Fine-fintantoche

Restituisci ( Alb );

TRADUCI

Se ( NOT Alberovuoto ( A ) )

Allora

Crea pila di nodi di nome Stack;

Crea un puntatore ad un nodo di nome Temp;

Crea un puntatore ad un nodo di nome;

Crea una pila di interi di nome Livello;

Crea un intero di nome Contatore impostata ad 1;

Scrivi nel file ( ‘ Swtch ( C ) ‘ );

S Radice ( A );

S Primofiglio ( A, S );

Fintantoche ( NOT Ultimofratello ( A, S )

Se ( NOT Foglia ( A, S ) )

Allora

Inpila ( Stack, S );

Inpila ( Livello, Contatore );

Fine-Se

S Succfratello ( A, S );

Fine-fintantoche


Allora

Inpilia ( Stack, S );

Inpilia ( Livello, Contatore );

Fine-Se

S Primofiglio ( A, Radice ( A ) );


Se ( Foglia ( A, S ) )

Allora



Fine-Se


Fine-fintantoche


Allora



Fine-Se

Fintantoche ( NOT Pilavuota ( Stack ) )

Temp Leggipila ( Stack );

Contatore Leggipila ( Livello );

Fuoripila ( Stack );

Fuoripila ( Livello );

Se ( Foglia ( A, Temp ) )

Allora

Per i che va 0 a Contatore-1

Scrivi nel file ( ‘ ‘ );

Fine-per

Scrivi nel file ( ‘ Printf ( ‘ , Legginodo ( A, Temp ), ‘ ) ‘ );

Altrimenti

Per i che va 0 a Contatore-1


Fine-per

Se ( Foglia ( A, Primoflglio ( A, Temp ) ) )

Allora

Scrivi nel file ( ‘ Case ‘, Legginodo ( A, Temp ),

‘ { ‘ );

Altrimenti

Scrivi nel file ( ‘ Case ‘, Legginodo ( A, Temp ),

‘ : Switch ( C ) { ‘ );

Fine-Se

S Primofiglio ( A, Temp );

Contatore Contatore + 1;



Allora



Fine-Se


Fine-fintantoche


Allora



Fine-Se

S Primofiglio ( A, Radice ( A ) );



Allora



Fine-Se


Fine-fintantoche


Allora



Fine-Se

Fine-Se

Se ( Contatore > Leggipila ( Livello ) OR Leggipila ( Livello ) == 1 )

Allora

Per c che va da 0 a Contatore-Leggipila ( Livello )

Per i che va da 0 a Contatore-1


Fine-per

Scrivi nel file ( ‘ } ‘ );

Fine-per

Fine-se

Fine-fintatoche

Fine-Se

ACQUISISCITASTIERA è la medesima funzione di ACQUISISCIFILE con l’unica differenza che

prende la riga non dal file ma direttamente da tastiera

REALIZZAZIONI Gli alberi n-ari sono realizzati con puntatori.

Algoritmi E Strutture Dati Alberi N Ari

Documents

Transcript of Algoritmi E Strutture Dati Alberi N Ari