actionbrowser.com
Suche Um ein Element in der Liste zu suchen, hangelt man sich von einem Listenelement zum nächsten, entweder bis man die gesuchte Element gefunden hat, oder bis man NULL erreicht: node search_for(node list, int data) { while (list! = NULL) { if (list->data == data) return list; list = list->next;} return NULL;} Wenn man erst mal den node pointer hat, kann man z. B. C++ listen erstellen. rechts davon einfügen oder löschen. Zusammenfassung Eine einfach verkettete Liste speichert pro Element einen Zeiger auf das nächste Element und die Nutzdaten. Das Durchlaufen von Rechts nach Links, das Einfügen und das Entfernen des Elements rechts des aktuellen Elements sind einfach und erfordern nur das umsetzen von zwei Zeigern. Gegenüber doppelt verketteten Listen brauchen sie also weniger Verwaltungsaufwand, bei etwas geringerer Flexibilität. Weiteres Lesematerial doppelt verkettete Listen Heaps und Heapsort Überlegte Verwendung von Datentypen und Datenstrukturen Bücher "Algorithmen in C" von Robert Sedgewik ist allgemeinverständlich und praktisch.
Wird ein neues Datenelement benötigt, wird es erzeugt und in die Liste eingefügt. Benötigen Sie ein Element nicht mehr, wird es gelöscht. Wie viele Elemente in der Liste sind, ist nur durch den verfügbaren Speicher beschränkt. Der Zugriff auf die Elemente an einer bestimmten Positionsnummer ist allerdings aufwändiger als in einem Array. Daten und Zeiger Die Basis einer verketteten Liste ist eine Struktur, die einerseits die eigentlichen Daten und andererseits einen Zeiger enthält, um auf das nächste Element der Liste zu verweisen. Array Listen und Generische Listen. struct TListenKnoten int data; TListenKnoten *next;}; next Etwas verblüffend ist die Verwendung des Typs TListenKnoten innerhalb der Deklaration des Typs TListenKnoten. Dem Compiler muss an dieser Stelle das genaue Aussehen des Typs TListenKnoten noch nicht bekannt sein, da hier lediglich ein Zeiger darauf definiert wird. Ein Zeiger ist aber immer gleich groß, ganz gleich, auf was er zeigt. Für den flüchtigen Beobachter ist es vielleicht irritierend, dass in der Struktur ein Zeiger ist, der scheinbar auf sich selbst zeigt.
Einfach verkettete Listen oder linked lists sind eine fundamentale Datenstruktur, die ich hier anhand von Code-Beispielen und Grafiken erklären will. Einfach verkettete Listen zeichnen sich dadurch aus, dass man besonders einfach Elemente einfügen kann, wodurch sie sich besonders gut für Insertion Sort eignen. Eine Verallgemeinerung stellen die doppelt verketteten Listen da. Vektoren und Listen. Knoten Eine einfach verkettete Liste besteht aus Knoten, Englisch nodes, die einen Zeiger auf das nächste Element und auf Daten. struct list_node { int data; struct list_node *next;}; Um nicht jedes mal das struct mitschleppen zu müssen, kann man eine Abkürzung definieren: typedef struct list_node* node; Eine leere Liste besteht aus einem Kopf (Head) und nichts sonst: Eine leere Liste Wenn man mehrere Elemente einfügt, sieht das so aus: Eine einfach verkettete Liste mit einem Kopf und zwei Knoten. Elemente Einfügen Wenn man einen Zeiger auf ein Element der Liste hat, ist es einfach, ein Element dahinter einzufügen.
Stichwörter: Arrays, Pointer, Structs, verkettete Liste, Felder
Es sollen folgende Funktionen zur Verwendung einer verketteten Liste realisiert werden:
- Ausgeben der Liste
- Elemente vorne anfügen
- Elemente hinten anhängen
- Elemente zählen
- Erstes Element löschen
- Letztes Element löschen
- Wert suchen und Adresse zurückgeben
- Wert in der Liste auf Null setzen
#include