Körkörös összekapcsolt lista: Előnyök a C program példájával

Mi az a kör alakú összekapcsolt lista?

A kör alakú összekapcsolt lista olyan csomópontok sorozata, amelyek úgy vannak elrendezve, hogy minden csomópont visszakereshető legyen önmagához. Itt egy "csomópont" egy önreferencia elem, amely egy vagy két csomópontra mutat az iI közvetlen közelében.

Az alábbiakban egy kör alakú, 3 csomópontot tartalmazó link ábrázolása látható.

Itt láthatja, hogy minden csomópont visszakereshető saját maga számára. A fenti példa kör alakú, egyenként összekapcsolt lista.

Megjegyzés: A legegyszerűbb körkörös összekapcsolt lista egy olyan csomópont, amely csak az ábrán látható módon követi önmagát

Ebben a körkörös linkelt oktatóanyagban megtudhatja:

• Mi az a kör alakú összekapcsolt lista?
• Alapműveletek
• Beszúrási művelet
• Törlés művelet
• Kör alakú összekapcsolt lista áthaladása
• A kör alakú összekapcsolt lista előnyei
• Egyszerűen összekapcsolt lista körláncolt listaként
• A kör alakú összekapcsolt lista alkalmazásai

Alapműveletek

Az összekapcsolt körlista alapműveletei a következők:

1. Beszúrás
2. Törlés és
3. Traversal

• A beillesztés az a folyamat, amikor egy csomópontot a kör alakú összekapcsolt lista meghatározott helyzetébe helyezünk.
• A törlés egy meglévő csomópont eltávolításának folyamata a csatolt listából. A csomópont azonosítható értékének előfordulása vagy pozíciója alapján.
• A kör alakú összekapcsolt lista áthaladása a csatolt lista teljes tartalmának megjelenítése és visszalépés a forrás csomópontig.

A következő szakaszban megismerheti a csomópont beillesztését és a beillesztés típusait egy kör alakú, egyenként összekapcsolt listában.

Beszúrási művelet

Először létre kell hoznia egy csomópontot, amely önmagára mutat, ahogy ez a kép látható. E csomópont nélkül a beillesztés hozza létre az első csomópontot.

Ezután két lehetőség van:

• Beillesztés a kör alakú linkelt lista aktuális helyzetébe. Ez megfelel a szabályos, egyesített, összekapcsolt lista végén lévő beszúrásnak. Körkörös összekapcsolt listában az eleje és a vége megegyezik.
• Beszúrás indexelt csomópont után. A csomópontot az elem értékének megfelelő indexszámmal kell azonosítani.

A körkörös összekapcsolt lista elejére / végére történő beszúráshoz, vagyis azon a helyen, ahol az első csomópontot hozzáadták,

• Meg kell szakítania a meglévő önlinket a meglévő csomóponthoz
• Az új csomópont következő mutatója a meglévő csomópontra fog kapcsolódni.
• Az utolsó csomópont következő mutatója a beillesztett csomópontra mutat.

MEGJEGYZÉS: A token master vagy a kör kezdete / vége mutató megváltoztatható. Még mindig ugyanarra a csomópontra fog visszatérni egy átjárás során, amelyet előre megbeszéltek.

Az a) i-iii lépéseit az alábbiakban mutatjuk be:

(Meglévő csomópont)

1. LÉPÉS: Törje meg a meglévő kapcsolatot

2. LÉPÉS: Hozzon létre egy továbbító linket (új csomópontból egy meglévő csomópontba)

3. LÉPÉS Hozzon létre egy hurok linket az első csomóponthoz

Ezután megpróbálja beilleszteni egy csomópont után.

Például illesszük be a "VALUE2" szót a "VALUE0" csomópont után. Tegyük fel, hogy a kiindulási pont a "VALUE0" csomópont.

• Meg kell szakítania az első és a második csomópont közötti vonalat, és a csomópontot "VALUE2" -vel kell elhelyezni.
• Az első csomópont következő mutatójának kapcsolódnia kell ehhez a csomóponthoz, és ennek a csomópont következő mutatójának a korábbi második csomóponthoz kell kapcsolódnia.
• Az elrendezés többi része változatlan marad. Minden csomópont visszakereshető önmaguk számára.

MEGJEGYZÉS: Mivel ciklikus elrendezés létezik, egy csomópont beillesztése ugyanolyan eljárást igényel bármely csomópont esetében. A ciklust befejező mutató ugyanúgy fejezi be a ciklust, mint bármely más csomópont.

Ez az alábbiakban látható:

(Tegyük fel, hogy csak két csomópont van. Ez triviális eset)

1. LÉPÉS: Távolítsa el a belső összeköttetést a csatlakoztatott csomópontok között

2. LÉPÉS Csatlakoztassa a bal oldali csomópontot az új csomóponthoz

3. LÉPÉS Csatlakoztassa az új csomópontot a jobb oldali csomóponthoz.

Törlés művelet

Tegyük fel, hogy egy 3 csomópontos körkörös összekapcsolt lista szerepel. A törlés eseteit az alábbiakban adjuk meg:

• Az aktuális elem törlése
• Törlés egy elem után.

Törlés az elején / végén:

1. Ugrás az első csomópontra az utolsó csomópontból.
2. A végtől való törléshez csak egy bejárási lépés lehet, az utolsó csomóponttól az első csomópontig.
3. Törölje az utolsó és a következő csomópont közötti kapcsolatot.
4. Csatlakoztassa az utolsó csomópontot az első csomópont következő eleméhez.
5. Szabadítsa meg az első csomópontot.

(Meglévő beállítás)

1. LÉPÉS: Távolítsa el a kör alakú kapcsolót

2. LÉPÉSEK: Távolítsa el az első és a következő közötti kapcsolatot, kapcsolja össze az utolsó csomópontot az elsőt követő csomópontra

3. LÉPÉS: Szabadítsa fel / ossza meg az első csomópontot

Törlés egy csomópont után:

1. A törlendő csomópont a következő csomópontig halad.
2. Ugrás a következő csomópontra, mutató elhelyezése az előző csomóponton.
3. Csatlakoztassa az előző csomópontot a jelenlegi csomópont utáni csomóponthoz, annak következő mutatójával.
4. Szabadítsa fel az aktuális (törölt) csomópontot.

1. LÉPÉS Tegyük fel, hogy törölnünk kell egy "VALUE1" csomópontot.

2. LÉPÉS: Távolítsa el a kapcsolatot az előző és az aktuális csomópont között. Csatlakoztassa előző csomópontját a következő csomópontra, amelyet az aktuális csomópont mutat (VALUE1-kel).

3. LÉPÉS) Szabadítsa fel vagy ossza meg az aktuális csomópontot.

Kör alakú összekapcsolt lista áthaladása

A kör alakú linkek listájának bejárásához az utolsó mutatótól kezdve ellenőrizze, hogy maga az utolsó mutató NULL-e. Ha ez a feltétel hamis, ellenőrizze, hogy csak egy elem van-e. Ellenkező esetben egy ideiglenes mutató használatával haladjon addig, amíg az utolsó mutatót el nem éri, vagy ahányszor szükséges, amint az az alábbi GIF-ben látható.

A kör alakú összekapcsolt lista előnyei

A körkörös összekapcsolt listák néhány előnye:

1. Nincs szükség NULL hozzárendelésre a kódban. A körlista soha nem mutat NULL mutatóra, hacsak nincs teljesen elosztva.
2. A körkörös összekapcsolt listák előnyösek a végműveletek számára, mivel a kezdet és a vég egybeesnek. Az olyan algoritmusok, mint a Round Robin ütemezése, szépen kiküszöbölhetik azokat a folyamatokat, amelyek körkörös sorban állnak, anélkül, hogy függő vagy NULL-referenciális mutatókkal találkoznának.
3. A körkörös összekapcsolt lista az egyenként összekapcsolt lista összes rendszeres funkcióját is ellátja. Valójában az alábbiakban tárgyalt, kör alakú, kétszeresen összekapcsolt listák akár ki is küszöbölik a teljes hosszúságú áthaladás szükségességét egy elem megtalálásához. Ez az elem legfeljebb csak pontosan ellentétes lenne a kezdéssel, és csak a felét fogja össze a linkelt lista.

Egyszerűen összekapcsolt lista kör alakú összekapcsolt listaként

Javasoljuk, hogy próbálja meg elolvasni és végrehajtani az alábbi kódot. Bemutatja a körkörös összekapcsolt listákhoz társított mutató számtant.

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

A kód magyarázata:

1. Az első két kódsor a szükséges fejlécfájlok.
2. A következő szakasz az egyes önreferencia csomópontok felépítését ismerteti. A szerkezettel azonos típusú értéket és mutatót tartalmaz.
3. Minden szerkezet többször is összekapcsolódik azonos típusú szerkezeti objektumokkal.
4. Különböző függvény prototípusok léteznek:
   1. Elem hozzáadása egy üres linkelt listához
   2. Beszúrás egy kör alakú linkelt lista éppen hegyes helyzetébe.
   3. Beszúrás egy adott indexelt érték után a linkelt listába.
   4. Eltávolítás / törlés egy adott indexelt érték után a csatolt listában.
   5. Eltávolítás a kör alakú linkelt lista jelenleg hegyes helyzetéből
5. Az utolsó függvény minden elemet körkörös áthaladással nyomtat ki a csatolt lista bármely állapotában.

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)

A kód magyarázata:

1. Az addEmpty kódhoz rendeljen egy üres csomópontot a malloc függvény segítségével.
2. Ehhez a csomóponthoz helyezze az adatokat a temp változóba.
3. Rendelje hozzá és kapcsolja össze az egyetlen változót a temp változóval
4. Az utolsó elemet adja vissza a main () / alkalmazás környezetbe.

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;… 

A kód magyarázata

1. Ha nincs beillesztendő elem, akkor feltétlenül vegye fel az üres listára, és adja vissza a vezérlőt.
2. Hozzon létre egy ideiglenes elemet az aktuális elem után.
3. Kapcsolja össze a mutatókat az ábra szerint.
4. Adja vissza az utolsó mutatót, mint az előző függvényben.

… 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");… 

A kód magyarázata:

1. Ha nincs elem a listán, hagyja figyelmen kívül az adatokat, adja hozzá az aktuális elemet a lista utolsó eleméhez, és adja vissza a vezérlőt
2. A do-while ciklus minden iterációjához győződjön meg arról, hogy van egy előző mutató, amely az utoljára bejárt eredményt tartja.
3. Csak ezután következhet be a következő bejárás.
4. Ha az adatok megtalálhatók, vagy a hőmérséklet visszatér az utolsó mutatóra, a do-while befejeződik. A következő kódrész eldönti, hogy mit kell tennie az elemmel.

… 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)… 

A kód magyarázata:

1. Ha a teljes listát bejárta, de az elem még nem található, jelenítsen meg egy "elem nem található" üzenetet, majd adja vissza a vezérlést a hívónak.
2. Ha talált egy csomópontot, és / vagy a csomópont még nem az utolsó csomópont, akkor hozzon létre egy új csomópontot.
3. Csatlakoztassa az előző csomópontot az új csomóponthoz. Csatlakoztassa az aktuális csomópontot a temp-hoz (a bejárási változóhoz).
4. Ez biztosítja, hogy az elem egy adott csomópont után kerüljön a körkörös linkelt listába. Térjen vissza a hívóhoz.

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)

A kód magyarázata

1. Csak az utolsó (aktuális) csomópont eltávolításához ellenőrizze, hogy ez a lista üres-e. Ha igen, akkor egyetlen elem sem távolítható el.
2. A temp változó csak egy linket halad előre.
3. Kapcsolja össze az utolsó mutatót az első utáni mutatóval.
4. Szabadítsa fel a hőmérséklet mutatót. Elosztja az összekapcsolatlan utolsó mutatót.

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");… 

A kód magyarázata

1. Az előző eltávolítási funkcióhoz hasonlóan ellenőrizze, hogy nincs-e elem. Ha ez igaz, akkor egyetlen elem sem távolítható el.
2. Mutatókhoz speciális pozíciók vannak rendelve a törlendő elem megkereséséhez.
3. A mutatók haladnak, egymás mögött. (előző a hőmérséklet mögött)
4. A folyamat addig folytatódik, amíg egy elemet meg nem találnak, vagy a következő elem vissza nem tér az utolsó mutatóra.

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;

A program magyarázata

1. Ha az elem a teljes összekapcsolt lista bejárása után található, hibaüzenet jelenik meg, amely szerint az elem nem található.
2. Ellenkező esetben az elem törlődik és felszabadul a 3. és 4. lépésben.
3. Az előző mutató kapcsolódik a címhez, amelyet a törölni kívánt elem ("temp") "következőnek" jelöl.
4. A hőmérsékletmutatót ezért felosztják és felszabadítják.

… 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;}}

A kód magyarázata

1. A kukucskálás vagy bejárás nem lehetséges, ha nulla szükséges. A felhasználónak el kell rendelnie vagy be kell helyeznie egy csomópontot.
2. Ha csak egy csomópont van, akkor nincs szükség áthaladásra, a csomópont tartalma kinyomtatható, és a while ciklus nem hajt végre.
3. Ha egynél több csomópont van, akkor a temp kinyomtatja az összes elemet az utolsó elemig.
4. Abban a pillanatban, amikor az utolsó elem eléri, a hurok befejeződik, és a függvény visszatér a híváshoz a fő funkcióhoz.

A kör alakú összekapcsolt lista alkalmazásai

• Körméretes ütemezés megvalósítása a rendszerfolyamatokban és körkörös ütemezés megvalósítása nagy sebességű grafikában.
• Token cseng az ütemezés számítógépes hálózatokban.
• Olyan megjelenítő egységekben használják, mint a bolti táblák, amelyek folyamatos adatátvitelt igényelnek.