In diesem Tutorial lernen Sie die verknüpfte Liste und ihre Anwendungen kennen. Außerdem erfahren Sie, wie Sie verschiedene Verknüpfungslistenoperationen erstellen und ausführen.
Beim Schatzsuche-Spiel beginnen Sie damit, nach dem ersten Hinweis zu suchen. Wenn Sie ihn finden, finden Sie anstelle des Schatzes den Ort des nächsten Hinweises und dann des nächsten und so weiter. Du folgst den Hinweisen, bis du den Schatz erreichst.
Die verknüpfte Liste ähnelt dem Spielbeispiel. Es ist eine Reihe verbundener "Knoten", die die "Adresse" des nächsten Knotens enthalten. Jeder Knoten kann einen Datenpunkt speichern, der eine Zahl, eine Zeichenfolge oder ein beliebiger anderer Datentyp sein kann.
Repräsentieren einer verknüpften Liste
Wir müssen irgendwo anfangen, also geben wir der Adresse des ersten Knotens einen speziellen Namen namens HEAD. Außerdem kann der letzte Knoten in der verknüpften Liste identifiziert werden, weil sein nächster Teil auf NULL zeigt.
Wie wird auf einen anderen Knoten verwiesen?
Lassen Sie uns darüber nachdenken, was jeder Knoten enthält:
- Datenelement;
- Adresse eines anderen Hosts.
Wir verketten das Datenelement und den Link zum nächsten Knoten zu einer Struktur wie:
struct node
{
int data;
struct node *next;
};
Das Verständnis der Struktur des verknüpften Listenknotens ist der Schlüssel zum Verständnis.
Jeder Strukturknoten hat ein Datenelement und einen Zeiger auf einen anderen Strukturknoten. Lassen Sie uns eine einfache verknüpfte Liste mit drei Elementen erstellen, um zu sehen, wie sie funktioniert.
/* Инициализируем узлы */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Выделяем память */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Назначаем значения данных */ one->data = 1; two->data = 2; three->data=3; /* Соединяем узлы */ one->next = two; two->next = three; three->next = NULL; /* Сохраняем адрес первого узла в голове */ head = one;
Wenn Sie keine der obigen Zeilen verstehen, brauchen Sie nur die Zeiger und Strukturen zu aktualisieren.
In nur wenigen Schritten haben wir eine einfache verkettete Liste mit drei Knoten erstellt.
Der Vorteil einer verknüpften Liste liegt in der Möglichkeit, eine Kette zu unterbrechen und wieder daran anzuhängen. Wenn Sie beispielsweise Element 4 zwischen 1 und 2 platzieren möchten, gehen Sie folgendermaßen vor:
-
Erstellen Sie einen neuen Strukturknoten und weisen Sie ihm Speicher zu.
*Addieren Sie seinen Datenwert als 4 - Zeigen Sie mit dem nächsten Zeiger auf einen Strukturknoten, der 2 als Datenwert enthält
- Ändern Sie den nächsten Zeiger "1" auf den gerade erstellten Knoten.
Um etwas Ähnliches in einem Array zu tun, müssten die Positionen aller nachfolgenden Elemente verschoben werden.
Hilfsprogramm für verknüpfte Listen
Listen sind eine der beliebtesten und effizientesten Datenstrukturen, die in allen Programmiersprachen wie C, C++, Python, Java und C# implementiert sind.
Außerdem sind verknüpfte Listen eine großartige Möglichkeit, um zu lernen, wie Zeiger funktionieren. Indem Sie verknüpfte Listen üben, können Sie sich darauf vorbereiten, komplexere Datenstrukturen wie Diagramme und Bäume zu lernen.
