Kruhový dvojitý zoznam. Jednotne prepojený cyklický zoznam. Jednotne prepojená implementácia kruhového zoznamu

Ak chcete získať prístup k požadovanému prvku lineárneho zoznamu, musíte zoznam zobraziť od začiatku bez ohľadu na polohu pôvodného bodu zobrazenia. To spomaľuje operácie prístupu k prvkom v zozname. Uzavretie prvkov zoznamu do kruhu odstraňuje túto nevýhodu. Takýto zoznam sa nazýva cyklický. Kruhový zoznam môžete začať prezerať z akéhokoľvek prvku, nielen od jeho začiatku, pričom začiatkom zoznamu môže byť ktorýkoľvek z jeho prvkov. Logická štruktúra kruhového zoznamu:

1. Operácie na cyklickom zozname

Nad kruhovým zoznamom s možno vykonať všetky operácie definované pre lineárny zoznam. Všimnite si, že v logickej štruktúre cyklického zoznamu sú pojmy „začiatok“ a „koniec“ podmienené a sú určené polohou ukazovateľa na niektorý prvok zoznamu, ktorým je hlavička.

Pre cyklický zoznam sa zavádza aj nová operácia - zreťazenie dvoch cyklických zoznamov - Сoncat(s 1,s 2).

1. Jednotne prepojená implementácia kruhového zoznamu

Implementácia kruhového zoznamu pomocou dynamických premenných:

Takýto zoznam sa nazýva jednoducho prepojený kruhový zoznam. Z ktoréhokoľvek prvku zoznamu sa môžete dostať k akémukoľvek inému prvku. Upozorňujeme, že kruhový zoznam nemá prvý a posledný prvok. Externý ukazovateľ Head je vhodný na použitie ako ukazovateľ na aktuálny prvok zoznamu. Pri riešení konkrétnych problémov môžeme konvenčne predpokladať, že rieši posledný prvok zoznamu, vďaka čomu bude prvok automaticky nasledovať ako prvý.

Triedu tCircleList možno opísať takto:

tHodnota= Skutočná; // typ hodnoty prvku zoznamu - real

pItem= ^tItem; // typ ukazovateľa na prvok zoznamu

tItem= záznam// typ prvku zoznamu

Hodnota: tValue; // obsah prvku zoznamu

Ďalej: pItem; // ukazovateľ na ďalší prvok zoznamu

koniec; //záznam tItem

tCircleList= trieda // Trieda - cyklický zoznam

chránené

fHead:pItem; // lúka - ukazovateľ naaktuálny prvokzoznam

fSize:Word; // pole - počet prvkov zoznamu

verejnosti

// Vlastnosť - počet prvkov zoznamu (prístup na čítanie a zápis)

nehnuteľnosť Veľkosť: Word čítať fSize písať fSize;

// Vlastnosť – ukazovateľ na začiatok zoznamu (prístup na čítanie a zápis)

nehnuteľnosť Hlava: Slovo čítať fHlava písať fHead;

vza prvkom adresyAdr

postup InsertAfter(Addr: pItem; v: tValue);

// Zahrňte prvok s hodnotouvpred prvkom adresyAdr

postup InsertBefore(Addr: pItem; v: tValue);

// Vylúčte prvok nasledujúci za prvkom s adresou Addr

funkciu DeleteAfter(Addr: pItem): tValue;

// Vylúčenie prvku s ukazovateľomAdr

funkciu Delete(Addr:pItem):tValue;

// Zahrňte prvok s hodnotouvna začiatok zoznamu

postup InsertHead(v:tValue);

// Zahrňte prvok s hodnotouvna koniec zoznamu

postup InsertRear(v:tValue);

// Vylúčenie prvku zo začiatku zoznamu

funkciu DeleteHead:tValue;

// Vylúčenie prvku z konca zoznamu

funkciu DeleteRear:tValue;

postup Concat( var CList2: tCircleList); // spojka s zoznamCList2

// Vyhľadajte v zozname prvok s hodnotouva vrátenie jeho adresy

funkciu Search(v: tValue): pItem;

funkciu Prázdne: Boolean; // vrátiťpravda,Ak zoznam prázdny

postup Jasný; // vymazanie zoznamu

konštruktér Vytvorte; // konštruktor - vytvorenie prázdneho zoznamu

deštruktor Zničiť; prepísať; // deštruktor - vymazanie zoznam

koniec; // triedatCircleList

Trieda tCircleList nie je deklarovaná ako potomok triedy tList, pretože implementácia takmer všetkých jej metód sa líši od implementácie metód s rovnakým názvom pre necyklický zoznam. Rozdiely sú hlavne nasledovné:

– pri operáciách InsertAfter a InsertBefore sa zaradenie prvku do prázdneho zoznamu a zaradenie na začiatok a koniec cyklického zoznamu vykonáva odlišne;

– použitie operácie DeleteAfter na cyklický zoznam pozostávajúci z jedného prvku by nemalo viesť k vylúčeniu tohto prvku samotného;

– metódy DeleteAfter a Delete musia obnoviť ukazovateľ na posledný prvok cyklického zoznamu, ak sa počas týchto operácií odstráni;

– pri metódach Search a Clear je znakom dokončenia prehľadávania cyklického zoznamu, keď pomocný ukazovateľ dosiahne prvok, od ktorého sa začalo prehľadávanie.

A iba konštruktor Create a Destroy sú implementované rovnakým spôsobom ako metódy s rovnakým názvom v triede tList.

Je zrejmé, že operácie zahrnutia a vylúčenia vpravo a vľavo od aktuálneho prvku (InsertHead, InsertRear, DeleteHead, DeleteRear) vykonávajú rovnaké akcie ako operácie s rovnakým názvom pre necyklický zoznam. Rozdiel je v tom, že nové operácie zmenia hodnotu ukazovateľa na posledný prvok kruhového zoznamu, ak sa zoznam rozšíril doľava alebo doprava, alebo sa zúžil doľava alebo doprava.

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

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

zoznam štruktúr
{
int pole; // dátové pole
zoznam štruktúr *ptr; // ukazovateľ na ďalší prvok
};

Hlavné akcie vykonávané na prvkoch centrálneho digitálneho systému:

• Inicializácia zoznamu
• Pridanie uzla do zoznamu
• Odstránenie uzla zo zoznamu
• Zobrazujú sa položky zoznamu
• Výmena dvoch uzlov zoznamu

Keďže zoznam je kruhový, implementácia samostatnej funkcie na odstránenie koreňa zoznamu nie je potrebná.

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;
// pridelí pamäť koreňu 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 OCS

Funkcia na pridanie uzla do zoznamu má dva argumenty:

• Ukazovateľ na prvok, za ktorým dôjde k pripojeniu
• Údaje pre prvok, ktorý sa má pridať.

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


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

• vytvorenie uzla, ktorý sa má pridať, a vyplnenie jeho dátového poľa;
• resetovanie ukazovateľa uzla predchádzajúceho uzlu, ktorý sa pridáva, do pridávaného uzla;
• nastavenie ukazovateľa pridaného uzla do nasledujúceho uzla (toho, na ktorý ukazuje predchádzajúci uzol).

Funkcia pridania uzla do OCS 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 ďalší 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 OCS

Ako argumenty funkcie na vymazanie uzla OCS sa odovzdá ukazovateľ na uzol, ktorý sa má vymazať. Keďže zoznam je kruhový, nie je potrebné posúvať ukazovateľ na koreň zoznamu.

Funkcia vráti ukazovateľ na uzol vedľa uzla, ktorý sa odstraňuje.

Odstránenie uzla môže byť znázornené nasledujúcim diagramom:

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

• nastavenie ukazovateľa predchádzajúceho uzla na uzol, ktorý nasleduje po vymazanom uzle;
• uvoľnenie pamäte vymazávaného uzla.

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

zoznam štruktúr * deletelem(list *lst)
{
zoznam štruktúr *temp;
teplota = lst;
while (temp->ptr != lst) // prezrite si zoznam od koreňového adresára
{ // kým nenájdeme uzol predchádzajúci lst
temp = temp->ptr;
}
temp->ptr = lst->ptr; // preusporiadať ukazovateľ
free(lst); // uvoľní pamäť vymazávaného uzla
return(temp);
}

Výstup prvkov OCS

Funkcia pre výstup prvkov OCS je podobná funkcii pre OLS, až na podmienku pre ukončenie prechodu prvkov.
Ukazovateľ na koreň zoznamu sa odovzdá ako argument do funkcie výstupu prvku.
Funkcia postupne prechádza všetkými uzlami a zobrazuje ich hodnoty.

1
2
3
4
5
6
7
8
9

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

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

Výmena uzlov OCS

Ako argumenty funkcia výmeny OCS berie dva ukazovatele na uzly, ktoré sa vymieňajú, 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. Na to je potrebné určiť predchádzajúci a nasledujúci uzol pre každý nahradený. V tomto prípade sú možné dve situácie:

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

Pri výmene susedných uzlov vyzerá preinštalovanie ukazovateľov takto:


Pri výmene uzlov, ktoré nesusedia, preinštalovanie ukazovateľov vyzerá takto:

Pri resetovaní 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);
}

Text prednášky.

Štruktúrované dátové typy, ako sú polia, množiny, záznamy, sú statické štruktúry, pretože ich veľkosti zostávajú počas vykonávania programu nezmenené. Dátové štruktúry sú často potrebné zmeniť svoju veľkosť, keď sa problém vyrieši. 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 potrebný na riešenie problémov.

Pomocou typov štruktúr, 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ý určitý typ štruktúry 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 počas vykonávania programu ako názov „root“ (rodičovského mena) dynamickej štruktúry. Počas vykonávania programu, keď sa vytvára dynamická štruktúra, sú požadované dynamické premenné vhodných typov a prepojené odkazmi, počnúc premennou d alebo prvou dynamickou premennou, na ktorú premenná d obsahuje ukazovateľ. Tento prístup vám umožňuje vytvoriť dynamickú štruktúru s akoukoľvek topológiou.

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

Hlavnou črtou tejto organizácie je, že v tomto zozname nie sú žiadne prvky, ktoré by obsahovali nulové ukazovatele, a preto nie je možné vybrať najvzdialenejšie prvky.

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

Kruhový jednosmerný zoznam je podobný lineárnemu jednosmerné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. Koncept „prvého“ prvku je tu dosť svojvoľný a nie vždy sa vyžaduje. Aj keď niekedy je užitočné zvýrazniť niektorý prvok ako „prvý“ umiestnením špeciálneho ukazovateľa. Vyžaduje sa to napríklad, aby sa zabránilo „zacykleniu“ pri prezeraní zoznamu.

Ryža. 1. Kruhový jednosmerný zoznam

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

· vytvorenie zoznamu;

· vytlačiť (zobraziť) zoznam;

· vloženie prvku do zoznamu;

· vyhľ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 jednosmerný zoznam.

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

//vytvor kruhový jednosmerný 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ý jednosmerný 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 jednosmerného zoznamu*/

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ánenie prvku s daným číslom z kruhové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 (Head->Next != Head)(

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

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

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

ptr = ptr->Ďalší;

//priame odstránenie prvku

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

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

delete(Aktuálne);

delete(Aktuálne);

//hľadanie prvku v kruhovom jednosmernom zozname

bool Find_Item_Circle_Single_List(Circle_Single_List* Head,

Circle_Single_List *ptr = Head;

//pomocný ukazovateľ

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

else ptr = ptr->Ďalší;

while (ptr != Hlava);

//kontrola prázdnoty kruhového jednosmerného zoznamu

bool Empty_Circle_Single_List(Circle_Single_List* Head)(

//odstránenie kruhového jednosmerného zoznamu

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 je podobný lineárnemu dvojitému zoznamu, ale každý prvok má dva ukazovatele, jeden ukazuje na nasledujúci prvok v zozname a druhý ukazuje na predchádzajúci prvok (obrázok 2).

Obr.2. Kruhový dvojitý zoznam

Základné operácie vykonávané s kruhovým obojsmerným zoznamom:

· vytvorenie zoznamu;

· vytlačiť (zobraziť) zoznam;

· vloženie prvku do zoznamu;

· odstránenie prvku zo zoznamu;

· vyhľ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.

//vytvor kruhový dvojitý 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čí kruhový dvojitý zoznam

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 obojsmerné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ánenie prvku s daným číslom z kruhového obojsmerného zoznamu*/

Circle_Double_List* Delete_Item_Circle_Double_List(Circle_Double_List* Head,

if (hlava != NULL)(

Circle_Double_List *Current = Head;

if (Head->Next != Head)(

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

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

bool Empty_Circle_Double_List(Circle_Double_List* Head)(

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

//odstránenie kruhového dvojitého zoznamu

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

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

Cieľ prednášky: štúdium algoritmov a techník 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ú počas vykonávania programu nezmenené. Dátové štruktúry sú často potrebné zmeniť svoju veľkosť, keď sa problém vyrieši. 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 potrebný 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 statickej deklarované premenné alebo na zmesi statických a dynamické premenné. Myšlienka usporiadania všetkých dynamických štruktúr je rovnaká. Je definovaný určitý typ štruktúry 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 počas vykonávania programu ako názov „root“ (rodičovského mena) dynamickej štruktúry. Pri vykonávaní programu, keď sa buduje dynamická štruktúra, sa vytvárajú požiadavky dynamické premenné zodpovedajúce typy a sú prepojené odkazmi, začí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

Kruhový (krúžkový) zoznam- Toto 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 tejto organizácie je, že v tomto zozname nie sú žiadne prvky, ktoré by obsahovali nulové ukazovatele, a preto nie je možné vybrať najvzdialenejšie prvky.

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

Podobne ako pri lineárnom jednosmernom zozname, 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 dosť svojvoľný a nie vždy sa vyžaduje. Hoci niekedy je užitočné zvýrazniť niektorý prvok ako „prvý“ umiestnení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:

• vytvorenie zoznamu;
• vytlačiť (zobraziť) zoznam;
• vloženie prvku do zoznamu;
• vymazanie prvku zo zoznamu;
• hľadanie prvku 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 jednosmerný zoznam.

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

//vytvorenie cyklického jednosmerného zoznamu 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 ( Slučka = = NULL) Slučka = (*Hlava); cout<< "Введите значение "; cin >> (*Hlava)->Údaje; //zadajte hodnotu informačného poľa (*Head)->Next=NULL; //vynulovanie poľa adresy Make_Circle_Single_List(n-1,&((*Head)->Next),Loop); ) else ( (*Head) = Loop; ) ) //vytlačí kruhový jednosmerný zoznam 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 NewItem->Next = NewItem; Head = NewItem; ) 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ánenie prvku s daným číslom z kruhového jednosmerné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; //priame 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; ) //hľadanie prvku v cyklickom jednosmernom 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; ) //kontrola prázdnoty kruhového jednosmerného zoznamu bool Empty_Circle_Single_List(Circle_Single_List* Head)( return (Head != NULL ? false: true); ) //odstránenie kruhového jednosmerné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);

Podobne ako pri lineárnom dvojitom zozname, ale každý prvok má dva ukazovatele, jeden ukazuje na nasledujúci prvok v zozname a druhý ukazuje na predchádzajúci prvok (obrázok 32.2).

Ryža. 32.2.

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

• vytvorenie zoznamu;
• vytlačiť (zobraziť) zoznam;
• vloženie prvku do zoznamu;
• vymazanie prvku zo zoznamu;
• hľadanie prvku 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árne obojsmerný zoznam.

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

//vytvorenie cyklického zdvojeného zoznamu 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)_ new Circle_Head / alokovať pamäť pre nový prvok if (Loop == NULL) Loop = (*Head); cout<< "Введите значение "; cin >> (*Hlava)->Údaje; //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) (*Head)->Next->Prior = (*Head); if ((*Head)->Prior == NULL) (*Head)->Prior = ptr; if (ptr == NULL) return *Head; else return ptr; ) else ( (*Head) = Loop; return NULL; ) ) //vytlačí kruhový dvojitý zoznam 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ánenie prvku s daným číslom z cyklického dvojité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 (Circle_Double_List) = 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 (Hlava = Aktualna) //zmazanie prvej Hlavy = Aktualne->Nasleduje; delete(Aktuálne); ) else( Head = NULL; delete(Current); ) ) return Head; ) //hľadanie prvku v cyklickom dvojito orientovanom 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; ) //kontrola, či je cyklický dvojitý zoznam prázdny bool Empty_Circle_Double_List(Circle_Double_List* Head)( return (Head != NULL ? false: true) ; ) //vymazanie 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);(Head2_List)

Posledná aktualizácia: 25.10.2016

Kruhové (kruhové, cyklické) zoznamy sú typom prepojených zoznamov. Môžu byť jednoducho spojené alebo dvojité. Ich charakteristickým znakom je, že podmienený posledný prvok ukladá odkaz na prvý prvok, takže zoznam sa ukáže ako uzavretý alebo kruhový.

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

Head.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 kruhového zoznamu:

Používanie System.Collections; pomocou System.Collections.Generic; menný priestor SimpleAlgorithmsApp ( verejná trieda CircularLinkedList :IEpočetné // zoznam prepojených zvonení ( 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 premennú chvost, ak (aktuálny == chvost) chvost = predchádzajúci; ) else // ak sa vymaže 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 v podstate znamená prestavenie ukazovateľa na posledný prvok chvosta a umiestnenie nového prvku 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 z 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 premennú chvost, ak (aktuálny == chvost) chvost = predchádzajúci; ) else // ak sa vymaže 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; )

Pomocou kruhového zoznamu:

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("\nPo odstránení:\n"); foreach (položka var v kruhovom zozname) ( Console.WriteLine(item); )

Výstup na konzolu:

Tom Bob Alice Jack Po odstránení: Tom Alice Jack