Кожен вузол односпрямованого циклічного списку (ОЦС) містить одне поле вказівника на наступний вузол. Поле покажчика останнього вузла містить адресу кореневого елемента.

Вузол ОЦС можна у вигляді структури, аналогічної однозв'язному лінійному списку

struct list
{
int field; // поле даних
struct list *ptr; // покажчик на наступний елемент
};

Основні дії, що виконуються над елементами ОЦС:

• Ініціалізація списку
• Додавання вузла до списку
• Видалення вузла зі списку
• Виведення елементів списку
• Взаємообмін двох вузлів списку

Оскільки список є циклічним, реалізація окремої функції видалення кореня списку не потрібна.

Ініціалізація списку призначена для створення кореневого вузла списку, у якого вказівник на наступний елемент містить адресу самого кореневого елемента.

1
2
3
4
5
6
7
8
9

struct list * init (int a) // а- значення першого вузла
{
struct list *lst;
// Виділення пам'яті під корінь списку
lst = (struct list *) malloc (sizeof (struct list));
lst->field = a;
lst->ptr = lst; // покажчик сам кореневий вузол
return (lst);
}

Додавання вузла до ОЦС

Функція додавання вузла до списку приймає два аргументи:

• Вказівник на елемент, після якого відбувається додавання
• Дані для елемента, що додається.

Процедуру додавання елемента можна відобразити такою схемою:


Додавання елемента в ОЦС включає наступні етапи:

• створення вузла, що додається, і заповнення його поля даних;
• переустановка покажчика вузла, попереднього додається, на вузол, що додається;
• установка покажчика вузла, що додається, на наступний вузол (той, на який вказував попередній вузол).

Таким чином, функція додавання вузла в ОЦС має вигляд, що повністю аналогічний функції додавання вузла в однозв'язний лінійний список :

1
2
3
4
5
6
7
8
9
10

struct list * addelem (list * lst, int number)
{
struct list *temp, *p;
temp = (struct list *) malloc (sizeof (list));
p = lst->ptr; // Збереження покажчика на наступний елемент
lst->ptr = temp; // Попередній вузол вказує на створюваний
temp->field = number; // збереження поля даних вузла, що додається
temp->ptr = p; // Створений вузол вказує на наступний елемент
return (temp);
}

Значення функції, що повертається, є адреса доданого вузла.

Видалення вузла ОЦС

Як аргументи функції видалення вузла ОЦС передається покажчик на вузол, що видаляється. Оскільки список циклічний, не потрібно передавати вказівник на корінь списку.

Функція повертає покажчик на вузол, що йде за видаленим.

Видалення вузла може бути представлене наступною схемою:

Видалення вузла ОЦС включає наступні етапи:

• установка покажчика попереднього вузла на вузол, що йде за видаленим;
• звільнення пам'яті вузла, що видаляється.

1
2
3
4
5
6
7
8
9
10
11
12

struct list * deletelem (list * lst)
{
struct list * temp;
temp = lst;
while (temp->ptr! = lst) // переглядаємо список починаючи з кореня
{ // поки не знайдемо вузол, що передує lst
temp = temp->ptr;
}
temp->ptr = lst->ptr; // Переставляємо вказівник
free(lst); // звільняємо пам'ять вузла, що видаляється
return (temp);
}

Виведення елементів ОЦС

Функція виведення елементів ОЦС аналогічна функції для ОЛС крім умови закінчення обходу елементів.
Як аргумент у функцію виведення елементів передається покажчик на корінь списку.
Функція здійснює послідовний обхід всіх вузлів із виведенням їх значень.

1
2
3
4
5
6
7
8
9

void listprint(list *lst)
{
struct list *p;
p = lst;
do (
printf("%d ", p->field); // Висновок значення вузла p
p = p->ptr; // Перехід до наступного вузла
) while (p! = lst); // умова закінчення обходу
}

Для ОЦС можна викликати функцію виведення елементів списку починаючи з будь-якого вузла.

Взаємообмін вузлів ОЦС

В якості аргументів функція взаємообміну ОЦС приймає два покажчики за вузли, що обмінюються, а також покажчик на корінь списку. Функція повертає адресу кореневого сайту списку.

Взаємообмін вузлів списку здійснюється шляхом перевстановлення покажчиків. Для цього необхідно визначити попередній та наступний вузли для кожного, що замінюється. При цьому можливі дві ситуації:

• вузли, що замінюються, є сусідами;
• вузли, що замінюються, не є сусідами, тобто між ними є хоча б один елемент.

При заміні сусідніх вузлів переустановка покажчиків виглядає так:


При заміні вузлів, що не є сусідніми, переустановка покажчиків виглядає наступним чином:

При перевстановленні покажчиків необхідність перевірки кореневого вузла відсутня (на відміну аналогічної функції для lst2->ptr = lst1;
lst1->ptr = next2;
prev1->ptr = lst2;
}
else if (lst1 == next2)
{
// обмінюються сусідні вузли
lst1->ptr = lst2;
lst2->ptr = next1;
prev2->ptr = lst2;
}
else
{
// обмінюються віддалені вузли
prev1->ptr = lst2;
lst2->ptr = next1;
prev2->ptr = lst1;
lst1->ptr = next2;
}
if (lst1 == head)
return (lst2);
if (lst2 == head)
return (lst1);
return (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);<< "Введите значение "; 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;>< 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 tru >Next; ) while (ptr! = Head); return false; 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) ((* виділяємо пам'ять під новий елемент if (Loop == NULL) Loop = (*Head);<< "Введите значение "; 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 = Hed=ad ( 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) tur >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; використовуючи 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 = новий 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

Текст лекції.

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

Використовуючи структурні типи, покажчики та динамічні змінні, можна створювати різноманітні динамічні структури пам'яті. Особливості покажчиків у мові З дозволяють будувати динамічні структури пам'яті на основі статично оголошених змінних або на суміші статичних і динамічних змінних. Ідея організації всіх динамічних структур одна й та сама. Визначається деякий структурний тип S, одне або кілька полів якого оголошено покажчиками на той самий або інший структурний тип. У програмі оголошується змінна d типу S або змінна типу покажчик S у разі повністю динамічного створення структури. Ім'я цієї змінної під час виконання програми використовується як ім'я «кореня» (батьківське ім'я) динамічної структури. При виконанні програми в міру побудови динамічної структури запитуються динамічні змінні відповідних типів і зв'язуються посиланнями, починаючи з змінної d або першої динамічної змінної, вказівник на яку міститься в змінній d. Цей підхід дозволяє створити динамічну структуру із будь-якою топологією.

Циклічний (кільцевий) список– це структура даних, що є послідовність елементів, останній елемент якої містить покажчик перший елемент списку, а перший (у разі двонаправленого списку) – на останній.

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

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

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

Для повного обходу такого списку достатньо мати вказівник на довільний елемент, а не на перший, як у однопрямому лінійному списку. Поняття «першого» елемента тут є досить умовним і не завжди потрібним. Хоча іноді буває корисно виділити певний елемент як "перший" шляхом встановлення на нього спеціального покажчика. Це потрібно, наприклад, для запобігання зациклюванню при перегляді списку.

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

Основні операції, що здійснюються з циклічним односпрямованим списком:

· Створення списку;

· Друк (перегляд) списку;

· Вставка елемента до списку;

· Пошук елемента у списку;

· Перевірка порожнечі списку;

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

Для опису алгоритмів цих основних операцій будемо використовувати самі оголошення, що й для лінійного односпрямованого списку.

Наведемо функції перелічених основних операцій під час роботи з циклічним односпрямованим списком.

//Створення циклічного односпрямованого списку

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