Listă circulară legată: Avantaje cu exemplu de program C

Cuprins:

Anonim

Ce este o listă circulară legată?

O listă circulară legată este o secvență de noduri dispuse în așa fel încât fiecare nod să poată fi retras în sine. Aici un "nod" este un element auto-referențial cu indicatori către unul sau două noduri în vecinătatea imediată a iI.

Mai jos este prezentată o listă circulară legată cu 3 noduri.

Aici, puteți vedea că fiecare nod este retracabil pentru sine. Exemplul prezentat mai sus este o listă circulară legată individual.

Notă: Cea mai simplă listă circulară legată este un nod care se urmărește doar la sine, așa cum se arată

În acest tutorial cu listă circulară legată, veți afla:

  • Ce este o listă circulară legată?
  • Operațiuni de bază
  • Operațiune de inserare
  • Operațiunea de ștergere
  • Transversarea unei liste circulare legate
  • Avantajele listei circulare legate
  • Listă legată individual ca listă circulară legată
  • Aplicații ale listei circulare legate

Operațiuni de bază

Operațiunile de bază pe o listă circulară legată sunt:

  1. Inserare
  2. Ștergerea și
  3. Traversal
  • Inserarea este procesul de plasare a unui nod într-o poziție specificată în lista circulară legată.
  • Ștergerea este procesul de eliminare a unui nod existent din lista legată. Nodul poate fi identificat prin apariția valorii sale sau prin poziția sa.
  • Traversarea unei liste circulare legate este procesul de afișare a întregului conținut al listei conectate și retracerea înapoi la nodul sursă.

În secțiunea următoare, veți înțelege inserarea unui nod și tipurile de inserare posibile într-o listă circulară legată individual.

Operațiune de inserare

Inițial, trebuie să creați un nod care să indice spre sine așa cum se arată în această imagine. Fără acest nod, inserția creează primul nod.

În continuare, există două posibilități:

  • Inserare în poziția curentă a listei circulare legate. Aceasta corespunde cu inserarea la începutul sfârșitului unei liste regulate legate la singular. Într-o listă circulară legată, începutul și sfârșitul sunt aceleași.
  • Inserare după un nod indexat. Nodul trebuie identificat printr-un număr de index corespunzător valorii elementului său.

Pentru inserarea la începutul / sfârșitul listei circulare legate, care este în poziția în care a fost adăugat primul nod,

  • Va trebui să rupeți auto-legătura existentă cu nodul existent
  • Următorul indicator al noului nod se va lega de nodul existent.
  • Următorul indicator al ultimului nod va indica nodul inserat.

NOTĂ: Pointerul care este maestrul simbolului sau începutul / sfârșitul cercului poate fi schimbat. Va reveni în continuare la același nod pe o traversare, discutată mai departe.

Etapele din (a) i-iii sunt prezentate mai jos:

(Nod existent)

PASUL 1) Întrerupeți legătura existentă

PASUL 2) Creați o legătură directă (de la un nod nou la un nod existent)

PASUL 3) Creați o legătură de buclă către primul nod

Apoi, veți încerca inserarea după un nod.

De exemplu, să inserăm „VALUE2” după nodul cu „VALUE0”. Să presupunem că punctul de plecare este nodul cu „VALOR0”.

  • Va trebui să rupeți linia dintre primul și al doilea nod și să plasați nodul cu „VALUE2” între ele.
  • Următorul indicator al primului nod trebuie să se conecteze la acest nod, iar următorul indicator al acestui nod trebuie să se conecteze la al doilea nod anterior.
  • Restul aranjamentului rămâne neschimbat. Toate nodurile sunt retracibile pentru ele însele.

NOTĂ: Deoarece există un aranjament ciclic, inserarea unui nod implică aceeași procedură pentru orice nod. Pointerul care finalizează un ciclu completează ciclul la fel ca orice alt nod.

Aceasta este prezentată mai jos:

(Să spunem că există doar două noduri. Acesta este un caz banal)

PASUL 1) Eliminați legătura interioară dintre nodurile conectate

PASUL 2) Conectați nodul din stânga la noul nod

PASUL 3) Conectați noul nod la nodul din partea dreaptă.

Operațiunea de ștergere

Să presupunem o listă circulară cu 3 noduri. Cazurile pentru ștergere sunt date mai jos:

  • Ștergerea elementului curent
  • Ștergerea după un element.

Ștergerea la începutul / sfârșitul:

  1. Treceți la primul nod de la ultimul nod.
  2. Pentru a șterge de la sfârșit, ar trebui să existe un singur pas de parcurgere, de la ultimul nod până la primul nod.
  3. Ștergeți legătura dintre ultimul nod și următorul nod.
  4. Conectați ultimul nod la următorul element al primului nod.
  5. Eliberați primul nod.

(Configurare existentă)

PASUL 1 ) Scoateți legătura circulară

PASUL 2) Eliminați legătura dintre primul și următorul, legați ultimul nod, de nodul următor primului

PASUL 3) Eliberați / alocați primul nod

Ștergerea după un nod:

  1. Treceți până la următorul nod este nodul care trebuie șters.
  2. Treceți la nodul următor, plasând un pointer pe nodul anterior.
  3. Conectați nodul anterior la nodul după nodul actual, folosind următorul indicator al acestuia.
  4. Eliberați nodul curent (deconectat).

PASUL 1) Să spunem că trebuie să ștergem un nod cu „VALUE1”.

PASUL 2) Eliminați legătura dintre nodul anterior și nodul curent. Conectați nodul anterior cu nodul următor indicat de nodul curent (cu VALUE1).

PASUL 3) Eliberați sau delocați nodul curent.

Transversarea unei liste circulare legate

Pentru a parcurge o listă circulară legată, pornind de la un ultim indicator, verificați dacă ultimul indicator în sine este NULL. Dacă această condiție este falsă, verificați dacă există un singur element. În caz contrar, parcurgeți folosind un indicator temporar până când ultimul indicator este atins din nou sau de câte ori este nevoie, așa cum se arată în GIF de mai jos.

Avantajele listei circulare legate

Unele dintre avantajele listelor circulare legate sunt:

  1. Nu este necesară o atribuire NULL în cod. Lista circulară nu indică niciodată un pointer NULL decât dacă este complet alocat.
  2. Listele circulare legate sunt avantajoase pentru operațiunile de final, deoarece începutul și sfârșitul coincid. Algoritmi precum programarea Round Robin pot elimina cu grijă procesele care sunt în coadă într-o manieră circulară, fără a întâlni indicatori cu referințe suspendate sau NULL.
  3. Lista cu legături circulare îndeplinește, de asemenea, toate funcțiile obișnuite ale unei liste conectate individual. De fapt, listele circulare dublu legate discutate mai jos pot chiar elimina necesitatea unei traversări pe toată lungimea pentru a localiza un element. Acest element ar fi cel mult exact opus începutului, completând doar jumătate din lista legată.

Listă legată individual ca listă legată circular

Vă încurajăm să încercați să citiți și să implementați codul de mai jos. Prezintă aritmetica indicatorului asociată cu listele circulare legate.

#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(){…

Explicația codului:

  1. Primele două linii de cod sunt fișierele antet necesare incluse.
  2. Următoarea secțiune descrie structura fiecărui nod auto-referențial. Conține o valoare și un pointer de același tip cu structura.
  3. Fiecare structură se leagă în mod repetat de obiecte de structură de același tip.
  4. Există diferite prototipuri de funcții pentru:
    1. Adăugarea unui element la o listă legată goală
    2. Inserarea în poziția actuală a unei liste circulare legate.
    3. Inserarea după o anumită valoare indexată în lista legată.
    4. Eliminarea / Ștergerea după o anumită valoare indexată din lista legată.
    5. Îndepărtarea în poziția îndreptată în prezent a unei liste circulare legate
  5. Ultima funcție tipărește fiecare element printr-o traversare circulară în orice stare a listei legate.
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)

Explicația codului:

  1. Pentru codul addEmpty, alocați un nod gol folosind funcția malloc.
  2. Pentru acest nod, plasați datele la variabila temp.
  3. Atribuiți și legați singura variabilă de variabila temp
  4. Întoarceți ultimul element în contextul main () / aplicație.
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;…

Explicația codului

  1. Dacă nu există niciun element de inserat, atunci trebuie să vă asigurați că adăugați la o listă goală și reveniți la control.
  2. Creați un element temporar pentru a plasa după elementul curent.
  3. Conectați indicatoarele așa cum se arată.
  4. Întoarceți ultimul indicator ca în funcția anterioară.
… 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");…

Explicația codului:

  1. Dacă nu există niciun element în listă, ignorați datele, adăugați elementul curent ca ultim element din listă și returnați controlul
  2. Pentru fiecare iterație din bucla do-while asigurați-vă că există un indicator anterior care deține ultimul rezultat parcurs.
  3. Abia atunci poate avea loc următoarea traversare.
  4. Dacă datele sunt găsite sau temperatura ajunge înapoi la ultimul indicator, do-while se termină. Următoarea secțiune de cod decide ce trebuie făcut cu elementul.
… 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)…

Explicația codului:

  1. Dacă întreaga listă a fost parcursă, totuși elementul nu este găsit, afișați un mesaj „element nu a fost găsit” și apoi returnați controlul către apelant.
  2. Dacă a fost găsit un nod și / sau nodul nu este încă ultimul nod, atunci creați un nod nou.
  3. Conectați nodul anterior cu noul nod. Conectați nodul curent cu temp (variabila de traversare).
  4. Acest lucru asigură că elementul este plasat după un anumit nod în lista circulară legată. Reveniți la apelant.
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)

Explicația codului

  1. Pentru a elimina doar ultimul nod (actual), verificați dacă această listă este goală. Dacă este, atunci niciun element nu poate fi eliminat.
  2. Variabila temp parcurge doar un link înainte.
  3. Conectați ultimul indicator cu indicatorul după primul.
  4. Eliberați indicatorul de temperatură. Se alocă ultimul indicator ne-legat.
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");…

Explicația codului

  1. Ca și în cazul funcției de eliminare anterioare, verificați dacă nu există niciun element. Dacă acest lucru este adevărat, atunci niciun element nu poate fi eliminat.
  2. Pointerilor li se atribuie poziții specifice pentru a localiza elementul care trebuie șters.
  3. Indicatorii sunt avansați, unul în spatele celuilalt. (anterior în spatele temperaturii)
  4. Procesul continuă până când se găsește un element sau elementul următor revine la ultimul indicator.
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;

Explicația programului

  1. Dacă elementul găsit după parcurgerea întregii liste legate, se afișează un mesaj de eroare care spune că elementul nu a fost găsit.
  2. În caz contrar, elementul este deconectat și eliberat în pașii 3 și 4.
  3. Pointerul anterior este legat de adresa indicată ca „următoare” de elementul de șters (temp).
  4. Prin urmare, indicatorul de temperatură este alocat și eliberat.
… 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;}}

Explicația codului

  1. Privirea sau traversarea nu este posibilă dacă sunt necesare zero. Utilizatorul trebuie să aloce sau să insereze un nod.
  2. Dacă există un singur nod, nu este nevoie să traversăm, conținutul nodului poate fi tipărit, iar bucla while nu se execută.
  3. Dacă există mai multe noduri, atunci temperatura imprimă tot elementul până la ultimul element.
  4. În momentul în care ultimul element este atins, bucla se termină și funcția returnează apelul către funcția principală.

Aplicații ale listei circulare legate

  • Implementarea programării round-robin în procesele de sistem și programarea circulară în grafică de mare viteză.
  • Programarea inelelor de jeton în rețelele de calculatoare.
  • Este utilizat în unități de afișare, cum ar fi panourile de magazin, care necesită o traversare continuă a datelor.