Programmierkurs Java WS 98/99 Vorlesung 8 Dietrich Boles 09/12/98Seite 1 Programmierkurs Java Vorlesung im WS 1998/1999 am FB Informatik der Universität

Programmierkurs Java WS 98/99 Vorlesung 8 Dietrich Boles 09/12/98 Seite 1

Programmierkurs Java

Vorlesung

im WS 1998/1999

am FB Informatik

der Universität Oldenburg

Vorlesung 8

Dietrich Boles


Gliederung von Vorlesung 8

• Strukturierte Datentypen

• Felder– Motivation

– Anmerkungen

– Definition

– Erzeugung

– Zugriff

– Initialisierung

– Zerstörung

– mehrdimensionale Felder

– Beispiel

• Referenzdatentypen– Motivation

– Zuweisung

– Parameter

– Funktionsrückgabewerte

– lokale Variablen

– Beispiel

• Verbunde– Motivation

– Verbundtypdefinition

– Verbundvariablen

– Zugriff auf Verbunde

– Beispiel

• Beispielprogramme


Strukturierte Datentypen

• bisher: einfache Datentypen (int, float, char, ...)

• Benutzung: Speicherung von „einfachen“ Daten in „einfachen“ Variablen

• häufig: besonderer Zusammenhang zwischen bestimmten Daten

• Beispiele:– Menge von Zahlen, die zu sortieren sind

– Verwaltung von Personendaten (Name, Alter, Adresse, ...)

• Strukturierte Datentypen: Zusammenfassung mehrerer Daten zu einer Einheit– Felder: Daten desselben Typs

– Verbunde: Daten mit u.U. unterschiedlichem Typ


Felder / Motivation

Definition:

Ein Feld repräsentiert ein homogenes kartesisches Produkt zur Aufnahme mehrere Daten des gleichen Typs (genannt Elementtyp), wobei auf die Komponenten mit Hilfe eines Index zugegriffen wird.

Synomyme:

Array, Tupel, Matrix, Vektor, Tabelle

2 -2 67 2 90

33 3 -6 5 2

4 2 2 78 93

0

1

2

0 1 2 3 4 • 3 x 5 - Matrix (2-dimensional)• Elementtyp: int• 3 Zeilen, 5 Spalten• Numerierung beginnt bei 0 m[0][0] == 2 m[0][2] == 67 m[5][5] Laufzeitfehler


Felder / Anmerkungen

• Alternative zu Arrays: int v1, v2, v3, ..., v1000; ?????– was ist bei 100.000 Elementen?

– es existiert kein Zusammenhang (Index)!

• Elementtyp ist fest

• Dimension ist fest

• 1-, 2-, ..., n-dimensionale Arrays erlaubt

• Zugriff über n-dimensionalen Index

• random-access-Zugriff (alternativ: sequentiell Dateien auslesen)

• Arrays sind in Java Referenzdatentypen (wie Objekte)

• Arrays werden in Java dynamisch erzeugt

• Arrays werden in Java automatisch gelöscht, wenn sie nicht mehr benutzt werden (können)


Felder / Definition einer Feldvariablen

<array-def> ::= <Typ> „[“ „]“ { „[“ „]“ } <Bezeichner> { „,“ <Bezeichner> } „;“

Beispiele:

int[] vektor1; // ElemTyp: int, Dim: 1 float[][] matrix1; // ElemTyp: float, Dim: 2 char[] buchstaben; // ElemTyp: char, Dim: 1

double[][][] quader1, quader2; // ElemTyp: double, Dim: 3

char ziffern[]; // Definitionsalternative!

Elementtyp

Dimension


Felder / Definition einer Feldvariablen

• Unterscheidung zwischen den eigentlichen Felder und den Feldvariablen

• Feldvariablen speichern die Adresse des eigentlichen Feldes

• Felder werden auf dem Heap angelegt

• bei der Definition einer Feldvariablen wird kein Speicherplatz für das Feld

selbst angelegt

• vielmehr wird ein Speicherbereich reserviert, dem mittels des new-Operators

Adressen zugewiesen werden können ( Zeiger, Felderzeugung)

• man kann die Adressen weder auslesen noch auf den Adressen Operationen

ausführen (wie bspw. in C oder C++)

• Default-Initialisierung einer Feldvariablen mit dem Literal null

• auch explizite Initialisierung möglich: int[] zahlen = null;


Felder / Erzeugung eines Feldes

<array-creation> ::= <Bezeichner> „=“ „new“ <Typ> „[“ <int-Ausdruck> „]“ { „[“ <int-Ausdruck> „]“ } „;“Nebenbedingung/Anmerkungen:

– Elementyp und Dimension müssen mit der Definition der vorher definierten Feldvariablen übereinstimmen

– int-Ausdrücke bestimmen die Anzahl an Elementen der jeweiligen Dimension– Feldelemente werden nicht implizit initialisiert!

Beispiele: int[] vektor1; vektor1 = new int[8]; // Reservierung von 8 Speicherplätzen für int-Variablen

int i = 3; float[][] vektor2 = new float[i][2]; // Reservierung von 3*2 Speicherplätzen für float-Variablen


Felder / Erzeugung eines Feldes

Schema:

Stack oder Heap

Heap

<vektor1> <vektor2>„Zeiger“

0 1 2 3 4 5 6 7

0

1

2

0 1


Felder / Zugriff auf Feldelemente

<array-access> ::= <Bezeichner>

„[“ <int-Ausdruck> „]“

{ „[“ <int-Ausdruck> „]“ }

Nebenbedingungen / Anmerkungen:– Bezeichner muß gültige Feldvariable sein

– int-Ausdruck muß Wert zwischen 0 und der Anzahl der Elemente - 1 der jeweiligen Dimension liefern ( Laufzeitfehler!)

– Zugriff auf Feldelemente nennt man Indexierung

Beispiele:

int[] vek = new int[5];

vek[0] = -23;

vek[1] = vek[0] + 25;

vek[vek[1]] = -4;

vek[5] = 56; // Laufzeitfehler!

0 1 2 3 4

vek


Felder / Initialisierung der Feldelemente

Explizite Initialisierung:

int[] vektor = new int[5];

for (int i=0; i<vektor.length; i++)

vektor[i] = i*i;

length: – liefert Anzahl an Elementen (der angegebenen Dimension)

– nur lesbar!

0 1 2 3 4

vektor

0 1 4 9 16


Felder / Initialisierung der Feldelemente

Implizite Erzeugung und Initialisierung:

int i = 3;

int[] vektor = {0, 1, 4, i*i, 16};

• erzeugt Feld mit entsprechender Elementanzahl

• initialisiert die Elemente

• Initialisierungswerte können durch Ausdrücke des entsprechenden Elementtyps gebildet werden (i.a. Literale)

0 1 2 3 4

vektor

0 1 4 9 16


Felder / Zerstörung eines Feldes

• Java: automatisches Garbage-Collection!

• Kein delete-Operator

• Speicherplatz wird automatisch freigegeben, wenn nicht mehr auf Heap-Speicherplatz referenziert („gezeigt“) wird

Beispiel:

int[] vek = new int[3];

vek[0] = 4;

// ...

vek = new int[5];

vek[2] = 45;

vek[4] = -5;

0 1 2

vek

0 1 2 3 4


Felder / Mehrdimensionale Felder

Normalfall: Anzahl an Elementen pro Dimension ist identisch

float[][] vektor = new float[2][3];

for (int z=0; z < vektor.length; z++)

for (int s=0; s < vektor[z].length; s++)

vektor[z][s] = z + s;

0 1 2

vektor

0.00

1

1.0 2.0

1.0 2.0 3.0

vektor[0]

vektor[1]



Möglich: Anzahl an Elementen pro Dimension ist unterschiedlich

float[][] vektor = new float[2][];

vektor[0] = new float[2];

vektor[1] = new float[3];

for (int z=0; z < vektor.length; z++)

for (int s=0; s < vektor[z].length; s++)

vektor[z][s] = z + s;

0 1 2

vektor

0

1

vektor[0]

vektor[1]

0.0 1.0

1.0 2.0 3.0



Implizite Erzeugung und Initialisierung:

char[][] zeichen = { {‘a‘, ‘b‘, ‘c‘},

{‘A‘, ‘B‘},

{‘0‘, ‘1‘, ‘2‘, ‘3‘, ‘4‘}

};

0 1 2 3 4

zeichen

a b c

A B

0 1 2 3 4

0

1

2


Felder / Beispiel

Berechnung der Summe zweier Vektoren:

public static float min(float v1, float v2) {

return v1 <= v2 ? v1 : v2;

}

public static float[] summe (float[] v1, float[] v2) {

float[] summe = new float[min(vek1.length,vek2.length)];

for (int i=0; i<summe.length; i++)

summe[i] = vek1[i] + vek2[i];

return summe;

}

public static void main(String[] args) {

float[] vek1 = {2.3F, 3.4F, -3.4F};

float[] vek2 = {4.5F, 2.0F, 0.0F, 8.4F};

float[] res = summe(vek1, vek2);

}

0 1 2

res

6.8 5.4 -3.4


Referenzdatentypen• Motivation

– es existieren bestimmte Variablen, die lediglich Adressen („Referenzen“, „Zeiger“) auf andere Speicherbereiche speichern können

– die Kontrolle über die referenzierten Speicherbereiche liegt beim Programmierer bzw. Anwendungsprogramm, nicht beim Laufzeitsystem

– das Anwendungsprogramm kann zur Laufzeit entscheiden, wieviel Speicherplatz denn tatsächlich benötigt wird; diese Menge fordert es sich mittels des new-Operators explizit an

– ein „Garbage Collector“ gibt automatisch nicht mehr benötigte Speicherbereiche frei

• Referenzdatentypen in Java sind Felder und Objekte

• es existieren einige Unterschiede zwischen „normalen“ Speicherelementen (Variablen von einem Standarddatentyp) und referenzierten Speicherelementen (Variablen vom Referenzdatentyp):

– Zuweisung– Parameterübergabe– Funktionswert– lokale Variablen


Referenzdatentypen / Zuweisung

Adreß-Zuweisung:

int[] v = {1, 2, 3}; v[0] = -77;

int[] w = {9, 8, 7, 6}; w[0] == -77 -> true!

v = w; // Adress-Zuweisung

• bei der Adreß-Zuweisung werden lediglich die Referenzen kopiert, nicht die referenzierten Elemente

0 1 2

v

1 2 3

0 1 2

w

9 8 7 6

0 1 2

v

1 2 3

0 1 2

w

9 8 7 6

v = w;


Referenzdatentypen / Zuweisung

Element-Zuweisung (Wert-Zuweisung):

int[] v = {1, 2, 3}; v[0] = -77;

int[] w = {9, 8, 7, 6}; w[0] == 9 -> true

for (int i=0; i<v.length, i++)

v[i] = w[i]; // Element-Zuweisung

• bei der Element-Zuweisung werden die Werte der referenzierten Elemente kopiert!

0 1 2

v

1 2 3

0 1 2

w

9 8 7 6

0 1 2

v

9 8 7

0 1 2

w

9 8 7 6


Referenzdatentypen / Parameterübergabe

• Sind bei einer Funktionsdefinition Referenzdatentypen als formale Parameter definiert, so werden als aktuelle Parameter die Referenzen als Wert übergeben

• in einer Funktionen können in diesem Fall die referenzierten Elemente manipuliert werden

• nicht manipuliert werden kann jedoch die Referenzvariable selbst

public static void init(int[] vek, int value) {

for (int i=0; i<vek.length; i++)

vek[i] = value;

}

„main“ {

int[] werte = new int[3];

init(werte, 47);

// werte[i] == 47 -> true

}

0 1 2

werte

47 47 47

mainStack

Heap

vekinit


Referenzdatentypen / Funktionswerte

• Funktionen können als Funktionswert Werte vom Referenztyp liefern

public static int[] init(int[] vek, int value) {

for (int i=0; i<vek.length; i++)

vek[i] = value;

return vek;

}

„main“ {

int[] w1 = new int[3];

int[] w2 = init(w1, 47);

// w1 == w2 -> true

} 0 1 2

w1

47 47 47

mainStack

Heap

vekinit

w2


Referenzdatentypen / lokale Variablen

• bzgl. des Gültigkeitsbereich von Variablen vom Referenztyp gilt dasselbe wie bei „normalen“ Variablen

• die referenzierten Elemente werden durch Anwendung des new-Operators lebendig; sie sind solange lebendig, bis sie nicht mehr referenziert werden, also u.U. länger als die Funktion lebendig ist ( Garbage Collection)

public static foat[] init(int[] vek) { float[] fvek = new float[vek.length]; for (int i=0; i<vek.length; i++) fvek[i] = (float)vek[i]; return fvek;}„main“ { int[] w1 = {9, 8, 7}; float[] w2 = init(w1); // w2[2] == 7.0 -> true}

0 1 2

w1

9.0 8.0 7.0

mainStack

Heap

vekinit

w2

fvek

0 1 2

9 8 7


Referenzdatentypen / Beispiel

Sortierung von Zahlen:


int[] feld = {2,5,3,7,1};

print(feld);

bubbleSort(feld);

print(feld);

}

public static void print(int[] vektor) {

Terminal.out.print(“Vektor: „);

for (int i=0; i<vektor.length; i++)

Terminal.out.print(vektor[i] + “ “);

Terminal.out.println();

}

0

2

1

5

2

3

3

7

4

1

0

1

1

2

2

3

3

5

4

7


Referenzdatentypen / Beispiel

public static void bubbleSort(int[] vektor) {

boolean veraendert = false;

do {

veraendert = false;

for (int i=1; i<vektor.length; i++) {

if (vektor[i-1] > vektor[i]) {

int help = vektor[i-1];

vektor[i-1] = vektor[i];

vektor[i] = help;

veraendert = true;

}

}

} while (veraendert);

}

0 1 2 3 4

2 5 3 7 1


Verbunde / Motivation

Definition:Datenstruktur/-typ zur Zusammenfassung von mehreren u.U. Elementen unterschiedlichen Typs zu einer Einheit. Der Wertebereich eines Verbundes ist das kartesische Produkt der Wertebereiche seiner einzelnen Elemente.

Synomyme:Records, Strukturen, Datensätze

Anmerkungen:– Verbunde gibt es in Java nicht; man kann sie aber mit Hilfe von Klassen bzw. Objekten nachbilden– Verbundtypen sind Referenzdatentypen!


Verbunde / Motivation

Beispiel: Personaldatei

Mitarbeiter:

Name: char[] name;

Alter: short alter;

Geschlecht: boolean ist_mann;

Gehalt: float gehalt;

Java:

Definition des Verbundtyps:

class Mitarbeiter {

char[] name;

short alter;

boolean maennlich;

float gehalt = 2000.0F;

}

Definition einer Verbundvariablen:

Mitarbeiter dibo;

Nutzung der Variablen:

dibo.alter = 35;


Verbunde / Definition eines Verbundtyps

<Verbundtyp> ::= „class“ <Bezeichner>

„{“ { <Variablendefinition> } „}“

Anmerkungen:– der Bezeichner legt den Namen für den neuen Typ fest

– die Variablen nennt man auch Elemente

– Ort der Definition: vor oder nach der Definition der public-Klasse:

Beispiel: Datei Personalverwaltung.java

class Mitarbeiter {...}

public class Personalverwaltung {...}


Verbunde / Verbundvariablen

Definition einer Verbundvariablen:

Mitarbeiter dibo; Mitarbeiter[] personen;

Erzeugung eines Verbundes:

Mitarbeiter dibo = new Mitarbeiter(); Mitarbeiter[] personen = new Mitarbeiter[3]; for (int i=0; i<3; i++) personen[i] = new Mitarbeiter();

210

personen namealter

maennlich

gehalt

210 3

...

null

0false2000.0


Verbunde / Zugriff auf Verbunde

Zugriff auf Verbund: (via Punkt-Notation)

dibo.name = {‘d‘, ‘i‘, ‘b‘, ‘o‘};

dibo.alter = 35;

dibo.gehalt = 2000.0F * (dibo.alter / 10);

personen[0] = dibo;

personen[2].maennlich = true;

personen[2].alter = personen[0].alter + 2;

Initialisierung eines Verbundes: – bei der Definition des Verbundtyps (allgemeingültig)– explizit für jedes Element via Punkt-Notation


Verbunde / Beispiel

class Mitarbeiter { String name; float gehalt = 2000.F; boolean maennlich = true; int alter;}

public class Verwaltung { public static void main(String[] args) { Mitarbeiter karl = genM(“Karl“, 5000, true, 30); Mitarbeiter ute = genM(“Ute“, 4500, false, 34); print(karl); print(ute); }


Verbunde / Beispiel

public static Mitarbeiter genM( String n, float gh, boolean gl, int a) { Mitarbeiter person = new Mitarbeiter(); person.name = n; person.gehalt = gh; person.maennlich = gl; person.alter = a; return person; } public static void print(Mitarbeiter person) { System.out.println(“Name: “ + person.name); System.out.println(“Geh: “ + person.gehalt); if (person.maennlich) System.out.println(“maennlich“); else System.out.println(“weiblich“); System.out.println(“Alter: “ + person.alter);} }


Beispielprogramm 1

import dibo.*;

class Position { int zeile; int spalte; }

public class SchiebeSpiel {


int[][] matrix = { {2, 14, 5, 7},

{3, 4, 15, 13},

{6, 1, 12, 11},

{3, 8, 9, 0} };

print(matrix);

while (!korrekt(matrix)) {

Position position = posEingabe(matrix);

verschieben(matrix, position);

print(matrix);

} }

2 14 5 7

3 4 15 13

6 1 12 11

3 8 9

15

1 2 3

4 5 6 7

8 9 10 11

12 13 14


Beispielprogramm 1

public static void print(int[][] matrix) {

for (int i=0; i<matrix.length; i++) {

for (int j=0; j<matrix[i].length; j++) {

if (matrix[i][j] <= 10)

Terminal.out.print(" ");

Terminal.out.print(matrix[i][j] + " ");

}


}


}


Beispielprogramm 1

public static boolean korrekt(int[][] matrix) { int vgl = 0; for (int i=0; i<matrix.length; i++) { for (int j=0; j<matrix[i].length; j++) { if (vgl != matrix[i][j]) return false; vgl++; } } return true; } public static Position posEingabe(int[][] matrix) { // Achtung: erwartet eine korrekte Eingabe! Position pos = new Position(); Terminal.out.println("korrekte Zeilennummer eingeben: "); pos.zeile = Terminal.readInt(); Terminal.out.println("korrekte Spaltennummer eingeben: "); pos.spalte = Terminal.readInt(); return pos; }


Beispielprogramm 1

public static void verschieben(int[][] m, Position pos) {

Position frei = freiesFeld(m);

m[frei.zeile][frei.spalte] = m[pos.zeile][pos.spalte];

m[pos.zeile][pos.spalte] = 0;

}

public static Position freiesFeld(int[][] matrix) {

for (int i=0; i<matrix.length; i++) {

for (int j=0; j<matrix[i].length; j++) {

if (matrix[i][j] == 0) {

Position pos = new Position();

pos.zeile = i; pos.spalte = j;

return pos;

} } }

return null; // sollte eigentlich nicht vorkommen!

}

} // end class


Beispielprogramm 2

import dibo.*;public class DamenProblem { public static void main(String[] args) { int[] zeile = new int[8];

boolean[] spalte = new boolean[8]; for (int k=0; k<8; k++) spalte[k] = true;

boolean[] steidiag = new boolean[15]; for (int k=0; k<15; k++) steidiag[k] = true;

boolean[] falldiag = new boolean[15]; for (int k=0; k<15; k++) falldiag[k] = true;

int[] loesungen = {0}; setze(0, zeile, spalte, steidiag, falldiag, loesungen); System.out.println(loesungen[0]); }

eine Lösung


Beispielprogramm 2

public static void setze(int i, int[] zeile, boolean[] spalte, boolean[] steidiag, boolean[] falldiag, int[] loe) { for (int j=0; j<8; j++) { if (spalte[j] && falldiag[i+j] && steidiag[i-j+7]) { zeile[i] = j; spalte[j] = false; falldiag[i+j] = false; steidiag[i-j+7] = false; if (i < 7) { setze(i+1, zeile, spalte, steidiag, falldiag, loe); } else { print(zeile); loe[0]++; } spalte[j] = true; falldiag[i+j] = true; steidiag[i-j+7] = true; } } }


Beispielprogramm 2

public static void print(int[] zeile) { for (int i=0; i<8; i++) { System.out.print(zeile[i] + " "); } System.out.println(); }} // end class

zeile 0

zeile 7

0spalte

7spalte

stei 7

stei 0

fall 7

fall 0

Documents

Programmierkurs Java WS 98/99 Vorlesung 8 Dietrich Boles 09/12/98Seite 1 Programmierkurs Java Vorlesung im WS 1998/1999 am FB Informatik der Universität