Handout 5

Informatik 1 für D-BAUG, HS 2015
Maximum
5 Strukturierte Datentypen
1
PROGRAM Maximum1;
3
VAR
werte : ARRAY [1..10] OF INTEGER;
i,max : INTEGER;
4
5
7
Arrays, Funktionen auf Arrays, FOR-IN Schleifen,
8
dynamische Arrays, Arrays als Argumente,
9
10
Records, benutzerdefinierte Typen
11
12
14
15
16
20.10.2015
17
19
20
21
BEGIN
{ Eingabe der Messwerte }
FOR i := 1 TO 10 DO
BEGIN
Write(’Messwert ’,i,’: ’); Readln(werte[i]);
END;
{ Berechnung des Maximums }
max := werte[1];
FOR i := 2 TO 10 DO
IF werte[i] > max THEN max := werte[i];
{ Ausgabe }
Writeln(’Maximum: ’,max);
END.
Strukturierte Datentypen
Arrays
Unstrukturierte Daten
Syntax
• ARRAY [hstarti . . hendi] OF hBasistypi
• Viele Variablen, jede speichert genau einen Wert
• hstarti, hendi ganze Zahlen mit hstarti ≤ hendi
• Bsp: VAR h1,h2,h3,h4,h5,h6,h7,h8,h9 : INTEGER // Velo
VAR z1,n1,z2,n2,zres,nres : INTEGER // Brueche
• hBasistypi ist ein beliebiger Typ (z.B. REAL)
Arrays
Semantik
• Eine Variable beinhaltet beliebig viele Werte, alle vom gleichen Typ
• Speichert mehrere Werte vom gleichen Typ hBasistypi
• Bsp: Zähne pro Zahnrad, Messwerte (INTEGERs oder REALs), etc
• Index zwischen hstarti und hendi (inkl.)
Records
• Entspricht a1, a2, . . . , an in Mathe
• Eine Variable beinhaltet mehrere Werte, jeder Wert hat fixen Typ
Zugriff
• Bsp: Ein Bruch (z,n), eine Person (alter,student,weiblich), etc
• arr[i] für Array arr und Index i (lesen und schreiben)
• Index ist Ordinaltyp (INTEGER, CARDINAL, etc)
5–3
Funktionen auf Arrays
5–4
Maximum mit Low und High
Praktische Funktionen
• Low(arr) – kleinster Index des Arrays arr
1
PROGRAM Maximum2;
3
VAR
werte : ARRAY [1..10] OF INTEGER;
i,max : INTEGER;
4
5
• High(arr) – grösster Index des Arrays arr
7
• Length(arr) – Anzahl Elemente im Array arr
8
9
Wozu?
10
11
• Änderung der Länge erfordert keine Änderung des Programms
12
14
Übrigens
15
16
• Low und High auch für ordinale Variablen und Typen
17
• High(SHORTINT) → grösster Wert eines SHORTINT
• Low(x) → kleinster Wert, den x annehmen kann
5–2
19
20
5–5
21
BEGIN
{ Eingabe der Messwerte }
FOR i := Low(werte) TO High(werte) DO
BEGIN
Write(’Messwert ’,i,’: ’); Readln(werte[i]);
END;
{ Berechnung des Maximums }
max := werte[Low(werte)];
FOR i := Low(werte)+1 TO High(werte) DO
IF werte[i] > max THEN max := werte[i];
{ Ausgabe }
Writeln(’Maximum: ’,max);
END.
5–6
Informatik 1 für D-BAUG, HS 2015
Maximum mit Minimalwert
FOR-IN Schleifen
1
PROGRAM Maximum3;
Syntax:
3
VAR
werte : ARRAY [1..10] OF INTEGER;
i,max : INTEGER;
Semantik: Setze hVariablei auf jeweils einen Wert in hArrayi,
führe jedes Mal hAnweisungi aus
BEGIN
{ Eingabe der Messwerte }
FOR i := Low(werte) TO High(werte) DO
BEGIN
Write(’Messwert ’,i,’: ’); Readln(werte[i]);
END;
Beispiel
4
5
7
8
9
10
11
12
14
15
16
17
19
20
21
FOR a IN werte DO IF a > max THEN max := a
Achtung
• Reihenfolge ist nicht spezifiziert!
{ Berechnung des Maximums }
max := Low(max); // kleinster Wert dieses Typs
FOR i := Low(werte) TO High(werte) DO
IF werte[i] > max THEN max := werte[i];
{ Ausgabe }
Writeln(’Maximum: ’,max);
END.
FOR hVariablei IN hArrayi DO hAnweisungi
5–7
5–8
Maximum mit FOR-IN
Dynamische Arrays
1
PROGRAM Maximum4;
Deklaration
3
VAR
werte
: ARRAY [1..10] OF INTEGER;
i,max,a : INTEGER;
• ARRAY OF hBasistypi
BEGIN
{ Eingabe der Messwerte }
FOR i := Low(werte) TO High(werte) DO
BEGIN
Write(’Messwert ’,i,’: ’); Readln(werte[i]);
END;
• hBasistypi ist ein beliebiger Typ (z.B. REAL)
4
5
7
8
9
10
11
12
14
15
16
18
19
20
• Keine Grössenangaben!
Grösse festlegen
• SetLength(arr,n) – setzt Grösse von arr auf n Elemente
• Grösse ändern → bestehende Werte bleiben erhalten
{ Berechnung des Maximums }
max := Low(max); // kleinster Wert dieses Typs
FOR a IN werte DO IF a > max THEN max := a;
• Indizes immer von 0 bis n-1
Nachteile von dynamischen Arrays
{ Ausgabe }
Writeln(’Maximum: ’,max);
END.
• Compiler kennt Grösse nicht → mehr Laufzeitfehler
5–9
Maximum mit dynamischen Arrays
• Zuweisung idiotisch: arr1 := arr2 → arr1 ist ein Alias für arr2
Besser: arr2 := Copy(arr1) (aber nur bei dynamischen Arrays!)
Aufgabe
1
PROGRAM Maximum5;
3
VAR
werte
: ARRAY OF INTEGER;
n,i,max,a : INTEGER;
Sei arr ein ARRAY [1..10] OF INTEGER und sei i ein INTEGER.
BEGIN
Write(’Anzahl Messwerte: ’); Readln(n);
SetLength(werte,n);
Vorher:
4
5
7
8
9
11
12
13
14
15
17
18
19
21
22
23
Was bewirken die folgenden Codeschnipsel?
arr = 1
2
3
4
5
6
7
8
9
0
FOR i := 1 TO 9 DO arr[i+1] := arr[i];
{ Eingabe der Messwerte }
FOR i := Low(werte) TO High(werte) DO
BEGIN
Write(’Messwert ’,i,’: ’); Readln(werte[i]);
END;
Nachher: arr =
{ Berechnung des Maximums }
max := Low(max); // kleinster Wert dieses Typs
FOR a IN werte DO IF a > max THEN max := a;
FOR i := 9 DOWNTO 1 DO arr[i+1] := arr[i];
{ Ausgabe }
Writeln(’Maximum: ’,max);
END.
5–10
Vorher:
arr = 1
2
3
4
5
6
7
8
9
0
Nachher: arr =
5–11
5–12
Informatik 1 für D-BAUG, HS 2015
Arrays als Prozedur-Argumente
Maximum als Funktion
Open Arrays
• Array ohne Grössenangaben in Funktions-/Prozedurdeklaration
PROGRAM Maximum6;
3
FUNCTION Maximum (arr : ARRAY OF INTEGER) : INTEGER;
VAR m,a : INTEGER;
BEGIN
m := Low(m);
// kleinster Wert dieses Typs
FOR a IN arr DO IF a > m THEN m := a;
Maximum := m;
END;
4
• Nimmt ein statisches oder dynamisches Arrays als Argument
5
6
• Indizes immer von 0 bis n-1
7
8
• Open Array 6= dynamisches Array (z.B. SetLength nicht erlaubt)
9
Open Array
Deklaration
1
?
FUNCTION Maximum (werte : ARRAY OF INTEGER) : INTEGER;
11
VAR
15
BEGIN
{ Eingabe der Messwerte }
...
16
Aufruf
24
m := Maximum(arr);
// fuer statische und dynamische Arrays
m := Maximum(arr[3..5]);
// nur die Elemente 3..5 (Slice)
5–13
25
27
28
29
Mehrdimensionale Arrays
{ Berechnung des Maximums }
max := Maximum(werte);
{ Ausgabe }
Writeln(’Maximum: ’,max);
END.
• ARRAY [hstarti . . hendi] OF hBasistypi
1
PROGRAM Spur;
3
VAR
m
: ARRAY [1..5,1..5] OF INTEGER;
i,j,s : INTEGER;
4
• hBasistypi ist ein beliebiger Typ (z.B. REAL)
5
7
Deklaration
8
9
• ARRAY [a..b] OF ARRAY [c..d] OF hBasistypi
10
• Basistyp vom äusseren Array ist ein Array
11
12
• Syntactic Sugar: ARRAY [a..b,c..d] OF hBasistypi
13
14
Zugriff
16
17
(arr[i] ist eine Variable vom Typ Array)
18
• Syntactic Sugar: arr[i,j]
20
5–15
21
22
{ Berechnung }
s := 0;
FOR i := Low(m) TO High(m) DO s := s + m[i,i];
{ Ausgabe }
Writeln(’Spur = ’, s);
END.
Records (Datensätze)
Deklaration
Syntax
• RECORD
hVar1i : hTyp1i;
hVar2i : hTyp2i;
...
• ARRAY OF ARRAY OF hBasistypi
• Basistyp vom äusseren Array ist ein dynamisches Array
Grösse festlegen (auf n × m Elemente)
END
SetLength(arr,n); SetLength(arr[0],m); . . .; SetLength(arr[n-1],m)
• Syntactic Sugar: SetLength(arr,n,m)
5–16
Beispiel
VAR bruch : RECORD
zaehler : INTEGER;
nenner : INTEGER;
END
• hTyp1i, hTyp2i, . . . sind beliebige (auch verschiedene) Typen
Semantik
• Speichert mehrere Werte von beliebigen Typen
Achtung
• Geeignet um verschiedene Eigenschaften eines Objekts
• Keine Garantie, dass „rechteckig“
•
// 5x5 Matrix
BEGIN
{ Eingabe }
FOR i := Low(m) TO High(m) DO
FOR j := Low(m[i]) TO High(m[i]) DO
BEGIN
Write(’m[’, i, ’,’, j, ’] = ’);
Readln(m[i,j]);
END;
Mehrdimensionale Dynamische Arrays
•
5–14
Spur einer Matrix
Syntax (normale Arrays)
• arr[i][j]
...
zusammenzufassen (z.B. Marke, Farbe und Preis eines Autos)
SetLength(arr,7); SetLength(arr[0],3); SetLength(arr[1],5); . . .
Zugriff
• Bitte nicht . . .
5–17
• bruch.nenner für den Zugriff auf Komponente (lesen und schreiben)
5–18
Informatik 1 für D-BAUG, HS 2015
Benutzerdefinierte Typen
Syntax:
Bruchrechnen
TYPE hNamei = hTypi
Semantik:
3
4
hNamei ist ein neuer Typ
5
7
Beispiele
8
9
• TYPE INTEGER = LONGINT
10
• TYPE TWerte = ARRAY [1..10] OF INTEGER // statisches Arr.
• TYPE TWerte = ARRAY OF INTEGER
// dynamisches Arr.
• TYPE TBruch = RECORD
17
18
5–19
Typkompatibilität in Pascal
PROCEDURE Proc (x : hTyp1i);
...
3
4
5
6
7
8
Kompatibel sind
a und b: ja nein
a und c: ja nein
a und d: ja nein
d und e: ja nein
e und f: ja nein
= RECORD i : INTEGER END;
= RECORD i : INTEGER END;
T1;
T1;
T2;
RECORD i : INTEGER END;
RECORD i : INTEGER END;
TYPE TMatrix = ARRAY OF ARRAY OF INTEGER;
5
FUNCTION Spur (m : TMatrix) : INTEGER;
// Pre: m ist eine quadratische Matrix
// Post: Gibt die Summe der Diagonalelemente zureck
VAR i,s : INTEGER;
BEGIN
s := 0;
FOR i := Low(m) TO High(m) DO s := s + m[i,i];
Spur := s;
END;
7
8
9
10
11
12
13
15
VAR
19
BEGIN
SetLength(m,5,5);
...
20
28
• PROCEDURE (x : ARRAY OF REAL) → Open Array
• Dynamische Arrays als Argumente → geht nicht
Records
Lösung
• TYPE TRealArr = ARRAY OF REAL // dynamisches Array
PROCEDURE (arr : TRealArr) → geht!
5–21
...
s := Spur(m);
...
5–20
• keine „Open Records“
PROGRAM Spur2;
3
6
22
• PROCEDURE (x : RECORD . . . END) → geht nicht
Matrizen als dynamische Arrays
1
21
• PROCEDURE (x : ARRAY [1..10] OF REAL) → geht nicht
VAR y : hTyp2i;
Proc(y);
Beispiel
2
20
FUNCTION Add (a,b : TBruch) : TBruch;
VAR k : LONGINT;
BEGIN
k := Kgv(a.nenner,b.nenner);
Add.zaehler := a.zaehler * (k div a.nenner)
+ b.zaehler * (k div b.nenner);
Add.nenner := k;
END;
Arrays
• Typen sind gleich, wenn sie gleich heissen.
TYPE T1
T2
VAR
a
:
b
:
c
:
d
:
e,f :
19
PROCEDURE Kuerzen (VAR a : TBRUCH);
VAR g : LONGINT;
BEGIN
g := Ggt(a.zaehler,a.nenner);
a.zaehler := a.zaehler div g;
a.nenner := a.nenner div g;
END;
Strukturierte Variablen als Prozedur-Argumente
Grundregeln
• Variablen sind zuweisungskompatibel, wenn sie vom gleichen Typ sind.
1
13
16
Namen von benutzerdefinierten
Typen fangen mit ’T’ an
x := y;
12
15
zaehler : INTEGER;
nenner : INTEGER;
END
Pascal-Konvention:
VAR x : hTyp1i;
y : hTyp2i;
...
11
TYPE TBruch = RECORD
zaehler, nenner : LONGINT;
END;
// 5x5 Matrix
5–23
• TYPE TBruch = RECORD zaehler,nenner: LONGINT; END
PROCEDURE (a : TBruch) → geht!
5–22

Download Report