Циклический однонаправленный список. Циклические (кольцевые) списки. Удаление узла ОЦС

Текст лекции.

Структурированные типы данных, такие, как массивы, множества, записи, представляют собой статические структуры, так как их размеры неизменны в течение всего времени выполнения программы. Часто требуется, чтобы структуры данных меняли свои размеры в ходе решения задачи. Такие структуры данных называются динамическими, к ним относятся стеки, очереди, списки, деревья и другие. Описание динамических структур с помощью массивов, записей и файлов приводит к неэкономному использованию памяти и увеличивает время решения задач.

Используя структурные типы, указатели и динамические переменные, можно создавать разнообразные динамические структуры памяти. Особенности указателей в языке С++ позволяют строить динамические структуры памяти на основе статически объявленных переменных или на смеси статических и динамических переменных. Идея организации всех динамических структур одна и та же. Определяется некоторый структурный тип S, одно или несколько полей которого объявлены указателями на тот же или некоторый другой структурный тип. В программе объявляется переменная d типа S или переменная типа указатель на S в случае полностью динамического создания структуры. Имя этой переменной при выполнении программы используется как имя «корня» (родительское имя) динамической структуры. При выполнении программы по мере построения динамической структуры запрашиваются динамические переменные соответствующих типов и связываются ссылками, начиная с переменной d или первой динамической переменной, указатель на которую содержится в переменной d. Этот подход позволяет создать динамическую структуру с любой топологией.

Циклический (кольцевой) список – это структура данных, представляющая собой последовательность элементов, последний элемент которой содержит указатель на первый элемент списка, а первый (в случае двунаправленного списка) – на последний.

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

Циклические списки, так же как и линейные, бывают однонаправленными и двунаправленными.

Циклический однонаправленный список похож на линейный однонаправленный список, но его последний элемент содержит указатель, связывающий его с первым элементом (рис. 1).

Для полного обхода такого списка достаточно иметь указатель на произвольный элемент, а не на первый, как в линейном однонаправленном списке. Понятие «первого» элемента здесь достаточно условно и не всегда требуется. Хотя иногда бывает полезно выделить некоторый элемент как «первый» путем установки на него специального указателя. Это требуется, например, для предотвращения «зацикливания» при просмотре списка.

Рис. 1. Циклический однонаправленный список

Основные операции, осуществляемые с циклическим однонаправленным списком:

· создание списка;

· печать (просмотр) списка;

· вставка элемента в список;

· поиск элемента в списке;

· проверка пустоты списка;

· удаление списка.

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

Приведем функции перечисленных основных операций при работе с циклическим однонаправленным списком.

//создание циклического однонаправленного списка

void Make_Circle_Single_List(int n,

Circle_Single_List** Head,Circle_Single_List* Loop){

(*Head) = new Circle_Single_List();

cout << "Введите значение ";

cin >> (*Head)->Data;

(*Head)->

Make_Circle_Single_List(n-1,&((*Head)->Next),Loop);

//печать циклического однонаправленного списка

void Print_Circle_Single_List(Circle_Single_List* Head) {

Circle_Single_List* ptr=Head;

//вспомогательный указатель

cout << ptr->Data << "\t";

ptr=ptr->Next;

} while (ptr!=Head);

cout << "\n";

/*вставка элемента после заданного номера в циклический однонаправленный список*/

Circle_Single_List* Insert_Item_Circle_Single_List(Circle_Single_List* Head,

int Number, int DataItem){

//встали на первый элемент

Circle_Single_List *NewItem = new(Circle_Single_List);

//создали новый элемент

NewItem->Data = DataItem;

NewItem->Next = NewItem;

else {//список не пуст

for (int i = 1; i < Number; i++)

Current = Current->Next;

NewItem->Next = Current->Next;

Current->Next = NewItem;

/*удаление элемента с заданным номером из циклического однонаправленного списка*/

Circle_Single_List* Delete_Item_Circle_Single_List

(Circle_Single_List* Head, int Number){

if (Head != NULL){

Circle_Single_List *Current = Head;

if (Head->Next != Head){

for (int i = 1; i < Number; i++)

Current = Current->Next;

while (ptr->Next != Current)

ptr = ptr->Next;

//непосредственное удаление элемента

ptr->Next = Current->Next;

if (Head = Current) Head = Current->Next;

delete(Current);

delete(Current);

//поиск элемента в циклическом однонаправленном списке

bool Find_Item_Circle_Single_List(Circle_Single_List* Head,

Circle_Single_List *ptr = Head;

//вспомогательный указатель

if (DataItem == ptr->Data) return true;

else ptr = ptr->Next;

while (ptr != Head);

//проверка пустоты циклического однонаправленного списка

bool Empty_Circle_Single_List(Circle_Single_List* Head){

//удаление циклического однонаправленного списка

void Delete_Circle_Single_List(Circle_Single_List* Head){

if (Head != NULL){

Head = Delete_Item_Circle_Single_List(Head, 1);

Delete_Circle_Single_List(Head);

Циклический двунаправленный список похож на линейный двунаправленный список, но его любой элемент имеет два указателя, один из которых указывает на следующий элемент в списке, а второй указывает на предыдущий элемент (рис. 2).

Рис.2. Циклический двунаправленный список

Основные операции, осуществляемые с циклическим двунаправленным списком:

· создание списка;

· печать (просмотр) списка;

· вставка элемента в список;

· удаление элемента из списка;

· поиск элемента в списке

· проверка пустоты списка;

· удаление списка.

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

Приведем функции перечисленных основных операций при работе с циклическим двунаправленным списком.

//создание циклического двунаправленного списка

Circle_Double_List* Make_Circle_Double_List(int n,

Circle_Double_List** Head,Circle_Double_List* Loop){

Circle_Double_List* ptr;//вспомогательный указатель

(*Head) = new Circle_Double_List();

//выделяем память под новый элемент

if (Loop == NULL) Loop = (*Head);

cout << "Введите значение ";

cin >> (*Head)->Data;

//вводим значение информационного поля

(*Head)->Next=NULL;//обнуление адресного поля

ptr = Make_Circle_Double_List(n-1,&((*Head)->Next),Loop);

if ((*Head)->Next != NULL)

(*Head)->Next->Prior = (*Head);

if ((*Head)->Prior == NULL)

(*Head)->Prior = ptr;

if (ptr == NULL)

else return ptr;

//печать циклического двунаправленного списка

void Print_Circle_Double_List(Circle_Double_List* Head) {

Circle_Double_List* ptr=Head;

//вспомогательный указатель

cout << ptr->Data << "\t";

ptr=ptr->Next;

} while (ptr!=Head);

cout << "\n";

/*вставка элемента после заданного номера в циклический двунаправленный список*/

Circle_Double_List* Insert_Item_Circle_Double_List

(Circle_Double_List* Head, int Number, int DataItem){

//встали на первый элемент

Circle_Double_List *NewItem = new(Circle_Double_List);

//создали новый элемент

NewItem->Data = DataItem;

if (Head == NULL) {//список пуст

NewItem->Next = NewItem;

NewItem->Prior = NewItem;

else {//список не пуст

for (int i = 1; i < Number; i++)

Current = Current->Next;

NewItem->Next = Current->Next;

Current->Next = NewItem;

NewItem->Prior = Current;

NewItem->Next->Prior = NewItem;

/*удаление элемента с заданным номером из циклического двунаправленного списка*/

Circle_Double_List* Delete_Item_Circle_Double_List(Circle_Double_List* Head,

if (Head != NULL){

Circle_Double_List *Current = Head;

if (Head->Next != Head){

for (int i = 1; i < Number; i++)

Current = Current->Next;

Circle_Double_List *ptr = Current->Next;

Current->Prior->Next = Current->Next;

Current->Next->Prior = Current->Prior;

if (Head = Current) //удаляем первый

Head = Current->Next;

delete(Current);

delete(Current);

//поиск элемента в циклическом двунаправленном списке

bool Find_Item_Circle_Double_List(Circle_Double_List* Head,

Circle_Double_List *ptr = Head;

//вспомогательный указатель

if (DataItem == ptr->Data)

else ptr = ptr->Next;

while (ptr != Head);

//проверка пустоты циклического двунаправленного списка

bool Empty_Circle_Double_List(Circle_Double_List* Head){

return (Head != NULL ? false: true);

//удаление циклического двунаправленного списка

void Delete_Circle_Double_List(Circle_Double_List* Head){

if (Head != NULL){

Head = Delete_Item_Circle_Double_List(Head, 1);

Delete_Circle_Double_List(Head);

Аннотация: В лекции рассматриваются определения, способы объявления, инициализация и особенности использования при решении задач циклических списков, деков, красно-черных деревьев, приводятся примеры решения задач на обработку кольцевых списков, деков, красно-черных деревьев.

Цель лекции : изучить алгоритмы и приемы работы с динамическими структурами данных , научиться решать задачи с использованием динамических структур данных и алгоритмов работы с ними на языке C++.

Структурированные типы данных , такие, как массивы, множества , записи, представляют собой статические структуры, так как их размеры неизменны в течение всего времени выполнения программы. Часто требуется, чтобы структуры данных меняли свои размеры в ходе решения задачи. Такие структуры данных называются динамическими, к ним относятся стеки, очереди, списки, деревья и другие. Описание динамических структур с помощью массивов, записей и файлов приводит к неэкономному использованию памяти и увеличивает время решения задач.

Используя структурные типы , указатели и динамические переменные , можно создавать разнообразные динамические структуры памяти. Особенности указателей в языке С++ позволяют строить динамические структуры памяти на основе статически объявленных переменных или на смеси статических и динамических переменных . Идея организации всех динамических структур одна и та же. Определяется некоторый структурный тип S , одно или несколько полей которого объявлены указателями на тот же или некоторый другой структурный тип . В программе объявляется переменная d типа S или переменная типа указатель на S в случае полностью динамического создания структуры. Имя этой переменной при выполнении программы используется как имя "корня" (родительское имя) динамической структуры. При выполнении программы по мере построения динамической структуры запрашиваются динамические переменные соответствующих типов и связываются ссылками, начиная с переменной d или первой динамической переменной , указатель на которую содержится в переменной d . Этот подход позволяет создать динамическую структуру с любой топологией.

Циклические (кольцевые) списки

Циклический (кольцевой) список – это структура данных , представляющая собой последовательность элементов, последний элемент которой содержит указатель на первый элемент списка , а первый (в случае двунаправленного списка) – на последний.

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

Циклические списки, так же как и линейные, бывают однонаправленными и двунаправленными .

Похож на линейный однонаправленный список , но его последний элемент содержит указатель , связывающий его с первым элементом ( рис. 32.1).

Для полного обхода такого списка достаточно иметь указатель на произвольный элемент, а не на первый, как в линейном однонаправленном списке. Понятие "первого" элемента здесь достаточно условно и не всегда требуется. Хотя иногда бывает полезно выделить некоторый элемент как "первый" путем установки на него специального указателя. Это требуется, например, для предотвращения "зацикливания" при просмотре списка.

Рис. 32.1.

Основные операции , осуществляемые с циклическим однонаправленным списком:

• создание списка;
• печать (просмотр) списка;
• вставка элемента в список;
• удаление элемента из списка;
• поиск элемента в списке;
• проверка пустоты списка;
• удаление списка.

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

Приведем функции перечисленных основных операций при работе с циклическим однонаправленным списком.

//создание циклического однонаправленного списка void Make_Circle_Single_List(int n, Circle_Single_List** Head,Circle_Single_List* Loop){ if (n > 0) { (*Head) = new Circle_Single_List(); //выделяем память под новый элемент if (Loop == NULL) Loop = (*Head); cout << "Введите значение "; cin >> (*Head)->Data; //вводим значение информационного поля (*Head)->Next=NULL;//обнуление адресного поля Make_Circle_Single_List(n-1,&((*Head)->Next),Loop); } else { (*Head) = Loop; } } //печать циклического однонаправленного списка void Print_Circle_Single_List(Circle_Single_List* Head) { Circle_Single_List* ptr=Head; //вспомогательный указатель do { cout << ptr->Data << "\t"; ptr=ptr-> << "\n"; } /*вставка элемента после заданного номера в циклический однонаправленный список*/ Circle_Single_List* Insert_Item_Circle_Single_List(Circle_Single_List* Head, int Number, int DataItem){ Circle_Single_List *Current = Head; //встали на первый элемент Circle_Single_List *NewItem = new(Circle_Single_List); //создали новый элемент NewItem->Data = DataItem; if (Head == NULL) {//список пуст NewItem->Next = NewItem; Head = NewItem; } else {//список не пуст for (int i = 1; i < Number; i++) Current = Current->Next; NewItem->Next = Current->Next; Current->Next = NewItem; } return Head; } /*удаление элемента с заданным номером из циклического однонаправленного списка*/ Circle_Single_List* Delete_Item_Circle_Single_List (Circle_Single_List* Head, int Number){ if (Head != NULL){ Circle_Single_List *Current = Head; if (Head-> < Number; i++) Current = Current->Next; Circle_Single_List *ptr = Head; while (ptr->Next != Current) ptr = ptr->Next; //непосредственное удаление элемента ptr->Next = Current->Next; if (Head = Current) Head = Current->Next; delete(Current); } else{ Head = NULL; delete(Current); } } return Head; } //поиск элемента в циклическом однонаправленном списке bool Find_Item_Circle_Single_List(Circle_Single_List* Head, int DataItem){ Circle_Single_List *ptr = Head; //вспомогательный указатель do { if (DataItem == ptr->Data) return true; else ptr = ptr->Next; } while (ptr != Head); return false; } //проверка пустоты циклического однонаправленного списка bool Empty_Circle_Single_List(Circle_Single_List* Head){ return (Head != NULL ? false: true); } //удаление циклического однонаправленного списка void Delete_Circle_Single_List(Circle_Single_List* Head){ if (Head != NULL){ Head = Delete_Item_Circle_Single_List(Head, 1); Delete_Circle_Single_List(Head); } } Листинг 1.

Похож на линейный двунаправленный список , но его любой элемент имеет два указателя, один из которых указывает на следующий элемент в списке, а второй указывает на предыдущий элемент ( рис. 32.2).

Рис. 32.2.

Основные операции , осуществляемые с циклическим двунаправленным списком:

• создание списка;
• печать (просмотр) списка;
• вставка элемента в список;
• удаление элемента из списка;
• поиск элемента в списке
• проверка пустоты списка;
• удаление списка.

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

Приведем функции перечисленных основных операций при работе с циклическим двунаправленным списком.

//создание циклического двунаправленного списка Circle_Double_List* Make_Circle_Double_List(int n, Circle_Double_List** Head,Circle_Double_List* Loop){ Circle_Double_List* ptr;//вспомогательный указатель if (n > 0) { (*Head) = new Circle_Double_List(); //выделяем память под новый элемент if (Loop == NULL) Loop = (*Head); cout << "Введите значение "; cin >> (*Head)->Data; //вводим значение информационного поля (*Head)->Next=NULL;//обнуление адресного поля ptr = Make_Circle_Double_List(n-1,&((*Head)->Next),Loop); if ((*Head)->Next != NULL) (*Head)->Next->Prior = (*Head); if ((*Head)->Prior == NULL) (*Head)->Prior = ptr; if (ptr == NULL) return *Head; else return ptr; } else { (*Head) = Loop; return NULL; } } //печать циклического двунаправленного списка void Print_Circle_Double_List(Circle_Double_List* Head) { Circle_Double_List* ptr=Head; //вспомогательный указатель do { cout << ptr->Data << "\t"; ptr=ptr->Next; } while (ptr!=Head); cout << "\n"; } /*вставка элемента после заданного номера в циклический двунаправленный список*/ Circle_Double_List* Insert_Item_Circle_Double_List (Circle_Double_List* Head, int Number, int DataItem){ Circle_Double_List *Current = Head; //встали на первый элемент Circle_Double_List *NewItem = new(Circle_Double_List); //создали новый элемент NewItem->Data = DataItem; if (Head == NULL) {//список пуст NewItem->Next = NewItem; NewItem->Prior = NewItem; Head = NewItem; } else {//список не пуст for (int i = 1; i < Number; i++) Current = Current->Next; NewItem->Next = Current->Next; Current->Next = NewItem; NewItem->Prior = Current; NewItem->Next->Prior = NewItem; } return Head; } /*удаление элемента с заданным номером из циклического двунаправленного списка*/ Circle_Double_List* Delete_Item_Circle_Double_List(Circle_Double_List* Head, int Number){ if (Head != NULL){ Circle_Double_List *Current = Head; if (Head->Next != Head){ for (int i = 1; i < Number; i++) Current = Current->Next; Circle_Double_List *ptr = Current->Next; Current->Prior->Next = Current->Next; Current->Next->Prior = Current->Prior; if (Head = Current) //удаляем первый Head = Current->Next; delete(Current); } else{ Head = NULL; delete(Current); } } return Head; } //поиск элемента в циклическом двунаправленном списке bool Find_Item_Circle_Double_List(Circle_Double_List* Head, int DataItem){ Circle_Double_List *ptr = Head; //вспомогательный указатель do { if (DataItem == ptr->Data) return true; else ptr = ptr->Next; } while (ptr != Head); return false; } //проверка пустоты циклического двунаправленного списка bool Empty_Circle_Double_List(Circle_Double_List* Head){ return (Head != NULL ? false: true); } //удаление циклического двунаправленного списка void Delete_Circle_Double_List(Circle_Double_List* Head){ if (Head != NULL){ Head = Delete_Item_Circle_Double_List(Head, 1); Delete_Circle_Double_List(Head); } } Листинг 2.

Последнее обновление: 25.10.2016

Кольцевые (круговые, циклические) списки являются разновидностью связных списков. Они могут быть односвязными или двусвязными. Их отличительной особенностью является то, что условной последний элемент хранит ссылку на первый элемент, поэтому список получается замкнутым или кольцевым.

Например, если у нас список состоит из одного головного элемента head, то мы можем замкнуть такой список следующим образом:

Head.next = head;

Для реализации возьмем класс элемента, который используется в односвязном списке:

Public class Node { public Node(T data) { Data = data; } public T Data { get; set; } public Node Next { get; set; } }

Теперь определим класс кольцевого списка:

Using System.Collections; using System.Collections.Generic; namespace SimpleAlgorithmsApp { public class CircularLinkedList : IEnumerable // кольцевой связный список { Node head; // головной/первый элемент Node tail; // последний/хвостовой элемент int count; // количество элементов в списке // добавление элемента public void Add(T data) { Node node = new Node(data); // если список пуст if (head == null) { head = node; tail = node; tail.Next = head; } else { node.Next = head; tail.Next = node; tail = node; } count++; } public bool Remove(T data) { Node current = head; Node previous = null; if (IsEmpty) return false; do { if (current.Data.Equals(data)) { // Если узел в середине или в конце if (previous != null) { // убираем узел current, теперь previous ссылается не на current, а на current.Next previous.Next = current.Next; // Если узел последний, // изменяем переменную tail if (current == tail) tail = previous; } else // если удаляется первый элемент { // если в списке всего один элемент if(count==1) { head = tail = null; } else { head = current.Next; tail.Next = current.Next; } } count--; return true; } previous = current; current = current.Next; } while (current != head); return false; } public int Count { get { return count; } } public bool IsEmpty { get { return count == 0; } } public void Clear() { head = null; tail = null; count = 0; } public bool Contains(T data) { Node current = head; if (current == null) return false; do { if (current.Data.Equals(data)) return true; current = current.Next; } while (current != head); return false; } IEnumerator IEnumerable.GetEnumerator() { return ((IEnumerable)this).GetEnumerator(); } IEnumerator IEnumerable.GetEnumerator() { Node current = head; do { if (current != null) { yield return current.Data; current = current.Next; } } while (current != head); } } }

Добавление фактически сводится к переустановке указателя на последний элемент tail, а новый элемент помещается между tail и head:

Public void Add(T data) { Node node = new Node(data); // если список пуст if (head == null) { head = node; tail = node; tail.Next = head; } else { node.Next = head; tail.Next = node; tail = node; } count++; }

При удалении переустанавливаем указатель на следующий элемент у предыдущего элемента по отношению к удаляемому:

Public bool Remove(T data) { Node current = head; Node previous = null; if (IsEmpty) return false; do { if (current.Data.Equals(data)) { // Если узел в середине или в конце if (previous != null) { // убираем узел current, теперь previous ссылается не на current, а на current.Next previous.Next = current.Next; // Если узел последний, // изменяем переменную tail if (current == tail) tail = previous; } else // если удаляется первый элемент { // если в списке всего один элемент if(count==1) { head = tail = null; } else { head = current.Next; tail.Next = current.Next; } } count--; return true; } previous = current; current = current.Next; } while (current != head); return false; }

Применение кольцевого списка:

CircularLinkedList circularList = new CircularLinkedList(); circularList.Add("Tom"); circularList.Add("Bob"); circularList.Add("Alice"); circularList.Add("Jack"); foreach (var item in circularList) { Console.WriteLine(item); } circularList.Remove("Bob"); Console.WriteLine("\n После удаления: \n"); foreach (var item in circularList) { Console.WriteLine(item); }

Консольный вывод:

Tom Bob Alice Jack После удаления: Tom Alice Jack