Циркулярный связанный список: преимущества примера программы C

Содержание:

Anonim

Что такое круговой связанный список?

Циклический связанный список - это последовательность узлов, организованная таким образом, что каждый узел может быть восстановлен до самого себя. Здесь «узел» - это самореферентный элемент с указателями на один или два узла в непосредственной близости от iI.

Ниже представлен круговой связанный список с 3 узлами.

Здесь вы можете видеть, что каждый узел восходит к самому себе. Показанный выше пример представляет собой круговой односвязный список.

Примечание. Самый простой круговой связанный список - это узел, который отслеживает только себя, как показано.

В этом уроке с круговыми связными списками вы узнаете:

  • Что такое круговой связанный список?
  • Основные операции
  • Операция вставки
  • Операция удаления
  • Обход кругового связного списка
  • Преимущества циркулярного связного списка
  • Односвязный список как круговой связанный список
  • Приложения Циркулярного связного списка

Основные операции

Основные операции с круговым связным списком:

  1. Вставка
  2. Удаление и
  3. Обход
  • Вставка - это процесс помещения узла в указанную позицию в круговом связном списке.
  • Удаление - это процесс удаления существующего узла из связанного списка. Узел можно идентифицировать по появлению его значения или по его положению.
  • Обход кругового связанного списка - это процесс отображения всего содержимого связанного списка и возврата к исходному узлу.

В следующем разделе вы поймете, как вставить узел и какие типы вставки возможны в кольцевом односвязном списке.

Операция вставки

Первоначально вам нужно создать один узел, который указывает на себя, как показано на этом изображении. Без этого узла при вставке создается первый узел.

Далее есть две возможности:

  • Вставка в текущую позицию кругового связного списка. Это соответствует вставке в начало конца обычного единственного связного списка. В круговом связном списке начало и конец совпадают.
  • Вставка после индексированного узла. Узел должен быть идентифицирован номером индекса, соответствующим значению его элемента.

Для вставки в начало / конец кругового связанного списка, то есть в позицию, где был добавлен первый узел,

  • Вам нужно будет разорвать существующую ссылку на существующий узел.
  • Следующий указатель нового узла будет ссылаться на существующий узел.
  • Следующий указатель последнего узла будет указывать на вставленный узел.

ПРИМЕЧАНИЕ. Указатель, который является мастером токена или началом / концом круга, можно изменить. Он все равно вернется к тому же узлу при обходе, о котором будет сказано выше.

Шаги в (a) i-iii показаны ниже:

(Существующий узел)

ШАГ 1) Разорвите существующую ссылку

ШАГ 2) Создайте прямую ссылку (от нового узла к существующему узлу)

ШАГ 3) Создайте петлевую ссылку на первый узел

Затем вы попробуете вставить после узла.

Например, давайте вставим «VALUE2» после узла с «VALUE0». Предположим, что отправной точкой является узел с "VALUE0".

  • Вам нужно будет разорвать линию между первым и вторым узлами и поместить между ними узел с «VALUE2».
  • Следующий указатель первого узла должен связываться с этим узлом, а следующий указатель этого узла должен связываться с более ранним вторым узлом.
  • В остальном аранжировка осталась без изменений. Все узлы прослеживаются сами к себе.

ПРИМЕЧАНИЕ. Поскольку существует циклическая структура, вставка узла включает ту же процедуру для любого узла. Указатель, завершающий цикл, завершает цикл, как и любой другой узел.

Это показано ниже:

(Допустим, есть только два узла. Это тривиальный случай)

ШАГ 1) Удалите внутреннюю ссылку между подключенными узлами.

ШАГ 2) Подключите левый узел к новому узлу

ШАГ 3) Подключите новый узел к узлу правой стороны.

Операция удаления

Предположим, что это трехузловой круговой связанный список. Случаи удаления приведены ниже:

  • Удаление текущего элемента
  • Удаление после элемента.

Удаление в начале / конце:

  1. Перейти к первому узлу от последнего узла.
  2. Для удаления с конца должен быть только один шаг обхода от последнего узла к первому.
  3. Удалите связь между последним узлом и следующим узлом.
  4. Свяжите последний узел со следующим элементом первого узла.
  5. Освободите первый узел.

(Существующая установка)

ШАГ 1 ) Удалите круговую ссылку

ШАГИ 2) Удалите связь между первым и следующим, свяжите последний узел с узлом, следующим за первым.

ШАГ 3) Освободите / освободите первый узел

Удаление после узла:

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

ШАГ 1) Допустим, нам нужно удалить узел с «VALUE1».

ШАГ 2) Удалите связь между предыдущим узлом и текущим узлом. Свяжите его предыдущий узел со следующим узлом, указанным текущим узлом (с VALUE1).

ШАГ 3) Освободите или освободите текущий узел.

Обход кругового связного списка

Чтобы просмотреть круговой связанный список, начиная с последнего указателя, проверьте, является ли последний указатель NULL. Если это условие ложно, проверьте, есть ли только один элемент. В противном случае перемещайтесь с использованием временного указателя, пока снова не будет достигнут последний указатель, или столько раз, сколько необходимо, как показано в GIF ниже.

Преимущества циркулярного связного списка

Некоторые из преимуществ круговых связанных списков:

  1. Нет требований для присвоения NULL в коде. Круговой список никогда не указывает на NULL-указатель, если он полностью не освобожден.
  2. Списки с круговой связью удобны для конечных операций, поскольку начало и конец совпадают. Алгоритмы, такие как планирование циклического перебора, могут аккуратно исключать процессы, которые ставятся в очередь циклически, не сталкиваясь с висячими или нулевыми ссылочными указателями.
  3. Циклический список также выполняет все обычные функции односвязного списка. Фактически, кольцевые двусвязные списки, обсуждаемые ниже, могут даже устранить необходимость полного обхода для поиска элемента. Этот элемент будет не больше, чем прямо напротив начала, завершая половину связанного списка.

Односвязный список как круговой связанный список

Предлагаем вам попытаться прочитать и реализовать приведенный ниже код. Он представляет собой арифметику указателя, связанную с циклическими связными списками.

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

Расшифровка кода:

  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. Для кода addEmpty выделите пустой узел с помощью функции malloc.
  2. Для этого узла поместите данные во временную переменную.
  3. Назначьте и свяжите единственную переменную с временной переменной
  4. Вернуть последний элемент в контекст 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;…

Пояснение к коду

  1. Если нет элемента для вставки, вы должны обязательно добавить его в пустой список и вернуть управление.
  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. Если данные найдены или temp возвращается к последнему указателю, do-while завершается. В следующем разделе кода решается, что делать с этим элементом.
… 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. Переменная temp просто переходит на одну ссылку вперед.
  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. Если имеется более одного узла, временная программа печатает все элементы до последнего элемента.
  4. В тот момент, когда достигается последний элемент, цикл завершается, и функция возвращает вызов основной функции.

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

  • Реализация циклического планирования в системных процессах и циклического планирования в высокоскоростной графике.
  • Планирование Token Ring в компьютерных сетях.
  • Он используется в устройствах отображения, таких как торговые доски, которые требуют непрерывного просмотра данных.