Cyklický jednosmerný zoznam. Riešenie problémov s dynamickými dátovými štruktúrami. Pridanie uzla do skrytej kópie

Posledná aktualizácia: 25.10.2016

Prstencové (kruhové, kruhové) zoznamy sú akési prepojené zoznamy. Môžu byť spojené jednotlivo alebo dvojito. Ich charakteristickou črtou 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 hlavičky, potom môžeme takýto zoznam uzavrieť takto:

Head.next = hlava;

Na implementáciu si zoberme triedu prvku, 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; menný priestor SimpleAlgorithmsApp (verejná trieda CircularLinkedList : IPočetné // kruhový prepojený zoznam (Node hlava; // head / prvý prvok Node chvost; // posledný / chvostový 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 = uzol; tail = uzol; tail.Next = hlava;) else (node.Next = hlava; tail.Next = uzol; chvost = 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 sa netýka aktuálneho, 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 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;) zatiaľ čo ( aktuálny! = hlava); vrátiť nepravdu; ) public int Počet (získať (vrátiť počet;)) public bool IsEmpty (získať (vrátiť počet == 0;)) public void Clear () (head = null; tail = null; count = 0;) public bool Obsahuje (T údaje) (Uzol prúd = hlava; if (aktuálne == null) return false; do (ak (aktuálne.Údaje.Rovná sa (údaje)) vráti hodnotu true; aktuálne = aktuálne.Ďalej;) while (aktuálne! = hlava); vrátiť nepravdu; ) IEnumerator IEnumerable.GetEnumerator () (vrátiť ((IEnumerable) toto) .GetEnumerator ();) IEnumerator IEpočetné .GetEnumerator () (Uzol prúd = hlava; do (if (aktuálny! = null) (výnos spätného prúdu.Údaje; prúd = aktuálny.Ďalší;)) while (aktuálny! = hlava); )))

Pridanie v skutočnosti znamená resetovanie ukazovateľa na posledný prvok chvosta a umiestnenie nového prvku medzi chvost a hlavu:

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

Pri odstraňovaní prestavíme ukazovateľ na nasledujúci prvok predchádzajúceho prvku vo vzťahu k odstránenému prvku:

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 sa netýka aktuálneho, 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 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;) zatiaľ čo ( 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 (položka);) circleList.Remove ("Bob"); Console.WriteLine ("\ n Po odstránení: \ n"); foreach (položka var v kruhovom zozname) (Console.WriteLine (položka);)

Výstup na konzolu:

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

Ak chcete získať prístup k požadovanému prvku lineárneho zoznamu, musíte zoznam zobraziť od jeho začiatku bez ohľadu na polohu pôvodného pohľadu. To spomaľuje operácie na prístup k položkám v zozname. Uzavretie prvkov zoznamu do prstenca túto nevýhodu odstraňuje. Takýto zoznam sa nazýva kruhový. 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 cyklického zoznamu:

1. Operácie s cyklickým zoznamom

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 kruhový zoznam sa zavádza aj nová operácia - zreťazenie dvoch kruhových zoznamov - Сoncat(s 1,s 2).

1. Jednorazovo prepojená implementácia cyklického zoznamu

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

Takýto zoznam sa nazýva jednoducho prepojený cyklický zoznam... Akýkoľvek iný prvok je dostupný z ktorejkoľvek položky v zozname. Všimnite si, že cyklický 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 možno podmienečne uvažovať, že rieši posledný položka zoznamu, ktorá automaticky vytvorí nasledujúcu položku ako prvú.

Triedu tCircleList možno opísať takto:

tHodnota = Skutočná; // typ hodnoty položky zoznamu - real

pItem = ^ tItem; // typ ukazovateľa na položku zoznamu

tItem = záznam// typ položky zoznamu

Hodnota: tValue; // obsahová časť položky zoznamu

Ďalej: pItem; // ukazovateľ na ďalšiu položku v zozname

koniec; // záznam tItem

tCircleList = trieda // Trieda - cyklický zoznam

chránené

fHead: pItem; // lúka - ukazovateľ naaktuálna položkazoznam

fSize: Word; // pole - počet položiek v zozname

verejnosti

// Vlastnosť - počet položiek 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ť fHlava;

vza prvkom s adresouAdr

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

// Zahrňte prvok s hodnotouvpred prvkom s adresouAdr

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

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

funkciu DeleteAfter (Addr: pItem): tValue;

// Vylúčenie prvku pomocou ukazovateľaAdr

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 položky zo začiatku zoznamu

funkciu DeleteHead: tValue;

// Vylúčenie položky 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 Hľadať (v: tValue): pItem;

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

postup Jasný; // vymazať zoznam

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 dedič triedy tList, pretože implementácia takmer všetkých jej metód sa líši od implementácie rovnakých metód pre necyklický zoznam. Rozdiely sú hlavne nasledovné:

- pre operácie InsertAfter a InsertBefore je prvok zahrnutý do prázdneho zoznamu a zaradený na začiatok a koniec cyklického zoznamu 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ý;

- pri metódach Search a Clear je znakom dokončenia zobrazenia cyklického zoznamu to, že pomocný ukazovateľ dosiahne prvok, od ktorého zobrazenie začalo.

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

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 menia hodnotu ukazovateľa na posledný prvok kruhového zoznamu, ak sa zoznam rozšíril doľava alebo doprava, prípadne sa zúžil doľava alebo doprava.

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ú nezmenené počas celej doby vykonávania programu. Často sa vyžaduje, aby dátové štruktúry počas riešenia problému menili svoju veľkosť. Takéto dátové štruktúry sa nazývajú dynamické a zahŕňajú zásobníky, fronty, zoznamy, stromy a iné. Popis 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 typov štruktúr, ukazovateľov a dynamických premenných môžete vytvárať rôzne dynamické pamäťové štruktúry. Zvláštnosti ukazovateľov v jazyku C++ umožňujú budovať 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í sú deklarované 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 počas vykonávania programu sa používa ako názov "root" (rodičovského názvu) dynamickej štruktúry. Počas vykonávania programu, keď sa buduje dynamická štruktúra, sú požadované dynamické premenné zodpovedajúcich 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ý (kruhový) 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 tejto organizácie je, že v tomto zozname nie sú žiadne prvky obsahujúce nulové ukazovatele, a preto nie je možné vybrať extrémne prvky.

Zoznamy slučiek sú rovnako ako lineárne zoznamy jednosmerné a obojsmerné.

Cyklický 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. Pojem „prvý“ prvok je tu skôr 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. Vyžaduje sa to napríklad preto, aby sa zabránilo "zacykleniu" pri prehliadaní zoznamu.

Ryža. 1. Cyklický jednosmerný zoznam

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

· Vytvorenie zoznamu;

· Tlač (zobrazenie) zoznamu;

· Vloženie položky do zoznamu;

· Vyhľadajte položku v zozname;

· Kontrola prázdnoty zoznamu;

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

// vytvorte 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 >> (* Hlava) -> Údaje;

(* 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 = Head;

// pomocný ukazovateľ

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

ptr = ptr-> Ďalej;

) while (ptr! = Hlava);

cout<< "\n";

/ * vložiť položku 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) (

// stál na prvom prvku

Circle_Single_List * NewItem = new (Circle_Single_List);

// vytvoril novú položku

NewItem-> Data = DataItem;

NewItem-> Next = NewItem;

else (// zoznam nie je prázdny

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

Aktuálny = Aktuálny-> Ďalej;

NewItem-> Next = Current-> Next;

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

/ * odstráňte prvok 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 (Hlava-> Ďalej! = Hlava) (

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

Aktuálny = Aktuálny-> Ďalej;

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

ptr = ptr-> Ďalej;

// priamo odstrániť prvok

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

if (Hlava = Prúd) Hlava = Prúd-> Ďalej;

vymazať (Aktuálne);

vymazať (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-> Ďalej;

while (ptr! = Hlava);

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

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

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

Obr. Cyklický obojsmerný zoznam

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

· Vytvorenie zoznamu;

· Tlač (zobrazenie) zoznamu;

· Vloženie položky do zoznamu;

· Odstránenie položky zo zoznamu;

Vyhľadajte položku v zozname

· Kontrola prázdnoty zoznamu;

· 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 kruhový 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 (Slučka == NULL) Slučka = (* Hlava);

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 ((* Hlavička) -> Ďalej! = NULL)

(* Hlava) -> Ďalej-> Predchádzajúca = (* Hlava);

if ((* Hlavička) -> Predošlé == NULL)

(* Hlava) -> Prior = ptr;

if (ptr == NULL)

else return ptr;

// vytlačí kruhový obojsmerný zoznam

void Print_Circle_Double_List (Circle_Double_List * Head) (

Circle_Double_List * ptr = Hlava;

// pomocný ukazovateľ

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

ptr = ptr-> Ďalej;

) while (ptr! = Hlava);

cout<< "\n";

/ * vložiť položku 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) (

// stál na prvom prvku

Circle_Double_List * NewItem = new (Circle_Double_List);

// vytvoril novú položku

NewItem-> Data = DataItem;

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

NewItem-> Next = NewItem;

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

else (// zoznam nie je prázdny

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

Aktuálny = Aktuálny-> Ďalej;

NewItem-> Next = Current-> Next;

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áňte prvok 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 (Hlava-> Ďalej! = Hlava) (

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

Aktuálny = Aktuálny-> Ďalej;

Circle_Double_List * ptr = Aktuálne-> Ďalej;

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

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

if (Head = Current) // odstráňte prvý

Hlava = Prúd-> Ďalej;

vymazať (Aktuálne);

vymazať (Aktuálne);

// nájdenie položky v kruhovom obojsmernom zozname

bool Find_Item_Circle_Double_List (Circle_Double_List * Head,

Circle_Double_List * ptr = Hlava;

// pomocný ukazovateľ

if (DataItem == ptr-> Data)

else ptr = ptr-> Ďalej;

while (ptr! = Hlava);

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

bool Empty_Circle_Double_List (Circle_Double_List * Head) (

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

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

void Delete_Circle_Double_List (Circle_Double_List * Head) (

if (hlava! = NULL) (

Head = Delete_Item_Circle_Double_List (Hlava, 1);

Delete_Circle_Double_List (Head);