Datenstruktur - Zirkulär verkettete Liste
Eine zirkuläre verkettete Liste ist eine Variante der Struktur verketteter Listen. Ihr Kernmerkmal ist, dass der letzte Knoten der verketteten Liste nicht mehr auf NULL zeigt, sondern stattdessen auf den ersten Knoten zurückzeigt, wodurch die gesamte verkettete Liste logisch eine Ringstruktur bildet.
Strukturelle Merkmale der zirkulären verketteten Liste
Einfach verkettete zirkuläre Liste
Doppelt verkettete zirkuläre Liste
Gewöhnliche verkettete Liste: Ende next = NULL, Abbruchbedingung der Traversierung ist cur == NULL
Zirkuläre verkettete Liste: Ende next = head, Abbruchbedingung der Traversierung ist cur == head (zurück zum Anfangspunkt)
Häufige Operationen:Kopfknoten einfügen O(n) — zuerst den Endknoten finden | Traversierung verwendet do...while-Schleife
Endknoten einfügen O(1) (tail-Zeiger pflegen) | Löschen analog
Zirkuläre verkettete Listen werden hauptsächlich in zwei Typen unterteilt:
- Einfach verkettete zirkuläre Liste: Jeder Knoten speichert nur einen next-Zeiger, und das next des letzten Knotens zeigt zurück auf den Kopfknoten
- Zirkuläre doppelt verkettete Liste: basierend auf der doppelt verketteten Liste zeigt next des letzten Knotens auf den Kopfknoten, und prev des Kopfknotens zeigt auf den letzten Knoten
Das größte Merkmal der Struktur der zirkulären verketteten Liste ist, dass sie natürlicherweise eine kontinuierliche Traversierung unterstützt, bei der das Ende wieder mit dem Anfang verbunden ist.
Die Bedingung zum Bestimmen des Endes der Traversierung ist nicht "ob NULL erreicht wird", sondern "ob zum Startknoten zurückgekehrt wird".
Grundlegende Operationen
Beispiel
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
/* Neuen Knoten erstellen */
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = newNode; /* Für einen einzelnen Knoten zeigt next auf sich selbst und bildet eine Selbstschleife */
return newNode;
}
/* Füge einen Knoten am Kopf der zirkulären verketteten Liste ein
Zeitkomplexität: O(n) — der Endknoten muss zuerst gefunden werden, um seinen next-Zeiger zu aktualisieren */
struct Node* insertAtHead(struct Node* head, int value) {
struct Node* newNode = createNode(value);
if (head == NULL) {
return newNode; /* Leere verkettete Liste, der neue Knoten bildet eine Selbstschleife */
}
/* Finde den Endknoten (d. h. den Knoten, dessen next auf head zeigt) */
struct Node* tail = head;
while (tail->next != head) {
tail = tail->next;
}
newNode->next = head; /* Das next des neuen Knotens zeigt auf den ursprünglichen Kopfknoten */
tail->next = newNode; /* Das next des Endknotens zeigt auf den neuen Knoten (neuer Kopfknoten) */
return newNode; /* Der neue Knoten wird der neue Kopfknoten */
}
/* Durchlaufe die zirkuläre verkettete Liste (ein Zyklus)
Beginne beim Kopfknoten, stoppe, wenn du wieder zum Kopfknoten zurückkehrst */
void traverse(struct Node* head) {
if (head == NULL) return;
struct Node* cur = head;
printf("Zirkuläre verkettete Liste: ");
do {
printf("%d -> ", cur->data);
cur = cur->next;
} while (cur != head); /* Stopp, wenn zum Startpunkt zurückgekehrt wird */
printf("(zurück zum Start)\n");
}
int main() {
struct Node* head = NULL;
head = insertAtHead(head, 30);
head = insertAtHead(head, 20);
head = insertAtHead(head, 10);
traverse(head);
/* Ausgabe: Zirkuläre verkettete Liste: 10 -> 20 -> 30 -> (zurück zum Start) */
return 0;
}
Der Schlüssel zum Durchlaufen einer zirkulären verketteten Liste ist die Verwendung einer
do...whileAnweisung anstelle vonwhile. Denn bei Verwendung vonwhile (cur != head), ist der Anfangszustand cur gleich head, und die Schleife wird überhaupt nicht ausgeführt. Unddo...whilestellt sicher, dass der Schleifenkörper mindestens einmal ausgeführt wird, und prüft dann die Abbruchbedingung.
Klassische Anwendung: Josephus-Ringproblem
Eliminierungsreihenfolge und Endergebnis (n=7, m=3)
Josephus-Ringproblem (Josephus-Problem)ist ein klassisches mathematisches Problem:
Angenommen, n Personen stehen in einem Kreis. Die Zählung beginnt bei der 1. Person, und jede m-te Person wird aus dem Kreis eliminiert. Dann beginnt die Zählung wieder bei der nächsten Person, und dies wird fortgesetzt, bis nur noch die letzte Person übrig bleibt.
Dieses Problem passt auf natürliche Weise zu den strukturellen Eigenschaften einer kreisförmigen verketteten Liste: "Ende-zu-Ende verbunden, zyklisch zugegriffen."
Beispiel
#include <stdlib.h>
struct Node {
int data; /* Personennummer */
struct Node* next;
};
/* Josephus-Ring-Lösung
Parameter: n Gesamtzahl der Personen, m jede m-te gezählte Person verlässt den Kreis
Verwenden Sie eine zirkuläre verkettete Liste, um den gesamten Prozess zu simulieren */
void josephus(int n, int m) {
if (n <= 0) return;
/* Schritt 1: Erstellen Sie eine zirkuläre verkettete Liste mit n Personen (nummeriert 1~n) */
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 1;
head->next = head; /* Wenn es nur eine Person gibt, bildet sie eine Selbstschleife */
struct Node* tail = head;
for (int i = 2; i <= n; i++) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = i;
newNode->next = head; /* Das next des neuen Knotens zeigt immer auf den Kopf */
tail->next = newNode; /* Der next-Zeiger des vorherigen Knotens zeigt auf den neuen Knoten */
tail = newNode; /* tail vorrücken */
}
/* Schritt 2: Eliminierungsprozess simulieren */
struct Node* cur = head;
struct Node* prev = tail; /* prev zeigt auf den Vorgänger von cur, anfangs der tail-Knoten */
printf("Josephus-Ring (n=%d, m=%d) Eliminierungsreihenfolge: ", n, m);
while (cur->next != cur) { /* Ende, wenn nur noch ein Knoten übrig ist (Selbstschleife) */
/* Zählen: m-1 Mal zählen, prev und cur gleichzeitig vorrücken */
for (int count = 1; count < m; count++) {
prev = cur;
cur = cur->next;
}
/* Wenn der Zähler m erreicht, wird cur eliminiert */
printf("%d ", cur->data);
prev->next = cur->next; /* cur überspringen */
free(cur); /* Den eliminierten Knoten freigeben */
cur = prev->next; /* Zählung ab der nächsten Person neu starten */
}
printf("=> Letzter Überlebender: %d\n", cur->data); /* Die letzte Person ausgeben */
free(cur);
}
int main() {
josephus(7, 3);
/* Ausgabe: Josephus-Ring (n=7, m=3) Eliminierungsreihenfolge: 3 6 2 7 5 1 => Letzter Überlebender: 4 */
return 0;
}
Weitere Anwendungsszenarien
| Szenario | Beschreibung |
|---|---|
| Round-Robin-Zeitscheibenplanung im Betriebssystem | Die CPU weist jedem Prozess der Reihe nach Zeitscheiben zu. Wenn ein Prozess seine Zeitscheibe aufgebraucht hat, ist der nächste Prozess an der Reihe, wodurch ein Zyklus entsteht. |
| Mehrspieler-Spiele, bei denen abwechselnd Karten gespielt werden | In Brett- und Kartenspielen sind die Spieler abwechselnd im Uhrzeigersinn (oder gegen den Uhrzeigersinn) an der Reihe. |
| Ringpuffer | Ein Ringpuffer für Audio-/Video-Datenströme; wenn er voll ist, kehrt er zum Anfang zurück und überschreibt alte Daten. |