ESERCIZIOAssegnata 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 }CONSTNullItem= ' ' ;TYPESTRING20=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;BEGINIF 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 MakeNode(AItem:ItemType; VAR Nod:LNodeP);BEGIN

new(Nod);Nod^.Item:= AItem;Nod^.Next:=NIL

END;

PROCEDURE CreaLista(VAR L1:LnodeP);VAR AnItem:ItemType; L,Node:LnodeP;BEGINWriteln('Dammi gli item (* per uscire) ');readln(AnItem);IF AnItem='*' THEN L1:=NILELSEBEGIN MakeNode(AnItem,L); L1:=L; WHILE AnItem <> '*' DO BEGIN readln(AnItem); IF AnItem<>'*' THEN BEGIN MakeNode(AnItem,Node); L^.next:=Node; L:=Node END; ENDEND;END;

{ ******** 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.

FUNCTION occur(prev:LNodeP;VAR TLista:LNodeP;mylist:LNodeP;k:itemType):LNodeP;BEGINIF mylist<>NIL THEN BEGIN IF mylist^.item=k THEN

BEGIN Cancella(TLista,prev,myList);

occur:=occur(prev, Tlista, mylist,k)END

ELSE BEGIN Prev:=mylist; Occur:=occur(prev, Tlista, mylist^.next,k) END; END;occur:=Tlista;END;

PROCEDURE Cancella(VAR TLis, prevc,myL:LNodeP);VARTemp:LNodeP;BEGINIF prevc<>NIL THEN

Temp:= Prevc^.nextELSE

Temp:=Tlis; IF temp<>NIL THEN IF prevc<>NIL THEN BEGIN myL:=temp^.next;

Prevc^.next:=temp^.next END ELSE BEGIN Tlis:=temp^.next; myL:=Tlis END;KillNode(Temp);END;

PROCEDURE KillNode(VAR Node:LNodeP);BEGIN

IF Node <> NIL THEN BEGIN

dispose(Node);Node:=NIL

ENDEND;

ESERCIZIOAssegnata 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

Prevc^.next:=myLis^.next;Temp:=Tlis;Tlis:=mylis;Tlis^.next:=temp

END;

FUNCTION aggiorna (VAR TLista:LNodeP; prev:LNodeP; mylist:LNodeP; k:itemType):LNodeP;

BEGIN IF myList<>NIL THEN BEGIN IF myList^.item=k THEN BEGIN

prev^.next:=mylist^.next;mylist^.next:=TLista;TLista:=myList;Aggiorna:=Aggiorna(TLista,prev,prev^.next,k)

END ELSE

Aggiorna:=Aggiorna(TLista,prev^.next, myList^.next,k); END ELSE aggiorna:=Tlista;END;

{ ******** MAIN *********}BEGINCreaLista(L1);write(' Dammi occorrenza ');readln(occ);writeln(' LISTA INIZIALE'); writeln;LeggiLista(L1);prec:=L1;writeln(' LISTA CORRETTA');LeggiLista(aggiorna(L1, prec,L1^.next,occ));readln;END.

{ ******** MAIN *********}BEGINCreaLista(L1);writeln(' LISTA INIZIALE'); LeggiLista(L1);prec:=nil;writeln(' LISTA ORDINATA ');LeggiLista(ordinata(L1, prec,L1,L1,L1^.next));readln;END.

ESERCIZIOData 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 BEGIN Prevci^.next:=mylis; PrevcM^.next:=mylis^.next;

mylis^.next:=ind; END ELSE BEGIN prevcM^.next:=mylis^.next; mylis^.next:=Tlis; Tlis:=mylis; END;END;

FUNCTION ordinata (VAR TLista:LNodeP; prevI, I, prevM:LNodeP; mylist:LNodeP):LNodeP;

BEGIN IF myList<>NIL THEN BEGIN IF i<>myList THEN BEGIN IF i^.item>mylist^.item THEN BEGIN SpostaNodo(TLista,prevI,i,prevM,myList); prevI:=NIL; ordinata:= ordinata(TLista,prevI,Tlista, mylist,myList^.next); END ELSE ordinata:= ordinata(TLista,i,i^.next,prevM, myList) END ELSE BEGIN prevI:=NIL; ordinata:= ordinata(TLista,prevI,Tlista,mylist, myList^.next); END; END ELSE ordinata:=Tlista;END;

ESERCIZI DA FAREData 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 LISTEa.a. 2005-2006

PROCEDURE Search(Tree: BSTT, KeyValue: KItemType, VAR TNode, Parent: BSTP);VAR NodesKey: KItemType;BEGINParent:= 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) DOBEGINParent:= Tnode;IF NodesKey > KeyValue THENTnode:= NodesLeftTree(TNode)ELSETnode:= 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) ENDEND;

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;BEGINSearch(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; BEGINSearch(Albero, Padr, TNode, Parent);Figliod:=TNode^.right;END;

PROCEDURE Figli(Alber:BSTP);{Dato il padre cerco i figli}VAR padre:KitemType;BEGINWriteln(' 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;BEGINWriteln(' 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^.leftELSEfratel:= Parent^.rightEND;

PROCEDURE Fratello(Alb:BSTP);{Dato un soggetto cerco suo fratello}VAR fratello:KitemType;BEGINWriteln(' 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;BEGINWriteln(' 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;BEGINWriteln(' 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;BEGINWriteln(' 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;BEGINWriteln(' 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);RepeatBEGINwriteln(' 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 OF1: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 listaEs. APRUIRAA -> ARIAPURA }

{ ******** MAIN *********}

BEGINCreaLista(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;BEGINP1:=L;P2:=P1^.next^.next;N1:=P1^.next;Nini:=N1;N2:= N1^.next^.next; Finito:=FALSE;

WHILE Not Finito DOBEGINP1^.next:=P2;P1:=P2;P2:=P1^.next^.next;

IF N2^.NEXT=NIL THEN BEGIN Finito:=TRUE;

N1^.next:=N2 END ELSE BEGIN

N1^.next:=N2; N1:=N2; N2:=N1^.next^.next;

END;END;

P1^.next:=Nini;END;

U | A | N | P | A | E |

U |

A |

N |

P |

A |

E |

P1 P2

N1 N2

P1 P2

N1 N2

Esercizio esnor3 .

Assegnato un albero non ordinato di interi scrivere una procedura ricorsivache 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;BEGINIF emptytree(tree) THEN Contadispari2:=0ELSE IF (Tree^.Right=NIL) AND (Tree^.Key MOD 2 <>0) THEN ContaDispari2:=ContaDispari2(NodesLeftTree(tree))+

ContaDispari2(NodesRightTree(tree))+1ELSE

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=RECORDnome: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=RECORDnome: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 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].

Dato un albero non ordinato contare, con una funzione ricorsiva, quante foglie possiede.