ESERCIZIO
Assegnata una lista L di caratteri ed un carattere k, scrivere una procedura che cancelli tutte le
occorrenze di k in L.
PROGRAM Liste(output,input); { Occorrenze }
CONST
NullItem= ' ' ;
TYPE
STRING20=STRING[20];
ItemType= char;
LNodeP=^LNodeType;
LNodeType = RECORD
Item:ItemType;
Next:LNodeP
END;
VAR L1,prec:LNodeP;occ:ItemType;
{ ******** MAIN *********}
BEGIN
CreaLista(L1);
write(' Dammi occorrenza '); readln(occ);
writeln(' LISTA INIZIALE'); writeln;
LeggiLista(L1);
prec:=NIL;
writeln(' LISTA CORRETTA');
LeggiLista(occur(prec,L1,L1,occ));
readln;
END.
PROCEDURE LeggiLista(L1:LnodeP);
VAR Nod: LnodeP;Aitem:ItemType;
BEGIN
IF L1=NIL THEN writeln(‘ Lista vuota ')
ELSE
BEGIN
Nod:=L1;
WHILE Nod^.next<>NIL DO
BEGIN
AItem:=Nod^.item;
writeln(' - ',Aitem);
Nod:=Nod^.next;
END;
AItem:=Nod^.item;
writeln(' - ',Aitem);
END;
END;
PROCEDURE CreaLista(VAR L1:LnodeP);
VAR AnItem:ItemType; L,Node:LnodeP;
BEGIN
Writeln('Dammi gli item (* per uscire) ');
readln(AnItem);
IF AnItem='*' THEN L1:=NIL
ELSE
BEGIN
MakeNode(AnItem,L);
L1:=L;
WHILE AnItem <> '*' DO
BEGIN
readln(AnItem);
IF AnItem<>'*' THEN
BEGIN
MakeNode(AnItem,Node);
L^.next:=Node;
L:=Node
END;
END
END;
END;
PROCEDURE MakeNode(AItem:ItemType; VAR
Nod:LNodeP);
BEGIN
new(Nod);
Nod^.Item:= AItem;
Nod^.Next:=NIL
END;
FUNCTION occur(prev:LNodeP;VAR
PROCEDURE KillNode(VAR Node:LNodeP);
TLista:LNodeP;mylist:LNodeP;k:itemType):LNodeP; BEGIN
BEGIN
IF Node <> NIL THEN
IF mylist<>NIL THEN
BEGIN
BEGIN
dispose(Node);
IF mylist^.item=k THEN
Node:=NIL
BEGIN
END
Cancella(TLista,prev,myList);
END;
occur:=occur(prev, Tlista, mylist,k)
END
PROCEDURE Cancella(VAR TLis, prevc,myL:LNodeP);
ELSE
VAR
BEGIN
Temp:LNodeP;
Prev:=mylist;
BEGIN
Occur:=occur(prev, Tlista, mylist^.next,k)
IF prevc<>NIL THEN
END;
Temp:= Prevc^.next
END;
ELSE
occur:=Tlista;
Temp:=Tlis;
END;
IF temp<>NIL THEN
{ ******** MAIN *********}
IF prevc<>NIL THEN
BEGIN
BEGIN
myL:=temp^.next;
CreaLista(L1);
Prevc^.next:=temp^.next
write(' Dammi occorrenza '); readln(occ);
END
writeln(' LISTA INIZIALE'); writeln;
ELSE
LeggiLista(L1);
BEGIN
prec:=NIL;
Tlis:=temp^.next;
myL:=Tlis
writeln(' LISTA CORRETTA');
END;
LeggiLista(occur(prec,L1,L1,occ));
KillNode(Temp);
readln;
END;
END.
ESERCIZIO
Assegnata una lista L legata di caratteri ed un carattere k, spostare all’inizio della lista tutti i
caratteri k senza cambiare l’ordine dei restanti elementi.
PROCEDURE SpostaNodo(VAR prevc:LNodeP;mylis:LNodeP;VAR Tlis:LNodeP);
VAR temp:LNodeP;
BEGIN
FUNCTION aggiorna (VAR TLista:LNodeP; prev:LNodeP;
Prevc^.next:=myLis^.next;
mylist:LNodeP; k:itemType):LNodeP;
Temp:=Tlis;
BEGIN
Tlis:=mylis;
IF myList<>NIL THEN
Tlis^.next:=temp
BEGIN
END;
IF myList^.item=k THEN
BEGIN
prev^.next:=mylist^.next;
mylist^.next:=TLista;
TLista:=myList;
Aggiorna:=Aggiorna(TLista,prev,prev^.next,k)
END
{ ******** MAIN *********}
ELSE
BEGIN
Aggiorna:=Aggiorna(TLista,prev^.next, myList^.next,k);
CreaLista(L1);
END
write(' Dammi occorrenza ');
ELSE
readln(occ);
aggiorna:=Tlista;
writeln(' LISTA INIZIALE'); writeln;
END;
LeggiLista(L1);
prec:=L1;
writeln(' LISTA CORRETTA');
LeggiLista(aggiorna(L1, prec,L1^.next,occ));
readln;
END.
ESERCIZIO
Data una lista L non ordinata, ordinarla in ordine crescente.
PROCEDURE SpostaNodo(VAR Tlis:LNodeP; VAR prevci, ind, prevcm, mylis:LNodeP);
VAR temp:LNodeP;
BEGIN
IF prevcI<>NIL THEN
FUNCTION ordinata (VAR TLista:LNodeP; prevI, I,
BEGIN
prevM:LNodeP; mylist:LNodeP):LNodeP;
Prevci^.next:=mylis;
BEGIN
PrevcM^.next:=mylis^.next;
IF myList<>NIL THEN
mylis^.next:=ind;
BEGIN
END
IF i<>myList THEN
ELSE
BEGIN
BEGIN
IF i^.item>mylist^.item THEN
prevcM^.next:=mylis^.next;
BEGIN
mylis^.next:=Tlis;
SpostaNodo(TLista,prevI,i,prevM,myList);
Tlis:=mylis;
prevI:=NIL;
END;
ordinata:= ordinata(TLista,prevI,Tlista, mylist,myList^.next);
END;
END
ELSE
ordinata:= ordinata(TLista,i,i^.next,prevM, myList)
END
{ ******** MAIN *********}
ELSE
BEGIN
BEGIN
CreaLista(L1);
prevI:=NIL;
writeln(' LISTA INIZIALE');
ordinata:= ordinata(TLista,prevI,Tlista,mylist, myList^.next);
LeggiLista(L1);
END;
prec:=nil;
END
writeln(' LISTA ORDINATA ');
ELSE
LeggiLista(ordinata(L1, prec,L1,L1,L1^.next));
ordinata:=Tlista;
readln;
END;
END.
ESERCIZI DA FARE
Data una lista L di interi, scrivere una funzione ricorsiva che modifichi la lista
duplicando tutti gli elementi divisibili per 3 e mantenendo lo stesso ordine che gli
elementi avevano in L.
ESERCIZI SU ALBERI E LISTE
a.a. 2005-2006
PROCEDURE Search(Tree: BSTT, KeyValue: KItemType, VAR TNode, Parent: BSTP);
VAR
NodesKey: KItemType;
BEGIN
Parent:= NIL; {la root non ha genitori}
Tnode:= Tree; {la radice è il primo nodo esaminato}
GetNodesKey(TNode, NodesKey); {estrai la chiave del primo nodo}
WHILE NOT EmptyTree(TNode) AND (NodesKey <> KeyValue) DO
BEGIN
Parent:= Tnode;
IF NodesKey > KeyValue THEN
Tnode:= NodesLeftTree(TNode)
ELSE
Tnode:= NodesRightTree(TNode);
GetNodesKey(TNode, NodesKey) {estrai la chiave del nodo in esame}
END
END;
FUNCTION SearchTNode(Tree: BSTP; KeyValue:KItemType): BSTP;
{cerca il nodo con chiave KeyValue, se esso non esiste ritorna NIL}
VAR TheKey: KItemType;
BEGIN
IF EmptyTree(Tree) THEN
SearchTNode:= NIL
ELSE
BEGIN
GetNodesKey(Tree, TheKey);
IF TheKey = KeyValue THEN
SearchTNode:= Tree
ELSE
IF KeyValue < TheKey Then
SearchTNode :=SearchTNode(NodesLeftTree(Tree), KeyValue)
ELSE
SearchTNode:= SearchTNode(NodesRightTree(Tree), KeyValue)
END
END;
ESERCIZIO
{Scrivere un algoritmo che dato un albero binario ne dia tutte le relazioni familiari}
FUNCTION Figlios(Albero:BSTP;Padr:KitemType):BSTP;
{Dato il padre cerco il figlio sinistro}
VAR TNode, Parent:BSTP;
BEGIN
Search(Albero, Padr, TNode, Parent);
Figlios:=TNode^.left;
END;
FUNCTION Figliod(Albero:BSTP;Padr:KitemType):BSTP;
{Dato il padre cerco il figlio destro}
VAR TNode, Parent:BSTP;
BEGIN
Search(Albero, Padr, TNode, Parent);
Figliod:=TNode^.right;
END;
PROCEDURE Figli(Alber:BSTP);
{Dato il padre cerco i figli}
VAR padre:KitemType;
BEGIN
Writeln(' Nome del padre ');
readln(padre);
writeln('Il primo figlio è ',figlios(Alber,padre)^.key,
' il secondo figlio è ',figliod(Alber,padre)^.key);
END;
FUNCTION Nonn(Albero:BSTP;Nipot:KitemType):BSTP;
{Dato il nipote cerco prima il padre e poi il nonno}
VAR TNode, Non,Parent:BSTP;
BEGIN
Search(Albero, Nipot, TNode, Parent);
Search(Albero, Parent^.key, TNode, Non);
Nonn:=Non;
END;
PROCEDURE Nonno(Alber:BSTP);
{Dato il nipote cerco il nonno}
VAR nipote:KitemType;
BEGIN
Writeln(' Nome del nipote ');
readln(nipote);
writeln('Il nonno di ',nipote,' è ',nonn(Alber,nipote)^.key);
END;
FUNCTION Fratel(Albero:BSTP;Fratell:KitemType):BSTP;
{Dato un soggetto cerco suo padre e quindi suo fratello}
VAR TNode,Parent:BSTP;
BEGIN
Search(Albero, Fratell, TNode, Parent);
IF Fratell>Parent^.key THEN fratel:= Parent^.left
ELSE
fratel:= Parent^.right
END;
PROCEDURE Fratello(Alb:BSTP);
{Dato un soggetto cerco suo fratello}
VAR fratello:KitemType;
BEGIN
Writeln(' Nome del fratello ');
readln(fratello);
writeln('Il fratello di ', fratello,’è',fratel(Alb,fratello)^.key);
END;
FUNCTION Zi(Albero:BSTP; Nipot:KitemType):BSTP;
{Dato un soggetto cerco il fratello di suo padre}
VAR Alb, TNode, Parent:BSTP;
BEGIN
Search(Albero, Nipot, TNode, Parent);
Zi:=Fratel(Albero,Parent^.key);
END;
PROCEDURE Zio(Alb:BSTP);
{Dato un soggetto cerco suo zio}
VAR nipote:KitemType;
BEGIN
Writeln(' Nome del nipote ');
readln(nipote);
writeln('Lo zio di ',nipote,' è ',zi(Alb,nipote^.key);
END;
FUNCTION Papa(Albero:BSTP; figl:KitemType):BSTP;
{Dato un figlio cerco suo padre}
VAR Alb,TNode, Parent:BSTP;
BEGIN
Search(Albero, figl, TNode, Parent);
Papa:=Parent;
END;
PROCEDURE Padre(Alb:BSTP);
{Dato un figlio cerco suo padre}
VAR figlio:KitemType;
BEGIN
Writeln(' Nome del figlio ');
readln(figlio);
writeln('Il padre di ',figlio,' è ',papa(Alb,figlio)^.key);
END;
PROCEDURE NipNon(Albero:BSTP; nono:KitemType;
VAR Nip1,Nip2,Nip3,Nip4:BSTP);
{Dato un nonno cerco i i figli dei suoi figli}
VAR TNode, Parent:BSTP;
BEGIN
Search(Albero, nono, TNode, Parent);
Nip1:=Tnode^.left^.left;
Nip2:=Tnode^.left^.right;
Nip3:=Tnode^.right^.left;
Nip4:=Tnode^. right^.right;
END;
PROCEDURE Nipote(Alber:BSTP);
{Dato un nonno cerco i suoi nipoti}
VAR nonno:KitemType;N1,N2,N3,N4:BSTP;
BEGIN
Writeln(' Nome del nonno ');
readln(nonno);
NipNon(Alber,nonno,N1,N2,N3,N4);
writeln('I nipoti di nonno ',nonno,' sono ',N1^.key,' ',N2^.key,' ',N3^.key,'
',N4^.key);
END;
FUNCTION Cugin1(Albero:BSTP; pers:KitemType):BSTP;
{Dato un soggetto cerco il figlio sinistro di suo zio}
VAR Alb,TNode, Parent:BSTP;
BEGIN
Cugin1:=Zi(Albero,tipo)^.left;
END;
FUNCTION Cugin2(Albero:BSTP; pers:KitemType):BSTP;
{Dato un soggetto cerco il figlio destro di suo zio}
VAR Alb,TNode, Parent:BSTP;
BEGIN
Cugin2:=Zi(Albero,tipo)^.right;
END;
PROCEDURE Cugino(Alb:BSTP);
{Dato un soggetto cerco i suoi cugini}
VAR persona:KitemType;
BEGIN
Writeln(' Nome della persona');
readln(persona);
writeln('I cugini di ',persona,' sono ',cugin1(Alb, persona)^.key,' e ',
cugin2(Alb, persona)^.key);
END;
{************** MAIN***********}
BEGIN
writeln('Costruiamo un Albero. ');
BuildNameTree(Albero);
WriteAlbero(Albero);
Repeat
BEGIN
writeln(' 1 - Dammi il figlio di');
writeln(' 2 - Dammi il nonno di');
writeln(' 3 - Dammi lo zio di ');
writeln(' 4 - Dammi il padre di ');
writeln(' 5 - Dammi il nipote del nonno ');
writeln(' 6 - Dammi il cugino di ');
writeln(' 7 - Dammi il fratello di ');
writeln(' 0 - Per uscire ');
readln(Caso);
CASE caso OF
1:figlio(Albero);
2:nonno(Albero);
3:zio(Albero);
4:padre(Albero);
5:nipote(Albero);
6:cugino(Albero);
7:fratello(Albero)
END;
WriteAlbero(Albero);
END;
writeln;
UNTIL Caso=0;
writeln(' FINE');
END.
PROGRAM Famiglia(input,output);
uses Crt, Alberi0;
CONST
NKey=-100;
var Albero: BSTP;
Item: KItemType;
Chiave:KItemType;
Info:InfoType;
Done:boolean;
VAR caso:integer;
Esercizio 1
Dato un albero BST trovare in maniera ricorsiva tutti gli zii che hanno un solo nipote
Esercizio
2
esnor3 .
Determinare l'altezza di un albero non ordinato e di un albero BST.
Esercizio 3
Dato un albero determinare quanti nonni hanno un solo nipote.
.
PROGRAM Parole(output,input);
{Data una lista contenente caratteri relativi a due parole messe in maniera
alternata, ricostruire la lista
Es. APRUIRAA -> ARIAPURA }
{ ******** MAIN *********}
BEGIN
CreaLista(L1);
writeln(' LISTA 0'); writeln;
LeggiLista(L1);
Alterna(L1);
writeln(' LISTA 1'); writeln;
LeggiLista(L1);
END;
PROCEDURE Alterna(L:LnodeP);
VAR P1,P2,N1,N2,Nini:LNodeP;Finito:boolean;
BEGIN
P1:=L;
P2:=P1^.next^.next;
N1
N1:=P1^.next;
Nini:=N1;
U|
A|
N2:= N1^.next^.next;
Finito:=FALSE;
P1
WHILE Not Finito DO
BEGIN
P1^.next:=P2;
P1:=P2;
P2:=P1^.next^.next;
IF N2^.NEXT=NIL THEN
BEGIN
Finito:=TRUE;
U|
N1^.next:=N2
END
ELSE
BEGIN
A|
N1^.next:=N2;
N1:=N2;
N2:=N1^.next^.next;
END;
END;
P1^.next:=Nini;
END;
N1
N2
N2
N|
P|
A|
E|
P2
P1
P2
N|
A|
P|
E|
Esercizio
esnor3 .
Assegnato un albero non ordinato di interi scrivere una procedura ricorsiva
che trasformi l'albero non ordinato in un albero BST.
Determinare l'altezza dell'albero non ordinato e dell'albero BST.
Esercizio
Dato un albero determinare quanti nonni hanno un solo nipote.
.
ESERCIZIO
{Scrivere una procedura o funzione che assegnato un albero binario di interi dica
quanti nodi con chiave dispari, hanno sottoalbero destro nullo.}
FUNCTION ContaDispari2(Tree:BSTP):integer;
BEGIN
IF emptytree(tree) THEN
Contadispari2:=0
ELSE
IF (Tree^.Right=NIL) AND (Tree^.Key MOD 2 <>0) THEN
ContaDispari2:=ContaDispari2(NodesLeftTree(tree))+
ContaDispari2(NodesRightTree(tree))+1
ELSE
ContaDispari2:=ContaDispari2(NodesLeftTree(tree))+
ContaDispari2(NodesRightTree(tree))
END;
PROCEDURE ContaDispari1(Tree:BSTP; VAR num:integer);
BEGIN
IF not (emptytree(tree)) THEN
IF (Tree^.Right=NIL) AND (Tree^.Key MOD 2 <>0) THEN num:=num+1;
ContaDispari1(NodesLeftTree(tree),num);
ContaDispari1(NodesRightTree(tree),num);
END;
PROCEDURE ContaDispari3(Tree:BSTP; VAR num:integer);
BEGIN
if not (emptytree(tree)) THEN
BEGIN
ContaDispari3(NodesLeftTree(tree),num);
ContaDispari3(NodesRightTree(tree),num);
IF (Tree^.Right=NIL) AND (Tree^.Key MOD 2 <>0) THEN num:=num+1;
END;
END;
ESERCIZIO
Data la seguente definizione
TYPE
Pnodo=^tiporecord;
Tiporecord=RECORD
Car : char;
Link: Pnodo;
END;
tipolista: Pnodo;
Siano assegnate le variabili L, Lmin e Lmax del tipo tipolista rappresentanti
liste legate di caratteri.
Scrivere una procedura che data la lista legata L non ordinata, contenente
caratteri maiuscoli e minuscoli, li estragga e li inserisca in maniera ordinata
nelle liste Lmax (maiuscoli ) ed Lmin (minuscoli).
ESERCIZIO
Sia clienti.bin il nome fisico di un file contenente record del tipo:
TYPE
String20=string[20];
clientetipo=RECORD
nome:string20;
cognome:string20;
prodotto:integer;
END;
Dove prodotto rappresenta il numero di prodotti che il cliente ha acquistato.
Scrivere una funzione ricorsiva che stampi tutti i clienti che non hanno
acquistato più di k prodotti e indicarne il numero complessivo.
Assegnata una lista di interi, scrivere una funzione ricorsiva che
conti quanti numeri primi sono presenti nella lista.
Sia clienti.bin il nome fisico di un file contenente record del tipo:
TYPE
String20=string[20];
clientetipo=RECORD
nome:string20;
cognome:string20;
prodotto:integer;
END;
Estrarre dal file tutti i record con cognome clienti compresi tra A e K e
ordinarli per cognome e per prodotto utilizzando gli array di puntatori.
Dato un albero BST contare quanti nodi ci sono al di sotto di un
nodo preassegnato.
Dato un albero non ordinato contare, con una funzione ricorsiva,
quante foglie possiede.
Dato un albero BST e la chiave K di un suo nodo determinare il
valore della chiave più piccola e di quella più grande del sotto albero
di K. Si suppone che i valori delle chiavi siano comprese
nell’intervallo [10-100].