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() könnte dann folgendermaßen aussehen:
public void einordnen(Dokument dokument) { dokumente[ersteFreieStelle] = dokument; ersteFreieStelle = ersteFreieStelle + 1;
}
▪ Problem: Das Array hat die Länge 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 voll“ Programmierung – VE06 5 Die verkettete Liste: Motivation ▪ Wenn mehr als 5 Dokumente eingeordnet werden sollen, dann muss ein neues Array mit der Länge beispielsweise 10 erzeugt werden. ▪ Der Inhalt des alten Arrays muss in das neue Array kopiert werden. einordnen(e) a b c d a b c d e a b c d e a b c d e a b c d e f einordnen(f) Programmierung – VE06 6 Die verkettete Liste: Konzept Ergebnis: Da sich der Inhalt eines Ordners dynamisch ändert, kann das Szenario mit Arrays nicht gut abgebildet werden. ▪ Dagegen können Listenstrukturen, die sich dynamisch ändern, 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 List 0..1 head 0..1 0..1 next :List 0..1 :Node :Node :Node :Node :Node Programmierung – VE06 7 Die verkettete Liste: Warteschlange als Beispiel ▪ Ein weiteres Beispiel für 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 häufig durch folgende Notation dargestellt: (Sie endet mit einer Referenz auf null) Person Person „a“ „b“ Person „c“ Referenz auf Nachfolger gespeicherter Wert :List a b c d Position 0 1 2 3 Programmierung – VE06 8 Die verkettete Liste: Warteliste als Beispiel ▪ Fall 3: Der Kunde „a“ verlässt die Warteschlange gespeicherter Wert Referenz auf Nachfolger :List Position 0 1 2 ▪ Fall 4: Der Kunde „bb“ kommt hinzu :List Position 0 1 2 3 Fazit: • Die Positionen sind veränderlich • Liste endet mit der Referenz auf null b c d b bb c d Programmierung – VE06 9 Die verkettete Liste: Konzept ▪ Listenkopf, „head“, referenziert immer nur den ersten Knoten ▪ Ein Knoten kann nicht gleichzeitig der Nachfolger eines anderen Knoten und der erste Knoten einer Liste sein. :List :List :Node :Node :Node :Node :Node Programmierung – VE06 10 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..1 Programmierung – VE06 11 Die verkettete Liste: Konzept ▪ Wenn eine Liste auf der Konsole ausgegeben werden soll, dann sollte man die toString()-Methode überschreiben: 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:
▪ Anhängen eines Elements an das
Ende der Liste
▪ Einfügen eines Elements an einer
bestimmten Position
▪ Löschen aller Elemente aus der Liste
▪ Zugriff auf ein Element über dessen
Position
▪ Bestimmung der Position eines Elements
▪ Bestimmen, ob die Liste leer ist
▪ Löschen eines Elements aus der
Liste
▪ Berechnung der Länge 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 zerstört
a
b
c
Programmierung – VE06
14

Die verkettete Liste: Basisoperationen
▪ Die Länge 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 letzten Elements ist size() – 1. ▪ Wenn der übergebene Index ungültig ist, dann gibt die Methode null zurück. Programmierung – VE06 16 Die verkettete Liste: Basisoperationen ▪ Mit Hilfe der gerade gezeigten privaten Methode kann man in der öffentlichen 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 – VE06 17 Die verkettete Liste: Basisoperationen ▪ Wenn ein Element an der i-ten Stelle in die Liste eingefügt werden soll, dann geht man folgendermaßen vor: • Ist i = 0, dann muss der head-Zeiger der Liste umgehängt werden. • Ist i > 0, dann muss der next-Zeiger des (i-1)-ten Knotens umgehängt
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 angehängt wird, dann wird es an der Position size() eingefügt (Länge entspricht Index des letzen Listenelements):
public void add(Document value) { add(size(), value);
}
Programmierung – VE06
19

Die verkettete Liste: Basisoperationen
▪ Das Anhängen 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 müssten 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 zunächst eine Möglichkeit, um die Elemente der Liste mit dem vorgegebenen Element zu vergleichen.
▪ Dazu realisieren wir die private Klassenmethode isEqual, der zwei zu vergleichende Objekte übergeben werden können:
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 zurück, wenn die Liste das übergebene Element nicht enthält.
▪ Wenn die Liste das übergebene Element enthält, dann gibt die Methode diejenige Position zurück, 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 gelöscht werden soll, dann geht man folgendermaßen vor:
• Ist i = 0, dann muss der head-Zeiger der Liste auf den Nachfolger des ersten Knotens umgehängt werden.
• Ist i > 0, dann muss der next-Zeiger des (i-1)-ten Knotens auf den Nachfolger des i-ten Knotens umgehängt 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 gelöscht.
Programmierung – VE06
24

Die verkettete Liste: Basisoperationen
▪ Da die Methode getNodeAt() zweimal aufgerufen wird, wird die Liste zweimal durchlaufen. Das ist aber unnötig:
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 – VE06 25 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 Vorgänger erweitert werden. Node -value:Document +toString():String :List 0..1 0..1 prev next 0..1 0..1 a b c ▪ Das Löschen eines Knotens orientiert sich dann an folgendem Schema: a b c Programmierung – VE06 26 Die verkettete Liste: Basisoperationen ▪ Wenn die Liste auf der Konsole ausgegeben werden soll, dann muss die toString()-Methode überschrieben 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 können 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