Какво представлява списък с кръгови връзки?
Кръгово свързан списък е последователност от възли, подредени по такъв начин, че всеки възел може да бъде прибран към себе си. Тук "възел" е самореферентен елемент с указатели към един или два възела в непосредствена близост до iI.
По-долу е изобразен кръгово свързан списък с 3 възли.
Тук можете да видите, че всеки възел е проследим към себе си. Примерът, показан по-горе, е кръгов единично свързан списък.
Забележка: Най-простият кръгово свързан списък е възел, който проследява само себе си, както е показано
В този урок за кръгъл свързан списък ще научите:
- Какво представлява списък с кръгови връзки?
- Основни операции
- Операция за вмъкване
- Операция по изтриване
- Обхождане на кръгово свързан списък
- Предимства на циркулярно свързан списък
- Единично свързан списък като кръгово свързан списък
- Приложения на списъка с кръгови връзки
Основни операции
Основните операции в кръгово свързан списък са:
- Вмъкване
- Изтриване и
- Обхождане
- Вмъкването е процес на поставяне на възел на определена позиция в списъка с кръгови връзки.
- Изтриването е процес на премахване на съществуващ възел от свързания списък. Възелът може да бъде идентифициран чрез появата на неговата стойност или от позицията му.
- Обхождането на кръгъл свързан списък е процес на показване на цялото съдържание на свързания списък и връщане обратно към изходния възел.
В следващия раздел ще разберете вмъкването на възел и видовете вмъкване в кръгов единично свързан списък.
Операция за вмъкване
Първоначално трябва да създадете един възел, който да сочи към себе си, както е показано на това изображение. Без този възел, вмъкването създава първия възел.
След това има две възможности:
- Вмъкване в текущата позиция на списъка с кръгови връзки. Това съответства на вмъкването в началото на края на редовен единствено свързан списък. В кръгово свързан списък началото и краят са еднакви.
- Вмъкване след индексиран възел. Възелът трябва да бъде идентифициран с номер на индекс, съответстващ на стойността на елемента.
За вмъкване в началото / края на кръговия свързан списък, който е на мястото, където е добавен първият възел,
- Ще трябва да прекъснете съществуващата самовръзка към съществуващия възел
- Следващият указател на новия възел ще се свърже със съществуващия възел.
- Следващият указател на последния възел ще сочи към вмъкнатия възел.
ЗАБЕЛЕЖКА: Указателят, който е главният маркер или началото / края на кръга, може да бъде променен. Той все пак ще се върне към същия възел при обхождане, обсъдено напред.
Стъпките в (а) i-iii са показани по-долу:
(Съществуващ възел)
СТЪПКА 1) Прекъснете съществуващата връзка
СТЪПКА 2) Създайте препращаща връзка (от нов възел към съществуващ възел)
СТЪПКА 3) Създайте връзка към първия възел
След това ще опитате да вмъкнете след възел.
Например, нека въведем „VALUE2“ след възела с „VALUE0“. Нека приемем, че началната точка е възелът с "VALUE0".
- Ще трябва да прекъснете линията между първия и втория възел и да поставите възела с "VALUE2" между тях.
- Следващият указател на първия възел трябва да се свързва с този възел, а следващият указател на този възел трябва да се свързва с по-ранния втори възел.
- Останалата част от споразумението остава непроменена. Всички възли са проследими към себе си.
ЗАБЕЛЕЖКА: Тъй като има циклично подреждане, вмъкването на възел включва същата процедура за всеки възел. Указателят, който завършва цикъл, завършва цикъла точно както всеки друг възел.
Това е показано по-долу:
(Да кажем, че има само два възела. Това е тривиален случай)
СТЪПКА 1) Премахнете вътрешната връзка между свързаните възли
СТЪПКА 2) Свържете левия възел към новия възел
СТЪПКА 3) Свържете новия възел към дясната страна.
Операция по изтриване
Нека приемем 3-възелен кръгово свързан списък. Случаите за изтриване са дадени по-долу:
- Изтриване на текущия елемент
- Изтриване след елемент.
Изтриване в началото / края:
- Преминаване към първия възел от последния възел.
- За да изтриете от края, трябва да има само една стъпка на обръщане, от последния възел до първия възел.
- Изтрийте връзката между последния възел и следващия възел.
- Свържете последния възел със следващия елемент на първия възел.
- Освободете първия възел.
(Съществуваща настройка)
СТЪПКА 1 ) Премахнете кръговата връзка
СТЪПКИ 2) Премахнете връзката между първия и следващия, свържете последния възел с възела, следващ първия
СТЪПКА 3) Освободете / освободете първия възел
Изтриване след възел:
- Преминаване до следващия възел е възелът, който трябва да бъде изтрит.
- Преминаване към следващия възел, поставяне на указател върху предишния възел.
- Свържете предишния възел с възела след настоящия възел, като използвате следващия му указател.
- Освободете текущия (развързан) възел.
СТЪПКА 1) Да кажем, че трябва да изтрием възел с „СТОЙНОСТ1“.
СТЪПКА 2) Премахнете връзката между предишния възел и текущия възел. Свържете предишния му възел със следващия възел, посочен от текущия възел (с VALUE1).
СТЪПКА 3) Освободете или освободете текущия възел.
Обхождане на кръгово свързан списък
За да прекосите кръгово свързан списък, започвайки от последния указател, проверете дали самият последен указател е NULL. Ако това условие е невярно, проверете дали има само един елемент. В противен случай преминете с помощта на временен указател, докато последният показалец бъде достигнат отново или толкова пъти, колкото е необходимо, както е показано в GIF по-долу.
Предимства на циркулярно свързан списък
Някои от предимствата на циркулярно свързани списъци са:
- Няма изискване за присвояване на NULL в кода. Циркулярният списък никога не сочи към NULL указател, освен ако не се освободи напълно.
- Циркулярно свързани списъци са изгодни за крайните операции, тъй като началото и краят съвпадат. Алгоритми като планирането на Round Robin могат добре да елиминират процеси, които се поставят в опашка по кръг, без да се натъкват на висящи или NULL-референтни указатели.
- Циркулярно свързан списък изпълнява и всички редовни функции на единично свързан списък. Всъщност обсъдените по-долу кръгови двойно свързани списъци дори могат да премахнат необходимостта от обхождане в цял ръст, за да се намери елемент. Този елемент би бил най-много точно противоположен на началото, попълвайки само половината от свързания списък.
Единично свързан списък като кръгово свързан списък
Препоръчваме ви да се опитате да прочетете и приложите кода по-долу. Той представя аритметиката на указателя, свързана с кръгови свързани списъци.
#include#include 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(){…
Обяснение на кода:
- Първите два реда код са необходимите включени заглавни файлове.
- Следващият раздел описва структурата на всеки самореферентен възел. Той съдържа стойност и указател от същия тип като структурата.
- Всяка структура многократно се свързва със структурни обекти от същия тип.
- Има различни прототипи на функции за:
- Добавяне на елемент към празен свързан списък
- Вмъкване в посочената в момента позиция на кръгово свързан списък.
- Вмъкване след определена индексирана стойност в свързания списък.
- Премахване / изтриване след определена индексирана стойност в свързания списък.
- Премахване в посочената в момента позиция на кръгово свързан списък
- Последната функция отпечатва всеки елемент чрез кръгово обхождане при всяко състояние на свързания списък.
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)
Обяснение на кода:
- За кода addEmpty разпределете празен възел с помощта на функцията malloc.
- За този възел поставете данните във временната променлива.
- Задайте и свържете единствената променлива с временната променлива
- Върнете последния елемент в контекста main () / application.
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;…
Обяснение на кода
- Ако няма елемент за вмъкване, трябва да добавите към празен списък и да върнете контрола.
- Създайте временен елемент, който да поставите след текущия елемент.
- Свържете указателите, както е показано.
- Върнете последния указател, както в предишната функция.
… 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");…
Обяснение на кода:
- Ако в списъка няма елемент, игнорирайте данните, добавете текущия елемент като последен елемент в списъка и върнете контрола
- За всяка итерация в 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)…
Обяснение на кода:
- Ако целият списък е преминал, но елементът не е намерен, покажете съобщение „елемент не е намерен“ и след това върнете контрола на повикващия.
- Ако има намерен възел и / или възелът все още не е последният възел, създайте нов възел.
- Свържете предишния възел с новия възел. Свържете текущия възел с temp (променлива на обхода).
- Това гарантира, че елементът се поставя след определен възел в списъка с кръгови връзки. Върнете се при повикващия.
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)
Обяснение на кода
- За да премахнете само последния (текущ) възел, проверете дали този списък е празен. Ако е така, тогава нито един елемент не може да бъде премахнат.
- Променливата temp просто пресича една връзка напред.
- Свържете последния указател с показалеца след първия.
- Освободете временния указател. Той освобождава несвързания последен указател.
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");…
Обяснение на кода
- Както при предишната функция за премахване, проверете дали няма елемент. Ако това е вярно, тогава нито един елемент не може да бъде премахнат.
- На указателите се присвояват специфични позиции за намиране на елемента, който ще се изтрива.
- Указателите са напреднали, един зад друг. (пред зад темп)
- Процесът продължава, докато не бъде намерен елемент или следващият елемент се прибере към последния указател.
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;
Обяснение на програмата
- Ако елементът е намерен след обхождането на целия свързан списък, се показва съобщение за грешка, което казва, че елементът не е намерен.
- В противен случай елементът се разграничава и освобождава в стъпки 3 и 4.
- Предишният указател е свързан с адреса, посочен като "следващ" от елемента, който трябва да бъде изтрит (temp).
- Следователно указателят за темп се освобождава и освобождава.
… 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;}}
Обяснение на кода
- Надникването или обръщането не е възможно, ако са нули. Потребителят трябва да разпредели или вмъкне възел.
- Ако има само един възел, няма нужда да се обхожда, съдържанието на възела може да бъде отпечатано и цикълът while не се изпълнява.
- Ако има повече от един възел, тогава temp отпечатва целия елемент до последния елемент.
- В момента, в който е достигнат последният елемент, цикълът се прекратява и функцията връща повикване към основната функция.
Приложения на списъка с кръгови връзки
- Внедряване на кръгово планиране в системни процеси и кръгово планиране във високоскоростни графики.
- Планиране на пръстени на токени в компютърни мрежи.
- Използва се в дисплейни единици като табла, които изискват непрекъснато обхождане на данни.