Kurs:Algorithmen und Datenstrukturen/Vorlesung/Listen

Startseite

Vorlesung

1.Einleitung

2. Theoretische Grundlagen

2.1 Programmierparadigmen

2.2. Laufzeitanalysen

2.3. Entwurfsmuster

3. Suchen

3.1 Suchen in sortierten Folgen

3.2 Suchen in Texten

4. Sortieren

4.1 Algorithmen für vergleichsbasiertes Sortieren

4.2 Weitere Sortierprobleme

5. Dynamische Datenstrukturen

5.1 Binäre Suchbäume

5.2 AVL Bäume

5.3 2-3-4-Bäume und Rot-Schwarz Bäume

5.4 Heaps

5.5 Hashtabellen

6. Graphen

6.1 Einführung

6.2 Breitensuche

6.3 Tiefensuche

6.4 Topologisches Sortieren

6.5 Berechnung kürzester Wege

6.6 Berechnung maximaler Flüsse

6.7 Spannbäume

7. Optimierung

7.1 Grundlagen

7.2 Kombinatorische Optimierung

7.4 Lineare Optimierung

7.5 Simplex Verfahren

Liste

Eine Liste ist entweder die leere Liste oder ein Term gefolgt von einer Liste.

Definition in Prolog

list([]).
list([X|Y]) :- list(Y). 

Der |-Operator trennt den Kopf (Head=erstes Element)einer Liste vom Rumpf (Tail=Restliste) ab

Beispiele

• Liste von Zahlen:

[1|[2|[3]]] = [1,2,3]

• Liste von beliebigen Termen:

[male(bob), female(anna),male(carl)]

Listenmanipulation

• Aneinanderreihung:

append(X,Y,Z): X ist die Liste, die entsteht, wenn Z an Y angehängt wird

append(X,X,[]).
append([Y|X], [Y|Z],L) :- append(X,Z,L). 

• Invertierung:

invert(X,Y): X ist die Invertierung von Y

invert([],[]).
invert([X|Y],L) :- invert(Y,Z), append(L,Z,[X]).

Literatur

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 3.4.1 zu finden.