Skip to content

Latest commit

 

History

History
71 lines (50 loc) · 2.46 KB

141207-V.md

File metadata and controls

71 lines (50 loc) · 2.46 KB

Listen (Vgl. GdI)

Motivation: Arrays sind niht dynamisch erweiterbar - d.h. es können später keine Elemente engefügt werden. Listen sind dynamische Datenstrukturen, sie können zur Laufzeit erweiter werden.

Einfach verkettete Listen (s.a. 18.c)

Jedes Element enthält einen Verweis auf das nächste, sofern vorhanden.

Operationen: - auf erstes Element zurgreifen (am Kopf der Liste) - neues Element am Anfang hinzufügen 1. Neues Elm erzeugen 2. Elm. forn anhängen (Zeiger auf Liste als Nachfolger des Elm) 3. Zeiger auf Liste auf Elm setzen - erstes Elm entfernen 1. Elm Aushängen: Zeiger auf 2. Elm setzen 2. erstes Elm löschen bzw. Speicher freigeben

Listenelement Implementierung in C: Listenelemente werden durch eine struct darestellt, die als Variable enthält: * inhalt * *nachfolger (Nullpointer, wenn Ende)

struct mylist {
	int item;
	struct mylist *naechste;
};

Doppelt verkettete Listen

Listenelement: * *vorgänger (Nullpointer, wenn Anfang) * inhalt * *nachfolger (Nullpointer, wenn Ende)

Dynamische Speicherallokation

Dynamisch Speicher adresseieren: malloc

Syntax: (Typ*) malloc(sizeof(Typ))

sizeof(Typ) berechnet, wieviel Speicher für eine Variable des Typs Typ benötig wird. Das Ergebnis vonmalloc ist ein ungetypter Zeiger auf den Speicherbereich. Durch den expliziten Typecast-Operator (Typ*) zu einem Zeiger auf Typ konvertiert. Das Egebnis ist NULL, wenn kein Speicher mehr verfügbar ist.

Speicher freigeben mit free

Syntax: free(ZeigerAufSpeicherbereich)

Dabei wird der Speicherplatz selbst nicht verändert, aber als nicht mehr benötigt markiert. Ein Fehler ist: Auf einen Speicherplatz zuzugreifen, nach dem dieser freigegeben wurde. Dieser Fehler ist durch Tests nicht auffindbar.

Stack / Kellerspeicher (lifo - last in first out)

Ein Stack, Batch/Stapel, oder auch Kellerspeicher funktioniert wie ein Bücherstapel. Es handelt sich um eine LIFO Datenstruktur. D.h. die Elemente können nur oben abgelegt oder entnommen werden.

Operationen: - push(x), x wird auf den Stack abgelegt - x=pop(), x wird vom Stack genommen - nur zulässig, wenn der Stack nicht leer ist - is_empty, wahr wenn der Stack leer ist.

Ein Stack lässt sich durch eine einfach verkettete Liste implementieren. - push(x) -> x als erstes Elm anhängen - x=pop() -> erstes Elm entfernen und zurückliefern - is_empty -> Prüfung, ob die Liste leer ist

Lässt sich als Klasse betrachten: - Datenstruktur - Operationen als Methoden