Programmazione Mod. B - prof.
Burattini - Cap 17
1
GLI INSIEMI
Un insieme è una collezione di oggetti aventi in comune determinate
proprietà.
Per determinare se una espressione assume un valore che appartiene ad
un certo insieme si è finora adoperata l’espressione
IF Variabile IN [‘xx’,’yy’,…..,’zz’] THEN
Per meglio lavorare con gli insiemi in Pascal si introducono variabili
ed espressioni definite specificamente per essi.
Programmazione Mod. B - prof.
Burattini - Cap 17
2
Il valore che può assumere una espressione di insiemi deve
appartenere ad un preciso insieme.
Esempio
Insieme delle vocali maiuscole e dei primi dieci digiti decimali (0-9)
[‘A’,’E’,’I’,’O’,’U’,’0’..’9’]
[‘A’,’E’ ,’0’..’9’,’I’,’U’,’O’]
L’ordine con cui sono elencati gli elementi appartenenti ad un insieme
è non significativo.
Programmazione Mod. B - prof.
Burattini - Cap 17
3
SET VARIABLE : valore assunto da una variabile di un set espression
[‘A’..’C’]
[‘K’..’Z’]
SET
OF
TYPE
TYPE
Numeri=1..100
InsiemeNumeri = SET OF Numeri
VAR
Universale, AlcuniInteri, Nullo: InsiemeNumeri
Universale:=[1..100] ;
AlcuniInteri:=[20,40,60,80,100] ;
Nullo:=[];
Programmazione Mod. B - prof.
Burattini - Cap 17
4
Un SET VARIABLE può contenere solo elementi appartenenti al type
del set di definizione. Questo type è detto BASE TYPE.
BASE TYPE: un ordinal type che definisce tutti i possibili membri che
un set variable può assumere.
Ordinal type: type dove ciascun valore, escluso il primo e l’ultimo ha un valore precedente o seguente
riconoscibile (Meyers pg.191)
UNIVERSAL SET: l’insieme di tutti i possibili membri definiti dal
BASE TYPE (al massimo 256 elementi).
EMPTY SET è un insieme che non contiene elementi.
TYPE
Numeri=1..100
InsiemeNumeri = SET OF Numeri
VAR
Universale, AlcuniInteri, Nullo: InsiemeNumeri
Universale:=[1..100] ;
AlcuniInteri:=[20,40,60,80,100] ;
Nullo:=[];
Programmazione Mod. B - prof.
Burattini - Cap 17
5
SET EXPRESSION : una espressione che opera su SET VARIABLE
[‘A’..’C’]+[‘K’..’Z’]
Programmazione Mod. B - prof.
Burattini - Cap 17
6
Esempio
Si vuole realizzare un correttore di testi che controlli se i caratteri letti
appartengono a Lettere, Numeri o caratteri speciali come quelli usati
per la Punteggiatura di fine frase.
Introduciamo le seguenti SET VARIABLE
Lettere=[tutte le lettere Maiuscole e tutte le lettere Minuscole]
Numeri =[caratteri numerici tra 0 e 9]
Punteggiatura=[punto, punto interrogativo e punto esclamativo ]
Programmazione Mod. B - prof.
Burattini - Cap 17
7
TYPE
CharSet=SET OF char;
……….
VAR
{variabili globali}
Lettere,
Numeri,
Punteggiatura: CharSet;
………………………….
PROCEDURE InizializzaSet(VAR Lettere, Numeri, Punteggiatura:
CharSet);
BEGIN
Lettere:=[‘A’..’Z’,’a’..’z’];
Numeri:=[‘0’..’9’];
Punteggiatura:=[‘.’,’?’,’!’]
END;
Programmazione Mod. B - prof.
8
Burattini - Cap 17
ESEMPIO
Dato un testo, su un file, vogliamo estrarre da questo le parole.
Quando si giunge a fine rigo allora al posto dell’eoln si mette un
blank.
Soluzione
Leggiamo le parole del testo carattere per carattere e ricostruiamole
mediante una operazione di concatenazione. Controlliamo ad ogni
lettura che il carattere letto appartenga all’insieme Lettere e che non
siamo giunti alla fine della linea (eoln). Se siamo in questo caso
sostituiamo eoln con un blank.
Programmazione Mod. B - prof.
Burattini - Cap 17
9
PROCEDURE ReadInCh(VAR Ch.char; VAR InFile:text);
{}
BEGIN
IF NOT eoln(InFile) THEN
read(InFile,Ch)
ELSE
Ch:=‘ ‘
END;
PROCEDURE GetWord(VAR Word:StringType; VAR LastCh:char;
VAR InFile:text);
{}
BEGIN
Word:=‘’;
ReadInCh(LastCh, InFile);
WHILE LastCh IN Letters DO
BEGIN
Word:=Word+Ch;
ReadInCh(LastCh, InFile)
END
Programmazione Mod. B - prof.
10
END;
Burattini - Cap 17
Esercizio
Dato un testo, su un file, vogliamo estrarre da questo le parole
escludendo numeri e punteggiatura o altri tipi di caratteri. Quando
appare un carattere non appartenente a Lettere questo viene ignorato, e
la parola viene scritta su un file.
Esempio
Testo: La vispa Teresa,
avea tra l'erbetta,
a volo sorpresa
gentil Farfalletta!
Risultato: LavispaTeresaaveatral'erbettaavolosorpresagentilFarfalletta
Programmazione Mod. B - prof.
Burattini - Cap 17
11
ESPRESSIONI E OPERAZIONI CON INSIEMI
Operatore
Operazione
+
*
-
unione
intersezione
differenza
A
A+B
B
Esempio
[‘A’..’C’] + [‘1’..’5’]  [‘A’..’C’,‘1’..’5’]
[1,3,5,7] * [1,2,5]  [1,5]
[1,3,5,7] - [1,2,5]  [3,7]
A
B
A*B
A
B
A-B
Per definire insiemi di oggetti distinti possiamo ricorrere agli
Enumerated Type
Programmazione Mod. B - prof.
Burattini - Cap 17
12
ESEMPIO
TYPE
VegType=(Asparagi, Bietole, Broccoli, Carote, Cipolle, Patate,
Piselli, Pomodori, Sedano,Spinaci);
VegSet=SET OF VegType;
VAR
Coop,
{verdure per la Coop}
Gs,
{verdure per il GS}
TutteVerdure,
{insieme di tutte le verdure}
Verdure:
{verdure per la Coop e GS}
VegSet;
TutteVerdure:=[Asparagi..Spinaci];
Coop:=[Bietole..Patate, Spinaci];
Gs:=[Asparagi..Carote,Pomodori,Spinaci]
Programmazione Mod. B - prof.
Burattini - Cap 17
13
Coop:=[Bietole..Patate, Spinaci];
Gs:=[Asparagi..Carote,Pomodori,Spinaci]
TutteVerdure:=[Asparagi..Spinaci];
Nella set variable Verdure possiamo mettere il risultato delle
operazioni insiemistiche che si possono applicare agli insiemi Coop
e Gs e TutteVerdure
Verdure:=Coop+Gs
[Asparagi..Patate, Pomodori, Spinaci]
Verdure:=Coop*Gs
[Bietole..Carote, Spinaci]
Verdure:=TutteVerdure-Coop
[Asparagi,Piselli..Sedano]
Verdure:=TutteVerdure-Gs
[Cipolle..Piselli,Sedano]
Verdure:=TutteVerdure-Coop -GS [Piselli,Sedano]
Verdure:=Gs-Coop
[Asparagi,Pomodori,Spinaci]
Verdure:=Coop-GS
[Cipolle,Patate]
TutteVerdure Asparagi, Bietole, Broccoli, Carote, Cipolle, Patate, Piselli, Pomodori, Sedano,Spinaci
Coop
Bietole, Broccoli, Carote, Cipolle, Patate,
Spinaci
Gs Asparagi, Bietole, Broccoli,
Carote, Mod. B - prof.
Pomodori,
Programmazione
14 Spinaci
Burattini - Cap 17
Verdure:=Coop+Gs
[Asparagi..Patate, Pomodori, Spinaci]
Tutte le verdure disponibili nei due supermercati
Verdure:=Coop*Gs
[Bietole..Carote, Spinaci]
Tutte le verdure disponibili sia nell’uno che nell’altro supermercato
Verdure:=TutteVerdure-Coop
[Asparagi,Piselli..Sedano]
Tutte le verdure non disponibili alla Coop
Verdure:=TutteVerdure-Gs
[Cipolle..Piselli,Sedano]
Tutte le verdure non disponibili al Gs
Verdure:=TutteVerdure-Coop-GS
[Piselli,Sedano]
Tutte le verdure non disponibili né alla Coop né al Gs
Verdure:=Gs-Coop
[Asparagi,Pomodori,Spinaci]
Tutte le verdure disponibili al Gs ma non alla Coop
Verdure:=Coop-GS
[Cipolle,Patate]
Tutte le verdure disponibili alla Coop ma non al Gs
TutteVerdure Asparagi, Bietole, Broccoli, Carote, Cipolle, Patate, Piselli, Pomodori, Sedano,Spinaci
Programmazione
Mod. B - prof.
15Spinaci
Coop
Bietole, Broccoli,
Carote, Cipolle,
Patate,
Gs Asparagi, Bietole, Broccoli, Burattini
Carote,- Cap 17
Pomodori,
Spinaci
=
<>
<=
<
<=
<
OPERATORI RELAZIONALI
eguaglianza tra insiemi
[Coop+Gs]*[Piselli,Sedano]=[]
diseguaglianza tra insiemi
Coop<>Gs
sottoinsieme di altro insieme
[Bietole,Carote..Patate]<Coop
sottoinsieme proprio di altro insieme
Coop<=TutteVerdure
soprainsieme di altro insieme
Coop+Gs+[Piselli,Sedano]>=TutteVerdure
soprainsieme proprio di altro insieme
TutteVerdure >Coop+Gs
TutteVerdure Asparagi, Bietole, Broccoli, Carote, Cipolle, Patate, Piselli, Pomodori, Sedano,Spinaci
Programmazione
Mod. B - prof.
16Spinaci
Coop
Bietole, Broccoli,
Carote, Cipolle,
Patate,
Gs Asparagi, Bietole, Broccoli, Burattini
Carote,- Cap 17
Pomodori,
Spinaci
SEMANTICA
[Coop+Gs]*[Piselli,Sedano]=[]
Né la Coop né il Gs hanno Piselli e Sedano
Coop<>Gs
La Coop e il Gs non hanno esattamente le stesse verdure
[Bietole,Carote,Patate]<Coop
Le Carote, Cipolle e Patate sono tutte vendute alla Coop
Coop<TutteVerdure
La Coop non ha tutte le verdure possibili
Coop+Gs+[Piselli,Sedano]>=TutteVerdure
Le verdure della Coop più quelle del Gs più i Piselli e il Sedano
rappresentano tutte le verdure del mercato
TutteVerdure >Coop+Gs
Le verdure disponibili sulProgrammazione
mercato sono
più di quelle vendute17dalla
Mod. B -di
prof.
Burattini - Cap 17
Coop e dal Gs
Alcuni algoritmi per l’elaborazione di insiemi
Algoritmo 14.1
Sia dato un insiemi di possibili eventi, esempio tutti i numeri interi tra 1
e 100. Si vuole costruire l’insieme di tutti i numeri estratti a caso da un
generatore random in 50 chiamate.
Chiamiamo
AccumulatoreUniversale l’insieme di tutti i possibili numeri da estrarre,
Accumulatore l’insieme in cui mettiamo i numeri estratti,
EventoCasuale il singolo numero estratto.
Pseudo Codice
Accumulatore  []
WHILE non si sono generati tutti i numeri DO
genera un EventoCasuale
IF EventoCasuale appartiene all’AccumulatoreUniversale THEN
Programmazione Mod. B - prof.
18
Accumulatore

Accumulatore
+
[EventoCasuale]
Burattini - Cap 17
Algoritmo 14.2
Sia dato un insiemi di possibili eventi, esempio tutti i numeri interi tra 1
e 100. Si vuole costruire l’insieme di tutti i numeri non estratti da un
generatore random in 150 chiamate.
Chiamiamo
RegistratoreUniversale l’insieme di tutti i possibili numeri da estrarre
Registratore l’insieme di tutti i possibili numeri ancora non estratti
EventoCasuale il singolo numero estratto.
Pseudo Codice
Registratore  RegistratoreUniversale {insieme universale degli eventi}
WHILE non si sono generati tutti i numeri DO
genera un EventoCasuale
IF EventoCasuale appartiene al Registratore THEN
Mod. B - prof.
19
Registratore Programmazione
 Registratore
[EventoCasuale]
Burattini - Cap 17
Un SET VARIABLE può essere interpretato come una astrazione
capace di caratterizzare uno o più oggetti di un array di variabili
booleane.
Quando un SET VARIABLE è inizializzato a [ ] questo implica che
tutti i flag booleani che riguardano i suoi elementi nell’array sono
posti a FALSE.
In altre parole è falso che un qualunque elemento X appartenga
all’insieme vuoto.
Quando un SET VARIABLE è inizializzato all’UNIVERSAL SET
questo implica che tutti i flag booleani che riguardano i suoi elementi
nell’array sono posti a TRUE.
In altre parole è vero che qualunque elemento X dell’UNIVERSAL
SET appartiene all’insieme.
Se si aggiunge un nuovo elemento al SET VARIABLE il flag
corrispondente diventa TRUE
Se si elimina un elemento dal SET VARIABLE il flag corrispondente
Programmazione Mod. B - prof.
20
diventa FALSE
Burattini - Cap 17
Algoritmo 14.3
Supponiamo di voler fare delle elaborazioni su un set variable
denominato SomeSet.
Chiamiamo
SomeSet il set variable su cui si vuole operare
Candidato il singolo elemento di SomeSet.
MinVal e MaxVal i valori minimo e massimo assunti dagli elementi di
SomeSet tra i quali si vuole fare l’elaborazione
{Elabora gli elementi di SomeSet}
Pseudo Codice
FOR Candidato  MinVal TO MaxVal DO
IF Candidato IN SomeSet THEN
elabora Candidato
SomeSet deve essere un sottoinsieme di un UNIVERSAL SET mentre
la Base Type è determinataProgrammazione
dal sub-range
Mod. B -MinVal..MaxVal
prof.
21
Burattini - Cap 17
Caso di studio 14.1
Scrivere un programma che mostri tutte le lettere maiuscole presenti in
un preassegnato testo e tutte le minuscole non presenti.
Abbiamo bisogno di due SET VARIABLE
InsiemeMaiuscole
InsiemeMinuscole
Pseudo codice
Inizializza(InsiemeMinuscole, InsiemeMaiuscole, File)
{assegna gli insiemi universali a InsiemeMinuscole=[‘a’..’z’], InsiemeMaiuscole=[] e reset File}
RegistraInformazioni(InsiemeMinuscole, InsiemeMaiuscole, File)
{legge i caratteri da File li cancella da InsiemeMinuscole se minuscoli, se maiuscoli li aggiuge a
InsiemeMaiuscole}
MostraInformazioni(InsiemeMinuscole, InsiemeMaiuscole)
{mostra il contenuto di InsiemeMinuscole e InsiemeMaiuscole al termine dell’elaborazione}
Programmazione Mod. B - prof.
Burattini - Cap 17
22
PROGRAM MostraCaratteri(output,Teresa)
{}
TYPE
MinuSetType=SET OF ‘a’..’z’;
MaiuSetType=SET OF ‘A’..’Z’;
VAR
Teresa :text;
InsiemeMaiuscole: MaiuSetType;
InsiemeMinuscole: MinuSetType;
PROCEDURE Inizializza(VAR InsiemeMaiuscole: MaiuSetType;
VAR InsiemeMinuscole: MinuSetType; VAR Teresa:text);
BEGIN
reset(Teresa);
InsiemeMinuscole:=[‘a’..’z’];
InsiemeMaiuscole:=[]
END;
Programmazione Mod. B - prof.
23
…………………………………...
Burattini - Cap 17
RegistraInformazioni
WHILE NOT eof(Teresa) DO
read(Teresa,Ch)
IF Ch IN [‘a’..’z’] THEN
InsiemeMinuscole  InsiemeMinuscole - [Ch]
ELSE
IF Ch IN [‘A’..’Z’] THEN
InsiemeMaiuscole  InsiemeMaiuscole + [Ch]
Domanda: perché non è necessario controllare l’eoln?
Programmazione Mod. B - prof.
Burattini - Cap 17
24
PROCEDURE RegistraInformazioni(VAR InsiemeMinuscole:
MinuSetType; VAR InsiemeMaiuscole: MaiuSetType; VAR
Teresa:text);
{}
VAR
Ch:char;
BEGIN
WHILE NOT eof(Teresa) DO
BEGIN
read(Teresa,Ch);
IF Ch IN [‘a’..’z’] THEN
InsiemeMinuscole:= InsiemeMinuscole - [Ch]
ELSE
IF Ch IN [‘A’..’Z’] THEN
InsiemeMaiuscole:= InsiemeMaiuscole + [Ch]
END
Programmazione Mod. B - prof.
25
END;
Burattini - Cap 17
MostraInformazioni
mostra testo esplicativo
FOR Ch  ‘A’ TO ‘Z’ DO
IF Ch IN InsiemeMaiuscole THEN
write(Ch)
writeln
mostra testo esplicativo
FOR Ch  ‘a’ TO ‘z’ DO
IF Ch IN InsiemeMinuscole THEN
write(Ch)
writeln
Programmazione Mod. B - prof.
Burattini - Cap 17
26
PROCEDURE MostraInformazioni(VAR InsiemeMinuscole: MinuSetType;
VAR InsiemeMaiuscole: MaiuSetType;
{}
VAR
Ch: char;
BEGIN
write(‘ Lettere maiuscole presenti: ‘);
FOR Ch  ‘A’ TO ‘Z’ DO
IF Ch IN InsiemeMaiuscole THEN
write(Ch);
writeln;
write(‘ Lettere minuscole assenti: ‘);
FOR Ch  ‘a’ TO ‘z’ DO
IF Ch IN InsiemeMinuscole THEN
write(Ch);
writeln
END;
Programmazione Mod. B - prof.
Burattini - Cap 17
27
{BODY}
BEGIN
Inizializza(InsiemeMinuscole, InsiemeMaiuscole, Teresa);
RegistraInformazioni(InsiemeMinuscole, InsiemeMaiuscole, Teresa);
MostraInformazioni(InsiemeMinuscole, InsiemeMaiuscole);
END.
Programmazione Mod. B - prof.
Burattini - Cap 17
28
SET VARIABLE
SET VARIABLE
[ ]
[X,Y,…... ]
INSIEME VUOTO
INSIEME UNIVERSALE
Problema n. 14.2
Sistema per evidenziare l’eventuale assenza di vocali nell’ambito di
una parola. Se c’è almeno una vocale va bene altrimenti il sistema deve
eseguire la seguente procedura:
mostrare la parola
memorizzarla in un file
memorizzarla in un array
Programmazione Mod. B - prof.
Burattini - Cap 17
29
Pseudo codice
GetAWord(Word, ChSet, SomeFile)
IF VocaliMancanti(Vocali, ChSet) THEN
Process(Word)
Dove
SomeFile è un file testo da cui si legge la parola
Vocali è il valore che assume un insieme inizializzato con tutte le vocali
ChSet è l’insieme di caratteri che costituiscono la parola contenuta nella
variabile Word
VocaliMancanti è una funzione booleana che ritorna TRUE se mancano
le vocali in Word
Programmazione Mod. B - prof.
Burattini - Cap 17
30
Prima di lanciare GetAWord e VocaliMancanti supponiamo di avere
eseguito il seguente codice:
TYPE
ChSet Type= SET OF char;
VAR
Wordset, Vocali: ChSetType;
{inizializza Vocali}
Vocali:=[‘A’,’E’,’I’,’O’,’U’,’a’,’e’,’i’,’o’,’u’];
se ora facciamo l’intersezione tra Vocali e WordSet e troviamo che
l’intersezione è vuota questo significa che nella parola non ci sono
vocali.
FUNCTION VocaliMancanti(Vocali,WordSet:ChSetType):boolean;
BEGIN
VocaliMancanti:=(Vocali*WordSet=[])
Programmazione Mod. B - prof.
31
END;
Burattini - Cap 17
Se vogliamo una funzione che controlli che ci sia almeno una
consonante nella nostra parola basterà definire un inseme di consonanti
ottenuto per differenza tra tutte le lettere dell’alfabeto e Vocali.
FUNCTION NoConsonant(Vocali,WordSet:ChSetType):boolean;
VAR
ConSet:ChSetType;
BEGIN
ConSet:=[‘a’..’z’;’A’..’Z’]- Vocali;
NoConsonant :=(ConSet*WordSet=[])
END;
Programmazione Mod. B - prof.
Burattini - Cap 17
32
Problema del Consiglio di Amministrazione
Supponiamo che un Consiglio di Amministrazione possa tenere riunioni
valide solo quando:
la metà più uno dei suoi membri è presente
e
o il presidente (P) e la segretaria (S) sono presenti
o il presidente (P) e il tesoriere (T) sono presenti
o il vice-presidente (VP) e la segretaria (S) e il tesoriere (T) sono presenti
Valido=
(TotMembri/2) AND (
(P AND S)
OR
(P AND T)
OR
(VP AND S AND T) )
Programmazione Mod. B - prof.
Burattini - Cap 17
33
TYPE
ConsiglioType=(P,S,T,M1,M2,M3,M4,M5,M6,M7,M8,M9);
InsiemePresenti=SET OF ConsiglioType;
CONST TotaleMembri:=9;
VAR
Presenti: InsiemePresenti;
TotPresenti:integer;
………………..
FUNCTION Valido(Presenti: InsiemePresenti;
TotPresenti:integer):boolean;
BEGIN
Valido:=(TotPresenti>TotaleMembri DIV 2) AND
( ([P,S]< Presenti) OR
([P,T]< Presenti) OR
([VP,S,T]< Presenti) )
Programmazione Mod. B - prof.
34
END;
Burattini - Cap 17
UNIT STRINGHE
Si vuole creare una UNIT che operi sulle stringhe e che sia il più
possibile indipendente dal dialetto PASCAL adoperato.
Adoperiamo una struttura a RECORD per il data Type
StringADT
Chars
Len
Array
Programmazione Mod. B - prof.
Burattini - Cap 17
35
UNIT Stringa;
INTERFACE
CONST
MaxLength=80;
TYPE
SysString=STRING[MaxLength];
StringADT=RECORD
Chars:ARRAY[1.. MaxLength] OF char;
Len:0.. MaxLength
END;
Programmazione Mod. B - prof.
Burattini - Cap 17
36
Constructor - cambia o inizializza i valori di una variabile astratta
Primitive constructor - assegna un valore ad una variabile astratta
senza fare uso di altre variabili astratte dello stesso tipo. Ha una sola
variabile di output e quelle di input servono per costruire l’output.
Programmazione Mod. B - prof.
Burattini - Cap 17
37
IMPLEMENTATION
PROCEDURE NullString(VAR OutStr:StringADT);
BEGIN
END;
Primitive constructor
ritorna una la stringa nulla ‘’.
PROCEDURE ConvertSysString(StrValue:SysString;
VAR OutStr:StringADT);
VAR
Position:1..MaxLength;
BEGIN
WITH OutStr DO
BEGIN
Len:=length(StrValue);
FOR Position:=1 TO Len DO
Chars[Position]:=StrValue[Position]
END
END;
converte una stringa rappresentata in un qualche sistema
Mod. B - prof.
nella stringa equivalente di Programmazione
typeBurattini
StringADT
- Cap 17
38
Primitive constructor
PROCEDURE ReadString(Sentinel:char;VAR OutStr:StringADT;
VAR InFile:text);
VAR
Ch:char;
BEGIN
WITH OutStr DO
BEGIN
Len:=0;
ReadCh(Sentinel,Ch,Len,InFille)
WHILE Ch<>Sentinel DO
BEGIN
Len:=Len+1;
Chars[Len]:=Ch;
ReadCh(SentinelCh,Len,InFile)
END
END
END;
legge la stringa da un file escludendo eventuali caratteri sentinella
Programmazione Mod. B - prof.
Burattini - Cap 17
39
Primitive constructor
PROCEDURE ReadlnString (Sentinel:char;
VAR OutStr:StringADT;VAR InFile:text);
VAR
Ch:char;
BEGIN
WITH InString DO
BEGIN
Len:=0;
WHILE NOT eoln(InFile) AND NOT (Len=MaxLength) DO
BEGIN
Read(Infile,Ch);
Len:=Len+1;
Chars[Len]:=Ch;
END
END
END;
legge una stringa da una linea di un file predeterminato
Programmazione Mod. B - prof.
Burattini - Cap 17
40
SELECTOR - fornisce informazioni su una variabile di input
ADT ad un parametro di uscita. Spesso è una funzione (il parametro
di uscita in tal caso è la funzione stessa).
Primitive selector - ritorna il valore di uno dei componenti della
variabile astratta.
Programmazione Mod. B - prof.
Burattini - Cap 17
41
FUNCTION ACh(Instr:StringADT;Position:integer):char;
BEGIN
IF Position>InStr.Len THEN
Ach:=chr(0)
ELSE
Ach:=InStr.Chars[Position]
END;
Primitive selector
ritorna il carattere N-esimo di una stringa
FUNCTION StrLength(Instr:StringADT):integer;
BEGIN
StrLength:=Instr.Len
END;
Primitive selector
ritorna la lunghezza della stringa
Programmazione Mod. B - prof.
Burattini - Cap 17
42
Non-primitive selector - ritorna il valore che non è relativo ad uno
dei componenti della variabile astratta ma ciò nonostante è utile al
client.
Programmazione Mod. B - prof.
Burattini - Cap 17
43
PROCEDURE WriteString (InStr:StringADT; VAR OutFile:text);
VAR
Position:integer;
BEGIN
Non-primitive
WITH InStr DO
FOR Position:=1 TO Len DO
write(OutFile,Chars[Position])
END;
selector
scrive una stringa in un file
PROCEDURE WritelnString(InStr:StringADT; VAR OutFile:text);
BEGIN
WriteString(Instr,OutFile);
Non-primitive
writeln(OutFile)
END;
selector
scrive una stringa in un file seguita da un <eoln>
Programmazione Mod. B - prof.
Burattini - Cap 17
44
FUNCTION StartPos((Substr, SearchStr:StringADT):integer;
VAR
SLen,Pos: integer;
Found: Boolean;
CandStr: StringADT;
BEGIN
SLen:=SubStr.Len;
Found:=FALSE;
Pos:=1;
WHILE NOT (SearchStr.Len+1-Pos>SLen) AND NOT Found DO
BEGIN
StrExtract(SearcStr,Pos,SLen,CandStr);
IF StrEqual(CandStr,SearchStr) THEN
Found:=TRUE
ELSE
Selector operations
Pos:=Pos+1
END;
IF Found THEN
StratPos:=Pos
ELSE
StratPos:=0
Ritorna la posizione di partenza di una data subEND;
Mod. B - prof.
45
stringaProgrammazione
nell’ambito
di
una
preassegnata
stringa
Burattini - Cap 17
PREDICATE - è una funzione booleana che ritorna informazioni
sul valore o lo stato di una variabile astratta.
Programmazione Mod. B - prof.
Burattini - Cap 17
46
FUNCTION StrEqual(Instr1, Instr2:StringADT):boolean;
VAR
Pos,
TotalChars:integer;
StillEqual:boolean;
Predicate operations
BEGIN
IF Instr1.Len<>Instr2.Len THEN
StillEqual:= FALSE
ELSE
StillEqual:= TRUE;
TotalChars:= Instr1.Len;
Pos:=1;
WHILE NOT(Pos>TotalChars) AND StillEqual DO
IF Minuscole(InStr1.Chars[Pos])<> Minuscole(InStr2.Chars[Pos]) THEN
StillEqual:= FALSE
ELSE
Pos:=Pos+1;
StrEqual:=StillEqual
END;
ritorna TRUE se due stringhe hanno gli stessi caratteri e la stessa
lunghezza
Programmazione Mod. B - prof.
47
Burattini - Cap 17
Predicate operations
FUNCTION StrLessThan(InStr1, InStr2:StringADT):boolean
BEGIN
……………….
END;
ritorna TRUE se la prima stringa precede alfabeticamente la seconda
Programmazione Mod. B - prof.
Burattini - Cap 17
48
Non-primitive constructor -. Ha almeno una variabile di input il cui
tipo è uguale a quello dell’output.
Programmazione Mod. B - prof.
Burattini - Cap 17
49
Non-primitive constructor
PROCEDURE ChConcat (Ch; VAR InOutStr:StringADT);
BEGIN
WITH InOutStr DO
IF Len<MaxLength THEN
BEGIN
Len:=Len+1;
Chars[Len]:=Ch
END
END;
concatena un singolo carattere ad una stringa
Programmazione Mod. B - prof.
Burattini - Cap 17
50
Non-primitive constructor
PROCEDURE StrConcat (InStr1, InStr2:StringADT Ch; VAR InOutStr:StringADT);
VAR
PosStr2:integer;
BEGIN
OutStr:=Instr1;
PosStr2=0;
WITH OutStr DO
WHILE NOT (PosStr2=Instr2.Len) AND NOT (Len=MaxChars) DO
BEGIN
PosStr2:= PosStr2+1;
Len:=Len+1;
Chars[Len]:=InStr2.Chars[PosStr2]
END
END;
concatena due stringhe
Programmazione Mod. B - prof.
Burattini - Cap 17
51
PROCEDURE StrExtract(InStr:StringADT; Start, TotalChs:integer; VAR OutStr: StringADT);
VAR
InStrPos,
OutStrPos
:integer;
Non-primitive constructor
BEGIN
WITH OutStr DO
BEGIN
IF Start > Instr.Len THEN
Len:=0
ELSE IF TotalChs > InStr.Len+1-Start THEN
Len:=InStr.Len+1-Start
ELSE
Len:=TotalChs;
InStrPos:=Start;
FOR OutStrPos:=1 TO Len DO
BEGIN
Chars[OutStrPos]:=InStr.Chars[InStrPos];
InStrPos:=InStrPos+1
END
END
END;
copia una stringa di una predeterminata
lunghezza a partire da
una
Programmazione Mod. B - prof.
52
- Cap di
17 output
determinata posizione in unaBurattini
stringa
Non-primitive constructor
PROCEDURE StrRemove(Start, TotalChs:integer; VAR InOutStr: StringADT);
PredString,
SuccString:
StringADT;
BEGIN
IF NOT (Start>InOutStr.Len) THEN
BEGIN
StrExtract(InOutStr,1,Start-1,PredString);
StrExtract(InOutStr,1,Start+TotalChs,InOutStr.Len,SuccString);
StrConcat(PredString, SuccString,InOutStr)
END
END;
rimuove un predeterminato numero di caratteri a partire da
una certa posizione di una stringa di input/output
PROCEDURE StrInsert(InStr:StringADT; Start:integer; VAR InOutStr: StringADT);
BEGIN
END;
inserisce un predeterminata
stringa
caratteri a partire da 53una
Programmazione
Mod. di
B - prof.
Burattini - Cap 17
certa posizione in una variabile
stringa.
Non-primitive constructor
PROCEDURE ReadCh(Sentinel:char;PresentLength:integer;
VAR Ch:char;VAR InFile:text);
BEGIN
IF NOT(eoln(InFile) OR (PredsentLength= MaxLength)) THEN
Read(InFile,Ch);
ELSE
Ch:=Sentinel
END;
legge i caratteri di una stringa da un file e se supera la lunghezza
prefissata o trova eoln restituisce un carattere sentinella
Programmazione Mod. B - prof.
Burattini - Cap 17
54
FUNCTION Minuscole(Ch:char):char;
BEGIN
IF Ch IN ['A'..'Z'] THEN
Minuscole:=chr(ordCh)+ord('a')-ord('A'))
ELSE
Minuscole:=Ch
END;
trasforma le maiuscole in minuscole
Programmazione Mod. B - prof.
Burattini - Cap 17
55
PROCEDURE ChConcat (Ch; VAR InOutStr:StringADT);
BEGIN
WITH InOutStr DO
IF Len<MaxLength THEN
BEGIN
Len:=Len+1;
Chars[Len]:=Ch
END
END;
concatena i caratteri in una stringa controllando che la
lunghezza massima non venga superata
Programmazione Mod. B - prof.
Burattini - Cap 17
56
Dato il tipo astratto lista utilizzare le routine elencate per sviluppare il seguente
algoritmo:
date tre liste di interi L1, L2, L3, aggiungere in L1 solo gli elementi di L2 presenti
in L3 e non in L1, eliminando tutti gli altri.
Function Lung(L:tipolista): integer;
(*valuta la lunghezza della lista*)
Function estrai(L:tipolista, n:integer): integer;
(* fornisce il valore dell’ennesimo intero della lista, se esiste, maxint
altrimenti*)
Procedure aggiungi(L:tipolista, n:integer; k:integer): integer;
(* aggiunge nella posizione n della lista, l’elemento k*)
Procedure cancella(var L:tipolista; n: integer);
(*cancella l’ennesimo elemento della lista, se esiste*)
Es.
L1
8
4
2
5
6
L2
2
1
7
4
3
6
L3
2
5
7
1
3
Risultato
Mod. B - prof.
57
L1
1
7
3 Programmazione
Burattini - Cap 17
Utilizzare le seguenti routine per il tipo astratto lista per sviluppare il seguente
algoritmo:
date tre liste L1, L2, L3, contenenti lettere dell’alfabeto, lasciare in L1 tutte le vocali
presenti in L1, L2 e L3, senza ripetizioni, ordinate in maniera crescente, in L2 tutte
le consonanti presenti in L1, L2 e L3, senza ripetizioni, ordinate in maniera
decrescente in L3, tutti caratteri, presenti in L1, L2 e L3, senza ripetizioni, ordinate
in maniera crescente.
Function Lung(L:tipolista): integer;
(*valuta la lunghezza della lista*)
Function estrai(L:tipolista, n:integer): char;
(* fornisce il valore dell’ennesimo carattere della lista, se esiste, ‘?’ altrimenti*)
Procedure cancella(var L:tipolista; n: integer);
(*cancella l’ennesimo elemento della lista, se esiste*)
Procedure aggiungi(var L:tipolista; n: integer; lettera:char);
(*aggiunge dopo l’ennesimo elemento della lista il carattere lettera*)
Es.
L1
b a z e f o  a e i o
L2
i q w e a z  Programmazione
z w q f Mod.
b B - prof.
L3
f b o a  a b e f iBurattini
o q- Cap
w 17z
58