Kap.6: REIHUNG
Kapitel-Index
6.1 Reihung in mehreren Dimensionen
6.2 Reihung als Referenztyp
6.3 Aggregat zur Initialisierung
6.4 Zuweisung von new-Reihungen
6.5 Testfragen
6.1 Reihung in mehreren Dimensionen
Reihungen von Komponenten gibt es in einer (Vektor), zwei (Matrix), drei (Quader) oder mehr Dimensionen. Die gewünschte Dimension ist bereits bei der Vereinbarung der Reihung festzulegen, die
Indexlänge in jeder Dimension erst bei der Initialisierung per
Aggregat (6.3) oder bei der Initialisierung oder Zuweisung per new
-Reihung (6.4). Die vorangehenden Kapitel behandelten Skalare,
d.h. Größen, die noch keine Reihungen darstellen.
VEKTOR z.B.
char[] zeile= {'Z' , 'e' , 'i' , 'l'};
1-dimens. Reihung 
-------
---------------------
aus Komponenten 
Z e i l
vom Typ char,
1 Index i 0 1 2 3 
-
i
-------
--------------------
zeile[1]
MATRIX z.B.
char[][] seite= {{'S' , 'e' , 'i' , 't'},
{'m' , 'i' , 't' , '3'},
{'Z' , 'e' , 'i' , 'l'}};
----------------------------
S e i t
0 0 0 1 0 2 0 3 -j
2-dimens. Reihung 
----------------------------
aus Komponenten m i t 3
vom Typ char,
1 0 1 1 1 2 1 3
---------------------------
Z e i l
2 Indizes i,j 2 0 2 1 2 2 2 3
--------------------------
i seite[1][2]
QUADER z.B.
char[][][] buch= {{{'B' , 'u' , 'c' , 'h'},
{'m' , 'i' , 't' , '2'},
{'S' , 'e' , 'i' , 't'}},
{{'S' , 'e' , 'i' , 't'},
{'m' , 'i' , 't' , '3'},
{'Z' , 'e' , 'i' , 'l'}}};
----------------------------
B u c h
0 0 0 0 0 1 0 0 2 0 0 3
----------------------------
m i t 2 --------
t
0 1 0 0 1 1 0 1 2 0 1 3
3-dimens. Reihung ---------------------------- 1 0 3 -k
aus Komponenten S e i t --------
vom Typ char, 3
0 2 0 0 2 1 0 2 2 0 2 3
--\---------------------- 1 1 3
\ ----------------------------
\ Z e i l
3 Indizes i,j,k i 1 2 0 1 2 1 1 2 2 1 2 3
--------------------------
buch[1][2][3]
j
In Java lassen sich auch "nichtrechtecksförmige" Reihungen bilden:
DREIECKSMATRIX z.B.
char[][] pascal= {{1},
{1 , 1},
{1 , 2 , 1}};
-------
1
0 0 -j
2-dimens. Reihung --------------
aus Komponenten 1 1
vom Typ int,
1 0 1 1
---------------------
1 2 1
2 Indizes i,j 2 0 2 1 2 2
-------------------
pascal[2][1]
i
Alle Komponenten einer Reihung müssen vom gleichen Typ sein. Die
Identifizierung der Komponenten geschieht zu Laufzeit durch Bestimmung der Indizes und Prüfung auf Einhaltung der Indexgrenzen.
Bei Überschreitung der Indexgrenzen wird IndexOutOfBoundsException
ausgeworfen. Die untere Indexgrenze in jeder Dimension ist 0, die
obere Indexgrenze ist Indexlänge-1, die Indexlängen sind mit
'.length' abfragbar (6.3). Das englische Wort 'subsrcipts' für
eckige Klammern [] (brackets) verweist auf die "Tiefstellung" von
Indizes in der Schul-Mathematik.
Eine new-Reihung, synonym Reihungserzeugungsausdruck (ArrayCreationExpression), mit ggf. darin enthaltenem Aggregat, synonym Reihungsinitialisierer (ArrayInitializer), ist nach Syntaxdiagramm
040 von der Form
040: ArrayCreationExpression ReihungsErzeugungsAusdruck
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
H H
H n e w - R e i h u n g H
H A r r a y C r e a t i o n E x p r e s s i o n H
H Allocator --------------- H
H - new -- PrimitiveType -------- H
H --------------- H
H ---------------------- H
H - ClassOrInterfaceType - H
H ---------------------- H
H --------------------------------- H
H --------------------------- H
H H
H promotable H
H to int >=0 H
H ------------ ----------- H
H -- [ - Expression - ] --- [ - ] - H
H ------------ ---------------- H
H indexlength H
H -<--------- H
H - [ - ] - H
H ----------- H
H H
H A g g r e g a t H
H A r r a y I n i t i a l i z e r H
H ----------- , 
-------- - , - H
H ------------ H
H - { --- Expression -------------- } -- H
H ------------ 
H
H ------------------ H
H - ArrayInitializer - H
H ------------------ H
H ----------------------------- H
H H
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
z.B. {"LEX","MIHI","ARS"} // Aggregat (Otto Dix)
new int[LENG][] // new-Reihung
new char[]{'A','B','C'} // new-Reihung mit Aggregat
Mit Aggregaten (6.3) lassen sich nur Reihungen mit fest vorgegebenen Indexgrenzen bilden, mit new-Reihungen (6.4) auch Reihungen mit dynamisch einlesbaren Indexgrenzen, siehe oben LENG.
Eine Reihungsvereinbarung (ArrayDeclaration) ist nach Syntaxdiagramm 065 (für LocalVariableDeclaration, hier Erweiterung 065°
durch Einsetzung von VariableModifier Syntax.070 und VariableInitializer Syntax.063) von der Form
065°:ArrayDeclaration ReihungsVereinbarung
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
H H
H ----------------- - H
H ------------ H
H -- Annotation - H
H ------------ - ArrayModifier H
H - final -- H
H A r r a y D e c l arator L i s t H
H ----------- - ------------- , ------------- H
H H
H A r r a y D e c l a r a tor H
H H
H Aggregat H
H ------ ------ H
H Primi- Array- H
H -tive- ----------- -Initi-- H
H Type Array- alizer H
H ------ ------ ------ H
H ------ - [ - ] -Identi-- = ------ -- H
H Class- -fier Array- H
H Or- ------ Cre- H
H -Inter-- -ation-- H
H face- Expres H
H Type -sion H
H ------ ------ H
H new-Reihung H
H H
H ------------------- H
H H
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
An die lokale Variablen-Vereinbarung (Syntax.075) wird als Block
-Vereinbarung im Block (Syntax.068, 3.1) noch ein Semikolon angehängt.
z.B.
@OttoDix String[] motto={"LEX","MIHI","ARS"}; // Aggregat
int[][] pas =new int[LENG][]; // new-Reihung
final char[] ABC;
ABC =new char[] {'A','B','C'};
// Zuweisung einer new-Reihung mit Aggregat
Aggregate sind nur bei der Initialisierung von Reihungen zulässig, new-Reihungen (ggf. mit Aggregaten) als Ausdrücke z.B. auch
als rechte Seite von Zuweisungen, siehe new char[] {'A','B','C'};.
Die Zusammenfassung von mehreren aufeinanderfolgenden eckigen
Klammern mit Indizes, z.B. [2][3], zu einer Liste von Indizes in
eckigen Kammern, z.B. [2,3], ist in Java nicht zulässig.
6.2 Reihung als Referenztyp
Im vorigen Abschnitt benutzten wir die dem Leser aus der Schul
-Mathematik vertraute Darstellung von Vektor, Matrix, Quader usw.
In diesem Abschnitt erläutern wir die in Java verwendete Zeiger
-Technik für Reihungen.
Ein Zeiger-Zugriff (Referenz) wird realisiert durch eine Konstruktion aus zwei Speichern, wobei der erste die Adresse des
zweiten Speichers zum Inhalt hat,
z.B. char[] zeile= {'Z','e','i','l'};
--
W e r t e
-- Referenz Adr.------------ Inhalte
Adr.34:16------------16: Z e i l konsekutiv
--- ------------ gespeichert
z.B. char[][] seite= {{'S','e','i','t'},
-- {'m','i','t','3'},
{'Z','e','i','l'}};
--
Adr.12:99
--
Referenz
Adr.99:
--- W e r t e
Referenz Adr.------------ Inhalte
33------------33: S e i t konsekutiv
------------ gespeichert
---
Inhalte Referenz Adr.------------ Inhalte
konsekutiv 78------------78: m i t 3 konsekutiv
gespeichert ------------ gespeichert
---
Referenz Adr.------------ Inhalte
57------------57: Z e i l konsekutiv
------------ gespeichert
---
Analog zum Verzicht auf goto-Sprünge ('goto considered harmful',
5.4) verzichtet man in Java auf explizite Zeiger ('explicite reference considered harmful') und führt statt dessen implizit Zeiger ein, d.h. Referenz-Typen (ReferenceType, 2, Syntax.030), für
Reihung (6, Syntax.040/065) und
Klasse/Schnittstelle (9, Syntax.101).
String (2.6) ist z.B. keine Reihung, aber als Klasse auch ein
Referenz-Typ.
Die final Vereinbarung einer Referenztyp-Variablen wirkt nur auf
die erste Referenz, nicht auf weitere Referenzen und nicht auf referenzierte Werte,
z.B. final char[] KONST={'K','O','N','S','T'};
// KONST =new char[]{'K','U','N','S','T'}; inkorrekt
KONST[1]='U'; // korrekt
for(char each:KONST){out.print(each);} // KUNST
Aus einer Reihung können nicht nur einzelne Komponenten, sondern
auch Teil-Reihungen niedriger Dimension ausgewählt werden,
z.B.
String[][] ehre={{"Oh","haengt","ihn","auf"},
{"den","Kranz","von","Lorbeerblaettern"}};
for(String each:ehre[0]){out.print(each+" ");}//Oh haengt ihn auf
6.3 Aggregat zur Initialisierung
Aggregate, synonym Reihungsinitialisierer (ArrayInitializer,
siehe VariableInitializer Syntax.063, siehe 6.1), dienen zur Initialisierung von Reihungen, sind in Java keine Ausdrücke und dürfen daher nicht als rechte Seite in einer Zuweisung (5.1) explizit
vorkommen. Allerdings dürfen sie implizit in einer new-Reihung
(6.4) in der rechten Seite einer Zuweisung vorkommen,
z.B.
char[] reihung= {'A','g','g','r','e','g','a','t'};
// reihung= {'e','x','p','l','i','z','i','t'}; inkorrekt
reihung=new char[]{'i','m','p','l','i','z','i','t'}; // korrekt
Das nachfolgende Demonstrationsbeispiel ReverseFigure zeigt, wie
eine zweidimensionale Reihung fig vereinbart, per Aggregat ininialisert und dann einmal direkt und einmal gespiegelt in j-Richtung
ausgegeben wird.
Zur Ausgabe einer n-dimensionalen Reihung verwendet man n ineinander geschachtelte for-Schleifen, bei einer Matrix fig[][] wie
hier also eine äußere i-Schleife und eine innere j-Schleife. Nach
Durchlaufen der j-Schleife, d.h. nach Ausgabe einer Zeile, gibt
die i-Schleife einen Zeilenvorschub out.println().
Soll die Matrix direkt ausgegeben werden, d.h. jede Zeile (eachLine) und jedes Zeichen (eachChar) in ursprünglicher Reihenfolge,
so kann man zwei ineinander geschachtelte for-Schleifen mit ForEachControl (5.3.1) verwenden.
Die Spaltenlänge der Figur fig ist 5, d.h. Spaltenindex i=0..4,
und die Zeilenlänge ist 7, d.h. Zeilenindex j=0..6. Diese Längen
sind mit '.length' abfragbar,
z.B. fig.length // Länge 5 der Spalten von fig
fig[i].length // Länge 7 der Zeile i von fig
Würde man die Spalten- und Zeilenlänge der Figur im Programm
explizit angeben, dann müssten bei Änderung der Figur alle Län-
gen-Angaben im Programm geändert werden, was leicht zu Fehlern
führen kann.
//********************* ReverseFigure.java ***********************
// Umkehrung einer aus Zeichen gebildeten Figur. *
// Reihungs-Initialisierung durch Aggregat. *
//****************************************************************
// java.lang. Object
import static java.lang.System.out; // `System
class ReverseFigure
{public static void main(String[] args) // args ungenutzt
{char[][] fig={{'#','#','#','#','#','#','#'},
{'#','.','.','.','.','.','.'},
{'#','#','#','#','.','.','.'},
{'#','.','.','.','.','.','.'},
{'#','.','.','.','.','.','.'}}; // Aggregat
for(char[] eachLine:fig)
{for(char eachChar:eachLine) // Zeile obvers
{out.print(eachChar);}
out.println();
}
out.println();
for(int i=0;i<fig.length;i++)
{for(int j=fig[i].length-1;j>=0;j--) // Zeile revers j--
{out.print(fig[i][j]);}
out.println();
}
}
}
//****************************************************************
fig
--
Adr.-- Adr.
Output 2:14--14: W e r t e
------- --- --- Adr.---------------------
####### 97--97: # # # # # # #
#...... ---------------------
####... --- Adr.---------------------
#...... 33--33: # . . . . . .
#...... ---------------------
--- Adr.---------------------
####### 79--79: # # # # . . .
......# ---------------------
...#### --- Adr.---------------------
......# 56--56: # . . . . . .
......# ---------------------
--- Adr.---------------------
8---8: # . . . . . .
---------------------
---
6.4 Zuweisung von new-Reihungen
Eine new-Reihung, synonym Reihungserzeugungsausdruck (ArrayCreationExpression, Syntax.040, siehe 6.1), dient zur Initialisierung
oder Zuweisung von Reihungen, z.B. z=new String[2*args.length];.
//************************ MergeSort.java ************************
// Sortieren durch geordnetes Zusammenmischen geordneter Mengen. *
// Command: java MergeSort args[0] ... args[length-1] *
//****************************************************************
// java.lang. Object
import static java.lang.System.out; // `System
class MergeSort
{static String[] z; // ZwillingsArray
static void test(String s,int L,int R)
{int M=(L+R)/2; M=(L%2==M%2 ? M : M-1);
for(int i=L;i<=R;i+=2)
{if (i==L && s.equals("merged ")
|| i==M+2 && s.equals("merge! "))
{out.print(s);}
out.print ("z["+i+"]="+z[i]+" ");
}
out.println();
}
static int alt(int i)
{return (i%2==0 ? i+1 : i-1);
}
static void mergeSort(int L,int R) // L..R teilen in
{int M=(L+R)/2;M=(L%2==M%2?M:M-1); // L..M, M+2..R
test ("merge! ",L,R);
if (L <M) {mergeSort(alt(L ),alt(M));}
if (M+2<R) {mergeSort(alt(M+2),alt(R));}
int l=L,r=M+2,i=alt(L);
while (l<=M && r<=R) // mergesortierte
{if (z[l].compareTo(z[r])<0) // L..M, M+2..R
{z[i]=z[l];l+=2;} // mischen nach
else {z[i]=z[r];r+=2;}i+=2; // alt(L)..alt(R)
}
while (l<=M) {z[i]=z[l];l+=2; i+=2;} // Reste nach
while (r<=R) {z[i]=z[r];r+=2; i+=2;} // alt(L)..alt(R)
test ("merged ",alt(L),alt(R));
}
public static void main(String[] args) // args genutzt
{ z=new String[2*args.length];
for(int i=0;i<args.length;i++)
{ z[2*i]=z[2*i+1]=args[i];}
mergeSort (0,z.length-2);
for(int i=0;i<args.length;i++)
{out.print (z[2*i+1]+" ");}
}
}
//****************************************************************
Command MergeSort
---------------------------------- von Neumann (1950)
java MergeSort 4 1 5 3 2 Binärverfahren,
Zwillingsarray 4 4 1 1 5 5 3 3 2 2 Anzahl der Vergleiche
Index 0 1 2 3 4 5 6 7 8 9 von Ordnung n*log2(n)
Output (mit Test) ----- log2(n) ----
----------------------------------------- 4-
z[0]=4 z[2]=1 z[4]=5 merge! z[6]=3 z[8]=2 -14-
z[1]=4 z[3]=1 merge! z[5]=5 1-
z[0]=4 merge! z[2]=1 -145-
merged z[1]=1 z[3]=4 n 5------
merged z[0]=1 z[2]=4 z[4]=5 -12345
z[7]=3 merge! z[9]=2 3-
merged z[6]=2 z[8]=3 -23-------
merged z[1]=1 z[3]=2 z[5]=3 z[7]=4 z[9]=5 2-
1 2 3 4 5
Das obige Programm MergeSort sortiert die Reihung String[] args
beliebiger Länge args.length durch geordnetes Zusammenmischen geordneter Mengen. Der Array args wird doppelt (gerade, ungerade)
auf einen Zwillingsarray z eingelesen und dort alternierend rekursiv sortiert.
MergeSort (von Neumann 1950) ist wie die anderen bekannten Sortierverfahren BinBubbleSort (Shell 1950), QuickSort (Hoare 1961)
und HeapSort (Williams 1964) ein Binärverfahren von der Ordnung
n*log2(n): für binäre heiß-kalt Suche nach dem kleinsten von n
Elementen benötigt man etwa log2(n) Vergleiche. Vor Einführung der
Binärverfahren sortierte man mit Direktverfahren von der Ordnung
n*n: für direkte durchlaufende Suche nach dem kleinsten von n Elementen benötigt man etwa n Vergleiche. Für n=1000 Elemente ist
ein Binärverfahren (2 hoch 10 = 1024, d.h. log2(1000) ~= 10) bereits hundertmal so schnell wie ein Direktverfahren!
In der Klasse java.util.Arrays wird ein MergeSort
public static <T> void sort(T[] a, Comparator<? super T> c)
angeboten, der garantiert stabil ist, d.h. 'eqal elements will not
be reordered', und für den 'n*log(n) performance' garantiert wird
für alle (generischen) Typen T und alle zu sortierenden Reihungen
T[]. Wird der Comparator zur Vorgabe der Sortier-Ordnung aktuell
mit null angegeben, dann wird in natürlicher Ordnung sortiert,
z.B. import static java.util.Arrays.*;
class Sort
{public static void main(String[] args)
{sort(args,null);
for(String each:args) {System.out.print(each+" ");}
}
}
Command Output
------------------- ---------
java Sort 4 1 5 3 2 1 2 3 4 5
Im nachfolgenden Beispiel PascalTriangle wird gezeigt, wie man
mit new-Reihungen eine zweidimensionale Reihung pascal[][] mit dynamisch einlesbarer Länge LENG als Dreiecksmatrix konstruieren
kann. Mit Aggregaten (6.1, 6.3) liessen sich nur Dreiecksmatrizen
mit fest vorgegebener Länge konstruieren.
//********************* PascalTriangle.java **********************
// Pascalsches Dreieck der Binomialkoeffizienten "n ueber k". *
// Reihungs-Initialisierung durch Zuweisung von new-Reihungen. *
// Command: java PascalTriangle LENG<=20 *
//****************************************************************
// java.lang. Object
import static java.lang.System .out; // |`System
import static java.lang.Integer.parseInt; // `Integer
class PascalTriangle
{public static void main(String[] args) // args[0] genutzt
{int[][] pascal=new int[parseInt(args[0])][];
for(int n=0;n<pascal.length;n++) // n-te Zeile
{ pascal[n]=new int[n+1];
for(int insert=0;insert<pascal.length-1-n;insert++)
{out.printf("%3c",' '); // Einruecken nach rechts
}
for(int k=0;k<=n;k++) // k-te Zahl
{out.printf("%6d", pascal[n][k] = (k==0||k==n ? 1
: pascal[n-1][k-1]+pascal[n-1][k]));
} // Pascals Rekursionsformel
out.println();
} } }
//****************************************************************
pascal
-----
Adr.-- Adr.
Command 2:14--14:
--------------------- --- --- Adr.---
java PascalTriangle 5 97--97: 1
---
--- Adr.------
33--33: 1 1
------
Output --- Adr.---------
------------------------------ 79--79: 1 2 1
1 ---------
1 1 --- Adr.------------
1 2 1 56--56: 1 3 3 1
1 3 3 1 ------------
1 4 6 4 1 --- Adr.---------------
8---8: 1 4 6 4 1
---------------
--- W e r t e
Für die obige Dreiecksmatrix int[][] pascal wird zunächst
mit new int[parseInt(args[0])][] die Spaltenlänge vereinbart
--------------
LENG
und dann in einer for-Schleife
mit new int[n+1] die jeweilige Zeilenlänge n+1 vereinbart.
Anders als "normale" vereinbarte Reihungen (Reihungsvereinbarung, Syntax.065, 6.1) haben new-Reihungen (Reihungserzeugungsausdruck, Syntax.040, 6.1) keinen Bezeichner (identifier), sind also
anonym und nur in Initialisierungen oder Zuweisungen an "normale"
Reihungen verwendbar.
Sowohl new-Reihungen als auch "normale" Reihungen zeigen (referieren) auf Größen, die keine Bereichsgrößen und bis zum Ende des
Programmlaufs "unsterblich" sind, sofern sie nicht von der automatischen Speicherbereinigung (garbage colllection, 5.5.1) eliminiert werden, wenn festgestellt wird, dass kein Zeiger mehr auf
sie verweist.
zu Frage abdeckbare Antwort
-----------------------------------------------------------------
6.1 Sind bei zeilenweiser Ausgabe einer
Matrix a[x][y] mit Zeilenvorschub nach
jeder Zeile die Elemente der Matrix
den Indizes x,y zugeordet wie in einer
kartesischen Ebene ?
zeilenweise Ausgabe: kartesische Ebene:
y
nein, bei
--a[0][0]--a[0][1]-y (0,1) (1,1) zeilenweis. Ausgabe
zählt x nach unten,
a[1][0] a[1][1] --(0,0)-(1,0)-x y nach rechts
?
x
6.1 Sind Reihungs - Indizes stets vom nein,
Typ int ? IntegralNotLongType
oder
IntegralNotLong-
ClassType
promotable to int>=0
6.1 Dürfen Reihungs - Indizes negative
Werte annehmen? nein
6.2 Welche Typen sind stets implizit ArrayType
Zeiger-Typen (ReferenceType)? ClassOrInterfaceType
6.2/4 Sind Zeiger auf Zeiger konstruier- ja, z.B. pascal in
bar , d.h. Zeiger der Stufe 2 (und PascalTriangle
höher)?
6.3 Kann man den Werte-Tausch mit Hilfe nein, ein Aggregat
von Aggregaten wie folgt programmie- ist weder Variable
ren? noch Ausdruck,
daher nicht zuläs-
{x,y}={y,x}; sig im Assignment
6.3/4 Es sei vereinbart
int[] feld=new int[2],wald={0,1};
Was ist im folgenden korrekt?
feld [0]=wald[0]; alles
feld =wald;
out.print(wald[wald[1]]);
out.print(feld); keines