PROGETTO MODULO B – a.a. 2000-2001 Possono scegliere questo progetto solo gli studenti che hanno...

PROGETTO MODULO B – a.a. 2000-2001

Possono scegliere questo progetto solo gli studenti che hanno superato la prova del

progetto di intercorso.

Siano dati tre distributori A,B,C, di bevande o cibo. Caricare nei distributori i prodotti con

date di scadenza non ordinate.

Simulare l’attività di vendita giornaliera come segue:

a inizio giornata si eliminano dalla coda di ogni distributore i prodotti scaduti scaricandoli in

unico contenitore (stack).

Quindi si effettua la vendita.

A fine settimana estrarre dal contenitore prima i prodotti di tipo B, poi C e infine A

caricandoli nell’ordine su un camion (altro stack).

Le strutture dati da adoperare sono:

per i distributori di prodotti code con liste legate,

per il contenitore e il camion stack realizzati con liste legate.

Implementare e utilizzare le Unit ADTQ e ADTS per code

Simulazione di prenotazione e vendita biglietti teatrali.Supponiamo di dover prenotare e vendere biglietti per uno spettacolo teatrale. Il teatro ha tre ordini di posti:A – prima fila con 10 postiB – sala con 50 postiC – loggione con 30 postiSimulare la vendita al botteghino. Siano N gli spettatori in coda. Vendere i biglietti agli spettatori in coda prenotando per loro il posto richiesto se libero.Ogni spettatore è rappresentato attraverso una struttura record del tipoCognome, Età, Posto richiesto, Posto ottenuto.La coda allo sportello viene creata prima della vendita (i dati possono anche stare su un file). Ad inizio simulazione si caricano i dati della coda in una struttura a coda con lista legata.Si inizia la vendita. Ad ogni richiesta si controlla se è disponibile il posto richiesto. In caso affermativo si trasferisce il record dalla struttura a coda in una struttura a lista legata diversa per ogni ordine di posto. Se il posto non è disponibile si propone un posto in una posizione diversa. Se lo spettatore accetta si prosegue altrimenti lo si colloca in una lista di attesa.E’ necessario prevedere le seguenti situazioni:Uno spettatore abbandona la coda.Uno spettatore in coda è servito prima perché raccomandato.Uno spettatore disdice il posto acquistato.Uno spettatore cambia ordine di posto.Fornire la lista degli spettatori in ogni ordine di posto.Fornire la lista degli spettatori in coda al botteghino.Fornire la lista degli spettatori nella lista di attesa.Le strutture da adoperare sono:Una coda realizzata con una lista legata.Una lista legata per i posti di tipo A.Una lista legata per i posti di tipo B.Una lista legata per i posti di tipo C.Una coda per la lista di attesa.Implementare e utilizzare le Unit ADTQ e ADTL per code e liste.

PROGETTO MODULO B – a.a. 2000-2001

LISTE E PUNTATORI

Una lista può essere vista come un array. Per la manipolazione degli array sono stati introdotti gli ADT delle code e degli stack, lo stesso faremo con le liste.

Una lista può anche essere vista come una serie di elementi gli uni collegati agli altri attraverso un sistema di puntatori.

a b c c d e

Le strutture a,b,…., possono essere di type integer, stringa, record, coda, stack, etc.

Una linear linked list ( o lista legata lineare) è una collezione di variabili dinamiche formate da un campo item e un campo puntatore. Ogni puntatore punta alla variabile successiva nell’ambito della struttura considerata.

Pt

P2Luca P3Ugo ?P1Emma

nodo

Variabile dinamicapuntatore

item puntatore

PxEmma ?

NextItemPt

Stringa di 20 caratteri

CONSTNullItem= ' ' ; {controllo di eventuali errori }TYPE

ItemType= STRING20[20]LNodeP=^LNodeType {puntatore a un nodo della lista}

{variabile nodo LNodeType = RECORD è anonima} Item:ItemType;

Next:LNodeP END;

VARPx:LNodeP;

Questa è una eccezione rispetto allo standard del Pascal in cui si fa riferimento a un Type che precede e non che segue.

Notare che l’identificatore LNodeP è definito prima del record dinamico LNodeType.

Px

P2Luca P3Ugo

NIL

P1Emma

Item

Next


ItemType= STRING20[20]LNodeP=^LNodeTypeLNodeType = RECORD Item:ItemType; Next:LNodeP END;

VARPx:LNodeP;

Px^.Item EmmaPx^.Next^.Item LucaPx^.Next^.Next^.Item UgoPx^.Next^.Next ^.Next^.Next NIL

Item Next

Obiettivo: progettare una ADT per le code ADTQ e una per gli stack ADTS utilizzando strutture del tipo Linear linked list.

UNIT ADTxxxxx;{documentazione}

INTERFACE {sezione interfaccia}{definizioni dell’ADT}

TYPE………………….END;{ le operazioni: primitive (constructor o selector), non primitive, predicati }PROCEDURE ……………………..FUNCTION ………………………….

IMPLEMENTATION {sezione implementazioni}PROCEDURE ……………………..FUNCTION ………………………….

Per le linear linked list vi sono operazioni che possono essere applicate a un qualunque nodo della lista. Queste primitive servono a gestire qualunque nodo e a implementare liste particolari come le code e gli stack.

Vi sono solo quattro operazioni nell’insieme delle primitive:

constructor•creazione di un nuovo nodo con un valore assegnato al campo dati (Item) e NIL al campo

link (Next)•dispose (dealloca) di un nodo supposto che esso esista come variabile dinamica

selector•selezione il campo dati (item)•seleziona il campo puntatore (next)



VARPx:LNodeP;

INTERFACE

PROCEDURE MakeNode(AnItem:ItemType; VAR Node:LNodeP);{Primitive constructor: Crea un nuovo nodo, assegnando a AnItem il valore per il campo Item e NIL al campo puntatore Next. }

PROCEDURE KillNode(VAR Node:LNodeP);{Constructor :se Node non è NIL, dispose la memoria allocata per il Node e poi pone il Node a NIL. }

PROCEDURE ItemValue(Node:LNodeP; VAR AnItem:ItemType);{Primitive Selector :ritorna il valore di AnItem per un dato Node; ritorna NullItem se il valore di Node è NIL indicando che esso rappresenta il nodo di partenza di una lista vuota}

FUNCTION NextNode(Node:LNodeP) : LNodeType;{assegnato un nodo ritorna il nodo successivo inteso come la parte di lista che ordinatamente segue il nodo in esame. Se il Node è NIL allora ritorna la lista vuota }

Item Next

Node

PROCEDURE MakeNode(AnItem:ItemType; VAR Node:LNodeP);BEGIN

new(Node);Node^.Item=AnItem;Node^.Next:=NIL

END;

PROCEDURE KillNode(VAR Node:LNodeP);BEGIN

IF Node <> NIL THEN BEGIN

dispose(Node);Node:=NIL

ENDEND;



VARPx:LNodeP;Node:LNodeP;

Item Next

Node

PROCEDURE ItemValue(Node:LNodeP; VAR AnItem:ItemType);BEGIN

IF Node <> NIL THEN AnItem := Node^.ItemELSE AnItem := NullItem

END;

FUNCTION NextNode(Node:LNodeP) : LNodeType;BEGIN

IF Node <> NIL THEN NextNode := Node^.NextELSE NextNode := NIL

END; CONSTNullItem= ' ' ; {controllo di eventuali errori }TYPE



Item Next

Node

ESEMPIOMostrare tutti i valori delle variabili dinamiche contenute in una lista a partire da un preassegnato nodo.

Soluzione ricorsivaPROCEDURE ShowList(Px:LNodeP);VARAName:ItemType;BEGINItemValue(Px,AName)If AName <> NullItem THEN

BEGINwriteln(AName);ShowList(NextNode(Px))END

END;

Soluzione iterativaPROCEDURE ShowList(Px:LNodeP);VARAName:ItemType;BEGINItemValue(Px,AName)WHILE AName <> NullItem DO

BEGINwriteln(AName);Px:=NextNode(Px);ItemValue(Px), AName)END

END;




Le code come linked list

Head

Alice

Betty

Tom

Dick

Harry

John

Tail

Head

Betty Tom Dick Harry John Alice

ItemsOnQueue 5

Head Tail

Queue

Nella logica delle code Head^ diventa il primo nodo da dereferenziare

La struttura della coda ha tre campi:ItemOnQueue : integer numero elementi in codaHead: LNodeP puntatore al primo elemento della codaTail: LNodeP puntatore all’ultimo elemento della coda

QType = RECORD ItemsOnQueue:integer; Head, Tail: LNodePEND;

CONSTNullItem= ' ' ;TYPE


Una ADTQType

HeadItemsOnQueue

Item Next Item Next

TailQType

LNodeType

LNodeP

INTERFACE

PROCEDURE MakeNode(AnItem:ItemType; VAR Node:LNodeP);{Primitive constructor: Crea un nuovo nodo, assegnando a AnItem il valore per il campo Item e NIL al campo puntatore Next.

PROCEDURE KillNode(VAR Node:LNodeP);{Constructor :se Node non è NIL, dispose la memoria allocata per il Node e poi pone il Node a NIL.

PROCEDURE ItemValue(Node:LNodeP; VAR AnItem:ItemType);{Primitive Selector :ritorna il valore di AnItem per un dato Node; ritorna NullItem se il valore di Node è NIL indicando che esso rappresenta il nodo di partenza di una lista vuota}

FUNCTION NextNode(Node:LNodeP) : LNodeType;{assegnato un nodo ritorna il nodo successivo inteso come la parte di lista che ordinatamente segue il nodo in esame. Se il Node è NIL allora ritorna la lista vuota }

Operazioni sui nodi

PROCEDURE MakeQueue(VAR Queue:QType);{Inizializza la coda }

PROCEDURE AddQueue(AnItem: ItemType; VAR Queue:QType);{Aggiunge un item alla coda }

PROCEDURE DeleteQueue(VAR Queue:QType);{Se la coda non è vuota cancella il primo item, altrimenti non fa nulla }

FUNCTION FirstOnQueue(Queue:QType): LNodeP;{Se la coda non è vuota fornisce il primo item, altrimenti da NIL }

FUNCTION QCount(Queue:QType):integer;{Fornisce il numero di oggetti che sono in coda }

FUNCTION QEmpty(Queue:QType):boolean;{E’ vera se non ci sono item in coda }

IMPLEMENTATION

PROCEDURE MakeQueue(VAR Queue:QType);{Inizializza la coda }BEGIN

WITH Queue DO BEGIN

ItemsOnQueue:=0Head:=NIL;Tail:=NIL

END;END;


HeadItemsOnQueue

Item Next Item Next

TailQType

FUNCTION FirstOnQueue(Queue:QType): LNodeP;{Se la coda non è vuota fornisce il primo item, altrimenti da NIL }BEGIN

FirsOnQueue:=Queue.HeadEND;

FUNCTION QCount(Queue:QType):integer; {Fornisce il numero di oggetti che sono in coda }BEGIN

QCount:=Queue.ItemsOnQueueEND;

FUNCTION QEmpty(Queue:QType):boolean; {E’ vera se non ci sono item in coda }BEGIN

QEmpty:=Queue.Head=NILEND;


HeadItemsOnQueue

Item Next Item Next

TailQType

Progettiamo AddQueue.

Per aggiungere un nodo contenente il valore di AnItem alla coda in primo luogo bisogna costruire il nodo (MakeNode). Questo avrà il campo Next=NIL e sarà quindi aggiunto alla coda dopo il nodo Tail^. Quindi il valore di Tail sarà assegnato al nuovo nodo.

Pseudo Codice.

MakeNode(AnItem, Temp)WITH Queue DO

collega il nodo Temp al resto della codaTail TempItemsOnQueue ItemsOnQueue + 1

Punta al nuovo nodo


HeadItemsOnQueue

Item Next Item Next

TailQType

AnItem NextTemp

La variabile locale Temp è di tipo LNodeP. Sebbene essa sia dichiarata e creata localmente il suo valore così come il valore della relativa variabile dinamica sopravvive oltre il blocco AddQueue a causa dell’operazione Tail Temp.

Se la coda non è vuota è possibile collegare direttamente il nodo usando l’istruzioneTail^.Next:=Temp

Joe NILTemp

Alice

Queue

HeadItemsOnQueue

Item Next Item Next

Tail

Joe

Se la coda è vuota i valori assegnati a Head e Tail sono entrambi NIL. In questo caso la coda con un solo item è creata dalla assegnazione

Head:=Temp e Tail:=Head

ItemsOnQueue 1

Head Tail

Queue

Joe NILTemp

NIL

Se la coda non è vuota si deve indirizzare il puntatore dell’ultimo elemento in coda Tail^.Next all’area puntata da Temp e altrettanto deve fare Tail che deve puntare all’area di Temp.Quindi

IF Head = NIL THEN Head=TempELSE Tail =Temp^.Next

Tail:=Temp

Joe NILTemp

Alice

Queue

HeadItemsOnQueue

Item Next Item Next

Tail

Joe

PROCEDURE AddQueue(AnItem: ItemType; VAR Queue:QType);{Aggiunge un item alla coda }VAR

Temp:LNodeP;BEGIN

MakeNode(AnItem,Temp);WITH Queue DO BEGIN

IF Head=NIL THEN Head:=TempELSE Tail^.Next:=Temp;

Tail:=Temp; ItemsOnQueue:= ItemsOnQueue+1

ENDEND;

HeadItemsOnQueue

Item Next Item Next

TailQType

Item Next

Temp




Progettiamo DeleteQueue.

Se la coda ha un item la postcondizione di DeleteQueue è che il suo Head è stato cancellato e un altro nodo è diventato Head. Ovviamente il vecchio nodo Head non servirà più e quindi su esso si applicherà una operazione di dispose.

Pseudo Codice.

Temp Queue.HeadIF Temp <> NIL THEN WITH Queue DO

assegna un nuovo valore a Head KillNode(Temp) ItemsOnQueue ItemsOnQueue - 1

Head Temp^.Next IF Head NIL THEN Tail NIL

Memorizza il puntatore del nododa deallocare

HeadItemsOnQueue

Item Next Item Next

TailQType

Item Next

Temp

Caso in cui in coda c’era solo unitem.

PROCEDURE DeleteQueue(VAR Queue:QType);{Se la coda non è vuota cancella il primo item, altrimenti non fa nulla }VAR

Temp: LNodeP;BEGIN

Temp:=Queue.Head;IF Temp <> NIL THEN WITH Queue DO

BEGIN Head:=Temp^.Next; IF Head = NIL THEN Tail:=NIL; dispose(Temp); ItemsOnQueue:= ItemsOnQueue-1END

END;




Data una coda di oggetti si vuole sapere in quale posizione nella coda si trova l’oggetto X.

ESEMPIOSi vuole sapere Ugo in che posizione sta.

Carla Lucio Ugo Maria Alice

A tal fine possiamo costruire una FUNCTION QPos(Queue,’Ugo’) che restituisce la posizione di Ugo e la mostra attraverso una istruzione del tipo

writeln(‘La posizione di Ugo in coda è ‘; QPos(Queue,’Ugo’))

FUNCTION QPos(Queue:Qtype; SearchItem:ItemType): integer; {Se la coda non è vuota ritorna il nodo che rappresnta il primo item nella coda; se la coda è vuota ritorna

NIL }VAR

CandNode: LNodeP;CandItem:ItemType;CandPos:integer;

BEGINCandNode:=FirstOnQueue(Queue); {il primo item nella coda o NIL}ItemValue(CandNode,CandItem);CandPos:=1;WHILE (CandItem <> NullItem) AND (CandItem <> SearchItem) DO BEGIN

CandNode:=NextNode(CandNode);ItemValue (CandNode,CandItem);CandPos:=CandPos+1;

END;IF CandItem=SearchItem THEN

Qpos:=CandPosELSE

Qpos:=0END;




BEGINwriteln(' CREA CODA');

MakeQueue(Coda);writeln(' Dammi un nome');readln(Nome);WHILE Nome<> NullItem DO

BEGIN AddQueue(Nome,Coda);

writeln(' Dammi un nome '); readln(Nome);

END;ShowList(FirstOnQueue(Coda));writeln('In coda ci sono ',QCount(Coda));WITH Coda DOBEGINwriteln(' Quanti elementi vuoi cancellare? ');readln(Nelem);Ncont:=0; WHILE ((Head<>NIL) AND (Ncont<>Nelem)) DO BEGIN readln; Ncont:=Ncont+1; ItemValue(Coda.Head,Nome); writeln('Cancello ',Nome); DeleteQueue(Coda); ShowList(FirstOnQueue(Coda)); END;writeln(' LISTA FINALE '); ShowList(FirstOnQueue(Coda)); writeln(' Cerca l''elemento '); readln(Nome); writeln(' L''elemento ' , Nome,'

e'' in ', QPos(Coda, Nome), ' posizione');IF QEmpty(Coda) THEN writeln(' La coda e'' vuota')

ELSE writeln(' In coda ci sono ',QCount(Coda),' elementi');END;END.

PROGRAM TestCodeListe;

USES ADTQ;VARCoda:QType;Nome:ItemType;Nelem, Ncont:integer;



ItemType= STRING20[20]LNodeP=^LNodeTypeLNodeType = RECORD

Item:ItemType; Next:LNodeP END;

GLI STACK COME LINKED LIST

Obiettivo progettare una ADT per uno stack di integer usando le liste.

Operazioni previste

• MakeStack primitive constructor che crea uno stack vuoto

• Push constructor per inserire un item nello stack

• Pop constructor per estrarre un elemento dalla testa dello stack

• TopItem primitive selector che ritorna il valore dell’item che è in testa allo stack

• StackEmpty predicate che ritorna TRUE se non vi sono item nello stack.

N.B. Se si cerca di estrarre un elemento da una lista vuota non deve succedere niente.Associamo il valore di maxint a TopItem quando abbiamo a che fare con una lista vuota

Lo Stack ADT non è altro che il puntatore all’item che è sul top.

CONSTNullItem=maxint;

TYPEStkP=^StkNode;ItemType=integer;StkNode= RECORD

Item:ItemType;Next:StkP

END;StkType = RECORD

Top:StkPEND;

INTERFACE

GLI OPERATORI

PROCEDURE MakeNode(AnItem:ItemType; VAR ANode:StkP);{Primitive constructor: Crea un nuovo nodo, assegnando a AnItem il valore per il campo Item e NIL al campo puntatore Next.

PROCEDURE KillNode(VAR ANode:StkP);}{Constructor :se Node non è NIL, dispose la memoria allocata per il Node e poi pone il Node a NIL}

Item Next

TOP

PROCEDURE MakeStack(VAR Stack:StkType);}{Constructor :crea uno Stack vuoto}

PROCEDURE Push(AnItem:ItemType; VAR Stack:StkType);{Inserisce il valore di AnItem nello Stack)}

PROCEDURE Pop(VAR Stack:StkType);{Estra dal top il valore di AnItem. Se lo Stack è vuoto non fa nulla)}

FUNCTION TopItem(Stack:StkType)ItemType;{Restituisce il valore dell’item che è nel top dello Stack. Se lo stack è vuoto restituisce maxint)}

FUNCTION StackEmpty(Stack:StkType)boolean;{Restituisce TRUE se non vi sono item nello Stack.}

5 Stack.Top

7

5 Stack.Top

7

PROCEDURE MakeStack(VAR Stack:StkType);}{Constructor :crea uno Stack vuoto}BEGIN

Stack.Top:=NILEND;

Stack.Top

FUNCTION TopItem(Stack:StkType)ItemType;{Restituisce il valore dell’item che è nel top dello Stack. Se lo stack è vuoto restituisce maxint)}BEGIN WITH Stack DO

IF Top <> NIL THEN TopItem:=Top^.ItemELSE TopItem:=NullItem

END;

FUNCTION StackEmpty(Stack:StkType)boolean;{Restituisce TRUE se non vi sono item nello Stack.}BEGIN

StackEmpty:= StackTOP = NILEND;

PROCEDURE Push(AnItem:ItemType; VAR Stack:StkType);{Inserisce il valore di AnItem nello Stack}VAR

Temp:StkP;BEGIN

MakeNode(AnItem,Temp); {Creo Temp=AnItem }Temp^.Next:=Stack.Top; {Assegno al puntatore di Temp il puntatore di StackTop }Stack.Top:= Temp {Stac.Top punta a Temp }

END;

5 Stack.Top

Heap

Se lo stack è vuoto Temp e quindi alla fineanche Stack.Top puntano a NIL.

7

Temp

5

Stack.Top

7

Temp

5

Stack.Top

7

Temp

PROCEDURE Pop(VAR Stack:StkType);{Elimina dal top il valore di AnItem. Se lo Stack è vuoto non fa nulla)}VAR

Temp:StkP;BEGIN

WITH Stack DO IF Top <> NIL THEN

BEGIN Temp:=Top; Top:=Temp^Next; KillNode(Temp)END;

END;

5

Stack.Top 7

Temp

Se lo stack è vuoto non si fa nulla.

Heap 5

Stack.Top

7

Temp

5

Stack.Top

7

Temp

PROGRAM TestStackListe;

USES ADTSTK;VARStack:StkType;Nome:ItemType;Nelem, Ncont:integer;

BEGINwriteln(' CREA STACK');

MakeStack(Stack);writeln;writeln(' Dammi un nome');readln(Nome);WHILE Nome<> NullItem DO

BEGIN Push(Nome,Stack);

writeln(' Dammi un nome '); readln(Nome);

END; ShowList(Stack.Top);

WITH Stack DOBEGINwriteln(' Quanti elementi vuoi cancellare? ');readln(Nelem);Ncont:=0; WHILE ((Top<>NIL) AND (Ncont<>Nelem)) DO BEGIN readln; Ncont:=Ncont+1; ItemValue(Stack.Top,Nome); ShowList(Top); writeln('Vado a cancellare ',Nome); Pop(Stack);

END; writeln(' FINE CANCELLAZIONE '); writeln(' LISTA FINALE '); ShowList(Top);END;END.



ItemType= STRING20[20]LNodeP=^LNodeTypeLNodeType = RECORD

Item:ItemType; Next:LNodeP END;

ESERCIZIO

Scrivere un algoritmo per il calcolo di una funzione tale che: ricevute in ingresso due variabili S e Z di tipo stringa calcola il numero delle occorrenze di S in Z.

Esempio:S=aaZ=ccbaaabaa

La funzione restituisce 3.

LE ESPRESSIONI ARITMETICHE

Una espressione aritmetica del tipo (7+5)*(9-8) si può rappresentare attraverso un albero di computazione come segue.

*

8957

-+

Percorrendo l’albero da sinistra a destra si ha 7+5*9-8 che secondo le convenzioni della aritmetica fornisce il risultato di 44.Se però ad ogni livello dell’albero introduciamo delle parentesi il risultato che otterremo sarà

((7+5)*(9-8))il cui valore 12 sarà identico a quello che otterremmo valutando l’espressione di partenza.

La notazione in cui i singoli termini vengono raccolti facendo uso di parentesi e sono rappresentati come sopra si chiama notazione infissa. Questa notazione è non ambigua.

Un’altra maniera per rappresentare espressioni aritmetica è la cosiddetta espressione polacca inversa introdotta dal polacco Jan Lukasiewicz nel 1951.

Questa notazione ci permette di scrivere in modo non ambiguo una espressione senza adoperare le parentesi.

Ricordando che ogni operatore aritmetico (+,-,*,/) è un operatore binario, si applica cioè a due operandi, avremo che posto della notazione infissa

a + b

scriveremo nella notazione polacca inversa

a b +

Ogni operatore binario deve quindi essere preceduto dal primo e dal secondo operando Allora (7+5)*(9-8) si scriverà:

7 5 + 9 8 - *

Nello scrivere una espressione in notazione polacca inversa o postfissa

adopereremo / al posto di DIV e \ al posto di MOD

Esempio: calcolare il valore dell’espressione:

7 3 5 + * 3 1 + /

7 8 * 3 1 + /

56 3 1 + /

56 4 /

14

Algoritmo

Si legga l’espressione in notazione polacca inversa.

Se il termine letto è un intero allora si inserisce nello stack.

Se il termine letto è un operatore allora gli ultimi due termini inseriti nello stack vengono estratti e l’operatore viene applicato ad essi.

Il risultato dell operazione viene inserita nello stack.

Quando tutte le operazioni sono state applicate allora il risultato finale dell’espressione si troverà nel top dello stack.

Applichiamo l’algoritmo all’espressione 8 6 1 - \ 4 +

8

8 6

8 1 6

8 5

3

3 4

7

68 1 - \ 4 +

Pseudo codice

MakeStack(InStack)WHILE NOT eoln DO

SkipBlanks(Ch)IF Ch is a digit THEN

GetInteger(Ch,Int)Push(Int,IntStack)

ELSE IF Ch is an operator THENApplyOperation(Ch,IntStack)ELSE IF NOT eoln THEN

Push(NullItem,IntStack)readlnShowValue(IntStack)

PROGRAM CalcolatoreRPN(input,output);Uses StackADT; VAR IntStack:StackType; Ch:char;Int:integer; ………………………... BEGIN MakeStack(IntStack);

WHILE NOT eoln DO BEGIN

SkipBlanks(Ch); IF Ch IN [‘0’..’9’] THEN BEGIN

GetInteger(Ch,Int);Push(Int,IntStack)

ENDELSE IF Ch IN [‘+’,’-’,’*’,’/’,’\’] THEN

ApplyOperation(Ch,IntStack) ELSE IF NOT eoln THEN

Push(NullItem,IntStack) END;

readln; ShowValue(Intstack)

END.

PROCEDURE SkipBlanks(VAR Ch:char);

BEGIN

Ch:=‘ ‘;

WHILE (Ch=‘ ‘) AND NOT eoln DO

read(Ch)

END;

PROCEDURE GetInteger(Ch:char;VAR Int:ItemType); BEGIN Int := 0; WHILE Ch IN [‘0’..’9’] DO BEGIN

Int:= Int*10 +ord(Ch) – ord(‘0’); IF NOT eoln THEN

read(Ch)

ELSE

Ch:=‘ ‘

END;

IF Ch <> ’ ‘ THEN

Int := NullItem

END;

Pseudo Codice ApplyOperation

Operand2 TopItem(IntStack)

Pop(IntStack)

Operand1 TopItem(IntStack)

Pop(IntStack)

IF (Operand2 = NullItem) OR (Operand1 = NullItem) THEN

Push(NullItem,IntStack)

ELSE

Result applica l’operatore ai due operandi

Push(Result,IntStack)

PROCEDURE ApplyOperation(Operator:char; VAR IntStack:StkType);VAR

Operand1, Operand2, Result: integer;BEGIN

Operand2:=TopItem(IntStack);Pop(IntStack);Operand1:=TopItem(IntStack);Pop(IntStack);IF (Operand1=NullItem OR (Operand2=NullItem) THEN

Push(NullItem,IntStack)ELSE BEGIN

CASE Operator OF ‘+’: Result:=Operand1 + Operand2; ‘-’: Result:=Operand1 - Operand2; ‘*’: Result:=Operand1 * Operand2; ‘/’: Result:=Operand1 DIV Operand2; ‘\’: Result:=Operand1 MOD Operand2;END;Push(Result,IntStack)

ENDEND;

PROCEDURE ShowValue(IntStack:StkType);VAR

Result: integer;BEGIN

Result:=TopItem(IntStack);Pop(IntStack);IF (Result=NullItem OR NOT StackEmpty(IntStack) THEN

writeln(‘ L’espressione è scritta male ‘)ELSE

writeln(Result:1)END;

LISTE GENERALIZZATE

Si vuole realizzare una ADT per le liste mediante la quale sia possibile aggiungere o eliminare nodi dalla lista in qualunque suo punto e non solo in testa o in coda come nel caso delle liste legate lineari (code e stack) fin qui viste.

A questo fine è necessario aggiungere un altro parametro nelle procedure di AddNode e DeleteNode che tenga conto della posizione del nodo da aggiungere o da eliminare rispetto alla lista. Questo può avvenire utilizzando opportunamente un puntatore.

INTERFACEPROCEDURE MakeList(VAR AList:ListType);{Crea una nuova lista vuota}

NullItem Next

ListFirst

PROCEDURE InsertNode(AnItem:ItemType; PrevNodeP:LNodeP; VAR AList:ListType);{Inserisce un Node con campo AnItem nella lista Alist. Il nodo è inserito subito dopo il nodo che ha come puntatore PrevNodeP. Se AListFirst=NIL allora il nodo sarà il primo della lista}

PROCEDURE DeleteNode(PrevNodeP:LNodeP; VAR AList:ListType);{Cancella il Nodo che nella lista segue quello puntato da PrevNodeP . Se PrevNodeP è Alist.First, viene cancellato il primo nodo. Se la lista è vuota o PrevNodeP=NIL allora non succede nulla }


ItemType= STRING[20]LNodeP=^LNodeTypeLNodeType = RECORD Item:ItemType; Next:LNodeP END;ListType = RECORD

First:LNodeP END;

VAR

FUNCTION FirstNode(AList:ListType) :LNodeP;{ritorna il puntatore del primo nodo della lista }

FUNCTION EmptyList(AList:ListType) :boolean;{ritorna TRUE se la lista è vuota }



First:LNodeP END;

VARAList:ListType;

FUNCTION CercaPrevP(Px:LNodeP; VAR AList:ListType):LNodeP;{dato il puntatore di un nodo Px fornisce il valore del puntatore del nodo che lo precede}

FUNCTION Seleziona(AList:ListType;Index:integer):ItemType;{Fornisce il nome del nodo che si trova al posto Index}

FUNCTION LPos(List:Listtype; SearchItem:ItemType):LNodeP;{Fornisce il puntatore di un preassegnato nodo SearchItem}

CONSTNullItem= ' ' ;{controllo di eventuali errori }TYPE


First:LNodeP END;

VARAList:ListType;

PROCEDURE MakeList(VAR AList:ListType);{Crea una nuova lista vuota mettendo nei campi di First rispettivamente NullItem e NIL }BEGIN MakeNode(NullItem,AList.First);END;END;

FUNCTION FirstNode(AList:ListType) :LNodeP;{ritorna il puntatore del primo nodo della lista }BEGIN

FirstNode:=ALIst.First^.NextEND;

FUNCTION EmptyList(AList:ListType) :boolean;{ritorna TRUE se la lista è vuota }BEGIN

EmptyList:=AList.First^.Next=NILEND;

AListFirst

NullItem Next

PROCEDURE InsertNode(AnItem:ItemType;PrevNodeP:LNodeP; VAR AList:ListType);VAR

Temp:LNodeP;BEGIN

MakeNode(AnItem,Temp); IF AList.First=NIL THEN BEGIN AList.First^.item:=NullItem; AList.First^.Next:=Temp END ELSE IF PrevNodeP<>NIL THEN BEGIN Temp^.Next:=PrevNodeP^.Next; PrevNodeP^.Next:=Temp; END; END;

Item NextTemp

AListFirst

NIL

Item NIL

Temp

AListFirst

Item Next Item Next Item Next

PrevNodeP

Temp Item Next

PrevNodeP

AListFirst

Item Next

Item Next

Item Next

PrevNodeP

Pseudo codice per cancellare un nodo

• Controllare se la lista è vuota.• Controllare che non si cerchi di cancellare un puntatore che vale NIL.• Cancellare il nodo indicato dal puntatore, noto, del nodo che lo precede, e far puntare quest’ultimo sul nodo succesivo a quello da cancellare.

AListFirst

NullItem Next Item Next Item Next

PrevNodeP

Item Next

PROCEDURE DeleteNode(PrevNodeP:LNodeP;VAR AList:ListType);

{Cancella il Nodo che nella lista segue quello puntato da PrevNodeP . Se PrevNodeP è NIL, viene cancellato il

primo nodo. Se la lista è vuota non succede nulla } PROCEDURE DeleteNode(PrevNodeP:LNodeP;VAR AList:ListType);VAR

Temp:LNodeP;BEGIN IF EmptyList(Alist)=FALSE THEN

IF PrevNodeP<>NIL THEN IF PrevNodeP^.Next<>NIL THEN BEGIN

Temp:=PrevNodeP^.Next; END; IF PrevNodeP=AList.First THEN BEGIN writeln(' PrevNP = AlistFirst '); Temp:=AList.First; AList.First:=AList.First^.Next; END

ELSEPrevNodeP^.Next:=PrevNodeP^.Next^.Next;

KillNode(Temp)END;

Controllare se la lista è vuota

Cancella il nodo puntato da PrevNodeP e punta PrevNodeP sul successore del nodo da eliminare

Controllare che non si cerchi di cancellare un puntatore preceduto da NIL

Caso in cui il nodo da cancellare è il primo

Introduciamo due funzioni che permettono la gestione delle liste invece che attraverso i puntatori, attraverso la posizione dei singoli nodi nella lista.

CONSTNullItem= ' ' TYPE


First:LNodeP END;

VARAList:ListType;

FUNCTION Ennesimo(P:LNodeP;n:integer):ItemType;{ricorsivamente cerca l'ennesimo elemento della lista}VARAnItem:ItemType;BEGIN

IF n=1 THEN BEGIN ItemValue(P,AnItem); Ennesimo:=AnItem; END

ELSE Ennesimo:= Ennesimo(NextNode(P),n-1) {funzione ricorsiva}

END;

FUNCTION Seleziona(AList:ListType;Index:integer):ItemType;{Data una lista resituisce l'Item che si trova nella posizione Index}BEGIN

IF Index<=0 THEN Seleziona:=NullItemELSE Seleziona:=Ennesimo(AList.First^.Next,Index)

END;

Introduciamo una funzione che permette la ricerca del puntatore che precede un preassegnato puntatore.

FUNCTION CercaPrevP(Px:LNodeP; Plist:LnodeP; VAR AList:ListType):LNodeP;

VARCandP,Temp:LNodeP;

BEGIN IF FirstNode(Alist)=Px THEN

CercaPrevP:=AList.FirstELSE

BEGINCandP:=FirstNode(Alist);WHILE (CandP <> Px) AND (CandP<>NIL) DO

BEGIN Temp:=CandP;

CandP:=CandP^.NextEND;

CercaPrevP:=TempEND

END;

Introduciamo una funzione che permette la ricerca del puntatore di un nodo di cui è noto l’item.

FUNCTION LPos(List:Listtype; SearchItem:ItemType):LNodeP;

VARCandNode: LNodeP;CandItem:ItemType;

BEGINCandNode:=FirstNode(List); {il primo item nella lista o NIL}ItemValue(CandNode,CandItem);WHILE (CandItem <> NullItem) AND (CandItem <> SearchItem) DO BEGIN

CandNode:=NextNode(CandNode);ItemValue (CandNode,CandItem);

END;IF CandItem=SearchItem THEN

Lpos:=CandNodeELSE

Lpos:=NIL ;END;

PROCEDURE ShowList(Px:LNodeP);VARAName:ItemType;BEGINItemValue(Px,AName);WHILE Px <> NIL DO

BEGINwriteln(AName);Px:=NextNode(Px);ItemValue(Px, AName)END

END;

PROGRAM TestListe;USES UList00;VARLista:ListType;Nome,Nome2:ItemType;Indice:integer;Nodo,Nodo1, Px,PrevPx:LNodeP;

PROCEDURE CaricaLista(VAR Lista:ListType);BEGIN

writeln(' CREA LISTA'); MakeList(Lista);

writeln; Nodo1:=Lista.First;

writeln(' Dammi un nome');readln(Nome);WHILE Nome<> NullItem DO

BEGIN InsertNode(Nome,Nodo1,Lista); Nodo1:=NextNode(Nodo1);

writeln(' Dammi un nome'); readln(Nome);

END; writeln('Lista iniziale'); ShowList(FirstNode(Lista));END;

PROCEDURE CancellaNodo(VAR Lista:ListType);BEGIN writeln(' Quale nome vuoi cancellare '); readln(Nome); writeln; Px:=Lpos(Lista,Nome); PrevPx:=CercaPrevP(Px,Lista); DeleteNode(PrevPx,Lista); writeln('Lista dopo la cancellazione'); ShowList(FirstNode(Lista)); readln;END;

PROCEDURE InserisciNodo(VAR Lista:ListType);BEGIN writeln('Inserisci un nodo dopo l''item '); readln(Nome); writeln('Nuovo nodo '); readln(Nome2); IF Nome='0' THEN Nodo1:=Lista.First ELSE Nodo1:=Lpos(Lista,Nome);

InsertNode(Nome2,Nodo1,Lista); writeln('Lista dopo inserimento di un nodo'); ShowList(FirstNode(Lista)); readlnEND;

PROCEDURE CancellaNumero(VAR Lista:ListType);BEGIN writeln('Cancella il nodo n. '); readln(Indice); Nome:=Seleziona(Lista,Indice); Px:=Lpos(Lista,Nome); PrevPx:=CercaPrevP(Px,Lista); DeleteNode(PrevPx,Lista); writeln('Lista dopo la cancellazione del nodo n. ',Indice); ShowList(FirstNode(Lista)); readlnEND;

{****************** BODY *****************}

BEGIN CaricaLista(Lista); CancellaNodo(Lista); InserisciNodo(Lista); CancellaNumero(Lista)END.

Consigli per un corretto uso dei puntatori e ADT

Un errore derivante da un cattivo uso di puntatori è difficilmente rilevabile.

Una ADT deve essere tale da non permettere mai all’utente di poter dereferenziare una variabile puntatore. Quindi l’utente non deve mai avere a che fare con operazioni che implicano direttamente la gestione dei puntatori.

I puntatori sono utili perché permettono la gestione di variabili dinamiche con conseguente risparmio di memoria e possono puntare direttamente a qualunque tipo di variabili incluse le variabili puntatore stesse.

Quando si progettano ADT che usano link bisogna definire due data type:- variabile nodo es. LNodeType- struttura dati nel suo complesso es. QType

Deve avere almeno un campo per i dati e un campo per il link

Deve avere almeno un campo che punta a un nodo

Per progettare una ADT bisogna costruire due insiemi di operazioni:Il primo deve avere a - costruttori per creare o eliminare nodib - selettori per accedere alle singole variabili contenute nei campi del nodoIl primo deve avere tutte le operazioni tipiche della applicazione cui fa riferimentoes. MakeStack, ShowOList, ….

Usare una chiamata per valore quando si vuole dereferenziare un puntatore.Quando si deve aggiungere o eliminare un nodo si passa il nodo per valore e la struttura per VAR

Se si vuole assegnare un nuovo valore (indirizzo) ad una variabile puntatore allora bisogna fare una chiamata per VAR.

La memoria riservata alle variabili non è mai allocata o deallocata da istruzioni di assegnazione ma solo attraverso le procedure new e dispose.Usare dispose non appena siamo sicuri che le variabili non sono più utilizzate.

Non è possibile dereferenziare un puntatore che punta a NIL. In caso contrario si ha errore.

Gli operatori che si possono applicare a NIL sono solo = o <>. Non funzionanno > o <.

Nel progetto di ADT di liste legate bisogna sempre avere una procedura di •creazione della struttura e di controllo se essa è vuota;•cancellazione di nodi della struttura con controllo se essa è vuota;

Algoritmo per aggiungere nodi

assegna i valori ai campi del nodo da aggiungereassegna i link dal nodo da aggiungere alla strutturaassegna i link dalla struttura al nodo da aggiungere

Algoritmo per eliminare nodi

assegna i valori dei link per bypassare il nodo da eliminaredispose il nodo da eliminare

Scrivere sempre una procedura per mostrare i valori delle variabili contenute nei campi delle strutture utilizzate.

Esercizio

Creare una lista legata lineare di interi in maniera casuale.Usando la ADTL introdotta a lezione:• cercare il numero più grande e metterlo in coda alla lista• eliminare tutti i numeri presenti più di una volta

PROCEDURE MakeList(VAR AList:ListType); crea una lista vuota

PROCEDURE InsertNode(AnItem:ItemType;PrevNodeP:LNodeP;VARLastNodeP:LNodeP;

VAR AList:ListType);inserisce il nodo AnItem in una lista subito dopo un altro nodo identificato tramite il suo puntatore PrevNodeP e fornisce il puntatore del nuovo nodo inserito LastNodeP

PROCEDURE DeleteNode(PrevNodeP:LNodeP;VAR AList:ListType);elimina un nodo in una lista subito dopo un altro nodo identificato tramite il suo puntatore PrevNodeP

FUNCTION CercaPrevP(Px:LNodeP; Plist:LnodeP; VAR AList:ListType):LNodeP;dato il puntatore di un nodo Px fornisce il valore del puntatore del nodo che lo precede

FUNCTION FirstNode(VAR AList:ListType):LNodeP;ritorna il puntatore al primo nodo della lista

FUNCTION EmptyList(AList:ListType):boolean;controlla se una lista è vuota

FUNCTION LPos(List:Listtype; SearchItem:ItemType):LNodeP;Fornisce il puntatore di un preassegnato nodo SearchItem

FUNCTION Seleziona(AList:ListType;Index:integer):ItemType;Fornisce il nome del nodo che si trova al posto Index

AListFirst

NullItem Next Item Next Item Next

PrevNodeP

AListFirst

Item Next Item Next Item Next

PrevNodeP

PROGETTO MODULO B – a.a. 2000-2001 Possono scegliere questo progetto solo gli studenti che hanno...

Documents

Transcript of PROGETTO MODULO B – a.a. 2000-2001 Possono scegliere questo progetto solo gli studenti che hanno...