Що таке круговий зв’язаний список?
Круговий зв’язаний список - це послідовність вузлів, розташованих таким чином, що кожен вузол може бути відведений до себе. Тут "вузол" - це самореференційний елемент із вказівниками на один або два вузли в безпосередній близькості iI.
Нижче наведено круговий зв’язаний список із 3 вузлами.
Тут ви можете бачити, що кожен вузол можна простежити до себе. Наведений вище приклад являє собою круговий односвязний список.
Примітка: Найпростішим круговим пов'язаним списком є вузол, який простежує лише себе, як показано
У цьому посібнику з круговим зв’язаним списком ви дізнаєтесь:
- Що таке круговий зв’язаний список?
- Основні операції
- Операція вставки
- Операція видалення
- Обхід кругового пов'язаного списку
- Переваги кругового пов'язаного списку
- Однозв’язаний список як круговий зв’язаний список
- Застосування списку кругових зв’язків
Основні операції
Основними операціями у списку з круговим зв’язком є:
- Вставка
- Видалення та
- Обхід
- Вставка - це процес розміщення вузла у визначеному положенні у списку кругових зв’язків.
- Видалення - це процес видалення існуючого вузла зі зв’язаного списку. Вузол можна ідентифікувати за входженням його значення або за його положенням.
- Обхід кругового пов’язаного списку - це процес відображення всього вмісту пов’язаного списку та повернення назад до вихідного вузла.
У наступному розділі ви зрозумієте вставку вузла та типи вставки, доступні в круговому списку з єдиним зв’язком.
Операція вставки
Спочатку вам потрібно створити один вузол, який вказує на себе, як показано на цьому зображенні. Без цього вузла вставка створює перший вузол.
Далі є дві можливості:
- Вставка в поточній позиції кругового пов'язаного списку. Це відповідає вставці на початку кінця регулярного єдиного пов'язаного списку. У круговому зв’язаному списку початок і кінець однакові.
- Вставка після індексованого вузла. Вузол повинен ідентифікуватися номером індексу, що відповідає значенню його елемента.
Для вставки на початку / в кінці кругового пов'язаного списку, тобто в позиції, де був доданий перший у світі вузол,
- Вам доведеться розірвати існуюче самозв’язок із існуючим вузлом
- Наступний вказівник нового вузла буде посилатися на існуючий вузол.
- Наступний вказівник останнього вузла буде вказувати на вставлений вузол.
ПРИМІТКА: Вказівник, який є головним маркером або початком / кінцем кола, можна змінити. Він все одно повернеться до того самого вузла в обхід, про який вже йшлося раніше.
Етапи в (a) i-iii показані нижче:
(Існуючий вузол)
КРОК 1) Поруште існуюче посилання
КРОК 2) Створіть пряме посилання (з нового вузла на існуючий вузол)
КРОК 3) Створіть циклічне посилання на перший вузол
Далі ви спробуєте вставити після вузла.
Наприклад, давайте вставимо "VALUE2" після вузла з "VALUE0". Припустимо, що початковою точкою є вузол із "VALUE0".
- Вам доведеться розірвати лінію між першим і другим вузлом і помістити вузол із "VALUE2" між ними.
- Наступний вказівник першого вузла повинен посилатися на цей вузол, а наступний вказівник цього вузла - на попередній другий вузол.
- Решта домовленості залишається незмінною. Всі вузли є відступними для себе.
ПРИМІТКА. Оскільки існує циклічне розташування, вставлення вузла передбачає однакову процедуру для будь-якого вузла. Покажчик, який завершує цикл, завершує цикл, як і будь-який інший вузол.
Це показано нижче:
(Скажімо, є лише два вузли. Це тривіальний випадок)
КРОК 1) Видаліть внутрішній зв'язок між підключеними вузлами
КРОК 2) Підключіть лівий бічний вузол до нового вузла
КРОК 3) Підключіть новий вузол до правого бокового вузла.
Операція видалення
Припустимо, що це круговий зв’язаний список із 3 вузлами. Випадки видалення наведені нижче:
- Видалення поточного елемента
- Видалення після елемента.
Видалення на початку / в кінці:
- Перехід до першого вузла від останнього вузла.
- Щоб видалити з кінця, повинен бути лише один крок обходу, від останнього вузла до першого вузла.
- Видаліть зв’язок між останнім вузлом та наступним вузлом.
- Пов’язати останній вузол із наступним елементом першого вузла.
- Звільніть перший вузол.
(Існуюче налаштування)
КРОК 1 ) Зніміть кругову ланку
КРОКИ 2) Видаліть зв’язок між першим і наступним, зв’яжіть останній вузол з вузлом, що слідує за першим
КРОК 3) Звільнити / звільнити перший вузол
Видалення після вузла:
- Перехід до наступного вузла є вузлом, який потрібно видалити.
- Перехід до наступного вузла, розміщення вказівника на попередньому вузлі.
- Підключіть попередній вузол до вузла після поточного вузла, використовуючи його наступний вказівник.
- Звільніть поточний (розмежований) вузол.
КРОК 1) Скажімо, що нам потрібно видалити вузол із "VALUE1".
КРОК 2) Видаліть зв’язок між попереднім вузлом і поточним вузлом. Пов’яжіть його попередній вузол із наступним вузлом, на який вказує поточний вузол (з VALUE1).
КРОК 3) Звільніть або звільніть поточний вузол.
Обхід кругового пов'язаного списку
Щоб пройти круговий зв’язаний список, починаючи з останнього вказівника, перевірте, чи не є останній вказівник NULL. Якщо ця умова хибна, перевірте, чи є лише один елемент. В іншому випадку виконайте обхід за допомогою тимчасового вказівника, доки останній вказівник не буде знову досягнутий, або стільки разів, скільки потрібно, як показано в GIF нижче.
Переваги кругового пов'язаного списку
Деякі з переваг кругових пов'язаних списків:
- У коді немає вимоги для присвоєння NULL. Циркулярний список ніколи не вказує на покажчик NULL, якщо він повністю не звільнений.
- Кругові зв’язані списки вигідні для кінцевих операцій, оскільки початок та кінець збігаються. Такі алгоритми, як планування кругового Робіна, можуть акуратно усунути процеси, які розміщуються в черзі круговим способом, не стикаючись із звисаючими або 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.
- Для цього вузла розмістіть дані у змінній temp.
- Призначте та прив’яжіть єдину змінну до тимчасової змінної
- Поверніть останній елемент до контексту 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 друкує весь елемент до останнього елемента.
- У момент, коли досягається останній елемент, цикл завершується, і функція повертає виклик до основної функції.
Застосування списку кругових зв’язків
- Впровадження кругового планування в системні процеси та кругове планування у високошвидкісній графіці.
- Планування токен-кілець у комп’ютерних мережах.
- Він використовується в дисплеях, таких як дошки магазинів, які вимагають постійного обходу даних.