Кръгов свързан списък: предимства и недостатъци

Какво е кръгов свързан списък?

Кръгов свързан списък е поредица от възли, подредени така, че всеки възел може да бъде преобразуван.tracсам по себе си. Всеки „възел“ е самореферентен елемент с указатели към един или два възела в непосредствена близост до него.

По-долу е изображение на кръгъл свързан списък с 3 възела.

Тук можете да видите, че всеки възел е преобразуванtracможе да се използва сам по себе си. Показаният по-горе пример е кръгов еднократно свързан списък.

Забележка: Най-простият кръгов свързан списък е единичен възел, чийто следващ указател tracсе връща обратно към себе си, както е показано по-долу.

Basic Operaции в кръгови свързани списъци

Трите основни операции върху кръгов свързан списък са:

1. вмъкване
2. Изтриване и
3. Обход

• Вмъкването е процес на поставяне на възел на определена позиция в кръговия свързан списък.
• Изтриването е процес на премахване на съществуващ възел от свързания списък. Възелът може да бъде идентифициран чрез появата на неговата стойност или чрез неговата позиция.
• Обхождането на кръгов свързан списък е процесът на показване на цялото съдържание на свързания списък и реtracобратно към изходния възел.

Следващият раздел обяснява как работи вмъкването и двата възможни вида вмъкване в кръгов едносвързан списък.

вмъкване OperaАЦИ

Първо създавате един възел, чийто следващ указател сочи обратно към себе си, както е показано по-долу. Без този начален възел, първото вмъкване става първият възел в списъка.

След това има две възможности:

• Вмъкване в текущата позиция на кръговия свързан списък. Това съответства на вмъкване в началото или края на обикновен еднократно свързан списък — в кръгов свързан списък началото и краят са една и съща точка.
• Вмъкване след индексиран възел. Възелът трябва да бъде идентифициран чрез номер на индекс, съответстващ на стойността на неговия елемент.

За да вмъкнете в началото или края на кръговия свързан списък — тоест на позицията, където е добавен първият възел — следвайте стъпките по-долу:

• Ще трябва да прекъснете съществуващата самовръзка към съществуващия възел
• Следващият указател на новия възел ще се свърже към съществуващия възел.
• Следващият указател на последния възел ще сочи към вмъкнатия възел.

ЗАБЕЛЕЖКА: Показалецът, който маркира началото или края на окръжността, може да бъде преназначен на всеки възел. Обходът все пак ще се върне към същия възел, както е обсъдено по-късно в тази статия.

Стъпките в (a) i-iii са показани по-долу:

(Съществуващ възел)

Стъпка 1) Прекъснете съществуващата връзка

Стъпка 2) Създайте препращаща връзка (от нов възел към съществуващ възел)

Стъпка 3) Създайте връзка към първия възел

След това ще опитате вмъкване след възел.

Например, вмъкнете „VALUE2“ след възела, съдържащ „VALUE0“, като приемем, че началната точка е възелът с „VALUE0“.

• Прекъснете връзката между първия и втория възел и поставете възела с „VALUE2“ между тях.
• Следващият указател на първия възел се свързва с новия възел, а следващият указател на новия възел се свързва с това, което преди това е било вторият възел.
• Останалата част от подредбата остава непроменена. Всички възли са пренаредениtracдостъпни за себе си.

ЗАБЕЛЕЖКА: Тъй като подредбата е циклична, процедурата за вмъкване на възел е идентична, независимо коя позиция изберете. Показалецът, който затваря цикъла, се държи като всеки друг показалец в списъка.

Това е показано по-долу:

(Да кажем, че има само два възела. Това е тривиален случай)

Стъпка 1) Премахнете вътрешната връзка между свързаните възли

Стъпка 2) Свържете възела от лявата страна към новия възел

Стъпка 3) Свържете новия възел към възела от дясната страна.

заличаване OperaАЦИ

Да приемем кръгов свързан списък с 3 възела. Двата случая на изтриване са:

• Изтриване на текущия елемент
• Изтриване след елемент.

Изтриване в началото/края:

1. Преминете към първия възел от последния възел.
2. Изтриването от края изисква само една стъпка на преминаване, от последния възел до първия възел.
3. Изтрийте връзката между последния възел и първия възел.
4. Свържете последния възел със следващия елемент на първия възел.
5. Освободете първия възел.

(Съществуваща настройка)

Стъпка 1) Премахнете кръговата връзка

Стъпка 2) Премахнете връзката между първия и следващия, свържете последния възел към възела, следващ първия

Стъпка 3) Освободете / деразпределете първия възел

Изтриване след възел:

1. Преминете, докато следващият възел е възелът, който ще бъде изтрит.
2. Преминете към следващия възел, като поставите показалец върху предишния възел.
3. Свържете предишния възел с възела след настоящия възел, като използвате неговия следващ указател.
4. Освободете текущия (прекъснат) възел.

Стъпка 1) Да кажем, че трябва да изтрием възел с „VALUE1“.

Стъпка 2) Премахнете връзката между предишния възел и текущия възел, след което свържете предишния възел директно с възела, към който сочи следващият указател на текущия възел (възелът след VALUE1).

Стъпка 3) Освободете или освободите текущия възел.

Обхождане на кръгъл свързан списък

За да обходите кръгов свързан списък от последен указател, първо проверете дали последният указател е NULL. Ако не е NULL, проверете дали списъкът има само един елемент. В противен случай, обходете списъка с временен указател, докато стигнете отново до последния указател, както е показано в анимацията по-долу.

Предимства на кръговия свързан списък

Някои от предимствата на кръговите свързани списъци са:

1. Няма изискване за присвояване NULL в кода. Кръговият списък никога не сочи към NULL указател, освен ако не е напълно освободен.
2. Кръговите свързани списъци са предимство за операции в края на списъка, защото началото и краят съвпадат. Algorithms като например кръговото планиране, може да се движи през опашките от процеси чисто, без да се натъква на висящи или NULL указатели.
3. Кръгъл свързан списък все още поддържа всички обичайни операции на еднократно свързан списък. Кръгъл двойносвързан списък може дори да елиминира необходимостта от пълно обхождане на списъка, за да се намери елемент — в най-лошия случай целта се намира срещу началния указател, така че най-много половината от списъка трябва да се обходи.

Недостатъци на кръговия свързан списък

Недостатъците при използването на кръгъл свързан списък са по-долу:

1. Кръговите списъци са по-сложни от единично свързани списъци.
2. RevОбръщането на кръгов списък е по-сложно от обръщането на еднократно или двойно свързан списък.
3. Ако прекратяването на цикъла не се обработва внимателно, кодът за преминаване може да влезе в безкраен цикъл.
4. По-трудно е да се намери краят на списъка и да се напишат правилни условия за управление на цикъла.
5. Вмъкването в началото изисква преминаване през целия списък, за да се достигне последният възел (от гледна точка на имплементацията).

Единично свързан списък като кръгов свързан списък

Препоръчително е да прочетете и имплементирате C кода по-долу. Той илюстрира аритметиката на указателите, свързана с кръгов едносвързан списък.

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

Обяснение на кода:

1. Първите два реда код са необходимите включени заглавни файлове.
2. Следващият раздел дефинира структурата на всеки самореферентен възел. Той съдържа стойност и указател от същия тип като структурата.
3. Всеки структурен екземпляр е свързан с други структурни обекти от същия тип.
4. Има различни прототипи на функции за:
   1. Добавяне на елемент към празен свързан списък
   2. Вмъкване при в момента посочи позиция на кръгъл свързан списък.
   3. Вмъкване след определено индексирани стойност в свързания списък.
   4. Премахване/Изтриване след определено индексирани стойност в свързания списък.
   5. Премахване на текущо посочената позиция на кръгъл свързан списък
5. Последната функция отпечатва всеки елемент чрез кръгово обхождане във всяко състояние на свързания списък.

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)

Обяснение на кода:

1. За кода addToEmpty, разпределете празен възел, използвайки функцията malloc().
2. Поставете входящите данни във временния възел.
3. Присвойте временния възел на последен и задайте следващия му указател към себе си, така че единичният възел да сочи обратно към себе си.
4. Връща последния указател обратно към контекста на main() / приложението.

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

Обяснение на кода

1. Ако списъкът е празен, прехвърлете управлението на addToEmpty().
2. Създайте временен възел, който да поставите след текущия възел.
3. Свържете показалците, както е показано на диаграмата по-горе.
4. Връща последния указател, съответстващ на шаблона, използван в предишната функция.

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

Обяснение на кода:

1. Ако списъкът е празен, игнорирайте ключа за търсене, добавете текущия елемент като единствен възел в списъка и върнете контрола.
2. Във всяка итерация на цикъла do-while, предишен указател съдържа последния обходен резултат.
3. Едва тогава се извършва следващата стъпка на преминаване.
4. Изпълнението do-while се прекратява, когато целевите данни бъдат намерени или когато temp достигне последния указател отново. Следният блок код решава какво да се направи с намерения елемент.

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

Обяснение на кода:

1. Ако целият списък е прегледан, но елементът не е намерен, се показва съобщение „Елементът не е намерен“ и контролът се връща на извикващата функция.
2. Ако целевият възел е намерен, разпределете нов възел за стойността, която ще бъде вмъкната.
3. връзка предишния възел към новия възел и свързва следващия указател на новия възел с temp (променливата за преминаване).
4. Това поставя новия елемент веднага след целевия възел в кръговия свързан списък. След това контролът се връща към извикващата функция.

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)

Обяснение на кода

1. За да премахнете последния (текущ) възел, първо проверете дали списъкът е празен. Ако е така, не може да се премахне нито един елемент.
2. Временната променлива премества една връзка напред.
3. Свържете последния указател с възела след първия възел.
4. Освободете временния указател, за да освободите несвързания възел.

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

Обяснение на кода

1. Както при предишната функция за премахване, първо проверете дали списъкът е празен. Ако е, не може да се премахне нито един елемент.
2. две указатели са присвоени конкретни позиции за намиране на елемента за изтриване.
3. Показалки се придвижват една след друга (темп. на предишните пътеки).
4. Обходът продължава, докато целевият елемент не бъде намерен или следващият указател не достигне отново последния възел.

    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;

Обяснение на програмата

1. Ако целият свързан списък бъде обходен, без да се намери целта, се показва съобщение „Елементът не е намерен“.
2. В противен случай елементът се откачва и се освобождава в стъпки 3 и 4.
3. Предишният указател е свързан с възела, към който сочи следващият указател на temp (възелът след този, който се изтрива).
4. След това временният показалец се освобождава.

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

Обяснение на кода

1. Прегледът на елементите не е възможен, ако няма никакви възли — потребителят първо трябва да разпредели или вмъкне възел.
2. Ако има само един възел, не се изисква обхождане — съдържанието на възела се отпечатва директно и цикълът while не се изпълнява.
3. Ако има повече от един възел, temp отпечатва всеки елемент до последния.
4. В момента, в който се достигне последният елемент, цикълът се прекратява и функцията връща управлението на main().

Приложения на кръговия свързан списък

• Внедряване на кръгово планиране в системни процеси и кръгово планиране във високоскоростна графика.
• Планиране по метода Token-Ring в компютърни мрежи.
• Използва се в дисплейни устройства, като например дигитални табла за магазини, които изискват непрекъснато преминаване през данни.

Въпроси и Отговори