Zirkuläre verknüpfte Liste: Vorteile mit C-Programmbeispiel

Inhaltsverzeichnis:

Anonim

Was ist eine zirkuläre verknüpfte Liste?

Eine zirkuläre verknüpfte Liste ist eine Folge von Knoten, die so angeordnet sind, dass jeder Knoten zu sich selbst zurückverfolgt werden kann. Hier ist ein "Knoten" ein selbstreferenzielles Element mit Zeigern auf einen oder zwei Knoten in unmittelbarer Nähe.

Unten sehen Sie eine Darstellung einer zirkular verknüpften Liste mit 3 Knoten.

Hier können Sie sehen, dass jeder Knoten auf sich selbst zurückverfolgt werden kann. Das oben gezeigte Beispiel ist eine zirkuläre, einfach verknüpfte Liste.

Hinweis: Die einfachste zirkuläre verknüpfte Liste ist ein Knoten, der wie gezeigt nur auf sich selbst zurückgeführt wird

In diesem Tutorial für zirkuläre verknüpfte Listen erfahren Sie:

  • Was ist eine zirkuläre verknüpfte Liste?
  • Grundoperationen
  • Einfügevorgang
  • Löschvorgang
  • Durchqueren einer zirkulären verknüpften Liste
  • Vorteile der zirkulären verknüpften Liste
  • Einfach verknüpfte Liste als zirkuläre verknüpfte Liste
  • Anwendungen der Circular Linked List

Grundoperationen

Die grundlegenden Operationen für eine zirkuläre verknüpfte Liste sind:

  1. Einfügen
  2. Löschen und
  3. Durchquerung
  • Beim Einfügen wird ein Knoten an einer bestimmten Position in der zirkular verknüpften Liste platziert.
  • Beim Löschen wird ein vorhandener Knoten aus der verknüpften Liste entfernt. Der Knoten kann durch das Auftreten seines Wertes oder durch seine Position identifiziert werden.
  • Beim Durchlaufen einer zirkulären verknüpften Liste wird der Inhalt der gesamten verknüpften Liste angezeigt und zum Quellknoten zurückverfolgt.

Im nächsten Abschnitt werden Sie das Einfügen eines Knotens und die Arten des Einfügens in eine zirkuläre, einfach verknüpfte Liste verstehen.

Einfügevorgang

Zunächst müssen Sie einen Knoten erstellen, der wie in diesem Bild gezeigt auf sich selbst zeigt. Ohne diesen Knoten wird durch Einfügen der erste Knoten erstellt.

Als nächstes gibt es zwei Möglichkeiten:

  • Einfügen an der aktuellen Position der zirkulären verknüpften Liste. Dies entspricht dem Einfügen am Anfang des Endes einer regulären singulären verknüpften Liste. In einer zirkulär verknüpften Liste sind Anfang und Ende gleich.
  • Einfügen nach einem indizierten Knoten. Der Knoten sollte durch eine Indexnummer identifiziert werden, die seinem Elementwert entspricht.

Zum Einfügen am Anfang / Ende der zirkular verknüpften Liste, dh an der Position, an der der erste Knoten hinzugefügt wurde,

  • Sie müssen die vorhandene Selbstverbindung zum vorhandenen Knoten trennen
  • Der nächste Zeiger des neuen Knotens wird mit dem vorhandenen Knoten verknüpft.
  • Der nächste Zeiger des letzten Knotens zeigt auf den eingefügten Knoten.

HINWEIS: Der Zeiger, der der Token-Master oder der Anfang / das Ende des Kreises ist, kann geändert werden. Es wird weiterhin auf demselben Knoten zu demselben Knoten zurückkehren, der zuvor besprochen wurde.

Die Schritte in (a) i-iii sind unten gezeigt:

(Bestehender Knoten)

SCHRITT 1) Unterbrechen Sie den vorhandenen Link

SCHRITT 2) Erstellen Sie eine Vorwärtsverbindung (vom neuen Knoten zu einem vorhandenen Knoten).

SCHRITT 3) Erstellen Sie eine Schleifenverbindung zum ersten Knoten

Als Nächstes versuchen Sie das Einfügen nach einem Knoten.

Fügen wir zum Beispiel "VALUE2" nach dem Knoten mit "VALUE0" ein. Nehmen wir an, der Startpunkt ist der Knoten mit "VALUE0".

  • Sie müssen die Linie zwischen dem ersten und dem zweiten Knoten unterbrechen und den Knoten mit "VALUE2" dazwischen platzieren.
  • Der nächste Zeiger des ersten Knotens muss mit diesem Knoten verknüpft sein, und der nächste Zeiger dieses Knotens muss mit dem früheren zweiten Knoten verknüpft sein.
  • Der Rest der Vereinbarung bleibt unverändert. Alle Knoten können auf sich selbst zurückverfolgt werden.

HINWEIS: Da es eine zyklische Anordnung gibt, erfolgt das Einfügen eines Knotens für jeden Knoten nach dem gleichen Verfahren. Der Zeiger, der einen Zyklus abschließt, schließt den Zyklus wie jeder andere Knoten ab.

Dies ist unten gezeigt:

(Nehmen wir an, es gibt nur zwei Knoten. Dies ist ein trivialer Fall.)

SCHRITT 1) Entfernen Sie die innere Verbindung zwischen den verbundenen Knoten

SCHRITT 2) Verbinden Sie den linken Knoten mit dem neuen Knoten

SCHRITT 3) Verbinden Sie den neuen Knoten mit dem rechten Knoten.

Löschvorgang

Nehmen wir eine zirkuläre verknüpfte Liste mit 3 Knoten an. Die Fälle für die Löschung sind unten angegeben:

  • Das aktuelle Element löschen
  • Löschen nach einem Element.

Löschen am Anfang / Ende:

  1. Vom letzten Knoten zum ersten Knoten wechseln.
  2. Um vom Ende zu löschen, sollte es nur einen Durchlaufschritt vom letzten zum ersten Knoten geben.
  3. Löschen Sie die Verbindung zwischen dem letzten Knoten und dem nächsten Knoten.
  4. Verknüpfen Sie den letzten Knoten mit dem nächsten Element des ersten Knotens.
  5. Geben Sie den ersten Knoten frei.

(Vorhandenes Setup)

SCHRITT 1 ) Entfernen Sie die Rundverbindung

SCHRITTE 2) Entfernen Sie die Verknüpfung zwischen dem ersten und dem nächsten, verknüpfen Sie den letzten Knoten mit dem Knoten, der dem ersten folgt

SCHRITT 3) Geben Sie den ersten Knoten frei / geben Sie die Zuordnung frei

Löschen nach einem Knoten:

  1. Durchqueren, bis der nächste Knoten der zu löschende Knoten ist.
  2. Fahren Sie zum nächsten Knoten und platzieren Sie einen Zeiger auf den vorherigen Knoten.
  3. Verbinden Sie den vorherigen Knoten mit dem Knoten nach dem aktuellen Knoten mit seinem nächsten Zeiger.
  4. Geben Sie den aktuellen (entkoppelten) Knoten frei.

SCHRITT 1) Nehmen wir an, wir müssen einen Knoten mit "VALUE1" löschen.

SCHRITT 2) Entfernen Sie die Verbindung zwischen dem vorherigen Knoten und dem aktuellen Knoten. Verknüpfen Sie den vorherigen Knoten mit dem nächsten Knoten, auf den der aktuelle Knoten zeigt (mit VALUE1).

SCHRITT 3) Geben Sie den aktuellen Knoten frei oder geben Sie die Zuordnung frei.

Durchqueren einer zirkulären verknüpften Liste

Überprüfen Sie, ob der letzte Zeiger selbst NULL ist, um eine zirkuläre verknüpfte Liste ausgehend von einem letzten Zeiger zu durchlaufen. Wenn diese Bedingung falsch ist, prüfen Sie, ob nur ein Element vorhanden ist. Andernfalls fahren Sie mit einem temporären Zeiger, bis der letzte Zeiger wieder erreicht ist, oder so oft wie nötig, wie im folgenden GIF gezeigt.

Vorteile der zirkulären verknüpften Liste

Einige der Vorteile von zirkular verknüpften Listen sind:

  1. Keine NULL-Zuweisung im Code erforderlich. Die zirkuläre Liste zeigt niemals auf einen NULL-Zeiger, es sei denn, die Zuordnung ist vollständig freigegeben.
  2. Zirkuläre verknüpfte Listen sind für Endoperationen vorteilhaft, da Anfang und Ende zusammenfallen. Algorithmen wie die Round Robin-Planung können Prozesse, die in einer zirkulären Weise in die Warteschlange gestellt werden, sauber eliminieren, ohne auf baumelnde oder NULL-referenzielle Zeiger zu stoßen.
  3. Die zirkuläre verknüpfte Liste führt auch alle regulären Funktionen einer einfach verknüpften Liste aus. In der Tat können kreisförmige, doppelt verknüpfte Listen, die unten diskutiert werden, sogar die Notwendigkeit einer Durchquerung in voller Länge beseitigen, um ein Element zu lokalisieren. Dieses Element wäre höchstens genau entgegengesetzt zum Start und würde nur die Hälfte der verknüpften Liste vervollständigen.

Einfach verknüpfte Liste als zirkuläre verknüpfte Liste

Es wird empfohlen, den folgenden Code zu lesen und zu implementieren. Es zeigt die Zeigerarithmetik, die mit zirkular verknüpften Listen verknüpft ist.

#include#includestruct node{int item;struct node *next;};struct node* addToEmpty(struct node*,int);struct node *insertCurrent(struct node *, int);struct node *insertAfter(struct node *, int, int);struct node *removeAfter(struct node *, int);struct node *removeCurrent(struct node *);void peek(struct node *);int main(){…

Erklärung des Codes:

  1. Die ersten beiden Codezeilen sind die erforderlichen enthaltenen Header-Dateien.
  2. Der nächste Abschnitt beschreibt die Struktur jedes selbstreferenziellen Knotens. Es enthält einen Wert und einen Zeiger des gleichen Typs wie die Struktur.
  3. Jede Struktur ist wiederholt mit Strukturobjekten desselben Typs verknüpft.
  4. Es gibt verschiedene Funktionsprototypen für:
    1. Hinzufügen eines Elements zu einer leeren verknüpften Liste
    2. Einfügen an der aktuell spitzen Position einer zirkulären verknüpften Liste.
    3. Einfügen nach einem bestimmten indizierten Wert in die verknüpfte Liste.
    4. Entfernen / Löschen nach einem bestimmten indizierten Wert in der verknüpften Liste.
    5. Entfernen an der aktuell angezeigten Position einer zirkulären verknüpften Liste
  5. Die letzte Funktion druckt jedes Element in einem beliebigen Zustand der verknüpften Liste durch eine kreisförmige Durchquerung.
int main(){struct node *last = NULL;last = insertCurrent(last,4);last = removeAfter(last, 4);peek(last);return 0;}struct node* addToEmpty(struct node*last, int data){struct node *temp = (struct node *)malloc(sizeof( struct node));temp->item = data;last = temp;last->next = last;return last;}struct node *insertCurrent(struct node *last, int data)

Erklärung des Codes:

  1. Weisen Sie für den addEmpty-Code mit der Funktion malloc einen leeren Knoten zu.
  2. Platzieren Sie für diesen Knoten die Daten in der temporären Variablen.
  3. Weisen Sie die einzige Variable zu und verknüpfen Sie sie mit der temporären Variablen
  4. Geben Sie das letzte Element in den Kontext main () / application zurück.
struct node *insertCurrent(struct node *last, int data){if(last == NULL){return addToEmpty(last, data);}struct node *temp = (struct node *)malloc(sizeof( struct node));temp -> item = data;temp->next = last->next;last->next = temp;return last;}struct node *insertAfter(struct node *last, int data, int item){struct node *temp = last->next, *prev = temp, *newnode =NULL;…

Erklärung des Codes

  1. Wenn kein Element zum Einfügen vorhanden ist, sollten Sie sicherstellen, dass Sie es zu einer leeren Liste hinzufügen und die Steuerung zurückgeben.
  2. Erstellen Sie ein temporäres Element, das nach dem aktuellen Element platziert werden soll.
  3. Verknüpfen Sie die Zeiger wie gezeigt.
  4. Geben Sie den letzten Zeiger wie in der vorherigen Funktion zurück.
… struct node *insertAfter(struct node *last, int data, int item){struct node *temp = last->next, *prev = temp, *newnode =NULL;if (last == NULL){return addToEmpty(last, item);}do{prev = temp;temp = temp->next;} while (temp->next != last && temp->item != data );if(temp->item != data){printf("Element not found. Please try again");…

Erklärung des Codes:

  1. Wenn die Liste kein Element enthält, ignorieren Sie die Daten, fügen Sie das aktuelle Element als letztes Element in der Liste hinzu und geben Sie die Steuerung zurück
  2. Stellen Sie für jede Iteration in der do-while-Schleife sicher, dass ein vorheriger Zeiger vorhanden ist, der das zuletzt durchquerte Ergebnis enthält.
  3. Nur dann kann die nächste Durchquerung erfolgen.
  4. Wenn die Daten gefunden werden oder die Temperatur bis zum letzten Zeiger zurückreicht, wird das Do-While beendet. Der nächste Codeabschnitt entscheidet, was mit dem Element zu tun ist.
… if(temp->item != data){printf("Element not found. Please try again");return last;}else{newnode = (struct node *)malloc(sizeof(struct node));newnode->item = item;prev->next = newnode;newnode->next = temp;}return last;}struct node *removeCurrent(struct node *last)…

Erklärung des Codes:

  1. Wenn die gesamte Liste durchlaufen wurde, das Element jedoch nicht gefunden wurde, zeigen Sie die Meldung "Element nicht gefunden" an und geben Sie die Kontrolle an den Anrufer zurück.
  2. Wenn ein Knoten gefunden wurde und / oder der Knoten noch nicht der letzte Knoten ist, erstellen Sie einen neuen Knoten.
  3. Verknüpfen Sie den vorherigen Knoten mit dem neuen Knoten. Verknüpfen Sie den aktuellen Knoten mit temp (der Traversalvariablen).
  4. Dadurch wird sichergestellt, dass das Element nach einem bestimmten Knoten in der zirkular verknüpften Liste platziert wird. Kehren Sie zum Anrufer zurück.
struct node *removeCurrent(struct node *last){if(last == NULL){printf("Element Not Found");return NULL;}struct node *temp = last->next;last->next = temp->next;free(temp);return last;}struct node *removeAfter(struct node *last, int data)

Erklärung des Codes

  1. Um nur den letzten (aktuellen) Knoten zu entfernen, überprüfen Sie, ob diese Liste leer ist. Wenn dies der Fall ist, kann kein Element entfernt werden.
  2. Die temporäre Variable durchläuft nur eine Verbindung vorwärts.
  3. Verknüpfen Sie den letzten Zeiger mit dem Zeiger nach dem ersten.
  4. Geben Sie den temporären Zeiger frei. Die Zuordnung des nicht verknüpften letzten Zeigers wird aufgehoben.
struct node *removeAfter(struct node *last,int data){struct node *temp = NULL,*prev = NULL;if (last == NULL){printf("Linked list empty. Cannot remove any element\n");return NULL;}temp = last->next;prev = temp;do{prev = temp;temp = temp->next;} while (temp->next != last && temp->item != data );if(temp->item != data){printf("Element not found");…

Erklärung des Codes

  1. Überprüfen Sie wie bei der vorherigen Entfernungsfunktion, ob kein Element vorhanden ist. Wenn dies zutrifft, kann kein Element entfernt werden.
  2. Zeigern werden bestimmte Positionen zugewiesen, um das zu löschende Element zu lokalisieren.
  3. Die Zeiger werden hintereinander vorgeschoben. (prev hinter temp)
  4. Der Vorgang wird fortgesetzt, bis ein Element gefunden wurde oder das nächste Element zum letzten Zeiger zurückverfolgt wird.
if(temp->item != data){printf("Element not found");return last;}else{prev->next = temp->next;free(temp);}return last;}void peek(struct node * last){struct node *temp = last;if (last == NULL){return;

Erklärung des Programms

  1. Wenn das Element nach dem Durchlaufen der gesamten verknüpften Liste gefunden wurde, wird eine Fehlermeldung angezeigt, die besagt, dass das Element nicht gefunden wurde.
  2. Andernfalls wird das Element in den Schritten 3 und 4 gelöscht und freigegeben.
  3. Der vorherige Zeiger ist mit der Adresse verknüpft, auf die das zu löschende Element (temp) als "next" zeigt.
  4. Der temporäre Zeiger wird daher freigegeben und freigegeben.
… void peek(struct node * last){struct node *temp = last;if (last == NULL){return;}if(last -> next == last){printf("%d-", temp->item);}while (temp != last){printf("%d-", temp->item);temp = temp->next;}}

Erklärung des Codes

  1. Das Peek oder Traversal ist nicht möglich, wenn keine Null benötigt wird. Der Benutzer muss einen Knoten zuweisen oder einfügen.
  2. Wenn nur ein Knoten vorhanden ist, muss er nicht durchlaufen werden, der Inhalt des Knotens kann gedruckt werden und die while-Schleife wird nicht ausgeführt.
  3. Wenn es mehr als einen Knoten gibt, druckt die Temperatur das gesamte Element bis zum letzten Element.
  4. Sobald das letzte Element erreicht ist, wird die Schleife beendet und die Funktion gibt den Aufruf der Hauptfunktion zurück.

Anwendungen der Circular Linked List

  • Implementierung der Round-Robin-Planung in Systemprozessen und der zirkulären Planung in Hochgeschwindigkeitsgrafiken.
  • Planung von Token-Ringen in Computernetzwerken.
  • Es wird in Anzeigeeinheiten wie Shop-Boards verwendet, die ein kontinuierliches Durchlaufen von Daten erfordern.