Programmazione 2 + Lab,
Canale A-G
Programmazione 2 + Lab,
Canale A-G
Segnalare eventuali errori ed inesattezze a Chiara Petrioli
Indice
type Puntatorelista = ^ Elementolista;
Elementolista = record
Valore: integer;
Next: Puntatorelista
end;
Esercizio
2
Scrivete
una procedura ricorsiva Stampalista per stampare una
lista. Dato un puntatore
alla testa della lista, Stampalista esamina ricorsivamente gli elementi
della lista a partire
dal primo e ne stampa il valore.
La
procedura verifica se la lista e' vuota o siamo arrivati alla fine della
scansione.
Se questo non e' il caso, scrive il valore dell'elemento corrente e chiama
ricorsivamente
la procedura sulla porzione residua della lista.
procedure Stampalista (L: Puntatorelista);
begin
if (L<>nil) then begin
writeln (L^.Valore);
Stampalista (L^.Next)
end
end;
Esercizio
3
Scrivete una funzione ricorsiva merge la quale, date in input due
liste ordinate a e b,
restituisca una lista anch'essa ordinata, contenente gli elementi di entrambe
le liste.
Date
due liste x e y siano xi e yi rispettivamente i valori dell' i-esimo elemento
delle
liste x e y. Essendo tali liste ordinate, xi <= xj, yi <=yj, per
ogni j>=i. In particolare x1
e y1 denotano gli elementi piu' piccoli rispettivamente nelle liste x e
y. Il primo elemento
piu' piccolo tra tutti gli elementi delle due liste sara' quindi il minimo
tra x1 e y1.
Supponiamo per semplicita' che tale elemento sia x1. Il secondo elemento
piu' piccolo
in x e y sara' il minimo tra x2 e y1, etc. All' i-esimo passo dell'algoritmo,
gli (i-1)
elementi piu' piccoli sono stati individuati e memorizzati in ordine nella
lista merge.
I puntatori alle due liste correnti, x e y, indicano le parti di a e b
ancora da esaminare
(ciascun puntatore punta all'elemento piu' piccolo ancora da esaminare
nella lista
dato che a e b sono liste ordinate): per quanto precedentemente spiegato
l'i-esimo
elemento piu' piccolo e' proprio dato dal minimo tra i valori puntati da
x e y. Osserviamo
che se una delle due liste e' vuota allora non e' necessario effettuare
ulteriori procedure
di ordinamento in quanto gli elementi residui da esaminare appartengono
tutti alla
stessa lista e sono quindi per definizione gia' ordinati.
Per realizzare questo algoritmo con una funzione ricorsiva osserviamo che
la funzione
restituisce, date due sottoliste a e b, il puntatore ad una lista che contiene
gli elementi
delle due sottoliste ordinati in ordine crescente. Quando si arriva ad
avere una delle due
liste vuote allora tale puntatore e' semplicemente il puntatore all'elemento
corrente della
lista non vuota; altrimenti si calcola il prossimo elemento piu' piccolo
(l'elemento
contenente il valore minore tra quelli puntati da a e b), si richiama la
procedura ricorsiva sulle
parti residue della lista (in modo da creare una lista ordinata con gli
elementi residui), e
si costruisce la lista ordinata degli elementi a e b facendo puntare il
campo Next dell'elemento
minimo alla lista residua ordinata dalla chiamata ricorsiva.
function merge (a, b: Puntatorelista):Puntatorelista;
begin
if (b=nil) then merge :=a
else if (a = nil) then merge := b
else if (a^.Valore < b^.Valore) then begin
a^.Next:=merge (a^.Next, b);
merge :=a
end
else begin
b^.Next:=merge (a, b^.Next);
merge :=b
end
end;
Esercizio
4
Scrivete una procedura ricorsiva insert la quale, dati in input
una lista ordinata L ed un puntatore ad un
elemento, inserisca l'elemento al posto giusto:
procedure insert (var L: Puntatorelista; X: Puntatorelista);
begin
if ((L=nil) or (L^.Valore > X^.Valore)) then begin
X^.Next:=L;
L:=X
end
else insert(L^.Next, X)
end;
Esercizio
5
Usando la funzione insert dell'esercizio precedente, scrivete
una procedura sort la quale, data in input
una lista L la ordini:
procedure sort (var L:Puntatorelista);
var temp, R: Puntatorelista;
begin
R:=nil;
while (L<>nil) do begin
new(temp);
temp^.Valore := L^.Valore;
temp^.Next:=nil;
L:=L^.Next;
insert (R, temp)
end;
L:=R
end;
Esercizio
6
Ripetere
l'esercizio 4 scrivendo una funzione:
function insert (var L: Puntatorelista; X: Puntatorelista): Puntatorelista;
begin
if ((L=nil) or (L^.Valore > X^.Valore)) then begin
X^.Next:=L;
L:=X;
insert:=L
end
else begin
L^.Next:=insert(L^.Next, X) ;
insert:=L
end
end;
Esercizio
8a
Ripetere l'esercizio 3 scrivendo una versione iterativa:
function mergeiterativa (a, b: Puntatorelista):Puntatorelista;
var c, prec: Puntatorelista;
begin
if (a = nil) then
mergeiterativa := b
else (if b = nil) then
mergeiterativa := a
else begin
if (a^.valore < b^.Valore) then begin
c:=a;
prec:=a;
a:=a^.Next
end
else begin
c:=b;
prec:=b;
b:=b^.Next
end;
while ((a<>nil) and (b<>nil)) do begin
if (a^.Valore < b^.Valore) then begin
prec^.Next:=a;
a:=a^.Next;
prec:=prec^.Next
end
else begin
prec^.Next:=b;
b:=b^.Next;
prec:=prec^.Next
end
end;
if (a = nil) then prec^.Next:=b
else prec^.next:=a;
mergeiterativa:=c
end
end;
Esercizio
8b
Ripetere l'esercizio 4 scrivendo una versione iterativa:
procedure insertiterativa (var L: Puntatorelista;X: Puntatorelista);
var prec, curr, temp: Puntatorelista;
begin
if ((L=nil) or (X^.Valore <L^.valore)) then
begin
X^.Next:=L;
L:=X
end
else begin
prec:=L;
curr:=L^.Next;
while ((curr<>nil) and (curr^.Valore <= X^.Valore)) do begin
prec:=prec^.Next;
curr:=curr^.Next
end ;
prec^.Next:=X,
X^.Next:=curr
end
end;
Scrivete
una funzione Selectmin che dato un array X ed un intervallo
all'interno dell'array i...n
(con indice i passato come parametro e n dimensione dell'array), individui
l'indice
dell'elemento contenente il valore minore tra X[i]..X[n].
Esempio:
sia X un array contenente i seguenti 5 interi 4 6 8 7 9 (X[1] = 4, X[2]
= 6,
X[3]= 8, X[4]= 7, X[5] = 9) e sia i= 3. Selectmin (3, X) esamina gli elementi
X[3]..X[5],
individua che l'elemento che contiene il valore minore e' X[4]=7, e restituisce
l'indice
di tale elemento. Selecmin (3, X) in questo caso restituira' quindi 4.
type vect = array[1..n] of integer;
procedure selectmin (i: integer; X: vect): integer;
var min, j: integer;
begin
min:=i;
for j:=(i+1) to n do
if X[j] < X[min] then min:=j;
selectmin:=min
end;
Esercizio 2
Scrivete
una procedura Swap che dato un vettore X e gli indici i, j di due
suoi elementi, scambi
i valori contenuti nelle due posizioni del vettore.
Esempio:
sia X un array contenente i seguenti 5 interi 4 6 8 7 9 (X[1] = 4, X[2]
= 6,
X[3]= 8, X[4]= 7, X[5] = 9) e siano i= 3, j= 5. All'uscita dalla procedura
Swap (3,5, X)
il vettore X dovra' contenere i seguenti valori: X[1] = 4, X[2] = 6, X[3]=
9, X[4]= 7, X[5] = 8.
procedure swap (i, j: integer; var X: vect);
var temp: integer;
begin
temp:=X[j];
X[j]:=X[i];
X[i]:=temp
end;
Si
osservi che il vettore X in questo caso deve essere passato
per variabile. Altrimenti l'operazione
di swap verrebbe effettuata su una copia del vettore X e non rimarrebbe
traccia dello scambio effettuato
all'uscita dalla procedura swap.
Esercizio 3
Utilizzando
la funzione selectmin e la procedura swap si scriva una procedura sort
che dato un vettore
X da 1 ad n, ordini gli elementi del vettore in ordine crescente utilizzando
l'algoritmo selection sort.
L'algoritmo di ordinamento selection sort procede per iterazioni successive
ad individuare
e mettere nella posizione assoluta corretta il primo elemento piu'
piccolo, il secondo elemento piu'
piccolo etc. Durante la prima iterazione tutti gli elementi del vettore
sono esaminati e viene
individuato l'elemento piu' piccolo che viene spostato in prima posizione.
Nella seconda iterazione,
il secondo elemento piu' piccolo (i.e. l'elemento piu' piccolo tra gli
elementi contenuti nelle
posizioni 2...n del vettore - il piu' piccolo elemento e' stato spostato
in possizione 1) viene
trovato e spostato in seconda posizione. Dopo (n-1) iterazioni, nelle posizioni
1...n-1 del vettore
sono contenuti, in ordine, gli (n-1) elementi piu' piccoli mentre nella
posizione n-esima e'
contenuto l'elemento piu' grande (vettore ordinato).
procedure sort (var X: vect);
var k: integer;
begin
for k:=1 to (n-1) do
swap (selectmin (k, X), k, X)
end;
Esercizio 5
Definite in Pascal un albero binario utilizzando i puntatori.
type AlberoBinario = ^ Nodo;
Nodo = record
Valore: integer;
Sinistro: AlberoBinario;
Destro: AlberoBinario
end;
Esercizio 6
Scrivete una funzione ricorsiva profondita che, dato
un albero binario, calcoli la sua profondita'
(numero di livelli). Un albero vuoto ha profondita'
0, un albero con un elemento ha profondita' 1,
un albero binario i cui sottoalberi sinistro e destro abbiano profondita'
x e y ha profondita' pari
a max (x, y) + 1.
function profondita (T: AlberoBinario): integer;
var t1, t2: integer;
begin
if (T = nil) then profondita :=0
else begin
t1:= profondita (T^: sinistro);
t2:= profondita (T^: destro);
if t1 >= t2 then profondita := t1 + 1
else profondita := t2 + 1
end
end;
Esercizio 7
Scrivete una funzione ricorsiva peso che, dato un
albero binario, calcoli il suo peso, definito
come il numero di nodi dell'albero. Un albero
vuoto ha peso 0, un albero con un elemento ha
peso 1, un albero binario i cui sottoalberi sinistro e destro abbiano peso
x e y ha peso pari
a x+y+ 1.
function peso (T: AlberoBinario): integer;
begin
if (T = nil) then peso :=0
else peso:=1 + peso(T^.sinistro) + peso(T^.destro)
end;
Definire
un tipo Pila utilizzando i puntatori. Una
pila e' una struttura dati per rappresentare
insiemi dinamici di elementi dello stesso tipo in cui si mantiene un puntatore
all'ultimo
elemento inserito (testa della pila) e sulla quale si possono effettuare
le operazioni di
inserimento in testa di un nuovo elemento (Push) ed eliminazione dell'ultimo
elemento inserito
(eliminazione dell'elemento in testa alla Pila o Pop). In questi esercizi
consideriamo Pile i
cui elementi contengono un campo Chiave di tipo char anche se in generale
tale campo
puo' contenere qualsiasi tipo di dato.
type
Pila = ^ElementoPila;
ElementoPila = record
Chiave: char;
Next: Pila
end;
Esercizio 2
Scrivere una funzione iterativa isEmpty che, data una Pila,
verifichi se la Pila sia o meno vuota.
IsEmpty restituisce true se la pila non contiene alcune elemento (Puntatore
alla testa della pila
= nil), false altrimenti.
function isEmpty (P: Pila): boolean;
begin
isEmpty:= (P = nil)
end;
Esercizio 3
Scrivere una procedura iterativa Push che, data una Pila
ed un carattere X, inserisca in cima alla Pila
un nuovo elemento contenente X come chiave.
procedure Push (var P: Pila; X: char);
var temp: Pila;
begin
new(temp);
temp^.Chiave :=X;
temp^.Next:=P;
P := temp
end;
Il
puntatore alla testa della Pila deve essere passato come variabile. Se
fosse passato come valore
all'uscita dalla procedura non rimarrebbe traccia dell'inserimento nella
pila.
Esercizio 4
Scrivere una funzione iterativa Pop che, data una Pila non
vuota elimini l'elemento in testa alla
Pila restituendone il campo Chiave. Prima
di chiamare la procedura Pop occorrera' nel programma
principale verificare che la Pila non sia vuota utilizzando isEmpty.
function Pop (var P: Pila): char);
var temp: Pila;
begin
temp:=P;
P:=P^.Next;
Pop:= temp^.Chiave;
dispose (temp)
end;
Esercizio 5
Definire
un tipo Pila utilizzando un vettore. Gli elementi
della pila sono memorizzati consecutivamente
a partire dalla posizione 1 del vettore. Dato che dalla Pila si estrae
e nella Pila si inserisce solo in testa
e' sufficiente mantenere l'indice della posizione in cui si deve inserire
il prossimo elemento, head. Gli
elementi in Pila sono quindi quelli nell'intervallo 1...head -1. La condizione
Pila Vuota verificata
da isEmpty si ha quindi quando head = 1, mentre non e' possibile inserire
( il vettore e' pieno)
quando head = maxdim+1, con maxdim dimensione del vettore.
type
vect = array [1..maxdim] of char;
Pila = record
Head: integer;
vettorePila: vect
end;
Esercizio 6
Riscrivere la funzione iterativa isEmpty nel caso in cui
la Pila sia implementata con i vettori.
Ricordiamo che, data una Pila, isEmpty verifica se la Pila sia o meno vuota.
IsEmpty restituisce true se la pila non contiene alcune elemento (P.head
= 1), false altrimenti.
function isEmpty (P: Pila): boolean;
begin
isEmpty:= (P.head = 1)
end;
Esercizio 7
Scrivere la procedura iterativa Push nel caso in cui la Pila
sia implementata con un vettore.
Ricordiamo che Push, data una Pila ed un carattere X, inserisce in cima
alla Pila
un nuovo elemento contenente X come chiave.
Si
procede verificando se la Pila e' piena (P.head = maxdim+1). in questo
caso si segnala che e'
impossibile inserire un nuovo elemento: altrimenti si inserisce il valore
X in posizione P.head
e si aggiorna P. head avanzandolo di una posizione.
procedure Push (var P: Pila; X: char);
var temp: Pila;
begin
if (P.head <> (maxdim +1)) then begin
P.vettorePila[P.head] := X;
P.head := P.head + 1
end
else writeln ('impossibile inserire : Pila piena')
end;
Il
puntatore alla testa della Pila deve essere passato come variabile. Se
fosse passato come valore
all'uscita dalla procedura non rimarrebbe traccia dell'inserimento nella
pila.
Esercizio 8
Riscrivere la funzione iterativa Pop nel caso in cui la Pila
sia implementata con un vettore.
Ricordiamo che Pop, data una Pila non vuota elimina l'elemento
in testa alla Pila restituendone
il campo Chiave. Prima di chiamare la procedura
Pop occorrera' nel programma principale
verificare che la Pila non sia vuota utilizzando isEmpty.
function Pop (var P: Pila): char;
var temp: Pila;
begin
Pop:= P.VettorePila[P.head-1];
P.head := P.head -1
end;
Esercizio 9
Utilizzando la procedura Push e le funzioni Pop e isEmpty, si scriva una
funzione
parentesi_bilanciate
che data una lista in cui e' stata memorizzata una sequenza di parentesi
tonde (aperte e chiuse) verifichi che le parentesi siano ben annidate,
restituendo true nel
caso in cui l'annidamento sia corretto, false altrimenti.
Esempio:
se nella lista e' memorizzata la sequenza (() () ) (), la funzione restituira
' true,
se invece fosse memorizzata la sequenza ( () (() - piu' parentesi aperte
che chiuse - o
( ( ))) - piu' chiuse che aperte- allora restituira' false.
Per
verificare che l'espressione sia corretta non e' in generale sufficiente
che il numero di
parentesi
aperte e chiuse sia lo stesso (Es: ( ) ) ( ha lo stesso numero di parentesi
tonde e aperte
ma non e' una sequenza corretta). Per verificare che l'espressione sia
ben annidata scandiamo
la sequanza di parentesi memorizzata nella lista. Ogni volta che leggiamo
una parentesi tonda aperta
la inseriamo in una Pila (Push). Ogni volta che leggiamo una parentesi
tonda chiusa eliminiamo
l'ultima parentesi tonda aperta inserita - che e' la parentesi corrispondente-
dalla Pila (Pop).
Si osservi che le parentesi sono ben annidate se durante l'esecuzione della
funzione NON si
verifica una delle due seguenti condizioni:
1) Viene invocata la funzione Pop su una Pila vuota (sintomo di sbilanciamento
- una parentesi
tonda chiusa non preceduta da una aperta)
2) Alla fine della scansione della lista la Pila non e' vuota (sbilanciamento
- piu' tonde aperte
delle parentesi tonde chiuse).
Se una delle due precedenti condizioni si verifica la funzione restituisce
false; altrimenti restituisce
true.
type Lista = ^Nodo;
Nodo = record
Valore: char;
Next: Lista
end;
function Parentesi_Bilanciate (L: Lista): boolean;
var
temp: Lista;
corretto: boolean;
P: Pila;
c: char;
begin
temp:= L;
corretto := true;
P := nil;
while ((temp <>nil) and corretto) do begin
case (temp^.Valore) of
'(': Push (P, temp^.Valore);
')': if isEmpty (P) then corretto:= false
else c:= Pop(P)
end;
temp:= temp^.Next
end;
if corretto and isEmpty (P) then
Parentesi_bilanciate := true
else Parentesi_Bilanciate := false
end;
Definire
un tipo Coda utilizzando un vettore. Una
coda e' una struttura dati per rappresentare
insiemi dinamici di elementi dello stesso tipo in cui vengono mantenuti
due indici,
rispettivamente al primo (head o testa) e all'ultimo (tail o coda) elemento
inserito, e su
cui sono permesse le operazioni di estrazione dalla testa ed inserimento
in coda.
type
vector = array [1..maxdim] of integer;
Coda = record
head: integer;
tail: integer;
vettorecoda: vector
end;
Quando una coda e' rappresentata tramite un vettore tale vettore e' un
vettore 'circolare'.
Questo significa che gli elementi della coda sono memorizzati sequenzialmente
nelle
posizioni del vettore a partire dalla posizione successiva a quella indicata
dall'indice
head. Quando si raggiunge l'ultima posizione del vettore (nel caso specifico
maxdim)
il prossimo elemento della coda e' memorizzato in posizione 1. Sono quindi
lecite situazioni
in cui tail < head. Tail punta alla prossima posizione in cui inserire.
La condizione
codavuota corrisponde quindi al caso Q.head = (Q.head +1) modulo la dimensione
del
vettore, mentre la condizione Coda Piena corrisponde al caso Q.tail = Q.head.
Il numero
massimo di posizioni che possono essere occupate e' maxdim -1 ma questo
permette di
distinguere facilmente tra le condizioni coda piena e coda vuota.
Esercizio
2
Scrivere una funzione iterativa CodaVuota che, data una Coda,
verifichi se la Coda sia o meno vuota.
CodaVuota restituisce true se la coda non contiene alcune elemento (Q.tail
= (Q.head) mod maxdim +1 )
false altrimenti.
function CodaVuota (Q: Coda): boolean;
begin
CodaVuota:= (Q.tail = (Q.head) mod maxdim +1)
end;
Esercizio 3
Scrivere una funzione iterativa CodaPiena che, data una Coda,
verifichi se la Coda sia o meno piena.
CodaVuota restituisce true se la coda e' piena (Q.tail = Q.head ) false
altrimenti.
function CodaPiena (Q: Coda): boolean;
begin
CodaPiena:= (Q.tail = Q.head)
end;
Esercizio
4
Scrivere una procedura iterativa Enqueue che, data una Pila
ed un intero X, inserisca in coda alla Coda
un nuovo elemento contenente X come chiave.
procedure Enqueue (var Q: Coda; X: integer);
var temp: Coda;
begin
if not isFull (Q) then
begin
Q.vettorecoda[Q.tail]:=X;
Q.tail:=(Q.tail) mod maxdim +1
end
else writeln (' impossibile inserire: coda piena')
end;
La
variabile coda deve essere passata come variabile. Se fosse passato come
valore
all'uscita dalla procedura non rimarrebbe traccia dell'inserimento nella
coda.
Esercizio 5
Scrivere una funzione iterativa Dequeue che, data una Coda
non
vuota elimini l'elemento in testa alla
Coda restituendone il campo Chiave. Prima
di chiamare la procedura Dequeue occorrera' nel programma
principale verificare che la Coda non sia vuota utilizzando CodaVuota.
function Dequeue (var Q: Coda): integer;
begin
Dequeue:=Q.vettorecoda[(Q.head) mod maxdim +1];
Q.head := (Q.head) mod maxdim +1
end;
Esercizio 6
Definire
un tipo Coda utilizzando i puntatori. Si mantengono
due puntatori alla testa e alla
coda della coda per permette l'inserimento in coda (ultimo elemento) e
l'estrazione in testa.
La condizione codavuota corrisponde quindi a Q.head = Q.tail = nil.
type
PuntatoreCoda = ^ Nodo;
Nodo = record
Valore: integer;
Next: PuntatoreCoda
end;
Coda = record
Head: PuntatoreCoda;
Tail: PuntatoreCoda
end;
Esercizio 7
Riscrivere la funzione iterativa CodaVuota nel caso in cui
la Coda sia implementata con i puntatori.
Ricordiamo che, data una Coda, CodaVuota verifica se la Coda
sia o meno vuota.
CodaVuota
restituisce true se la coda non contiene alcune elemento (Q.head= Q.tail
= nil), false altrimenti.
function CodaVuota (Q: Coda): boolean;
begin
CodaVuota:= ((Q.head = nil)and (Q.tail = nil))
end;
Esercizio 8
Scrivere la procedura iterativa EnQueue nel caso in cui la
Coda sia implementata con i puntatori.
Ricordiamo che EnQueue, data una Coda ed un intero X, inserisce in coda
alla Coda
un nuovo elemento contenente X come chiave.
procedure EnQueue (var Q: Coda; X: integer);
var temp: PuntatoreCoda;
begin
new(temp);
temp^.Valore:=X;
temp^.Next:=nil;
if CodaVuota (Q) then
begin
Q.tail:=temp;
Q.head := temp
end
else
begin
Q.tail^.Next := temp;
Q.tail := temp
end
end;
Esercizio 9
Riscrivere la funzione iterativa DeQueue nel caso in cui la Coda
sia implementata con puntatori.
Ricordiamo che DeQueue, data una Coda non vuota elimina l'elemento
in testa alla Coda restituendone
il campoValore. Prima di chiamare la procedura
DeQueue occorrera' nel programma principale
verificare che la Coda non sia vuota utilizzando CodaVuota.
function DeQueue (var Q: Coda): integer;
var temp: PuntatoreCoda;
begin
temp:= Q.head;
DeQueue:= temp^.Valore;
Q.head := Q.head^.Next;
if (Q.head = nil) then Q.tail := nil;
dispose (temp)
end;
Utilizzando la procedura Push e le funzioni Pop e isEmpty, si scriva una
funzione
valuta_polacca che data una lista in cui e' stata memorizzata
una espressione in notazione
polacca inversa, la valuti, restituendone il valore.
Ricordiamo che la notazione polacca inversa di una espressione E e' data
da
1) E stessa se E e' una variabile o una costante
2) E'1 E'2 op, con E' 1 e E' 2 le notazioni polacche inverse di E1 e E2,
se E e' una espressione
del tipo E1 op E2.
3) E'1, la notazione polacca inversa di E1, se E e' una espressione nella
forma (E1). Il
lettore ragioni infatti sul fatto che nella notazione polacca inversa le
parentesi non sono
necessarie (la posizione degli operandi e operatori implica una determinata
parentesizzazione).
Nelle nostre espressioni assumeremo che vengano usati solo gli operatori
binari su interi
+, *, div, - e valori numerici.
Esempio di notazione polacca inversa:
[4 + (6 * 2)] - [2 / ( 5 * 8)] si esprime come 462*+258*/-
Si assume che la sequenza 462*+258*/- sia memorizzata in una lista
(4 valore del primo elemento
, - valore dell'ultimo elemento della lista) i cui elementi contengono
quattro campi: un campo
tipo, contenente valore 0 nel caso in cui nell'elemento sia memorizzato
un intero, 1 nel caso in
cui nell'elemento sia memorizzato un operatore, un campo valore utilizzato
per memorizzare
il valore intero (nel caso in cui l'elemento memorizzi il valore di un
operando), un campo
operatore contenente un carattere (+, *, -, / per gli operatori di somma,
prodotto, sottrazione e
div), ed un campo Next che punta al prossimo elemento della lista. La funzione
valuta_polacca
si avvale di una funzione apply che, dati due interi i1 e
i2 ed un carattere op (che rappresenta uno dei
quattro operatori) restituisce come risultato un intero pari a i2 op i1.
Valuta_polacca scandisce
sequenzialmente gli elementi della lista. Se l'elemento corrente e' un
operando lo inserisce in pila.
Quando viene trovato un operatore op, allora si estraggono i due ultimi
operandi inseriti in pila,
e si utilizza l'apply per valutare l'espressione i2 op i1. Il risultato
della valutazione e' quindi
reinserito in pila.Quando si e' scandita tutta la lista nella pila sara'
contenuto un unico valore intero
pari al valore dell'espressione in notazione polacca inversa memorizzata
nella lista (che si assume
essere una espressione corretta).
type Lista = ^ElementoLista;
ElementoLista = record
Tipo: integer;
Valore: integer;
Operatore:char;
Next: Lista
end;
function apply (i, j: integer; c: char): integer;
begin
case c of
'+': apply:= j+i;
'-': apply:= j-i;
'*': apply:= j*i;
'/': apply:= j div i
end
end;
function valuta_polacca (L: Lista): integer;
var
P:Pila;
begin
P:=nil;
while (L<>nil) do
begin
case (L^.Tipo) of
0: Push (P, L^.Valore);
1: Push (P, apply(Pop(P), Pop(P), L^.Operatore))
end;
L:=L^.Next
end;
valuta_polacca:=Pop(P)
end;
Esercizio 2
Ricordiamo
la definizione di albero binario utilizzando i puntatori.
type AlberoBinario = ^ Nodo;
Nodo = record
Chiave: integer;
Sinistro: AlberoBinario;
Destro: AlberoBinario
end;
Esercizio 3
Scrivete una funzione ricorsiva find che, dato un
albero binario B implementato con i puntatori,
ed un intero i, verifichi se l'intero corrisponde al valore di una delle
chiavi dei nodi dell'albero.
Se esiste almeno un nodo la cui chiave e' pari ad i, find
costruisce una copia del primo nodo
di questo tipo e restituisce il puntatore a tale copia; altrimneti find
restituisce nil.
function find (B: AlberoBinario; i:integer):AlberoBinario;
var temp: AlberoBinario;
begin
if (B=nil)then find :=nil
else begin
if (B^.Chiave = i) then begin
new(temp);
temp^.Chiave:=i;
temp^.sinistro:nil;
temp^.destro:=nil;
find:=temp
end
else begin
temp:=find(B^.sinistro);
if (temp<>nil) then find:=temp
else find:=find(B^.destro)
end
end
end;
Esercizio 4
Scrivete una funzione ricorsiva isheap che, dato un
albero binario B implementato con i puntatori,
verifichi se la proprieta' di heap e' verificata. Ricordiamo
che per essere un heap un albero di
ricerca deve soddisfare la proprieta' che, per ogni nodo i, la chiave contenuta
in i e' minore
di tutte le chiavi contenute nel sottoalbero sonistro e destro. Osserviamo
che tale requisito
si traduce nel verificare che per ogni nodo i la chiave contenuta in i
sia minore delle chiavi
contenute nei suoi figli.
function isheap (B: AlberoBinario):boolean;
var condizione:boolean;
begin
if (B=nil) then isheap:=true
else begin
condizione:=true;
if (B^.sinistro <>nil) then
condizione := condizione and
(B^.Chiave<=B^.sinistro^.Chiave);
if (B^.destro <>nil) then
condizione := condizione and
(B^.Chiave<=B^.destro^.Chiave);
if condizione then
isheap:= (isheap(B^.sinistro) and
isheap(B^.destro));
else isheap:=condizione
end
end;
type
RB = (Red, Blue);
AlberoRB = ^ NodoRB;
NodoRB = record
Chiave: integer;
Colore: RB;
Sinistro: ^ NodoRB;
Destro: ^ NodoRB
end;
Esercizio
2
Si
scriva una funzione ricorsiva IsRB che, dato un albero binario, verifichi
se l'albero sia
o
meno red Blue. IsRB restituisce true se la proprieta' (1) e' verificata,
false altrimenti.
Si
procede verificando che il colore di figli esistenti sia diverso dal colore
del nodo.
Se
almeno un figlio ha colore uguale al padre, l'albero NON e' Red Blue e
la
IsRB
ritorna false; altrimenti si deve verificare che la proprieta' sia soddisfatta
anche
all'interno dei sottoalberi sinistro e destro. Si chiama quindi ricorsivamente
la
funzione su R^.Sinistro e R^.Destro e si pone IsRB pari all'AND dei
risultati
delle
due verifiche (IsRB restituira' quindi true se e solo se la condizione
e' verificata
1)sui
figli diretti 2)all'interno del sottoalbero sinistro, 3) all'interno del
sottoalbero destro).
function isRB (R: AlberoRB): boolean;
var t: boolean;
begin
if (R<>nil) then
if (R^.Colore = Red) then begin
t:=true;
if (R^.Sinistro <> nil) then
t:= (t and (R^.Sinistro^.Colore = Blue));
if (R^.Destro<>nil) then
t:=(t and (R^.Destro^.Colore = Blue));
if t then isRB:= (isRB (R^.Sinistro) and
isRB(R^.Destro))
else isRB:= t;
end else begin
t:=true;
if (R^.Sinistro <> nil) then
t:= (t and (R^.Sinistro^.Colore = Red));
if (R^.Destro<>nil) then
t:= (t and (R^.Destro^.Colore = Red));
if t then isRB:= (isRB (R^.Sinistro) and
isRB(R^.Destro))
else isRB:= t
end
else isRB:=true
end;
Una seconda soluzione piu' semplice puo' essere
fornita se si passa come parametro
anche il colore che il nodo dovrebbe avere. In tal caso e' sufficiente
verificare che
il colore del nodo sia corretto e richiamare (implicitamente verificando
quindi
la proprieta' RB) la funzione sui nodi figli e con colore opposto.
function f(R: AlberoRB, col: RB): boolean;
begin
if (R = nil) then f:=true
else if (R^.Colore <>col) then f:=false
else f:= (f(R^.Sinistro, succ(col)) and
f(R^.Destro, succ(col)))
end;
function ISRB(R: AlberoRB): boolean;
begin
if (R= nil) then isRB := true
else isRB:=f(R,R^.Colore)
end;
Esercizio 3
Dato un Vettore non ordinato V ed una posizione i di tale vettore, si scriva
la funzione predecessor che, trovi
l'elemento contenente il valore massimo tra quelli con valore minore di
V[i] e ne restituisca l'indice. I valori
contenuti in V sono interi positivi. Se V[i] contiene il valore piu' piccolo
in V (non esiste un predecessore
la funzione restituira' il valore -1).
function Predecessor (V: Vect; i:integer): integer;
var t,max, j: integer;
begin
t:=-1;
max:=-1;
for j:= 1 to maxdim do
if ((V[j]<V[i]) and (V[j]>max)) then begin
max:=V[j];
t:=j
end;
Predecessor:=t
end;