Popis kružnih veza: Prednosti na primjeru programa C

Sadržaj:

Anonim

Što je kružno povezani popis?

Kružno povezani popis niz je čvorova raspoređenih na takav način da se svaki čvor može povući prema sebi. Ovdje je "čvor" autoreferencijalni element s pokazivačima na jedan ili dva čvora u neposrednoj blizini II.

Ispod je prikaz kružno povezanog popisa s 3 čvora.

Ovdje možete vidjeti da se svaki čvor može sam povući. Gornji primjer je kružni pojedinačno povezani popis.

Napomena: Najjednostavniji kružno povezani popis čvor je koji se vodi samo do sebe kako je prikazano

U ovom vodiču s kružnim povezanim popisom naučit ćete:

  • Što je kružno povezani popis?
  • Osnovne operacije
  • Operacija umetanja
  • Operacija brisanja
  • Prijelaz kružno povezanog popisa
  • Prednosti kružno povezanog popisa
  • Pojedinačno povezani popis kao kružno povezani popis
  • Primjene popisa s kružnom vezom

Osnovne operacije

Osnovne operacije na kružno povezanom popisu su:

  1. Umetanje
  2. Brisanje i
  3. Preokret
  • Umetanje je postupak postavljanja čvora na određeno mjesto na kružno povezanom popisu.
  • Brisanje je postupak uklanjanja postojećeg čvora s povezanog popisa. Čvor se može identificirati pojavom njegove vrijednosti ili položajem.
  • Prijelaz kružnog povezanog popisa postupak je prikazivanja cijelog sadržaja povezanog popisa i vraćanje natrag na izvorni čvor.

U sljedećem ćete odjeljku razumjeti umetanje čvora i vrste umetanja u kružni pojedinačno povezani popis.

Operacija umetanja

U početku morate stvoriti jedan čvor koji pokazuje sam na sebe kako je prikazano na ovoj slici. Bez ovog čvora, umetanje stvara prvi čvor.

Dalje, postoje dvije mogućnosti:

  • Umetanje na trenutni položaj kružno povezanog popisa. To odgovara umetanju na početak kraja redovitog singularno povezanog popisa. U kružno povezanom popisu početak i kraj su isti.
  • Umetanje nakon indeksiranog čvora. Čvor bi trebao biti identificiran brojem indeksa koji odgovara vrijednosti njegovog elementa.

Za umetanje na početak / kraj kružno povezanog popisa, to jest na mjesto gdje je dodan prvi čvor,

  • Morat ćete prekinuti postojeću samo-vezu sa postojećim čvorom
  • Sljedeći pokazivač novog čvora povezat će se sa postojećim čvorom.
  • Sljedeći pokazivač zadnjeg čvora ukazat će na umetnuti čvor.

NAPOMENA: Pokazivač koji je glavni token ili početak / kraj kruga može se promijeniti. I dalje će se vratiti na isti čvor tijekom prijelaza, o čemu smo raspravljali unaprijed.

Koraci u (a) i-iii prikazani su u nastavku:

(Postojeći čvor)

KORAK 1) Prekinite postojeću vezu

KORAK 2) Stvorite prosljeđujuću vezu (od novog čvora do postojećeg čvora)

KORAK 3) Stvorite vezu petlje do prvog čvora

Zatim ćete pokušati umetnuti nakon čvora.

Na primjer, umetnimo "VALUE2" nakon čvora s "VALUE0". Pretpostavimo da je početna točka čvor s "VALUE0".

  • Morat ćete prekinuti liniju između prvog i drugog čvora i postaviti čvor s "VALUE2" između.
  • Sljedeći pokazivač prvog čvora mora se povezati s tim čvorom, a sljedeći pokazivač ovog čvora mora se povezati s ranijim drugim čvorom.
  • Ostatak aranžmana ostaje nepromijenjen. Svi čvorovi su sami do sebe moguće povući.

NAPOMENA: Budući da postoji ciklički raspored, umetanje čvora uključuje isti postupak za bilo koji čvor. Pokazivač koji dovršava ciklus dovršava ciklus kao i bilo koji drugi čvor.

To je prikazano u nastavku:

(Recimo da postoje samo dva čvora. Ovo je trivijalan slučaj)

KORAK 1) Uklonite unutarnju vezu između povezanih čvorova

KORAK 2) Spojite lijevi bočni čvor na novi čvor

KORAK 3) Spojite novi čvor na čvor s desne strane.

Operacija brisanja

Pretpostavimo da je kružno povezan popis s 3 čvora. Slučajevi brisanja navedeni su u nastavku:

  • Brisanje trenutnog elementa
  • Brisanje nakon elementa.

Brisanje na početku / kraju:

  1. Prelazak na prvi čvor od zadnjeg čvora.
  2. Da biste ga izbrisali s kraja, trebao bi postojati samo jedan korak prelaska, od zadnjeg do prvog čvora.
  3. Izbrišite vezu između zadnjeg i sljedećeg čvora.
  4. Povežite zadnji čvor sa sljedećim elementom prvog čvora.
  5. Oslobodite prvi čvor.

(Postojeće postavljanje)

KORAK 1 ) Uklonite kružnu vezu

KORACI 2) Uklonite vezu između prvog i sljedećeg, povežite posljednji čvor s čvorom koji slijedi prvi

KORAK 3) Oslobodite / oslobodite prvi čvor

Brisanje nakon čvora:

  1. Prijeđi do sljedećeg čvora čvora koji treba izbrisati.
  2. Prijeđite na sljedeći čvor, postavljajući pokazivač na prethodni čvor.
  3. Povežite prethodni čvor s čvorom nakon sadašnjeg čvora, koristeći sljedeći pokazivač.
  4. Oslobodite trenutni (delinked) čvor.

KORAK 1) Recimo da moramo izbrisati čvor s "VRIJEDNOST1".

KORAK 2) Uklonite vezu između prethodnog i trenutnog čvora. Povežite njegov prethodni čvor sa sljedećim čvorom na koji upućuje trenutni čvor (s VALUE1).

KORAK 3) Oslobodite ili oslobodite trenutni čvor.

Prijelaz kružno povezanog popisa

Da biste prešli kružno povezanu listu, počevši od zadnjeg pokazivača, provjerite je li zadnji posljednji pokazivač NULL. Ako je ovaj uvjet netačan, provjerite postoji li samo jedan element. U suprotnom, pređite pomoću privremenog pokazivača dok se ponovno ne postigne zadnji pokazivač ili onoliko puta koliko je potrebno, kao što je prikazano u GIF-u dolje.

Prednosti kružno povezanog popisa

Neke od prednosti kružno povezanih popisa su:

  1. Nema zahtjeva za NULL dodjelu u kodu. Kružni popis nikada ne upućuje na NULL pokazivač ako nije u potpunosti oslobođen.
  2. Kružno povezani popisi korisni su za završne operacije jer se početak i kraj podudaraju. Algoritmi kao što je zakazivanje Round Robin-a mogu uredno eliminirati procese koji su kružno stavljeni u red bez nailaženja na viseće ili NULL-referencijalne pokazivače.
  3. Kružno povezani popis također obavlja sve redovite funkcije pojedinačno povezanog popisa. Zapravo, dolje opisani kružni dvostruko povezani popisi mogu čak eliminirati potrebu za cjelovitom obilaznicom za pronalaženje elementa. Taj bi element bio samo u potpunosti suprotan početku, dovršavajući samo polovicu povezanog popisa.

Popis pojedinačno povezanih kao popis kružnih veza

Preporučujemo vam da pokušate pročitati i implementirati donji kod. Predstavlja aritmetiku pokazivača povezanu s kružno povezanim popisima.

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

Objašnjenje koda:

  1. Prva dva retka koda su potrebne datoteke zaglavlja.
  2. Sljedeći odjeljak opisuje strukturu svakog autoreferencijalnog čvora. Sadrži vrijednost i pokazivač istog tipa kao i struktura.
  3. Svaka se struktura više puta povezuje s objektima iste vrste.
  4. Postoje različiti prototipovi funkcija za:
    1. Dodavanje elementa na prazan povezani popis
    2. Umetanje na trenutno istaknuti položaj kružno povezanog popisa.
    3. Umetanje nakon određene indeksirane vrijednosti na povezani popis.
    4. Uklanjanje / brisanje nakon određene indeksirane vrijednosti na povezanom popisu.
    5. Uklanjanje na trenutno istaknutom položaju kružno povezanog popisa
  5. Posljednja funkcija ispisuje svaki element kroz kružno zaokretanje u bilo kojem stanju povezanog popisa.
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)

Objašnjenje koda:

  1. Za kôd addEmpty dodijelite prazan čvor pomoću funkcije malloc.
  2. Za ovaj čvor postavite podatke u vremensku varijablu.
  3. Dodijelite i povežite jedinu varijablu s privremenom varijablom
  4. Vratite zadnji element u glavni () / kontekst aplikacije.
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;…

Objašnjenje koda

  1. Ako nema elementa za umetanje, trebali biste dodati na prazan popis i vratiti kontrolu.
  2. Stvorite privremeni element koji ćete smjestiti nakon trenutnog elementa.
  3. Povežite pokazivače kao što je prikazano.
  4. Vrati zadnji pokazivač kao u prethodnoj funkciji.
… 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");…

Objašnjenje koda:

  1. Ako na popisu nema elementa, zanemarite podatke, dodajte trenutnu stavku kao zadnju stavku na popisu i vratite kontrolu
  2. Za svaku iteraciju u petlji do-while osigurajte da postoji prethodni pokazivač koji sadrži posljednji pređeni rezultat.
  3. Tek tada se može dogoditi sljedeći preokret.
  4. Ako se podaci pronađu ili temp dosegne natrag do zadnjeg pokazivača, vrijeme rada prekida. Sljedeći odjeljak koda odlučuje što se mora učiniti s predmetom.
… 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)…

Objašnjenje koda:

  1. Ako je prešao cijeli popis, ali stavka nije pronađena, prikažite poruku "stavka nije pronađena", a zatim vratite kontrolu pozivatelju.
  2. Ako je pronađen čvor i / ili čvor još nije zadnji čvor, stvorite novi čvor.
  3. Povežite prethodni čvor s novim čvorom. Povežite trenutni čvor s temp (varijabla zaokretanja).
  4. To osigurava da se element postavi nakon određenog čvora na kružno povezanom popisu. Vratite se pozivatelju.
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)

Objašnjenje koda

  1. Da biste uklonili samo posljednji (trenutni) čvor, provjerite je li ovaj popis prazan. Ako jest, nijedan se element ne može ukloniti.
  2. Varijabla temp samo prelazi jednu vezu prema naprijed.
  3. Povežite zadnji pokazivač s pokazivačem nakon prvog.
  4. Oslobodite pokazivač temperature. Oslobađa nepovezani zadnji pokazivač.
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");…

Objašnjenje koda

  1. Kao i kod prethodne funkcije uklanjanja, provjerite nema li elementa. Ako je to istina, tada se nijedan element ne može ukloniti.
  2. Pokazivačima se dodjeljuju određeni položaji za pronalaženje elementa koji će se brisati.
  3. Pokazivači su napredni, jedan iza drugog. (prev iza temperature)
  4. Proces se nastavlja sve dok se element ne pronađe ili se sljedeći element povuče do zadnjeg pokazivača.
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;

Objašnjenje programa

  1. Ako je element pronađen nakon prelaska cijelog povezanog popisa, prikazuje se poruka o pogrešci koja kaže da stavka nije pronađena.
  2. Inače, element se razdvaja i oslobađa u koracima 3 i 4.
  3. Prethodni pokazivač povezan je s adresom na koju je element za brisanje označio kao "sljedeći" (temp).
  4. Prema tome, pokazivač temperature je oslobođen i oslobođen.
… 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;}}

Objašnjenje koda

  1. Zavirivanje ili prelazak nije moguć ako je nula potrebna. Korisnik mora dodijeliti ili umetnuti čvor.
  2. Ako postoji samo jedan čvor, nema potrebe za prelaskom, sadržaj čvora može se ispisati, a while petlja se ne izvršava.
  3. Ako postoji više od jednog čvora, tada temp ispisuje sve stavke do zadnjeg elementa.
  4. U trenutku kada se postigne posljednji element, petlja se završava i funkcija vraća poziv glavnoj funkciji.

Primjene popisa s kružnom vezom

  • Implementacija kružnog planiranja u sistemske procese i kružno raspoređivanje u brzim grafikama.
  • Zakazivanje prstenova tokena u računalnim mrežama.
  • Koristi se u prikaznim jedinicama poput prodajnih ploča koje zahtijevaju kontinuirano obilaženje podataka.