Kružni povezani popis: prednosti i nedostaci

Što je kružni povezani popis?

Kružna povezana lista je niz čvorova raspoređenih tako da se svaki čvor može ponovno povezati.tracsamom sebi. Svaki „čvor“ je samoreferencijalni element s pokazivačima na jedan ili dva čvora u njegovoj neposrednoj blizini.

Ispod je prikaz kružne povezane liste s 3 čvora.

Ovdje možete vidjeti da je svaki čvor ponovnotracmože sam sebi. Gore prikazani primjer je kružna jednostruko povezana lista.

Napomena: Najjednostavnija kružna povezana lista je jedan čvor čiji sljedeći pokazivač tracvraća se samom sebi, kao što je prikazano dolje.

osnovni Operacije u kružno povezanim listama

Tri osnovne operacije na kružnoj povezanoj listi su:

1. Umetanje
2. Brisanje i
3. obuhvaćanje

• Umetanje je postupak postavljanja čvora na određeno mjesto u kružnom povezanom popisu.
• Brisanje je postupak uklanjanja postojećeg čvora s povezanog popisa. Čvor se može identificirati po pojavljivanju njegove vrijednosti ili po položaju.
• Prolazak kroz kružnu povezanu listu je proces prikazivanja cijelog sadržaja povezane liste i ponovnogtracvraćajući se na izvorni čvor.

Sljedeći odjeljak objašnjava kako funkcionira umetanje i dvije moguće vrste umetanja u kružnoj jednostruko povezanoj listi.

Umetanje OperaANJE

Prvo stvarate jedan čvor čiji sljedeći pokazivač pokazuje natrag na sebe, kao što je prikazano dolje. Bez ovog početnog čvora, prvo umetanje postaje prvi čvor na popisu.

Dalje, postoje dvije mogućnosti:

• Umetanje na trenutnu poziciju kružno povezane liste. To odgovara umetanju na početak ili kraj regularne jednostruko povezane liste - u kružno povezanoj listi, početak i kraj su ista točka.
• Umetanje nakon indeksiranog čvora. Čvor treba identificirati brojem indeksa koji odgovara vrijednosti njegovog elementa.

Za umetanje na početak ili kraj kružne povezane liste - odnosno na poziciju gdje je dodan prvi čvor - slijedite korake u nastavku:

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

NAPOMENA: Pokazivač koji označava početak ili kraj kruga može se premjestiti na bilo koji čvor. Obilazak će se i dalje vratiti na isti čvor, kao što će biti objašnjeno kasnije u ovom članku.

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

(Postojeći čvor)

Korak 1) Prekini postojeću vezu

Korak 2) Stvorite vezu prema naprijed (od novog čvora do postojećeg čvora)

Korak 3) Napravite vezu petlje do prvog čvora

Zatim ćete pokušati umetanje nakon čvora.

Na primjer, umetnite „VALUE2“ nakon čvora koji sadrži „VALUE0“, pretpostavljajući da je početna točka čvor s „VALUE0“.

• Prekinite vezu između prvog i drugog čvora i postavite čvor s "VALUE2" između.
• Sljedeći pokazivač prvog čvora povezuje se s novim čvorom, a sljedeći pokazivač novog čvora povezuje se s onim što je prethodno bio drugi čvor.
• Ostatak rasporeda ostaje nepromijenjen. Svi čvorovi su ponovnotracdostupni sami sebi.

NAPOMENA: Budući da je raspored ciklički, postupak umetanja čvora je identičan bez obzira na odabranu poziciju. Pokazivač koji zatvara ciklus ponaša se kao i bilo koji drugi pokazivač na popisu.

Ovo 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 čvor s lijeve strane na novi čvor

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

brisanje OperaANJE

Pretpostavimo kružnu povezanu listu s 3 čvora. Dva slučaja brisanja su:

• Brisanje trenutnog elementa
• Brisanje nakon elementa.

Brisanje na početku/kraju:

1. Pređite do prvog čvora od posljednjeg čvora.
2. Brisanje od kraja zahtijeva samo jedan korak prolaska, od posljednjeg čvora do prvog čvora.
3. Izbriši vezu između zadnjeg i prvog čvora.
4. Povežite posljednji čvor sa sljedećim elementom prvog čvora.
5. Oslobodite prvi čvor.

(Postojeće postavke)

Korak 1) Uklonite kružnu vezu

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

Korak 3) Oslobodite / dealocirajte prvi čvor

Brisanje nakon čvora:

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

Korak 1) Recimo da trebamo izbrisati čvor s "VALUE1."

Korak 2) Uklonite vezu između prethodnog čvora i trenutnog čvora, a zatim povežite prethodni čvor izravno s čvorom na koji pokazuje sljedeći pokazivač trenutnog čvora (čvor nakon VALUE1).

Korak 3) Oslobodite ili poništite trenutni čvor.

Prolazak kružnog povezanog popisa

Za kretanje po kružnoj povezanoj listi od zadnjeg pokazivača, prvo provjerite je li zadnji pokazivač NULL. Ako nije NULL, provjerite ima li lista samo jedan element. U suprotnom, prođite kroz listu s privremenim pokazivačem dok ponovno ne dođete do zadnjeg pokazivača, kao što je prikazano u animaciji ispod.

Prednosti kružnog povezanog popisa

Neke od prednosti kružnih povezanih popisa su:

1. Nema zahtjeva za NULL dodjelu u kodu. Kružni popis nikada ne pokazuje na NULL pokazivač osim ako nije potpuno oslobođen.
2. Kružno povezane liste su povoljne za operacije na kraju liste jer se početak i kraj podudaraju. Algorithms kao što je kružno raspoređivanje, može se čisto kretati kroz procese u redu čekanja, bez nailaženja na viseće ili NULL pokazivače.
3. Kružna povezana lista i dalje podržava sve redovne operacije jednostruko povezane liste. Kružna dvostruko povezana lista može čak eliminirati potrebu za obilaženjem cijele liste kako bi se locirao element - u najgorem slučaju, cilj se nalazi nasuprot početnog pokazivača, tako da je potrebno proći najviše polovicu liste.

Nedostaci kružnog povezanog popisa

Nedostaci korištenja kružnog povezanog popisa su sljedeći:

1. Kružne liste su složenije od pojedinačno povezane liste.
2. RevObrtanje kružne liste je složenije od obrtanja jednostruko ili dvostruko povezane liste.
3. Ako se prekid petlje ne obradi pažljivo, kod za prolazak kroz petlju može ući u beskonačnu petlju.
4. Teže je pronaći kraj popisa i napisati ispravne uvjete upravljanja petljom.
5. Umetanje na početak zahtijeva prolazak kroz cijelu listu kako bi se došlo do posljednjeg čvora (iz perspektive implementacije).

Jednostruko povezani popis kao kružni povezani popis

Potičemo vas da pročitate i implementirate C kod u nastavku. On ilustrira aritmetiku pokazivača povezanu s kružnom jednostruko povezanom listom.

#include<stdio.h>
#include<stdlib.h>

struct 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 uključene datoteke zaglavlja.
2. Sljedeći odjeljak definira strukturu svakog samoreferencijalnog čvora. Sadrži vrijednost i pokazivač istog tipa kao i struktura.
3. Svaka instanca strukture povezuje se s drugim objektima strukture istog tipa.
4. Postoje različiti prototipovi funkcija za:
   1. Dodavanje elementa na prazan povezani popis
   2. Umetanje u trenutno upereno položaj kružne povezane liste.
   3. Umetanje iza određenog indeksirano vrijednost na povezanom popisu.
   4. Uklanjanje/brisanje nakon određenog indeksirano vrijednost na povezanom popisu.
   5. Uklanjanje na trenutno naznačenoj poziciji kružnog povezanog popisa
5. Posljednja funkcija ispisuje svaki element kroz kružni obilazak u bilo kojem stanju povezane liste.

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 kod addToEmpty, dodijelite prazan čvor pomoću funkcije malloc().
2. Postavite dolazne podatke u privremeni čvor.
3. Dodijelite privremeni čvor kao zadnji i postavite njegov sljedeći pokazivač na sebe tako da pojedinačni čvor pokazuje natrag na sebe.
4. Vrati zadnji pokazivač natrag u main() / 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 je lista prazna, prepustiti je funkciji addToEmpty() i vratiti kontrolu.
2. Napravite privremeni čvor koji će se postaviti nakon trenutnog čvora.
3. Povežite pokazivače kao što je prikazano na gornjem dijagramu.
4. Vrati zadnji pokazivač, koji odgovara uzorku korištenom 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 je popis prazan, zanemarite ključ za pretraživanje, dodajte trenutnu stavku kao jedini čvor na popisu i vratite kontrolu.
2. U svakoj iteraciji do-while petlje, prethodni pokazivač sadrži rezultat zadnjeg prolaska kroz koji je prošao.
3. Tek tada dolazi do sljedećeg koraka prelaska.
4. Izvedba "do-while" završava kada se pronađu ciljni podaci ili kada temp ponovno dosegne zadnji pokazivač. Sljedeći blok koda odlučuje što učiniti s pronađenom stavkom.

...
    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 cijeli popis pregledan, ali stavka nije pronađena, prikaži poruku „Element nije pronađen“ i vrati kontrolu pozivatelju.
2. Ako je ciljni čvor pronađen, dodijelite novi čvor za vrijednost koju želite umetnuti.
3. Veza prethodni čvor s novim čvorom i poveži sljedeći pokazivač novog čvora s temp (varijablom prolaska).
4. Ovim se novi element postavlja odmah nakon ciljnog čvora u kružnoj povezanoj listi. Kontrola se zatim vraća 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. Za uklanjanje posljednjeg (trenutnog) čvora, prvo provjerite je li popis prazan. Ako jest, nijedan element se ne može ukloniti.
2. Privremena varijabla pomiče jednu vezu naprijed.
3. Poveži zadnji pokazivač s čvorom nakon prvog čvora.
4. Oslobodite privremeni pokazivač kako biste dealocirali nepovezani čvor.

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, prvo provjerite je li popis prazan. Ako jest, nijedan element se ne može ukloniti.
2. Dva upućuje dodjeljuju se određeni položaji za lociranje elementa koji se briše.
3. Pokazivači se pomiču jedan za drugim (temperatura prethodnih staza).
4. Prolazak se nastavlja sve dok se ne pronađe ciljni element ili sljedeći pokazivač ponovno ne dosegne posljednji čvor.

    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 se prođe kroz cijelu povezanu listu bez pronalaska cilja, prikazuje se poruka „Element nije pronađen“.
2. U suprotnom, element se odvezuje i oslobađa u koracima 3 i 4.
3. Prethodni pokazivač je povezan s čvorom na koji pokazuje sljedeći pokazivač temp. (čvor nakon onog koji se briše).
4. Privremeni pokazivač se zatim oslobađa.

...
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. Pregledavanje nije moguće ako nema čvorova - korisnik prvo mora dodijeliti ili umetnuti čvor.
2. Ako postoji samo jedan čvor, nije potreban prolaz - sadržaj čvora se ispisuje izravno i while petlja se ne izvršava.
3. Ako postoji više od jednog čvora, temp ispisuje sve stavke do posljednjeg elementa.
4. U trenutku kada se dosegne posljednji element, petlja se završava i funkcija vraća kontrolu funkciji main().

Primjene Kružnog povezanog popisa

• Implementacija kružnog raspoređivanja u sistemskim procesima i kružnog raspoređivanja u grafici velike brzine.
• Raspoređivanje token-ringa u računalnim mrežama.
• Koristi se u prikaznim jedinicama kao što su digitalne oglasne ploče trgovina koje zahtijevaju kontinuirani prijenos podataka.

Pitanja i odgovori