Кръгъл еднопосочен списък. Решаване на задачи върху динамични структури от данни. Добавяне на възел към OCS

Последна актуализация: 25.10.2016

Пръстеновите (кръгови, циклични) списъци са вид свързани списъци. Те могат да бъдат просто свързани или двойно свързани. Техен отличителна чертае, че условният последен елемент съхранява препратка към първия елемент, така че списъкът се оказва затворен или кръгъл.

Например, ако нашият списък се състои от един главен елемент, глава, тогава можем да затворим такъв списък, както следва:

Head.next = глава;

За изпълнение нека вземем класа на елемента, който се използва в единично свързан списък:

Публичен клас Node ( public Node(T data) ( Data = data; ) public T Data ( get; set; ) public Node Next(get;set;))

Сега нека дефинираме кръгов клас от списък:

Използване на System.Collections; използване на System.Collections.Generic; пространство от имена SimpleAlgorithmsApp ( публичен клас CircularLinkedList :Изброим // пръстеновидно свързан списък ( Възел глава; // глава/първи елемент Възел опашка; // последен/опашен елемент int count; // брой елементи в списъка // добавяне на елемент public void Add(T data) ( Node възел = нов възел (данни); // ако списъкът е празен 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 ток = глава; Възел ток = глава; if (current == null) върне false; do ( if (current.Data.Equals(data)) return true; current = current.Next; ) while (current != head); връща невярно; ) IEnumerator IEnumerable.GetEnumerator() ( return ((IEnumerable)this).GetEnumerator(); ) IEnumerator IEnumerable .GetEnumerator() ( Възел ток = глава; do ( if (current != null) ( yield return current.Data; current = current.Next; ) ) while (current != head); ) ) )

Добавянето по същество се свежда до нулиране на показалеца към последния елемент на опашката и поставяне на новия елемент между опашката и главата:

Public void Add(T data) ( Node възел = нов възел (данни);

// ако списъкът е празен if (head == null) ( head = node; tail = node; tail.Next = head; ) else ( node.Next = head; tail.Next = node; tail = node; ) count++ ; )

При изтриване нулираме указателя към следващия елемент от предишния елемент по отношение на този, който се изтрива: // ако списъкът е празен 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 Public bool Remove(T data) ( Node

предишен = нула; if (IsEmpty) върне false; do ( if (current.Data.Equals(data)) ( // Ако възелът е в средата или в края if (previous != null) ( // премахване на текущия възел, сега предишният се отнася не за текущия, а към 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; предишен = текущ; текущ. Следващ; текущ != глава); връща невярно; )

Използване на кръгъл списък: CircularLinkedList circularList = нов CircularLinkedList

(); circularList.Add("Том"); circularList.Add("Боб"); circularList.Add("Алиса"); circularList.Add("Джак"); foreach (променлив елемент в circularList) ( Console.WriteLine(item); ) circularList.Remove("Bob"); Console.WriteLine("\nСлед изтриване:\n"); foreach (променлив елемент в circularList) ( Console.WriteLine(item); )

Конзолен изход:

За да получите достъп до желания елемент от линеен списък, трябва да видите списъка от началото, независимо от позицията на оригиналната точка за гледане. Това забавя операциите за достъп до елементите в списъка. Затварянето на елементите на списъка в пръстен елиминира този недостатък. Такъв списък се нарича цикличен. Можете да започнете да разглеждате кръгъл списък от всеки елемент, а не само от началото му, а началото на списъка може да бъде всеки от неговите елементи. Логическа структура на кръгъл списък:

1. Операции върху цикличен списък

Над кръгъл списък смогат да се изпълняват всички операции, дефинирани за линеен списък. Имайте предвид, че в логическата структура на цикличен списък понятията „начало“ и „край“ са условни и се определят от позицията на показалеца към някакъв елемент от списъка, който е заглавката.

За цикличен списък също се въвежда нова операция - конкатенация на два циклични списъка - Сoncat(с 1,с 2).

1. Единично свързано изпълнение на кръгов списък

Внедряване на кръгъл списък с помощта на динамични променливи:

Такъв списък се нарича единично свързан кръгов списък. От всеки елемент на списъка можете да стигнете до всеки друг елемент. Имайте предвид, че кръговият списък няма първи и последен елемент. Външният указател Head е удобен за използване като указател към текущия елемент от списъка. Когато решаваме конкретни проблеми, можем условно да приемем, че адресира последноелемент от списъка, което автоматично прави елемента след него първи.

Класът tCircleList може да бъде описан по следния начин:

tValue= Реална; // типът стойност на елемента от списъка е реален

pItem= ^tItem; // тип указател към елемент от списък

tItem= запис// тип елемент на списък

Стойност: tValue; // съдържание на елемента списък

Следващ: pItem; // указател към следващия елемент от списъка

край; // запис tItem

tCircleList= клас // Клас - цикличен списък

защитени

fHead:pltem; // поле - показалец къмтекущ елементсписък

fSize:Word; // поле - брой елементи от списъка

публичен

// Свойство - брой елементи от списък (достъп за четене и запис)

ИмотРазмер: Word Прочети fРазмер пишете fSize;

// Свойство – указател към началото на списъка (достъп за четене и запис)

ИмотГлава: Слово Прочети fHead пишете fHead;

vслед адресния елементадрес

процедура InsertAfter(Addr: pItem; v: tValue);

// Включете елемент със стойностvпреди адресния елементадрес

процедура InsertBefore(Addr: pItem; v: tValue);

// Изключете елемента след елемента с адреса на Addr

функция DeleteAfter(Addr: pItem): tValue;

// Изключване на елемент с указателадрес

функцияИзтриване (Addr:pItem):tValue;

// Включете елемент със стойностvкъм началото на списъка

процедура InsertHead(v:tValue);

// Включете елемент със стойностvдо края на списъка

процедура InsertRear(v:tValue);

// Изключване на елемент от началото на списъка

функция DeleteHead:tValue;

// Изключване на елемент от края на списъка

функция DeleteRear:tValue;

процедура Concat( вар CList2: tCircleList); // съединител на кола с списъкCList2

// Търсене в списъка за елемент със стойностvи връщане на адреса му

функцияТърсене (v: tValue): pItem;

функцияПразно: Boolean; // връщаневярно,Ако списък празен

процедураЯсно; // изчистване на списъка

конструкторСъздаване; // конструктор - създаване на празен списък

деструкторУнищожи; отмени; // деструктор - изтриване списък

край; // класtCircleList

Класът tCircleList не е деклариран като потомък на класа tList, тъй като изпълнението на почти всички негови методи се различава от изпълнението на методи със същото име за нецикличен списък. Разликите са основно както следва:

– за операциите InsertAfter и InsertBefore включването на елемент в празен списък и включването в началото и края на цикличен списък се извършват по различен начин;

– прилагането на операцията DeleteAfter към цикличен списък, състоящ се от един елемент, не трябва да води до изключване на самия този елемент;

– методите DeleteAfter и Delete трябва да възстановят указател към последния елемент от цикличния списък, ако той бъде елиминиран по време на тези операции;

– при методите Search и Clear признак за завършване на разглеждането на цикличен списък е когато спомагателният показалец достигне елемента, от който е започнало разглеждането.

И само конструкторът Create и деструкторът Destroy са имплементирани по същия начин като методите със същото име в класа tList.

Очевидно операциите за включване и изключване отдясно и отляво на текущия елемент (InsertHead, InsertRear, DeleteHead, DeleteRear) изпълняват същите действия като операциите със същото име за нецикличен списък. Разликата е, че новите операции променят стойността на показалеца към последния елемент от кръгъл списък, ако списъкът се е разширил наляво или надясно или стесни наляво или надясно.

Текст на лекцията.

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

Използвайки типове структури, указатели и динамични променливи, можете да създадете различни динамични структури на паметта. Характеристиките на указателите в езика C++ ви позволяват да изграждате динамични структури на паметта, базирани на статично декларирани променливи или на смес от статични и динамични променливи. Идеята за организиране на всички динамични структури е една и съща. Дефинира се определен структурен тип 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;

(*Глава)->

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->Данни<< "\t";

ptr=ptr->Напред;

) докато (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;

Нов елемент->Следващ = Нов елемент;

иначе (//списъкът не е празен

за (int i = 1; i< Number; i++)

Current = Current->Next;

Нов елемент->Следващ = Текущ->Следващ;

Current->Next = NewItem;

/*премахване на елемент с даден номер от кръгъл еднопосочен списък*/

Circle_Single_List* Изтриване_Item_Circle_Single_List

(Circle_Single_List* Head, int Number)(

if (Head != NULL)(

Circle_Single_List *Текущ = Глава;

if (Head->Next != Head)(

за (int i = 1; i< Number; i++)

Current = Current->Next;

докато (ptr->Напред!= Текущо)

ptr = ptr->Напред;

//директно премахване на елемента

ptr->Следващ = Текущ->Следващ;

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

изтриване (Текущо);

изтриване (Текущо);

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

bool Find_Item_Circle_Single_List(Circle_Single_List* Head,

Circle_Single_List *ptr = Глава;

//спомагателен указател

if (DataItem == ptr->Data) върне true;

else ptr = ptr->Напред;

докато (ptr != Глава);

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

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** Глава, Circle_Double_List* Цикъл)(

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;

ако (ptr == NULL)

иначе върне ptr;

//отпечатване на кръгов двоен списък

void Print_Circle_Double_List(Circle_Double_List* Head) (

Circle_Double_List* ptr=Глава;

//спомагателен указател

cout<< ptr->Данни<< "\t";

ptr=ptr->Напред;

) докато (ptr!=Head);

cout<< "\n";

/*вмъкване на елемент след дадено число в кръгов двупосочен списък*/

Circle_Double_List* Вмъкване на елемент_Circle_Double_List

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

//застанете на първия елемент

Circle_Double_List *NewItem = нов(Circle_Double_List);

//създаде нов елемент

NewItem->Data = DataItem;

if (Head == NULL) (//списъкът е празен

Нов елемент->Следващ = Нов елемент;

NewItem->Prior = NewItem;

иначе (//списъкът не е празен

за (int i = 1; i< Number; i++)

Current = 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 *Текущ = Глава;

if (Head->Next != Head)(

за (int i = 1; i< Number; i++)

Current = Current->Next;

Circle_Double_List *ptr = Current->Next;

Текущо->Предишно->Следващо = Текущо->Следващо;

Текущо->Следващо->Предишно = Текущо->Предишно;

if (Head = Current) //изтриване на първия

Head = Current->Next;

изтриване (Текущо);

изтриване (Текущо);

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

bool Find_Item_Circle_Double_List(Circle_Double_List* Head,

Circle_Double_List *ptr = Глава;

//спомагателен указател

ако (DataItem == ptr->Data)

else ptr = ptr->Напред;

докато (ptr != Глава);

//проверете дали кръгъл двойно списък е празен

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