Každý uzol jednosmerného (jednosmerne prepojeného) kruhového zoznamu (SCL) obsahuje jedno pole ukazovateľa na nasledujúci uzol. Posledné pole ukazovateľa uzla obsahuje adresu koreňového prvku.

OC uzol môže byť reprezentovaný ako štruktúra podobná jednoducho prepojenému lineárnemu zoznamu

zoznam štruktúr
{
intfield; // dátové pole
zoznam štruktúr *ptr; // ukazovateľ na nasledujúci prvok
};

Hlavné akcie vykonávané na prvkoch CCS:

• Inicializácia zoznamu
• Pridanie uzla do zoznamu
• Odstránenie uzla zo zoznamu
• Zobrazenie položiek zoznamu
• Výmena dvoch uzlov zoznamu

Pretože zoznam je cyklický, nie je potrebné implementovať samostatnú funkciu na odstránenie koreňa zoznamu.

Inicializácia zoznamu je určená na vytvorenie koreňového uzla zoznamu, ktorého ukazovateľ na pole ďalšieho prvku obsahuje adresu samotného koreňového prvku.

1
2
3
4
5
6
7
8
9

zoznam štruktúr * init(int a) // a- hodnota prvého uzla
{
zoznam štruktúr *lst;
// alokuje pamäť pre koreň zoznamu
lst = (zoznam štruktúr*)malloc(veľkosť (zoznam štruktúr));
lst->pole = a;
lst->ptr = lst; // ukazovateľ na samotný koreňový uzol
return(lst);
}

Pridanie uzla do CSC

Funkcia na pridanie uzla do zoznamu má dva argumenty:

• Ukazovateľ na prvok, ktorý sa má pridať za
• Údaje pre prvok, ktorý sa má pridať.

Postup pridávania prvku môže byť znázornený na nasledujúcom diagrame:


Pridanie prvku do CCA zahŕňa nasledujúce kroky:

• vytvorenie uzla, ktorý sa má pridať, a vyplnenie jeho dátového poľa;
• preinštalovanie ukazovateľa uzla pred pridaným uzlom na pridaný uzol;
• nastavenie ukazovateľa pridaného uzla na nasledujúci uzol (ten, na ktorý ukazuje predchádzajúci uzol).

Funkcia pridania uzla do CCS má teda úplne podobnú formu ako funkcia pridania uzla do jednoducho prepojeného lineárneho zoznamu:

1
2
3
4
5
6
7
8
9
10

zoznam štruktúr * adelem(zoznam *lst, int číslo)
{
zoznam štruktúr *temp, *p;
temp = (zoznam štruktúr*)malloc(veľkosť (zoznam));
p = lst->ptr; // uloženie ukazovateľa na nasledujúci prvok
lst->ptr = teplota; // predchádzajúci uzol ukazuje na ten, ktorý sa vytvára
temp->pole = cislo; // uloženie dátového poľa pridaného uzla
temp->ptr = p; // vytvorený uzol ukazuje na ďalší prvok
return(temp);
}

Návratová hodnota funkcie je adresa pridaného uzla.

Odstránenie uzla CCA

Ukazovateľ na uzol, ktorý sa má vymazať, sa odovzdá ako argument funkcii vymazania uzla CCA. Keďže zoznam je cyklický, nie je potrebné odovzdávať ukazovateľ na koreň zoznamu.

Funkcia vráti ukazovateľ na uzol, ktorý nasleduje za uzlom, ktorý sa odstraňuje.

Odstránenie uzla môže byť znázornené nasledujúcou schémou:

Odstránenie uzla CCA zahŕňa nasledujúce kroky:

• nastavenie ukazovateľa predchádzajúceho uzla na uzol, ktorý nasleduje po vymazanom uzle;
• uvoľnenie pamäte uzla, ktorý sa má vymazať.

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

zoznam štruktúr * deletelem(list *lst)
{
zoznam štruktúr *temp;
temp=lst;
while (temp->ptr != lst) // prechádzať zoznamom od koreňa
{ // kým nenájdeme uzol predchádzajúci lst
temp = temp->ptr;
}
temp->ptr = lst->ptr; // preusporiadať ukazovateľ
free(lst); // uvoľní pamäť uzla, ktorý sa má vymazať
return(temp);
}

Výstup prvkov CKO

Funkcia výstupu prvkov CCS je podobná funkcii pre RL, až na podmienku ukončenia bypassu prvkov.
Ako argument sa do funkcie výstupu prvku odovzdá ukazovateľ na koreň zoznamu.
Funkcia vykonáva sekvenčný prechod všetkých uzlov s výstupom ich hodnôt.

1
2
3
4
5
6
7
8
9

void listprint(list*lst)
{
zoznam štruktúr *p;
p = lst;
robiť (
printf("%d " , p->pole); // výstupná hodnota uzla p
p = p->ptr; // presun na ďalší uzol
) while (p != lst); // podmienka ukončenia prechodu
}

V prípade CSC môžete tiež zavolať funkciu na zobrazenie prvkov zoznamu počnúc ľubovoľným uzlom.

Výmena uzlov OCS

Funkcia výmeny CCA používa ako argumenty dva ukazovatele na vymenené uzly, ako aj ukazovateľ na koreň zoznamu. Funkcia vráti adresu koreňového uzla zoznamu.

Výmena uzlov zoznamu sa vykonáva preinštalovaním ukazovateľov. Aby ste to dosiahli, musíte definovať predchodca a následník pre každý nahradený uzol. V tomto prípade sú možné dve situácie:

• uzly, ktoré sa nahrádzajú, sú susedmi;
• vymenené uzly nie sú susedmi, to znamená, že medzi nimi je aspoň jeden prvok.

Pri výmene susedných uzlov vyzerá resetovanie ukazovateľov takto:


Pri výmene uzlov, ktoré nie sú susedmi, resetovanie ukazovateľov vyzerá takto:

Pri preinštalovaní ukazovateľov nie je potrebné kontrolovať koreňový uzol (na rozdiel od podobnej funkcie pre lst2->ptr = lst1;
lst1->ptr = dalsi2;
prev1->ptr = lst2;
}
else if (lst1 == next2)
{
// výmena susedných uzlov
lst1->ptr = lst2;
lst2->ptr = dalsi1;
prev2->ptr = lst2;
}
inak
{
// výmena vzdialených uzlov
prev1->ptr = lst2;
lst2->ptr = dalsi1;
prev2->ptr = lst1;
lst1->ptr = dalsi2;
}
if (lst1 == hlava)
return(lst2);
if (lst2 == hlava)
return(lst1);
návrat (hlava);
}

Anotácia: Prednáška rozoberá definície, spôsoby deklarovania, inicializácie a vlastnosti použitia kruhových zoznamov, deques, červeno-čiernych stromov pri riešení úloh, uvádza príklady riešenia úloh na spracovanie kruhových zoznamov, deques, červeno-čierne stromy.

Účel prednášky: Naučte sa algoritmy a techniky na prácu s dynamické dátové štruktúry naučiť sa riešiť problémy pomocou dynamických dátových štruktúr a algoritmov na prácu s nimi v C++.

Typy štruktúrovaných údajov, ako sú polia, množiny, záznamy, sú statické štruktúry, pretože ich veľkosti zostávajú nezmenené počas celého vykonávania programu. Často sa vyžaduje, aby dátové štruktúry menili svoju veľkosť v priebehu riešenia problému. Takéto dátové štruktúry sa nazývajú dynamické, zahŕňajú zásobníky, fronty, zoznamy, stromy a iné. Opis dynamických štruktúr pomocou polí, záznamov a súborov vedie k nehospodárnemu využívaniu pamäte a zvyšuje čas na riešenie problémov.

Použitím konštrukčné typy, ukazovatele a dynamické premenné, môžete vytvárať rôzne dynamické pamäťové štruktúry. Vlastnosti ukazovateľov v jazyku C++ vám umožňujú vytvárať dynamické pamäťové štruktúry založené na statickom princípe deklarované premenné alebo na zmesi statických a dynamické premenné. Myšlienka usporiadania všetkých dynamických štruktúr je rovnaká. Je definovaný nejaký štruktúrny typ S, ktorého jedno alebo viac polí je deklarovaných ako ukazovatele na rovnaký alebo iný typ štruktúry. Program deklaruje premennú d typu S alebo premennú typu pointer na S v prípade plne dynamickej tvorby štruktúry. Názov tejto premennej sa používa ako názov "root" (rodičovského názvu) dynamickej štruktúry počas vykonávania programu. Pri spúšťaní programu, keď sa buduje dynamická štruktúra, dynamické premenné zodpovedajúcich typov a sú spojené odkazom počínajúc premennou d alebo prvou dynamická premenná, ukazovateľ na ktorý je obsiahnutý v premennej d . Tento prístup vám umožňuje vytvoriť dynamickú štruktúru s akoukoľvek topológiou.

Cyklické (krúžkové) zoznamy

Cyklický (krúžkový) zoznam- to dátová štruktúra, čo je postupnosť prvkov, ktorej posledný prvok obsahuje ukazovateľ na prvý prvok zoznamu a prvý (v prípade obojsmerný zoznam) do posledného.

Hlavnou črtou takejto organizácie je, že v tomto zozname nie sú žiadne prvky obsahujúce nuly, a preto nie je možné vybrať extrémne prvky.

Kruhové zoznamy, podobne ako lineárne zoznamy, môžu byť jednosmerné a obojsmerný.

Vyzerá ako lineárny jednoducho prepojený zoznam, ale jeho posledný prvok obsahuje ukazovateľ, ktorý ho spája s prvým prvkom (obrázok 32-1).

Na úplné prejdenie takéhoto zoznamu stačí mať ukazovateľ na ľubovoľný prvok, a nie na prvý, ako v lineárnom jednosmernom zozname. Koncept „prvého“ prvku je tu skôr podmienený a nie vždy sa vyžaduje. Hoci niekedy je užitočné zvýrazniť niektorý prvok ako „prvý“ nastavením špeciálneho ukazovateľa. Vyžaduje sa to napríklad preto, aby sa zabránilo "zacykleniu" pri prezeraní zoznamu.

Ryža. 32.1.

Základné operácie vykonávané s cyklickým jednosmerným zoznamom:

• tvorba zoznamu;
• tlač (prezeranie) zoznamu;
• vloženie prvku do zoznamu;
• vymazanie prvku zo zoznamu;
• vyhľadať prvok v zozname;
• kontrola, či je zoznam prázdny;
• vymazanie zoznamu.

Na opísanie algoritmov pre tieto základné operácie použijeme rovnaké deklarácie ako pre lineárny jednoducho prepojený zoznam.

Uveďme si funkcie uvedených základných operácií pri práci s cyklickým jednosmerným zoznamom.

//vytvor kruhový jednotlivo orientovaný zoznam void Make_Circle_Single_List(int n, Circle_Single_List** Head,Circle_Single_List* Loop)( if (n > 0) ( (*Head) = new Circle_Single_List(); //pridelenie pamäte pre nový prvok if (Loop = = NULL) Loop = (*Head); cout<< "Введите значение "; cin >> (*Hlava)->Údaje; //zadajte hodnotu informačného poľa (*Head)->Next=NULL;//vynulujte pole adresy Make_Circle_Single_List(n-1,&((*Head)->Next),Loop); ) else ( (*Head) = Loop; ) ) //Tlač kruhového jednosmerného zoznamu void Print_Circle_Single_List(Circle_Single_List* Head) ( Circle_Single_List* ptr=Head; //pomocný ukazovateľ do ( cout<< ptr->Údaje<< "\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) (//zoznam je prázdny NováPoložka->Ďalší = NováPoložka; Hlavička = NováPoložka; ) else (//zoznam nie je prázdny pre (int i = 1; i< Number; i++) Current = Current->Ďalšie; NováPoložka->Ďalšia = Aktuálna->Ďalšia; Aktuálny->Ďalší = NováPoložka; ) vrátiť hlavu; ) /*odstráni položku s daným číslom z kruhového samostatného zoznamu*/ 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->Ďalšie; Circle_Single_List *ptr = Head; while (ptr->Next != Current) ptr = ptr->Next; //okamžité odstránenie prvku ptr->Next = Current->Next; if (Hlava = Prúd) Hlava = Prúd->Ďalší; delete(Aktuálne); ) else( Head = NULL; delete(Current); ) ) return Head; ) //vyhľadajte prvok v kruhovom jednoducho orientovanom zozname bool Find_Item_Circle_Single_List(Circle_Single_List* Head, int DataItem)( Circle_Single_List *ptr = Head; //pomocný ukazovateľ do ( if (DataItem == ptr->Data) return true; else ptr = ptr- >Next; ) while (ptr != Head); return false; ) // skontrolujte, či je cyklický jednotlivý zoznam prázdny bool Empty_Circle_Single_List(Circle_Single_List* Head)( return (Head != NULL ? false: true) ; ) // vymazanie jednotlivo cyklického zoznamu 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);

Vyzerá ako lineárny obojsmerný zoznam, ale každý jeho prvok má dva ukazovatele, z ktorých jeden ukazuje na nasledujúci prvok v zozname a druhý ukazuje na predchádzajúci prvok (obr. 32.2).

Ryža. 32.2.

Základné operácie vykonávané cyklicky obojsmerný zoznam:

• tvorba zoznamu;
• tlač (prezeranie) zoznamu;
• vloženie prvku do zoznamu;
• vymazanie prvku zo zoznamu;
• hľadať prvok v zozname
• kontrola, či je zoznam prázdny;
• vymazanie zoznamu.

Na popis algoritmov týchto základných operácií použijeme rovnaké deklarácie ako pre lineárne obojsmerný zoznam.

Uveďme si funkcie uvedených základných operácií pri práci s cyklikou obojsmerný zoznam.

//vytvor kruhový obojsmerný zoznam Circle_Double_List* Make_Circle_Double_List(int n, Circle_Double_List** Head,Circle_Double_List* Loop)( Circle_Double_List* ptr;//pomocný ukazovateľ if (n > 0) (*CircleList) =_ new CircleList)); / alokovať pamäť pre nový prvok if (Loop == NULL) Loop = (*Head); cout<< "Введите значение "; cin >> (*Hlava)->Údaje; //zadajte hodnotu informačného poľa (*Head)->Next=NULL;//vynulujte pole adresy ptr = Make_Circle_Double_List(n-1,&((*Head)->Next),Loop); if ((*Hlava)->Ďalšia != NULL) (*Hlava)->Ďalšia->Predchádzajúca = (*Hlava); if ((*Head)->Prior == NULL) (*Head)->Prior = ptr; if (ptr == NULL) return *Head; else return ptr; ) else ( (*Head) = Loop; return NULL; ) ) //tlač kruhového dvojitého zoznamu void Print_Circle_Double_List(Circle_Double_List* Head) ( Circle_Double_List* ptr=Head; //pomocný ukazovateľ do ( cout<< ptr->Údaje<< "\t"; ptr=ptr->Ďalšie; ) while (ptr!=Hlava); 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) (//zoznam je prázdny NováPoložka->Ďalšia = NováPoložka; NováPoložka->Predchádzajúca = NováPoložka; Hlavička = NováPoložka; ) else (//zoznam nie je prázdny pre (int i = 1; i< Number; i++) Current = Current->Ďalšie; NováPoložka->Ďalšia = Aktuálna->Ďalšia; Aktuálny->Ďalší = NováPoložka; NováPoložka->Predchádzajúca = Aktuálny; NováPoložka->Ďalšia->Predchádzajúca = Nová položka; ) vrátiť hlavu; ) /*odstráni položku s daným číslom z kruhového zdvojeného zoznamu*/ Circle_Double_List* Delete_Item_Circle_Double_List(Circle_Double_List* Head, int Number)( if (Head != NULL)( Circle_Double_List *Current = Head; if (Head-> = Hlava) (pre (int i = 1; i< Number; i++) Current = Current->Ďalšie; Circle_Double_List *ptr = Aktuálny->Ďalší; Aktuálny->Predchádzajúci->Ďalší = Aktuálny->Ďalší; Aktuálny->Ďalší->Predchádzajúci = Aktuálny->Predchádzajúci; if (Head = Current) //odstráni prvú Head = Current->Next; delete(Aktuálne); ) else( Head = NULL; delete(Current); ) ) return Head; ) //hľadanie prvku v kruhovom obojsmernom zozname bool Find_Item_Circle_Double_List(Circle_Double_List* Head, int DataItem)( Circle_Double_List *ptr = Head; //pomocný ukazovateľ do ( if (DataItem == ptr->Data) return true; else ptr = ptr- >Next; ) while (ptr != Head); return false; ) //Skontrolujte, či je cyklický dvojitý zoznam prázdny bool Empty_Circle_Double_List(Circle_Double_List* Head)( return (Head != NULL ? false: true); ) //odstránenie cyklického dvojitého zoznamu void Delete_Circle_Double_List(Circle_Double_List* Head)( if (Head != NULL)( Head = Delete_Item_Circle_Double_List(Head, 1); Delete_Circle_Double_List)List (Head); 2.)

Posledná aktualizácia: 25.10.2016

Kruhové (kruhové, cyklické) zoznamy sú akési prepojené zoznamy. Môžu byť jednoduché alebo dvojité. ich charakteristický znak je, že podmienený posledný prvok ukladá odkaz na prvý prvok, takže zoznam je uzavretý alebo kruhový.

Napríklad, ak náš zoznam pozostáva z jednej hlavy prvku head, potom môžeme takýto zoznam uzavrieť takto:

hlava.next = hlava;

Na implementáciu si zoberme triedu prvkov, ktorá sa používa v jednoducho prepojenom zozname:

Verejná trieda Node ( public Node(T data) ( Data = data; ) public T Data ( get; set; ) public Node Ďalej (získať; nastaviť; ) )

Teraz definujme triedu zoznamu zvonení:

Používanie System.Collections; pomocou System.Collections.Generic; priestor názvov SimpleAlgorithmsApp (verejná trieda CircularLinkedList :IEpočetné // kruhový prepojený zoznam ( Node hlava; // head/first element Node chvost; // posledný/koncový prvok int pocet; // počet prvkov v zozname // pridanie prvku public void Add(T data) ( Node uzol = nový uzol (údaje); // ak je zoznam prázdny if (head == null) ( head = node; tail = node; tail.Next = head; ) else ( node.Next = head; tail.Next = uzol; tail = uzol; ) count++ ; ) public bool Remove(T data) (Node prúd = hlava; uzol predchádzajúci = null; if (IsEmpty) vráti hodnotu false; do ( if (current.Data.Equals(data)) ( // Ak je uzol v strede alebo na konci if (predchádzajúci != null) ( // odstráňte aktuálny uzol, teraz predchádzajúci odkazuje nie na aktuálny, ale na aktuálny.Ďalší predchádzajúci .Ďalší = aktuálny.Ďalší; // Ak je uzol posledný, // zmeňte koncovú premennú, ak (aktuálny == chvost) chvost = predchádzajúci; ) else // ak sa odstráni prvý prvok ( // ak je v zozname iba jeden prvok if(count= =1) (head = tail = null; ) else (head = current.Next; tail.Next = current.Next; ) ) count--; return true ; ) predchádzajúci = aktuálny; aktuálny = aktuálny. Ďalej; ) while ( aktuálny ! = hlava); vrátiť nepravdu; ) 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 údaje) ( Uzol prúd = hlava; if (aktuálne == null) return false; do ( if (current.Data.Equals(data)) return true; current = current.Next; ) while (current != head); vrátiť nepravdu; ) IEnumerator IEnumerable.GetEnumerator() ( return ((IEnumerable)this).GetEnumerator(); ) IEnumerator IEpočetné .GetEnumerator() (Uzol prúd = hlava; do ( if (aktuálny != null) ( výnos návratový prúd.Údaje; prúd = aktuálny.Ďalší; ) ) while (aktuálny != hlava); )))

Pridanie sa v skutočnosti scvrkáva na resetovanie ukazovateľa na posledný prvok chvosta a nový prvok sa umiestni medzi chvost a hlavu:

Public void Add(T data) (Node uzol = nový uzol (údaje); // ak je zoznam prázdny if (head == null) ( head = node; tail = node; tail.Next = head; ) else ( node.Next = head; tail.Next = uzol; tail = uzol; ) count++ ; )

Pri odstraňovaní prestavíme ukazovateľ na nasledujúci prvok predchádzajúceho prvku vo vzťahu k prvku, ktorý sa odstraňuje:

Public bool Remove(T data) (Node prúd = hlava; uzol predchádzajúci = null; if (IsEmpty) vráti hodnotu false; do ( if (current.Data.Equals(data)) ( // Ak je uzol v strede alebo na konci if (predchádzajúci != null) ( // odstráňte aktuálny uzol, teraz predchádzajúci odkazuje nie na aktuálny, ale na aktuálny.Ďalší predchádzajúci .Ďalší = aktuálny.Ďalší; // Ak je uzol posledný, // zmeňte koncovú premennú, ak (aktuálny == chvost) chvost = predchádzajúci; ) else // ak sa odstráni prvý prvok ( // ak je v zozname iba jeden prvok if(count= =1) (head = tail = null; ) else (head = current.Next; tail.Next = current.Next; ) ) count--; return true ; ) predchádzajúci = aktuálny; aktuálny = aktuálny. Ďalej; ) while ( aktuálny ! = hlava); vrátiť nepravdu; )

Aplikácia zoznamu prsteňov:

CircularLinkedList circleList = nový CircularLinkedList (); circleList.Add("Tom"); circleList.Add("Bob"); circleList.Add("Alice"); circleList.Add("Jack"); foreach (položka var v circleList) ( Console.WriteLine(item); ) circleList.Remove("Bob"); Console.WriteLine("\n Po odstránení: \n"); foreach (položka var v kruhovom zozname) ( Console.WriteLine(item); )

Výstup na konzolu:

Tom Bob Alice Jack Odstránený: Tom Alice Jack

Text prednášky.

Štruktúrované dátové typy, ako sú polia, množiny a záznamy, sú statické štruktúry, pretože ich veľkosti sa nemenia počas celého vykonávania programu. Často sa vyžaduje, aby dátové štruktúry menili svoju veľkosť v priebehu riešenia problému. Takéto dátové štruktúry sa nazývajú dynamické, zahŕňajú zásobníky, fronty, zoznamy, stromy a iné. Opis dynamických štruktúr pomocou polí, záznamov a súborov vedie k nehospodárnemu využívaniu pamäte a zvyšuje čas na riešenie problémov.

Pomocou štruktúrnych typov, ukazovateľov a dynamických premenných môžete vytvárať rôzne dynamické pamäťové štruktúry. Vlastnosti ukazovateľov v jazyku C++ vám umožňujú vytvárať dynamické pamäťové štruktúry založené na staticky deklarovaných premenných alebo na zmesi statických a dynamických premenných. Myšlienka usporiadania všetkých dynamických štruktúr je rovnaká. Je definovaný nejaký štruktúrny typ S, ktorého jedno alebo viac polí je deklarovaných ako ukazovatele na rovnaký alebo iný typ štruktúry. Program deklaruje premennú d typu S alebo premennú typu pointer na S v prípade plne dynamickej tvorby štruktúry. Názov tejto premennej sa používa ako názov "root" (rodičovského názvu) dynamickej štruktúry počas vykonávania programu. Keď je program spustený, keď sa vytvára dynamická štruktúra, sú požadované dynamické premenné príslušných typov a prepojené odkazmi, počnúc premennou d alebo prvou dynamickou premennou, ktorej ukazovateľ je obsiahnutý v premennej d. Tento prístup vám umožňuje vytvoriť dynamickú štruktúru s akoukoľvek topológiou.

Cyklický (krúžkový) zoznam je dátová štruktúra, ktorá je sekvenciou prvkov, ktorej posledný prvok obsahuje ukazovateľ na prvý prvok zoznamu a prvý (v prípade obojsmerného zoznamu) na posledný.

Hlavnou črtou takejto organizácie je, že v tomto zozname nie sú žiadne prvky obsahujúce nuly, a preto nie je možné vybrať extrémne prvky.

Kruhové zoznamy, podobne ako lineárne zoznamy, môžu byť jednosmerné alebo obojsmerné.

Kruhový jednotlivo riadený zoznam podobný lineárnemu jednoducho prepojenému zoznamu, ale jeho posledný prvok obsahuje ukazovateľ, ktorý ho spája s prvým prvkom (obrázok 1).

Na úplné prejdenie takéhoto zoznamu stačí mať ukazovateľ na ľubovoľný prvok, a nie na prvý, ako v lineárnom jednosmernom zozname. Pojem „prvý“ prvok je tu skôr podmienený a nie vždy sa vyžaduje. Hoci niekedy je užitočné zvýrazniť niektorý prvok ako „prvý“ nastavením špeciálneho ukazovateľa. Vyžaduje sa to napríklad preto, aby sa zabránilo "zacykleniu" pri prezeraní zoznamu.

Ryža. 1. Cyklický jednosmerný zoznam

Základné operácie vykonávané s cyklickým jednosmerným zoznamom:

vytvorenie zoznamu;

tlač (prezeranie) zoznamu;

Vloženie prvku do zoznamu

vyhľadať prvok v zozname;

Kontrola, či je zoznam prázdny

vymazanie zoznamu.

Na opísanie algoritmov pre tieto základné operácie použijeme rovnaké deklarácie ako pre lineárny jednoducho prepojený zoznam.

Uveďme si funkcie uvedených základných operácií pri práci s cyklickým jednosmerným zoznamom.

//vytvorí kruhový jednotlivo orientovaný zoznam

void Make_Circle_Single_List(int n,

Circle_Single_List** Head,Circle_Single_List* Slučka)(

(*Hlava) = new Circle_Single_List();

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

cin >> (*Head)->Data;

(*Hlava)->

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

//vytlačí kruhový jednotlivo orientovaný zoznam

void Print_Circle_Single_List(Circle_Single_List* Head) (

Circle_Single_List* ptr=Hlava;

//pomocný ukazovateľ

cout<< ptr->Údaje<< "\t";

ptr=ptr->Ďalší;

) while (ptr!=Hlava);

cout<< "\n";

/*vložiť prvok za dané číslo do kruhového zoznamu s jednoduchým odkazom*/

Circle_Single_List* Insert_Item_Circle_Single_List(Circle_Single_List* Head,

int Number, int DataItem)(

//stoj na prvom prvku

Circle_Single_List *NewItem = new(Circle_Single_List);

//vytvoril nový prvok

NewItem->Data = DataItem;

NováPoložka->Ďalšia = Nová položka;

else (// zoznam nie je prázdny

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

Prúd = Prúd->Ďalší;

NováPoložka->Ďalšia = Aktuálna->Ďalšia;

Aktuálny->Ďalší = NováPoložka;

/*odstráni prvok s daným číslom z cyklického jednosmerného zoznamu*/

Circle_Single_List* Delete_Item_Circle_Single_List

(Circle_Single_List* Head, int Number)(

if (hlava != NULL)(

Circle_Single_List *Current = Head;

if (Hlava->Ďalší != Hlava)(

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

Prúd = Prúd->Ďalší;

while (ptr->Next != Aktuálne)

ptr = ptr->Ďalší;

//okamžité odstránenie prvku

ptr->Ďalší = Aktuálny->Ďalší;

if (Hlava = Prúd) Hlava = Prúd->Ďalší;

delete(Aktuálne);

delete(Aktuálne);

//vyhľadá prvok v kruhovom, jednotlivo orientovanom zozname

bool Find_Item_Circle_Single_List(Circle_Single_List* Hlava,

Circle_Single_List *ptr = Head;

//pomocný ukazovateľ

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

else ptr = ptr->Ďalší;

while (ptr != Hlava);

//skontrolujeme, či je cyklický jednotlivý zoznam prázdny

bool Empty_Circle_Single_List(Circle_Single_List* Head)(

//odstráni kruhový jednotlivo orientovaný zoznam

void Delete_Circle_Single_List(Circle_Single_List* Head)(

if (hlava != NULL)(

Head = Delete_Item_Circle_Single_List(Head, 1);

Delete_Circle_Single_List(Head);

Kruhový dvojitý zoznam podobný lineárnemu obojsmernému zoznamu, ale každý jeho prvok má dva ukazovatele, z ktorých jeden ukazuje na nasledujúci prvok v zozname a druhý ukazuje na predchádzajúci prvok (obr. 2).

Obr.2. Kruhový dvojitý zoznam

Hlavné operácie vykonávané s cyklickým dvojitým zoznamom:

vytvorenie zoznamu;

tlač (prezeranie) zoznamu;

Vloženie prvku do zoznamu

odstránenie prvku zo zoznamu;

hľadať prvok v zozname

Kontrola, či je zoznam prázdny

vymazanie zoznamu.

Na popis algoritmov pre tieto základné operácie použijeme rovnaké deklarácie ako pre lineárny obojsmerný zoznam.

Uveďme si funkcie uvedených základných operácií pri práci s cyklickým obojsmerným zoznamom.

//vytvorte cyklický obojsmerný zoznam

Circle_Double_List* Make_Circle_Double_List(int n,

Circle_Double_List** Head,Circle_Double_List* Slučka)(

Circle_Double_List* ptr;//pomocný ukazovateľ

(*Hlava) = new Circle_Double_List();

//pridelenie pamäte pre nový prvok

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

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

cin >> (*Head)->Data;

//zadajte hodnotu informačného poľa

(*Head)->Next=NULL;//vynulovanie poľa adresy

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

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

(*Hlava)->Ďalšia->Predchádzajúca = (*Hlava);

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

(*Hlava)->Prior = ptr;

if (ptr == NULL)

else return ptr;

//vytlačenie kruhového obojsmerného zoznamu

void Print_Circle_Double_List(Circle_Double_List* Head) (

Circle_Double_List* ptr=Hlava;

//pomocný ukazovateľ

cout<< ptr->Údaje<< "\t";

ptr=ptr->Ďalší;

) while (ptr!=Hlava);

cout<< "\n";

/*vložiť prvok za dané číslo do kruhového dvojitého zoznamu*/

Circle_Double_List* Insert_Item_Circle_Double_List

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

//stoj na prvom prvku

Circle_Double_List *NewItem = new(Circle_Double_List);

//vytvoril nový prvok

NewItem->Data = DataItem;

if (Head == NULL) (//zoznam je prázdny

NováPoložka->Ďalšia = Nová položka;

NováPoložka->Predchádzajúca = NováPoložka;

else (// zoznam nie je prázdny

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

Prúd = Prúd->Ďalší;

NováPoložka->Ďalšia = Aktuálna->Ďalšia;

Aktuálny->Ďalší = NováPoložka;

NováPoložka->Predchádzajúca = Aktuálny;

NováPoložka->Ďalšia->Predchádzajúca = Nová položka;

/*odstráni prvok s daným číslom z cyklického dvojitého zoznamu*/

Circle_Double_List* Delete_Item_Circle_Double_List(Circle_Double_List* Head,

if (hlava != NULL)(

Circle_Double_List *Current = Head;

if (Hlava->Ďalší != Hlava)(

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

Prúd = Prúd->Ďalší;

Circle_Double_List *ptr = Aktuálny->Ďalší;

Aktuálny->Predchádzajúci->Ďalší = Aktuálny->Ďalší;

Aktuálny->Ďalší->Predchádzajúci = Aktuálny->Predchádzajúci;

if (Head = Current) //odstráni prvý

Hlava = Prúd->Ďalší;

delete(Aktuálne);

delete(Aktuálne);

//hľadanie prvku v kruhovom dvojitom zozname

bool Find_Item_Circle_Double_List(Circle_Double_List* Hlava,

Circle_Double_List *ptr = Hlava;

//pomocný ukazovateľ

if (DataItem == ptr->Data)

else ptr = ptr->Ďalší;

while (ptr != Hlava);

// skontrolujte, či je kruhový dvojitý zoznam prázdny

bool Empty_Circle_Double_List(Circle_Double_List* Head)(

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

//odstráni kruhový dvojitý zoznam

void Delete_Circle_Double_List(Circle_Double_List* Head)(

if (hlava != NULL)(

Head = Delete_Item_Circle_Double_List(Head, 1);

Delete_Circle_Double_List(Head);