Für die folgenden Elemente des strukturierten Programmierens wird der Typ "Paar" eingeführt. Ein Paar besteht aus zwei Speicherzellen, die entweder eine Zahl oder einen Zeiger auf ein Paar enthalten.
Paar:
links : Zahl oder Paar
rechts: Zahl oder Paar
ende
Mit Paaren lassen sich leicht komplexere Strukturen erzeugen:
Paar( 1, 3 ) ergibt
( 1, 3 )
Paar( Paar( 1, 3 ), Paar( 2, 4 ) ) ergibt
(( 1, 3 ), (2, 4 ))
und Paar( 0, Paar( 2, 4 ) ) ergibt
( 0, (2, 4 ))
Noch deutlicher werden die Strukturen, indem man sie in der Kästchen-Zeiger-Notation darstellt:
Die letzte Struktur bildet eine dynamische lineare Anordnung im Speicher und wird als Paarliste bezeichnet.
Durch die Befehle getCAR() und getCDR() lassen sich jeweils die linken oder rechten Anteile eines Paares ausgeben:
Pair q = new Pair( 1, 3 );
System.out.println( q.getTextRepresentation() );
"(1;3)"
System.out.println( q.getCAR() );
"1"
Pair p = new Pair( 0, new Pair( 2, 4 ) );
System.out.println( p.getTextRepresentation() );
"(0; (2;4))"
Die Klasse "Pair" besitzt zusätzlich eine Funktion, ein spezielles Element der gesamten Struktur anzusprechen, wie folgender Quelltext verdeutlicht:
Pair p = new Pair( 0, new Pair( 2, 4 ) );
System.out.println( p.getTextRepresentation() );
"(0; (2; 4))"
System.out.println( p.getCAR() );
"0"
System.out.println( p.getCDR() );
"(2; 4)"
System.out.println( p.getElem( "RL" ) );
"2"
Die Funktion getElem nimmt als Parameter eine Zeichenkette an, die einen Pfad zum entsprechenden Element beschreibt.
Ein Bruch ist durch einen jeweils ganzzahligen Zähler und Nenner eindeutig definiert. Deshalb ist es leicht, die Paardefinition zur Darstellung von Brüchen zu verwenden. Was noch fehlt sind geeignete Unterprogramme, um mit diesem neuen Datentyp "arbeiten" zu können. Versuchen wir es zuerst mit der Multiplikation zweier Brüche. Es existieren bereits zwei Brüche a und b mit jeweiligen Zähler und Nenner, als Ergebnis des Unterprogramms entsteht ein neuer Bruch nach folgendem Algorithmus
Diese Vorgehensweise hat noch einen Schönheitsfehler. Multiplizieren wir 2/3 mit 6/8:
2/3 * 6/4 = 12 / 24
Das Ergebnis hat zwar den richtigen Wert, befindet sich aber nicht in der einfachsten Darstellung (1/2). Um diese zu erreichen, muss der Bruch noch gekürzt werden. Dazu wird der größte gemeinsame Teiler von Zähler und Nenner gesucht und anschließend werden Zähler und Nenner durch diese Zahl geteilt.
Der größte gemeinsame Teiler wird mithilfe des euklidischen Algorithmus gesucht.
Es folgen die entsprechenden Java-Quelltexte.
public static int ggT( int a, int b ){
if (b == 0) return a;
else return ggT( b, a % b );
}
public static void kuerzen( Pair p ){
int m = ggT( p.getLeft(), p.getRight() );
if (m > 1) { p.setLeft( p.getLeft()/m ); p.setRight( p.getRight()/m ); }
}
public static Pair multiplizieren( Pair a, Pair b){
int z, n;
z = a.getLeft()*b.getLeft();
n = a.getRight()*b.getRight();
Pair p = new Pair( z, n );
kuerzen( p );
return p;
}
public static void main(String args[]) {
Pair a = new Pair( 2, 3 );
Pair b = new Pair( 6, 8 );
System.out.println( multiplizieren(a,b).getTextRepresentation() );
}
Um die umfangreichen Daten einer Datenbank leicht referenzieren und sortieren zu können werden die Tabellen indiziert, bestimmte Felder erhalten einen Schlüssel. Diese enthalten eindeutige Zahlen, die auf das entsprechende Feld in der Datenbank verweisen.
Da jeder Eintrag (jede Zeile) in der Tabelle einen eigenen Schlüssel besitzt, benötigt die Indexstruktur ein Feld von ganzen Zahlen. Felder sind aber im allgemeinen dazu gedacht, Strukturen fester Größe im Speicher zu halten. Zur Verwaltung einer dynamischen Anzahl von ganzen Zahlen eignen sich sogenannte Listen.
Listen verwenden als Basis ein Element, das aus zwei Teilen besteht. Der eine speichert den Inhalt eines Elementes, der andere verweist auf das nächste Listenelement:
Das Element in Java-Notation:
class LinkedElem{
public int value;
public LinkedElem next;
}
Um Listen ansprechen zu können benötigt man nur einen Zeiger auf den Kopf. Alle weiteren Elemente lassen sich dann durch "entlangwandern" in der Liste erreichen. Beispiel: Darstellung der Liste als Zeichenkette:
public static String toString( LinkedElem head ){
String result = "(";
LinkedElem current = head;
while (current != null) {
result = result+" "+Integer.toString( current.value );
current = current.next;
}
result = result+ " )";
return result;
}
Die Struktur des Algorithmus ist einfach: zuerst wird eine Variable result für das Ergebnis initialisiert und eine Variable current für das aktuelle LinkedElem. current zeigt am Anfang auf head. Ist head nicht leer, dann wird mit current die gesamte Liste durchlaufen. Jedes Element wird in seiner Textdarstellung an die Zeichenkette angefügt und am Schluss wird die Zeichenkette mit einem ")"-Symbol abgeschlossen.
Zur Illustration lassen wir uns die folgende Liste in eine Zeichenkette umwandeln:
Nach der Initialisierung zeigt current wie head auf das erste Element, result besteht nur aus einer offenen Klammer:
Jetzt wird die while-Schleife erreicht. Solange current nicht leer ist, wird zum result die Repräsentation des aktuellen Elementes hinzugefügt und current auf das nächste Element gesetzt:
Im nächsten Schritt wird current leer, die Schleife wird beendet und die Klammer wird in der result geschlossen.
Wie wird eine verkettete Liste aufgebaut? Da immer der Zeiger des letzten Elementes auf Null zeigt, bietet es sich an, neue Elemente am Ende anzufügen. Beispiel: Anfügen der 7 als neues Element
Dazu muss erst einmal das letzte Element gefunden und dort ein zusätzliches LinkedElem erzeugt werden:
last = getLast( head );
last.next = new LinkedElem();
Anschließend wird die "7" in das neue entstandene Element eingetragen:
last.next.value = 7;
Zwei wesentliche Dinge wurden dabei noch nicht erwähnt:
- Wenn die Liste leer ist, dann muss überhaupt ein erstes Element erzeugt werden.
- Es wird eine Routine getLast benötigt, die das letzte Element findet.
Hier die entsprechenden Quelltexte:
public static LinkedElem getLast( LinkedElem head ){
if (head == null) return null;
LinkedElem current = head;
while (current.next != null) current = current.next;
return current;
}
public static LinkedElem append( LinkedElem head, int value ){
if (head == null) {
head = new LinkedElem();
head.value = value;
}
else {
LinkedElem last = getLast( head );
last.next = new LinkedElem();
last.next.value = value;
}
return head;
}
Zum Schluss noch ein Unterprogramm zum Sortieren einer Liste:
Dies ist wieder der Quicksort: die Liste wird anhand des ersten Elementes in zwei Listen zerlegt ( eine enthält nur die größeren, die andere nur die kleineren Elemente), diese werden (rekursiv) wiederum sortiert und das Ergebnis wird aus der sortierten kleineren Liste, dem Vergleichselement und der sortierten größeren Liste zusammengesetzt.
Hier noch der Quelltext dazu:
public static LinkedElem higher_part( LinkedElem head, int value ){
LinkedElem result = null;
LinkedElem current = head;
while (current != null){
if (current.value > value) result = append( result, current.value );
current = current.next;
}
return result;
}
public static LinkedElem lower_part( LinkedElem head, int value ){
LinkedElem result = null;
LinkedElem current = head;
while (current != null){
if (current.value < value) result = append( result, current.value );
current = current.next;
}
return result;
}
public static LinkedElem sort( LinkedElem head ){
if (head == null) return head;
int v = head.value;
LinkedElem hp = higher_part( head, v );
LinkedElem lp = lower_part( head, v );
head = sort(lp);
head = append( head, v );
head = appendList( head, sort( hp ) );
return head;
}
- Erzeugen Sie folgende Speicherstruktur durch geeignete new Pair Befehlskombinationen und zeichnen Sie die zugehörigen Kasten-Zeigerdiagramme.
- ( 0; ( 1; ( 2; ( 3; 4 ) ) ) )
- ( ( ( ( 0; 1 ); 2 ); 3 ); 4 )
- ( 0; ( ( 1; 2 ); (3; 4 ) ) )
- Schreiben Sie den Quelltext, der das folgende Kasten-Zeiger-Diagramme erzeugt und ausgibt:
Geben Sie diese Struktur außerdem in Klammerschreibweise an.
- Geben Sie für Aufgabe 1 an, wie jeweils durch "L" und "R"-Kombinationen die Zahl 3 erreicht wird.
- Erzeugen Sie mittels der "new Pair"-Befehle eine Paarliste, die die ersten fünf Prinzahlen enthält.
- Versuchen Sie, eine geschlossene Paarkette zu erzeugen. Was passiert beim Aufruf von "getTextRepresentation"?
- Schreiben Sie weitere Unterprogramme für Brüche: "dividieren", "addieren" und "subtrahieren"
- Implementieren Sie mit der Klasse "Pair" ganzzahlige Koordinaten und schreiben sie die Unterprogramme "Skalarprodukt" und "Betrag"
- Schreiben Sie ein Unterprogramm, welches ein Paar als Bruch ausgibt und dabei auch negative Zähler und Nenner berücksichtigt.
- Schreiben Sie ein Unterprogramm, das
- Die Elemente einer verketteten Liste addiert.
- Die Quadratzahlen der Elemente einer verketteten Liste in eine Zeichenkette schreibt.
- Die Elemente einer verketteten Liste in umgekehrter Reihenfolge in eine Zeichenkette schreibt.
- Schreiben Sie ein Unterprogramm insert, das eine Zahl an der richtigen Position in einer Liste einfügt.
- Schreiben Sie ein Unterprogramm delete, das die Zahl an der Position i in der Liste löscht.
- Schreiben Sie ein Unterprogramm reverse, welches eine neue Liste erzeugt, in der die Zahlen umgekehrt stehen.
- Wie ermittelt man den Vorgänger eines Elementes in der Liste?
- Schreiben Sie ein Unterprogramm merge, welches zwei sortierte Listen in eine neue Liste sortiert.
- Entwerfen Sie einen Algorithmus zum Sortieren einer Liste in absteigender Größe. (Sie können dazu die Unterprogramm lower_part und higher_part verwenden)
class Pair{
private int left;
private int right;
private Pair pl;
private Pair pr;
public Pair( int v1, int v2 ){
left = v1; right = v2;
}
public Pair( int v1, Pair v2 ){
left = v1; pr = v2;
}
public Pair( Pair v1, int v2 ){
pl = v1; right = v2;
}
public Pair( Pair v1, Pair v2 ){
pl = v1; pr = v2;
}
public String getCAR(){
if (pl != null) return pl.getTextRepresentation(); else return Integer.toString( left );
}
public int getLeft(){
return left;
}
public void setLeft( int v ){
left = v;
}
public int getRight(){
return right;
}
public void setRight( int v ){
right = v;
}
public String getCDR(){
if (pr != null) return pr.getTextRepresentation(); else return Integer.toString( right );
}
public String getTextRepresentation(){
return '('+getCAR()+';'+getCDR()+')';
}
public String getElem( String path ){
if (path.length() == 0) return "Fehler";
if (path.length() == 1){
if (path.charAt( 0 ) == 'L') return getCAR(); else return getCDR();
} else {
if (path.charAt( 0 ) == 'L'){
if (pl != null){
return pl.getElem( path.substring( 1 ) );
} else {
return "Fehler: Pfad zu lang!";
}
} else {
if (pr != null){
return pr.getElem( path.substring( 1 ) );
} else {
return "Fehler: Pfad zu lang!";
}
}
}
}
}