Anotácia: Prednáška pojednáva o definíciách, metódach deklarácie, inicializácie a vlastnostiach použitia pri riešení problémov kruhových zoznamov, balíčkov, červeno-čiernych stromov, príkladov riešenia problémov pri spracovávaní zoznamov krúžkov, balíčkov, červeno-čiernych stromov.
Účel prednášky: naučiť sa algoritmy a techniky pre prácu s dynamické dátové štruktúry, sa naučia riešiť problémy pomocou dynamických dátových štruktúr a algoritmov na prácu s nimi v C ++.
Štruktúrované dátové typy, ako sú polia, množiny, záznamy, sú statické štruktúry, pretože ich veľkosť zostáva nezmenená počas celej doby vykonávania programu. Počas riešenia problému sa často vyžaduje, aby dátové štruktúry zmenili svoju veľkosť. Takéto dátové štruktúry sa nazývajú dynamické a zahŕňajú zásobníky, fronty, zoznamy, stromy a ďalšie. Opis dynamických štruktúr pomocou polí, záznamov a súborov vedie k zbytočnému využívaniu pamäte a zvyšuje čas na riešenie problémov.
Použitím štrukturálne typy, ukazovatele a dynamické premenné, môžete vytvoriť rôzne dynamické pamäťové štruktúry. Vlastnosti ukazovateľov v jazyku C ++ vám umožňujú budovať dynamické pamäťové štruktúry založené na statickom zobrazení 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ý štrukturálny typ S, z ktorých jedno alebo viac polí je deklarovaných ako ukazovatele na rovnaký alebo iný štrukturálny typ. Program deklaruje premennú d typu S alebo premennú typu ukazovateľ na S v prípade plne dynamického vytvorenia štruktúry. Názov tejto premennej počas vykonávania programu sa používa ako názov „koreňa“ (nadradeného názvu) dynamickej štruktúry. Pri vykonávaní programu, ako sa buduje dynamická štruktúra, dynamické premenné zodpovedajúcich typov a sú prepojené odkazmi, počnúc premennou d alebo prvou dynamická premenná, ktorého ukazovateľ je obsiahnutý v premennej d. Tento prístup umožňuje vytvoriť dynamickú štruktúru s ľubovoľnou topológiou.
Smyčkové (kruhové) zoznamy
Cyklický (kruhový) zoznam- Toto dátová štruktúra, čo je postupnosť prvkov, z ktorých posledný obsahuje ukazovateľ na prvý prvok zoznamu a prvý (v prípade obojsmerný zoznam) - na posledný.
Hlavným rysom tejto organizácie je, že v tomto zozname nie sú žiadne prvky, ktoré obsahujú nulové ukazovatele, a preto nie je možné zvoliť krajné prvky.
Cyklické zoznamy, ako aj lineárne, sú jednosmerné a obojsmerný.
Podobne ako lineárny jednosmerný zoznam, ale jeho posledný prvok obsahuje ukazovateľ, ktorý ho spája s prvým prvkom (obrázok 32.1).
Na úplný prechod takýmto zoznamom 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ť určitý prvok ako „prvý“ nastavením špeciálneho ukazovateľa. Je to potrebné napríklad na zabránenie opakovaniu sa počas prehľadávania zoznamu.
Ryža. 32.1.
Základné operácie vykonávané s kruhovým jednosmerným zoznamom:
- vytvorenie zoznamu;
- tlač (prezeranie) zoznamu;
- vloženie položky do zoznamu;
- vymazanie položky zo zoznamu;
- vyhľadať položku 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 jednosmerný zoznam.
Predstavme si funkcie uvedených základných operácií pri práci s cyklickým jednosmerným zoznamom.
// vytvorí cyklický jednosmerný zoznam void Make_Circle_Single_List (int n, Circle_Single_List ** Head, Circle_Single_List * Loop) (if (n> 0) ((* Head) = new Circle_Single_List (); // pridelí pamäť novému prvku if ( Loop = = NULL) Loop = (* Head); cout<< "Введите значение "; cin >> (* Head) -> Data; // zadajte hodnotu informačného poľa (* Head) -> Next = NULL; // vynulovanie adresného poľa Make_Circle_Single_List (n-1, & ((* Head) -> Next), Loop); ) else ((* Head) = Loop;)) // tlač cyklické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) (// list is empty NewItem-> Next = NewItem; Head = NewItem;) else (// list is not empty for (int i = 1; i< Number; i++) Current = Current->Ďalšie; NewItem-> Next = Current-> Next; Current-> Next = NewItem; ) návratová hlava; ) / * vymazať položku 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 (Head! = NULL) (Circle_Single_List * Current = Head; if (Head->< Number; i++) Current = Current->Ďalšie; Circle_Single_List * ptr = Head; while (ptr-> Ďalej! = Aktuálne) ptr = ptr-> Ďalej; // priame vymazanie prvku ptr-> Next = Current-> Next; if (Head = Current) Head = Current-> Next; vymazať (aktuálne); ) else (Head = NULL; delete (Current);)) návrat Head; ) // hľadanie položky 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) vráti true; else ptr = ptr-> Ďalej;) while (ptr! = Head); return false;) // kontrola prázdnosti kruhového jednosmerného zoznamu bool Empty_Circle_Single_List (Circle_Single_List * Head) (return (Head! = NULL? False: true);) // vymazanie kruhového jednosmerného zoznamu neplatné Delete_Circle_Single_List (Circle_Single_List * Head) (if (Head! = NULL) (Head = Delete_Item_Circle_Single_List (Head, 1); Delete_Circle_Single_List (Head);)) Zoznam 1.
Vyzerá to ako lineárny obojsmerný zoznam, ale akýkoľvek jeho prvok má dva ukazovatele, jeden smerujúci na ďalší prvok v zozname a druhý smerujúci k predchádzajúcemu prvku (obrázok 32.2).
Ryža. 32.2.
Základné operácie vykonávané s cyklickým obojsmerný zoznam:
- vytvorenie zoznamu;
- tlač (prezeranie) zoznamu;
- vloženie položky do zoznamu;
- vymazanie položky zo zoznamu;
- vyhľadať položku v zozname
- kontrola, či je zoznam prázdny;
- vymazanie zoznamu.
Na popísanie algoritmov pre tieto základné operácie použijeme rovnaké deklarácie ako pre lineárne obojsmerný zoznam.
Predstavme si funkcie uvedených základných operácií pri práci s cyklikou obojsmerný zoznam.
// vytvorenie kruhového obojsmerné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) ((* Head) = nový Circle_Double_List (); / / prideliť pamäť novému prvku if (Loop == NULL) Loop = (* Head); cout<< "Введите значение "; cin >> (* Head) -> Data; // zadajte hodnotu informačného poľa (* Head) -> Next = NULL; // vynulovanie adresného poľa 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;)) // tlač cyklického obojsmerné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 NewItem-> Next = NewItem; NewItem-> Prior = NewItem; Head = NewItem;) else (// zoznam nie je prázdny pre (int i = 1; i< Number; i++) Current = Current->Ďalšie; NewItem-> Next = Current-> Next; Current-> Next = NewItem; NewItem-> Prior = aktuálny; NewItem-> Next-> Prior = NewItem; ) návratová hlava; ) / * vymazanie položky s daným číslom z cyklického obojsmerné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-> Next!) = Hlava) (pre (int i = 1; i< Number; i++) Current = Current->Ďalšie; Circle_Double_List * ptr = Current-> Next; Current-> Prior-> Next = Current-> Next; Current-> Next-> Prior = Current-> Prior; if (Head = Current) // odstráni prvý Head = Current-> Next; vymazať (aktuálne); ) else (Head = NULL; delete (Current);)) návrat Head; ) // vyhľadať položku 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) vráti true; else ptr = ptr-> Ďalej;) while (ptr! = Head); return false;) // skontrolujte, či je kruhový obojsmerný zoznam prázdny bool Empty_Circle_Double_List (Circle_Double_List * Head) (return (Head! = NULL? False: true);) / / odstrániť kruhový obojsmerný zoznam neplatný Delete_Circle_Double_List (Circle_Double_List * Head) (if (Head! = NULL) (Head = Delete_Item_Circle_Double_List (Head, 1); Delete_Circle_Double_List (Head);)) Zoznam 2.
Ak chcete získať prístup k požadovanému prvku lineárneho zoznamu, musíte zobraziť zoznam od jeho začiatku bez ohľadu na pozíciu pôvodného hľadiska. To spomaľuje operácie pri prístupe k položkám v zozname. Uzavretie prvkov zoznamu do krúžku túto nevýhodu eliminuje. Takýto zoznam sa nazýva kruhový. Kruhový zoznam môžete začať prezerať z ľubovoľného prvku, nielen od jeho začiatku. Začiatok zoznamu môže byť akýkoľvek z jeho prvkov. Logická štruktúra cyklického zoznamu:
Operácie s cyklickým zoznamom
Nad kruhovým zoznamom s možno vykonať všetky operácie definované pre lineárny zoznam. Upozorňujeme, že v logickej štruktúre cyklického zoznamu sú pojmy „začiatok“ a „koniec“ podmienené a sú určené pozíciou ukazovateľa na niektorý prvok zoznamu, ktorým je nadpis.
Pre kruhový zoznam sa zavádza aj nová operácia - zreťazenie dvoch kruhových zoznamov - Сoncat(s 1,s 2).
Samostatne prepojená implementácia zoznamu opakovaných cyklov
Implementácia cyklického zoznamu pomocou dynamických premenných:
Takýto zoznam sa nazýva jednoducho prepojený cyklický zoznam... Akýkoľvek ďalší prvok je prístupný z ktorejkoľvek položky v zozname. Upozorňujeme, že cyklický zoznam nemá žiadne prvé a posledné prvky. Externý ukazovateľ pointerHead je vhodné používať ako ukazovateľ na aktuálny prvok zoznamu. Pri riešení konkrétnych problémov možno podmienečne považovať za ich riešenie posledný položka zoznamu, ktorá automaticky urobí nasledujúcu položku prvou.
Triedu tCircleList možno opísať takto:
tValue = Real; // typ hodnoty položky zoznamu - skutočný
pItem = ^ tItem; // typ ukazovateľa na položku v zozname
tItem = záznam// typ položky zoznamu
Hodnota: tValue; // obsahová časť položky zoznamu
Ďalej: pItem; // ukazovateľ na nasledujúcu položku v zozname
koniec; // záznam tItem
tCircleList = trieda // Trieda - cyklický zoznam
chránené
fHead: pItem; // lúka - ukazovateľ naaktuálna položkazoznam
fVeľkosť: Word; // pole - počet položiek v zozname
verejné
// Vlastnosť - počet položiek v zozname (prístup na čítanie a zápis)
nehnuteľnosť Veľkosť: Word čítať fVeľkosť napíš fSize;
// Vlastnosť - ukazovateľ na začiatok zoznamu (prístup na čítanie a zápis)
nehnuteľnosť Hlava: Slovo čítať fHlava napíš fHead;
vza prvkom s adresouAddr
postup InsertAfter (Addr: pItem; v: tValue);
// Zahrňte prvok s hodnotouvpred prvkom s adresouAddr
postup InsertBefore (Addr: pItem; v: tValue);
// Vylúčte prvok nasledujúci za prvkom s adresou Addr
funkcie DeleteAfter (Addr: pItem): tValue;
// Vylúčte prvok s ukazovateľomAddr
funkcie Odstrániť (Addr: položka): 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účiť položku zo začiatku zoznamu
funkcie DeleteHead: tValue;
// Vylúči položku z konca zoznamu
funkcie DeleteRear: tValue;
postup Concat ( var CList2: tCircleList); // spojka s zoznamZoznam2
// Vyhľadá v zozname prvok s hodnotouva vrátenie jeho adresy
funkcie Vyhľadávanie (v: tValue): pItem;
funkcie Prázdne: Boolean; // návratpravda,ak zoznam prázdny
postup Jasný; // vymaže zoznam
konštruktér Vytvoriť; // konštruktor - vytvorenie prázdneho zoznamu
deštruktor Zničiť; prepísať; // deštruktor - vypustenie zoznam
koniec; // triedatCircleList
Trieda tCircleList nie je vyhlásená za dediča 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 nasledujúce:
- pre operácie InsertAfter a InsertBefore je prvok zahrnutý v prázdnom zozname a na začiatku a na konci cyklického zoznamu je zahrnutý iným spôsobom;
- použitie operácie DeleteAfter pre cyklický zoznam pozostávajúci z jedného prvku by nemalo viesť k vymazaniu tohto prvku samotného;
- metódy DeleteAfter a Delete musia obnoviť ukazovateľ na posledný prvok cyklického zoznamu, ak je počas týchto operácií vylúčený;
- v metódach Search a Clear je znakom dokončenia zobrazenia cyklického zoznamu to, že pomocný ukazovateľ dosiahne prvok, od ktorého sa zobrazenie začalo.
A iba konštruktor Create a Destroy destructor sú implementované rovnakým spôsobom ako metódy triedy tList s rovnakým názvom.
Je zrejmé, že operácie začlenenia a vylúčenia napravo a naľ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 zúžil doľava alebo doprava.
Každý uzol jednosmerného (jednotlivo prepojeného) kruhového zoznamu (CCL) obsahuje jedno pole smerníka na nasledujúci uzol. Posledné pole ukazovateľa uzla obsahuje adresu koreňového prvku.
Uzol OCN môže byť znázornený ako štruktúra podobná samostatne prepojený lineárny zoznam
zoznam štruktúr
{
int pole; // dátové pole
zoznam štruktúr * ptr; // ukazovateľ na nasledujúci prvok
};
Hlavné činnosti vykonávané na prvkoch OCP:
- Inicializácia zoznamu
- Pridanie uzla do zoznamu
- Odstránenie uzla zo zoznamu
- Zobrazujú sa položky zoznamu
- Zamieňajte dva uzly zoznamu
Pretože je zoznam kruhový, 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, v ktorom pole ukazovateľa na nasledujúci prvok obsahuje adresu samotného koreňového prvku. 
1
2
3
4
5
6
7
8
9
štruktúrovaný zoznam * init (int a) // a- hodnota prvého uzla
{
zoznam štruktúr * lst;
// prideliť pamäť koreňu zoznamu
lst = (struct list *) malloc (sizeof (struct list));
lst-> pole = a;
lst-> ptr = lst; // ukazovateľ na samotný koreňový uzol
návrat (lst);
}
Pridanie uzla do súboru bcc
Funkcia pridania uzla do zoznamu má dva argumenty:
- Ukazovateľ na prvok, po ktorom dôjde k pridaniu
- Údaje pre pridanú položku.
Postup pridania prvku je možné zobraziť na nasledujúcom diagrame: 
Pridanie položky do OCP zahrnuje nasledujúce kroky:
- vytvorenie pridaného uzla a vyplnenie jeho údajového poľa;
- resetovanie ukazovateľa uzla predchádzajúceho pridanému k pridanému uzlu;
- nastavenie ukazovateľa pridaného uzla na nasledujúci uzol (na ktorý ukazoval predchádzajúci uzol).
Funkcia pridania uzla k ODC má teda tvar úplne analogický s funkciou pridania uzla k samostatne prepojený lineárny zoznam :
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; // uložiť ukazovateľ na nasledujúci prvok
lst-> ptr = teplota; // predchádzajúci uzol ukazuje na vytvorený
teplota-> pole = cislo; // uloží dátové pole pridaného uzla
teplota-> ptr = p; // vytvorený uzol ukazuje na nasledujúci prvok
návrat (teplota);
}
Návratová hodnota funkcie je adresa pridaného uzla.
Vymazanie uzla OCN
Ukazovateľ na uzol, ktorý sa má vymazať, sa odovzdá ako argumenty funkcii na odstránenie uzla ODC. Pretože je zoznam kruhový, nie je potrebné posielať ukazovateľ na koreň zoznamu.
Funkcia vráti ukazovateľ na uzol nasledujúci po odstránenom.
Odstránenie uzla môže byť znázornené na nasledujúcom diagrame:
Odstránenie uzla OTS zahŕňa nasledujúce kroky:
- nastavenie ukazovateľa predchádzajúceho uzla na uzol nasledujúci za vymazaným;
- uvoľnenie pamäte vymazaného uzla.
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) // prechádzať zoznamom začínajúcim od koreňa
{ // dokým nenájdeme uzol predchádzajúci lst
temp = temp-> ptr;
}
temp-> ptr = lst-> ptr; // zmena usporiadania ukazovateľa
zadarmo (lst); // uvoľnenie pamäte odstráneného uzla
návrat (teplota);
}
Zobrazovacie prvky OCP
Funkcia zobrazovania prvkov OCD je podobná funkcii pre OLS až na podmienku konca prechodu prvkov.
Ukazovateľ na koreň zoznamu sa odovzdá ako argument výstupnej funkcii.
Funkcia postupne prechádza všetkými uzlami a zobrazuje ich hodnoty.
1
2
3
4
5
6
7
8
9
void listprint (list * lst)
{
zoznam štruktúr * p;
p = prvý;
robiť (
printf ("% d", p-> pole); // vypíše hodnotu uzla p
p = p-> ptr; // prejsť na ďalší uzol
) while (p! = lst); // podmienka pre koniec prechodu
}
Pre ODC môžete tiež zavolať funkciu na zobrazenie položiek zoznamu začínajúcich od ľubovoľného uzla.
Výmena uzlov bcc
Funkcia výmeny OTS berie ako argumenty dva ukazovatele ako uzly, ktoré sa majú vymieňať, ako aj ukazovateľ na koreň zoznamu. Funkcia vráti adresu koreňového uzla zoznamu.
Výmena uzlov v zozname sa vykonáva opätovnou inštaláciou ukazovateľov. K tomu je potrebné definovať predchádzajúcu a nasledujúcu zostavu pre každú nahradenú. V takom prípade sú možné dve situácie:
- nahradené uzly sú susedia;
- uzly, ktoré sa majú nahradiť, nie sú susedmi, to znamená, že je medzi nimi 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 preinštalovávaní ukazovateľov nie je potrebné kontrolovať koreňový uzol (na rozdiel od podobnej funkcie pre lst2-> ptr = lst1;
lst1-> ptr = next2;
prev1-> ptr = lst2;
}
inak if (lst1 == next2)
{
// zameniť susedné uzly
lst1-> ptr = lst2;
lst2-> ptr = next1;
prev2-> ptr = lst2;
}
inak
{
// medzery medzi uzlami sa vymenia
prev1-> ptr = lst2;
lst2-> ptr = next1;
prev2-> ptr = lst1;
lst1-> ptr = next2;
}
if (lst1 == hlava)
návrat (lst2);
if (lst2 == hlava)
návrat (lst1);
návrat (hlava);
}
Posledná aktualizácia: 25.10.2016
Kruhové (kruhové, kruhové) zoznamy sú druhom prepojených zoznamov. Môžu byť spojené jednotlivo alebo dvojnásobne. Ich charakteristickým rysom je, že podmienený posledný prvok uchováva odkaz na prvý prvok, takže sa zoznam javí ako uzavretý alebo kruhový.
Ak sa napríklad náš zoznam skladá z jedného prvku hlavy, môžeme takýto zoznam zavrieť takto:
Head.next = hlava;
Na implementáciu vezmime triedu prvku, ktorý sa používa v jednotlivo prepojenom zozname:
Verejná trieda Uzol
Teraz definujeme triedu zoznamu zvonení:
Pomocou System.Collections; pomocou System.Collections.Generic; namespace SimpleAlgorithmsApp (verejná trieda CircularLinkedList
Dodatok sa vlastne scvrkáva na vynulovanie ukazovateľa na posledný prvok chvosta a nový prvok sa umiestni medzi chvost a hlavu:
Public void Add (údaje T) (uzol
Pri mazaní nastavíme ukazovateľ na nasledujúci prvok predchádzajúceho prvku vo vzťahu k odstránenému:
Public bool Remove (T dáta) (uzol
Uplatnenie zoznamu krúžkov:
CircularLinkedList
Výstup konzoly:
Tom Bob Alice Jack po odstránení: Tom Alice Jack