[SOLVED] CS Java ER Programmierung

Programmierung
Listen
Michael Goedicke (Basis Volker Gruhn und Mathias Book)

Die verkettete Liste: Motivation
Beispiel: Ein Ordner besteht aus mehreren Dokumenten.
Da ein Dokument nicht in verschiedenen Ordnern enthalten sein kann
und die Entsorgung eines Ordners die Entsorgung der in ihm enthaltenen Dokumente zur Folge hat, wird dieses Szenario wie folgt modelliert:
Ordner
-beschriftung
+einordnen(dokument)
Dokument
-inhalt
:Ordner
:Dokument
:Dokument
Programmierung VE06
2
:Dokument

Die verkettete Liste: Motivation
In Java kann die Situation mit Hilfe eines Arrays umgesetzt werden: public class Ordner {
private String beschriftung; private Dokument[] dokumente;
public Ordner(String beschriftung) { this.beschriftung = beschriftung; dokumente = new Dokument[5];
}
public void einordnen(Dokument dokument) { }
}
Frage: Wie kann die Methode einordnen() implementiert werden? Programmierung VE06
3

Die verkettete Liste: Motivation
Idee: Man kann sich die erste freie Stelle des Arrays merken. public class Ordner {
private String beschriftung; private Dokument[] dokumente;
public Ordner(String beschriftung) { this.beschriftung = beschriftung; dokumente = new Dokument[5];
}
public void einordnen(Dokument dokument) { }
}
private int ersteFreieStelle; erste freie Stelle des Arrays
ersteFreieStelle = 0;
das Array ist noch leer
Programmierung VE06
4

Die verkettete Liste: Motivation
Der erste Entwurf der Methode einordnen() konnte dann folgendermaen aussehen:
public void einordnen(Dokument dokument) { dokumente[ersteFreieStelle] = dokument; ersteFreieStelle = ersteFreieStelle + 1;
}
Problem: Das Array hat die Lange 5. Daher kann das sechste Dokument nicht ohne weitere Vorkehrungen eingeordnet werden.
public void einordnen(Dokument dokument) {
if (ersteFreieStelle < dokumente.length) { dokumente[ersteFreieStelle] = dokument;ersteFreieStelle = ersteFreieStelle + 1; } else {} }// Umgang mit der Situation Array vollProgrammierung VE065 Die verkettete Liste: Motivation Wenn mehr als 5 Dokumente eingeordnet werden sollen, dann muss ein neues Array mit der Lange beispielsweise 10 erzeugt werden. Der Inhalt des alten Arrays muss in das neue Array kopiert werden. einordnen(e) a b c da b c d e a b c d e a b c d ea b c d e feinordnen(f)Programmierung VE066 Die verkettete Liste: KonzeptErgebnis: Da sich der Inhalt eines Ordners dynamisch andert, kann das Szenario mit Arrays nicht gut abgebildet werden. Dagegen konnen Listenstrukturen, die sich dynamisch andern, mit verketteten Listen sehr gut abgebildet werden. Eine verkettete Liste (engl. List) besteht aus Knoten, wobei vom Listenkopf (engl. head) nur der erste Knoten der Liste referenziert wird. Jeder Knoten (engl. Node) kann einen Wert speichern und referenziert (d.h. merkt sich) seinen Nachfolger. Node -value: Document List0..1head 0..10..1 next :List0..1:Node:Node:Node:Node:Node Programmierung VE067 Die verkettete Liste: Warteschlange als Beispiel Ein weiteres Beispiel fur eine verkette Liste ist eine Warteschlange an Leuten, die in alphabetischer Reihenfolge der Namen geordnet ist. Fall 1: Keiner ist in der Warteschlange Der Head in List referenziert die leere Liste, d.h. er ist null Fall 2: Kunden mit den Namen a, b, c, d sind in der Warteschlange Die Liste wird dann haufig durch folgende Notation dargestellt: (Sie endet mit einer Referenz auf null)Person Person a bPerson cReferenz auf Nachfolgergespeicherter Wert:List abcd Position01 2 3Programmierung VE068 Die verkettete Liste: Warteliste als Beispiel Fall 3: Der Kunde a verlasst die Warteschlange gespeicherter Wert Referenz auf Nachfolger:ListPosition 0 1 2 Fall 4: Der Kunde bb kommt hinzu:ListPosition 0 1 2 3Fazit: Die Positionen sind veranderlich Liste endet mit der Referenz auf nullbcd bbbcd Programmierung VE069 Die verkettete Liste: Konzept Listenkopf, head, referenziert immer nur den ersten Knoten Ein Knoten kann nicht gleichzeitig der Nachfolger eines anderenKnoten und der erste Knoten einer Liste sein.:List :List :Node:Node:Node:Node:NodeProgrammierung VE0610 Die verkettete Liste: Konzept Ein Knoten wird in Java durch folgende Klasse implementiert:public class Node { private Document value;private Node next;public Node(Document value) { this.value = value;0..1 next Node -value: Document }public Document getValue() { . . . }public void setValue(Document value) { . . . } public Node getNext() { . . . }public void setNext(Node next) { . . . }}0..1Programmierung VE0611 Die verkettete Liste: Konzept Wenn eine Liste auf der Konsole ausgegeben werden soll, dann sollte man die toString()-Methode uberschreiben:public class Node { …public String toString() { return “[” + value + “]->;
} }
class Document { String text;
0..1 next
Node
-value:Document
+toString():String
Document (String v)
{ text = v;}
public String toString() {return text;}
}
0..1
main()-Methode
String value = Was wird passieren?; System.out.println(
new Node(new Document(value)));
Programmierung VE06
12
Konsole
[Was wird passieren?]->

Die verkettete Liste: Basisoperationen
Eine verkettete Liste besitzt in der Regel folgende Basisoperationen:
Anhangen eines Elements an das
Ende der Liste
Einfugen eines Elements an einer
bestimmten Position
Loschen aller Elemente aus der Liste
Zugriff auf ein Element uber dessen
Position
Bestimmung der Position eines Elements
Bestimmen, ob die Liste leer ist
Loschen eines Elements aus der
Liste
Berechnung der Lange der Liste
List
+add(value:Object):void +add(index:int, value:Object):void +clear():void +get(index:int):Object +indexOf(value:Object):int +isEmpty():boolean +remove(index:int):void +size():int
Programmierung VE06
13

Die verkettete Liste: Basisoperationen
Eine verkettete Liste ist genau dann leer, wenn sie kein erstes Element besitzt.
a
b
c
Liste ist nicht leer: :List Liste ist leer: :List
Damit erhalten wir:
public void clear() { head = null;
}
public boolean isEmpty() { return head == null;
}
Nicht mehr verlinkte Elemente werden automatisch vom Garbage Collector zerstort
a
b
c
Programmierung VE06
14

Die verkettete Liste: Basisoperationen
Die Lange der Liste berechnet man mit Hilfe einer Schleife:
public int size() { int size = 0;
Node node = head; while (node != null) {
node = node.getNext();
size = size + 1;
}
return size; }
Die Liste wird dabei mit node = node.getNext() durchlaufen.
node
node
a
b
a
b
node
a
b
Programmierung VE06
15

Die verkettete Liste: Basisoperationen
Die Liste muss ebenfalls durchlaufen werden, um auf einen Knoten an einer bestimmten Position zuzugreifen:
private Node getNodeAt(int index) { if (index < 0) {return null; }int currPos = 0;Node node = head;while (currPos < index && node != null) { node = node.getNext(); currPos = currPos + 1; }return node; } Der Index des ersten Elements ist 0 und der Index des letztenElements ist size() 1. Wenn der ubergebene Index ungultig ist, dann gibt die Methode nullzuruck.Programmierung VE0616 Die verkettete Liste: Basisoperationen Mit Hilfe der gerade gezeigten privaten Methode kann man in der offentlichen get-Methode auf ein bestimmtes Element zugreifen:public Document get(int index) { Node node = getNodeAt(index); if (node == null) {return null; }return node.getValue(); }Programmierung VE0617 Die verkettete Liste: Basisoperationen Wenn ein Element an der i-ten Stelle in die Liste eingefugt werden soll, dann geht man folgendermaen vor: Ist i = 0, dann muss der head-Zeiger der Liste umgehangt werden. Ist i > 0, dann muss der next-Zeiger des (i-1)-ten Knotens umgehangt
werden.
i > 0:
a
i = 0: :List
b
a
b
c
Programmierung VE06
18

Die verkettete Liste: Basisoperationen
public void add(int index, Document value) { Node node = new Node(value);
if (index == 0) {
node.setNext(head);
head = node;
} else if (index > 0) {
} }
Node prev = getNodeAt(index 1); if (prev != null) {
node.setNext(prev.getNext());
prev.setNext(node); }
Wenn ein Element an das Ende der Liste angehangt wird, dann wird es an der Position size() eingefugt (Lange entspricht Index des letzen Listenelements):
public void add(Document value) { add(size(), value);
}
Programmierung VE06
19

Die verkettete Liste: Basisoperationen
Das Anhangen eines Elements an das Ende der Liste kann man
beschleunigen, indem man die Liste um eine Referenz auf den letzten
Knoten erweitert, sodass kein kompletter Durchlauf erforderlich ist:
0..1
List
0..1
tail
private Node head; private Node tail;
public void add(Document value) { Node node = new Node(value); if (isEmpty()) {
head = node;
tail = head; } else {
Allerdings mussten dann die anderen Methoden entsprechend angepasst werden. Im Folgenden verzichten wir daher auf die Referenz auf den letzten Knoten.
tail.setNext(node);
tail = node;
0..1
head 0..1
}
}
Programmierung VE06
20
Node

Die verkettete Liste: Basisoperationen
Wenn die Position eines Elements bestimmt werden soll, dann brauchen wir zunachst eine Moglichkeit, um die Elemente der Liste mit dem vorgegebenen Element zu vergleichen.
Dazu realisieren wir die private Klassenmethode isEqual, der zwei zu vergleichende Objekte ubergeben werden konnen:
private static boolean isEqual(Document first, Document second) {
if (first == null) { return second == null;
}
return first.equals(second); }
Programmierung VE06
21

Die verkettete Liste: Basisoperationen
Mit Hilfe der gerade entwickelten Klassenmethode kann sodann die Position eines Elements bestimmt werden:
public int indexOf(Document value) { int index = 0;
Node node = head; while (node != null
&& !isEqual(node.getValue(), value)) { index = index + 1;
node = node.getNext();
}
return node == null ? -1 : index; }
Die Methode gibt -1 zuruck, wenn die Liste das ubergebene Element nicht enthalt.
Wenn die Liste das ubergebene Element enthalt, dann gibt die Methode diejenige Position zuruck, an der das Element zum ersten Mal auftritt.
Programmierung VE06
22

Die verkettete Liste: Basisoperationen
Wenn das Element an der i-ten Stelle aus der Liste geloscht werden soll, dann geht man folgendermaen vor:
Ist i = 0, dann muss der head-Zeiger der Liste auf den Nachfolger des ersten Knotens umgehangt werden.
Ist i > 0, dann muss der next-Zeiger des (i-1)-ten Knotens auf den Nachfolger des i-ten Knotens umgehangt werden.
Man muss sowohl auf den i-ten Knoten als auch auf den (i-1)-ten Knoten zugreifen.
i = 0: :List
i > 0:
a
b
a
b
c
Programmierung VE06
23

Die verkettete Liste: Basisoperationen
public void remove(int index) { if (index == 0) {
head = head == null ? null : head.getNext(); } else if (index > 0) {
} }
Node node = getNodeAt(index); if (node != null) {
Node prev = getNodeAt(index 1);
prev.setNext(node.getNext()); }
Zugriff auf den i-ten und den (i-1)-ten Knoten
Wenn getNodeAt(index) != null und index > 0 gilt, dann gilt auch getNodeAt(index 1) != null.
Da der Knoten an der Stelle index nach einem Aufruf der Methode nicht mehr referenziert wird, wird er vom Garbage Collector aus dem Speicher geloscht.
Programmierung VE06
24

Die verkettete Liste: Basisoperationen
Da die Methode getNodeAt() zweimal aufgerufen wird, wird die Liste zweimal durchlaufen. Das ist aber unnotig:
public void remove(int index) { if (index == 0) {
head = head == null ? null : head.getNext(); } else if (index > 0) {
} }
int currPos = 0;
Node prev = null;
Node node = head;
while (currPos < index && node != null) {currPos = currPos + 1;prev = node;node = node.getNext();}if (node != null) {prev.setNext(node.getNext()); }Programmierung VE0625 Die verkettete Liste: Basisoperationen Den Zugriff auf den i-ten und den (i-1)-ten Knoten kann man vereinfachen, indem die Knoten um einen Zeiger auf ihre Vorganger erweitert werden. Node -value:Document +toString():String :List0..1 0..1 prev next0..1 0..1 a b c Das Loschen eines Knotens orientiert sich dann an folgendem Schema:a b c Programmierung VE0626 Die verkettete Liste: Basisoperationen Wenn die Liste auf der Konsole ausgegeben werden soll, dann muss die toString()-Methode uberschrieben werden:public String toString() { Node node = head; String temp = ; while (node != null) {temp = temp + node;node = node.getNext(); }return temp; } main()-Methode List liste = new List(); liste.add(new Document(b)); liste.add(0, new Document(a)); System.out.println(liste); liste.remove(1); System.out.println(liste); Konsole [a]->[b]->
[a]->
Programmierung VE06
27

Die verkettete Liste: Beispiel
Nun konnen wir das Ordner-Modell mit Hilfe einer verketten Liste implementieren:
Ordner
-beschriftung
+einordnen(dokument)
Dokument
-inhalt
public class Ordner {
private String beschriftung;
private List dokumente;
public class Document { private String value; . . .
} }
Programmierung VE06
28

Die verkettete Liste: Beispiel
Der Konstruktor der Ordner-Klasse und die einordnen()-Methode haben dann folgende Form:
public Ordner(String beschriftung) { this.beschriftung = beschriftung; dokumente = new List();
}
public void einordnen(Document dokument) { dokumente.add(dokument);
}
Ordner
+einordnen(dokument):void
Document
-titel -inhalt
Programmierung VE06
29