Anotacija: Paskaitoje aptariami apibrėžimai, deklaravimo būdai, inicijavimas ir ciklinių sąrašų, kaladžių, raudonai juodų medžių panaudojimo sprendžiant uždavinius ypatumai, pateikiami apskritųjų sąrašų, kaladžių, raudonai juodų medžių apdorojimo uždavinių sprendimo pavyzdžiai.
Paskaitos tikslas: studijų algoritmai ir darbo su metodais dinamines duomenų struktūras, išmokti spręsti problemas naudojant dinamines duomenų struktūras ir darbo su jomis algoritmus C++.
Struktūrizuoti duomenų tipai, pvz., masyvai, rinkiniai, įrašai, yra statinės struktūros, nes jų dydžiai išlieka nepakitę per visą programos vykdymą. Duomenų struktūros dažnai turi pakeisti jų dydį, kai problema išsprendžiama. Tokios duomenų struktūros vadinamos dinaminėmis, jos apima krūvas, eiles, sąrašus, medžius ir kt. Dinaminių struktūrų aprašymas naudojant masyvus, įrašus ir failus veda prie tuščiai išnaudojamos atminties ir padidina laiką, reikalingą problemoms išspręsti.
Naudojant struktūriniai tipai, rodyklės ir dinaminiai kintamieji, galite sukurti įvairias dinaminės atminties struktūras. C++ kalbos rodyklių savybės leidžia kurti dinamines atminties struktūras, pagrįstas statine deklaruojami kintamieji arba ant statinio ir mišinio dinaminiai kintamieji. Visų dinamiškų struktūrų organizavimo idėja yra ta pati. Apibrėžiamas tam tikras S struktūros tipas, kurio vienas ar keli laukai deklaruojami kaip rodyklės į tą patį ar kitą struktūros tipą. Programa deklaruoja S tipo kintamąjį d arba S tipo kintamąjį nukreipia į S visiškai dinamiško struktūros kūrimo atveju. Šio kintamojo pavadinimas naudojamas programos vykdymo metu kaip dinaminės struktūros „root“ (pirminio pavadinimo) pavadinimas. Vykdant programą, kuriant dinaminę struktūrą, pateikiami užklausos dinaminiai kintamieji atitinkami tipai ir yra susieti nuorodomis, pradedant kintamuoju d arba pirmuoju dinaminis kintamasis, kurios rodyklė yra kintamajame d. Šis metodas leidžia sukurti dinamišką struktūrą su bet kokia topologija.
Cikliniai (žiediniai) sąrašai
Apvalus (žiedo) sąrašas- Tai duomenų struktūra, kuri yra elementų seka, kurios paskutiniame elemente yra rodyklė į pirmąjį sąrašo elementą, o pirmame (jei dvikryptis sąrašas) – iki paskutinio.
Pagrindinis šios organizacijos bruožas yra tas, kad šiame sąraše nėra elementų, kuriuose būtų nulinės rodyklės, todėl negalima pasirinkti atokiausių elementų.
Apvalūs sąrašai, kaip ir linijiniai, gali būti vienakrypčiai ir dvikryptis.
Panašus į linijinį vienpusį sąrašą, tačiau paskutiniame jo elemente yra rodyklė, susiejanti jį su pirmuoju elementu (32.1 pav.).
Norint visiškai pereiti tokį sąrašą, pakanka turėti žymeklį į savavališką elementą, o ne į pirmąjį, kaip tiesiniame vienpusiame sąraše. „Pirmojo“ elemento sąvoka čia yra gana savavališka ir ne visada reikalinga. Nors kartais pravartu kokį elementą paryškinti kaip „pirmą“, uždedant ant jo specialią rodyklę. Tai reikalinga, pavyzdžiui, norint išvengti „kilpos“ peržiūrint sąrašą.
Ryžiai.
32.1.
- Pagrindinės operacijos, atliekamos su cikliniu vienakrypčiu sąrašu:
- sudaryti sąrašą;
- atsispausdinti (peržiūrėti) sąrašą;
- elemento įterpimas į sąrašą; elemento ištrynimas
- iš sąrašo;
- elemento paieška sąraše;
- patikrinti, ar sąrašas tuščias;
ištrinant sąrašą.
Norėdami aprašyti šių pagrindinių operacijų algoritmus, naudosime tas pačias deklaracijas, kaip ir linijiniam vienkrypčiui sąrašui.
Pateiksime išvardytų pagrindinių operacijų funkcijas dirbant su cikliniu vienakrypčiu sąrašu.<< "Введите значение "; cin >//ciklinio vienakrypčio sąrašo kūrimas void Make_Circle_Single_List(int n, Circle_Single_List** Head,Circle_Single_List* Loop)( if (n > 0) ( (*Head) = new Circle_Single_List(); //paskirti atmintį naujam elementui Ciklas = = NULL) Ciklas = (*Head);<< ptr->> (*Head)->Duomenys; //įveskite informacijos lauko reikšmę (*Head)->Next=NULL //adreso laukelio Make_Circle_Single_List(n-1,&((*Head)->Next),Loop; ) else ( (*Head) = Ciklas; ) ) //spausdinti apskritą vienpusį sąrašą void Print_Circle_Single_List(Circle_Single_List* Head) ( Circle_Single_List* ptr=Head; //pagalbinė rodyklė do ( cout<< "\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->Duomenys< Number; i++) Current = Current->Kitas;< Number; i++) Current = Current->Naujas elementas->Kitas = Dabartinis->Kitas; Dabartinis->Kitas = Naujas elementas; ) grąžinti galvą; ) /*elemento su nurodytu numeriu ištrynimas iš apskrito vienpusio sąrašo*/ Circle_Single_List* Delete_Item_Circle_Single_List (Circle_Single_List* Head, int Number)( if (Head != NULL)( Circle_Single_List *Current = Head; if (Head = Head;
Kitas;
Circle_Single_List *ptr = galva; while (ptr->Kitas != Dabartinis) ptr = ptr->Kitas; //tiesiogiai pašalinant elementą ptr->Kitas = Dabartinis->Kitas; if (Head = dabartinis) Head = dabartinis->Kitas; ištrinti (dabartinis); ) else( Head = NULL; delete(Current); ) ) return Head; ) //ieškoti elemento cikliniame vienpusiame sąraše bool Find_Item_Circle_Single_List(Circle_Single_List* Head, int DataItem)( Circle_Single_List *ptr = Head; //pagalbinė rodyklė do ( if (DataItem == ptr->Data) grąžina true; else ptr = ptr- >Next; ) while (ptr != Head) return false void Delete_Circle_Single_List(Circle_Single_List* Head)( if (Head != NULL)( Head = Delete_Item_Circle_Single_List(Head, 1) ;S_Antraštė); Sąrašas 1.
Panašus į linijinį dvigubą sąrašą, tačiau kiekvienas elementas turi dvi rodykles, kurių viena nukreipia į kitą sąrašo elementą, o kita – į ankstesnį elementą (32.2 pav.). Ryžiai. 32.2.
- Pagrindinės operacijos, atliekamos su cikliniu vienakrypčiu sąrašu:
- sudaryti sąrašą;
- atsispausdinti (peržiūrėti) sąrašą;
- elemento įterpimas į sąrašą; elemento ištrynimas
- Pagrindinės operacijos, atliekamos su cikliniu
- elemento paieška sąraše;
- patikrinti, ar sąrašas tuščias;
dvikryptis dvikryptis sąrašas:
ieškant elemento sąraše Ryžiai. Norėdami aprašyti šių pagrindinių operacijų algoritmus, naudosime tas pačias deklaracijas kaip ir tiesinėms
sąrašą.<< "Введите значение "; cin >> (*Head)->Duomenys; //įveskite informacijos lauko reikšmę (*Head)->Next=NULL; //adreso lauko nustatymas į nulį 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) = Ciklas; return NULL; ) ) //spausdinti apskritą dvigubą sąrašą void Print_Circle_Double_List(Circle_Double_List* Head) ( Circle_Double_List* ptr=Head; // pagalbinė rodyklė do ( cout<< ptr->> (*Head)->Duomenys; //įveskite informacijos lauko reikšmę (*Head)->Next=NULL //adreso laukelio Make_Circle_Single_List(n-1,&((*Head)->Next),Loop; ) else ( (*Head) = Ciklas; ) ) //spausdinti apskritą vienpusį sąrašą void Print_Circle_Single_List(Circle_Single_List* Head) ( Circle_Single_List* ptr=Head; //pagalbinė rodyklė do ( cout<< "\t"; ptr=ptr->Kitas;<< "\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->) while (ptr!=Galva); cout< Number; i++) Current = Current->Duomenys = DataItem; if (Head == NULL) (//sąrašas tuščias NewItem->Next = NewItem; NewItem->Prior = NewItem; Head = NewItem; ) else (//sąrašas nėra tuščias (int i = 1; i< Number; i++) Current = Current->Kitas;
Norėdami pasiekti norimą linijinio sąrašo elementą, turite peržiūrėti sąrašą nuo pradžių, neatsižvelgiant į pradinio žiūrėjimo taško padėtį. Tai sulėtina prieigos prie sąrašo elementų operacijas. Sąrašo elementų uždarymas į žiedą pašalina šį trūkumą. Toks sąrašas vadinamas cikliniu. Galite pradėti žiūrėti apskritą sąrašą nuo bet kurio elemento, ne tik nuo jo pradžios, o sąrašo pradžia gali būti bet kuris jo elementas. Loginė apskrito sąrašo struktūra:
Operacijos cikliniame sąraše
Virš apskrito sąrašo Su gali būti atliekamos visos tiesiniam sąrašui apibrėžtos operacijos. Atkreipkite dėmesį, kad ciklinio sąrašo loginėje struktūroje sąvokos „pradžia“ ir „pabaiga“ yra sąlyginės ir jas lemia žymeklio padėtis į kurį nors sąrašo elementą, kuris yra antraštė.
Cikliniam sąrašui taip pat įvedama nauja operacija - dviejų ciklinių sąrašų sujungimas - Сoncat(Su 1,Su 2).
Atskirai susietas žiedinio sąrašo įgyvendinimas
Apvalaus sąrašo įgyvendinimas naudojant dinaminius kintamuosius:
Toks sąrašas vadinamas atskirai susietas žiedinis sąrašas. Iš bet kurio sąrašo elemento galite pasiekti bet kurį kitą elementą. Atminkite, kad apskritame sąraše nėra pirmojo ir paskutinio elemento. Išorinį žymeklį Head patogu naudoti kaip žymeklį į esamą sąrašo elementą. Spręsdami konkrečias problemas galime sutartinai manyti, kad ji sprendžia paskutinis sąrašo elementą, kuris automatiškai padaro pirmą po jo esantį elementą.
tCircleList klasę galima apibūdinti taip:
tValue= Real; // sąrašo elemento vertės tipas – realus
pItem= ^tItem; // rodyklės į sąrašo elementą tipas
tItem= rekordas// sąrašo elemento tipas
Reikšmė: tValue; // sąrašo elemento turinys
Kitas: pItem; // žymeklį į kitą sąrašo elementą
galas; //įrašas tPrekė
tCircleList= klasė // Klasė - cikliškas sąrašą
apsaugotas
fHead:pItem; // laukas - rodyklę įdabartinis elementassąrašą
fSize:Word; // laukas - sąrašo elementų skaičius
viešas
// Nuosavybė – sąrašo elementų skaičius (skaitymo ir rašymo prieiga)
nuosavybė Dydis: Word skaityti fDydis rašyti fSize;
// Ypatybė – žymeklis į sąrašo pradžią (skaitymo ir rašymo prieiga)
nuosavybė Vadovas: Žodis skaityti fGalva rašyti fGalva;
vpo adreso elementoAdr
procedūra InsertAfter(Addr: pItem; v: tValue);
// Įtraukite elementą su reikšmevprieš adreso elementąAdr
procedūra InsertBefore(Addr: pItem; v: tValue);
// Išskirkite elementą po elemento su Adr adresu
funkcija IštrintiAfter(Addr: pItem): tValue;
// Elemento išskyrimas žymekliuAdr
funkcija Ištrinti(Addr:pItem):tValue;
// Įtraukite elementą su reikšmeviki sąrašo pradžios
procedūra InsertHead(v:tValue);
// Įtraukite elementą su reikšmeviki sąrašo pabaigos
procedūra InsertRear(v:tValue);
// Elemento pašalinimas iš sąrašo pradžios
funkcija DeleteHead:tValue;
// Elemento pašalinimas iš sąrašo pabaigos
funkcija DeleteRear:tValue;
procedūra Concat( var CList2: tCircleList); // sankaba su sąrašąCList2
// Sąraše ieškokite elemento su reikšmevir grąžino jo adresą
funkcija Paieška(v: tValue): pItem;
funkcija Tuščia: Būlio; // grąžintitiesa,Jeigu sąrašą tuščia
procedūra Skaidrus; // išvalyti sąrašą
konstruktorius Sukurti; // konstruktorius – tuščio sąrašo kūrimas
naikintojas Sunaikinti; nepaisyti; // naikintojas - ištrynimas sąrašą
galas; // klasėtCircleList
Klasė tCircleList nėra paskelbta tList klasės palikuonimis, nes beveik visų jos metodų įgyvendinimas skiriasi nuo to paties pavadinimo metodų įgyvendinimo necikliniame sąraše. Iš esmės skirtumai yra tokie:
– operacijoms InsertAfter ir InsertBefore elemento įtraukimas į tuščią sąrašą ir įtraukimas į ciklinio sąrašo pradžią ir pabaigą atliekamas skirtingai;
– taikant operaciją DeleteAfter cikliniam sąrašui, sudarytam iš vieno elemento, pats elementas neturėtų būti pašalintas;
– DeleteAfter ir Delete metodai turi atkurti žymeklį į paskutinį ciklinio sąrašo elementą, jei jis pašalinamas atliekant šias operacijas;
– paieškos ir išvalymo metoduose ciklinio sąrašo naršymo užbaigimo ženklas yra tada, kai pagalbinė rodyklė pasiekia elementą, nuo kurio buvo pradėtas naršymas.
Ir tik „Create konstruktorius“ ir „Destroy destructor“ yra įgyvendinami taip, kaip to paties pavadinimo metodai tList klasėje.
Akivaizdu, kad įtraukimo ir išskyrimo operacijos dešinėje ir kairėje dabartinio elemento (InsertHead, InsertRear, DeleteHead, DeleteRear) atlieka tuos pačius veiksmus, kaip ir to paties pavadinimo operacijos necikliniame sąraše. Skirtumas tas, kad naujos operacijos pakeičia žymeklio reikšmę į paskutinį apskrito sąrašo elementą, jei sąrašas išsiplėtė į kairę arba dešinę arba susiaurėjo į kairę ar dešinę.
Kiekviename vienakrypčio (tiesiog susieto) apskrito sąrašo (OCL) mazge yra vienas žymeklio laukas į kitą mazgą. Paskutiniame mazgo rodyklės lauke yra šakninio elemento adresas.
OCS mazgas gali būti pavaizduotas kaip struktūra, panaši į atskirai susietas linijinis sąrašas
struktūrų sąrašas
{
int laukas; // duomenų laukas
struct list *ptr; // rodyklė į kitą elementą
};
Pagrindiniai veiksmai, atliekami su centrinės skaitmeninės sistemos elementais:
- Sąrašo inicijavimas
- Mazgo įtraukimas į sąrašą
- Mazgo pašalinimas iš sąrašo
- Rodomi sąrašo elementai
- Dviejų sąrašo mazgų apsikeitimas
Kadangi sąrašas yra apskritas, nereikia įdiegti atskiros funkcijos sąrašo šaknims pašalinti.
Sąrašo inicijavimas skirtas sukurti šakninį sąrašo mazgą, kurio žymeklyje į kito elemento lauką yra paties šakninio elemento adresas. 
1
2
3
4
5
6
7
8
9
struct list * init(int a) // a - pirmojo mazgo reikšmė
{
struct list *lst;
// paskirstyti atmintį sąrašo šaknyje
lst = (struktūrų sąrašas*)malloc(dydis (struktūrų sąrašas));
lst->laukas = a;
lst->ptr = lst; // rodyklė į patį šakninį mazgą
return(lst);
}
Mazgo pridėjimas prie OCS
Funkcijai įtraukti mazgą į sąrašą reikia dviejų argumentų:
- Nukreipkite žymiklį į elementą, po kurio įvyksta priedas
- Pridedamo elemento duomenys.
Elemento pridėjimo procedūra gali būti pavaizduota šioje diagramoje: 
Elemento įtraukimas į OCS apima šiuos veiksmus:
- sukurti pridedamą mazgą ir užpildyti jo duomenų lauką;
- mazgo, esančio prieš pridedamą mazgą, rodyklės atstatymas prie pridedamo mazgo;
- mazgo, kuris pridedamas prie kito mazgo (to, į kurį nurodė ankstesnis mazgas), žymeklio nustatymas.
Taigi, mazgo pridėjimo prie OCS funkcija yra visiškai panaši į mazgo pridėjimo prie OCS funkciją. atskirai susietas linijinis sąrašas :
1
2
3
4
5
6
7
8
9
10
struct sąrašas * addelem(sąrašas *lst, int numeris)
{
struct sąrašas *temp, *p;
temp = (struct list*)malloc(dydis (sąrašas));
p = lst->ptr; // žymeklio įrašymas į kitą elementą
lst->ptr = temp; // ankstesnis mazgas nurodo kuriamą
temp->laukas = skaičius; // išsaugomas pridėto mazgo duomenų laukas
temp->ptr = p; // sukurtas mazgas nukreipia į kitą elementą
grįžti(temp);
}
Grąžinama funkcijos reikšmė yra pridėto mazgo adresas.
OCS mazgo pašalinimas
Kaip OCS mazgo ištrynimo funkcijos argumentai, perduodama žymeklis į ištrintiną mazgą. Kadangi sąrašas yra apskritas, nereikia pervesti žymeklio į sąrašo šaknį.
Funkcija grąžina žymeklį į mazgą, esantį šalia ištrinamo.
Mazgo pašalinimas gali būti pavaizduotas šioje diagramoje:
OCS mazgo pašalinimas apima šiuos veiksmus:
- ankstesnio mazgo rodyklės nustatymas į mazgą, einantį po naikinamo;
- atlaisvinant ištrinamo mazgo atmintį.
1
2
3
4
5
6
7
8
9
10
11
12
struct sąrašas * deletelem(sąrašas *lst)
{
struct list *temp;
temp = lst;
while (temp->ptr != lst) // peržiūrėkite sąrašą pradedant nuo šaknies
{ // kol rasime mazgą prieš lst
temp = temp->ptr;
}
temp->ptr = lst->ptr; // pertvarkykite žymeklį
free(lst); // atlaisvinkite ištrinamo mazgo atmintį
grįžti(temp);
}
OCS elementų išvestis
OCS elementų rodymo funkcija yra panaši į funkciją OLS išskyrus elementų perėjimo užbaigimo sąlygą.
Rodyklė į sąrašo šaknį perduodama kaip argumentas elemento išvesties funkcijai.
Funkcija nuosekliai kerta visus mazgus ir rodo jų reikšmes.
1
2
3
4
5
6
7
8
9
negaliojantis sąrašo atspaudas (sąrašas *lst)
{
struktūrų sąrašas *p;
p = lst;
daryti (
printf("%d " , p->laukas); // išveda mazgo p reikšmę
p = p->ptr; // eikite į kitą mazgą
) while (p != lst); // perėjimo pabaigos sąlyga
}
OCS atveju taip pat galite iškviesti funkciją, kad būtų rodomi sąrašo elementai pradedant nuo bet kurio mazgo.
OCS mazgų keitimas
Kaip argumentus, OCS mainų funkcija naudoja du mazgus, kuriais keičiamasi, ir žymeklį į sąrašo šaknį. Funkcija grąžina sąrašo šakninio mazgo adresą.
Sąrašo mazgų apsikeitimas atliekamas iš naujo įdiegiant rodykles. Norėdami tai padaryti, kiekvienam pakeistam mazgui būtina nustatyti ankstesnį ir paskesnį mazgą. Šiuo atveju galimos dvi situacijos:
- keičiami mazgai yra kaimynai;
- keičiami mazgai nėra kaimynai, tai yra, tarp jų yra bent vienas elementas.
Keičiant gretimus mazgus, rodyklių iš naujo įdiegimas atrodo taip: 
Keičiant mazgus, kurie nėra greta, rodyklių įdiegimas iš naujo atrodo taip:
Atkuriant rodykles, nereikia tikrinti šakninio mazgo (skirtingai nuo panašios funkcijos lst2->ptr = lst1;
lst1->ptr = next2;
prev1->ptr = lst2;
}
kitaip jei (lst1 == next2)
{
// kaimyninių mazgų mainai
lst1->ptr = lst2;
lst2->ptr = next1;
prev2->ptr = lst2;
}
Kitas
{
// tolimųjų mazgų mainai
prev1->ptr = lst2;
lst2->ptr = next1;
prev2->ptr = lst1;
lst1->ptr = next2;
}
jei (lst1 == galva)
return(lst2);
jei (lst2 == galva)
return(lst1);
grįžti(galva);
}
Paskutinis atnaujinimas: 2016-10-25
Žiediniai (apvalūs, cikliniai) sąrašai yra susietų sąrašų tipas. Jie gali būti tiesiog sujungti arba sujungti dvigubai. Jų išskirtinis bruožas yra tas, kad sąlyginis paskutinis elementas išsaugo nuorodą į pirmąjį elementą, todėl sąrašas pasirodo uždaras arba apskritas.
Pavyzdžiui, jei mūsų sąrašą sudaro vienas galvos elementas, galva, tada tokį sąrašą galime uždaryti taip:
Head.ext = galva;
Diegimui paimkime elementų klasę, kuri naudojama atskirai susietame sąraše:
Viešosios klasės mazgas
Dabar apibrėžkime apskritojo sąrašo klasę:
Naudojant System.Collections; naudojant System.Collections.Generic; vardų erdvė SimpleAlgorithmsApp (viešoji klasė CircularLinkedList
Papildymas iš esmės reiškia žymeklio atstatymą į paskutinį uodegos elementą ir naujo elemento įdėjimą tarp uodegos ir galvos:
Public Void Add(T data) ( Mazgas
Ištrindami, iš naujo nustatome žymeklį į kitą elementą iš ankstesnio elemento, palyginti su tuo, kuris buvo ištrintas:
Vieša bool Pašalinti (T duomenys) ( Mazgas
Naudojant apskritą sąrašą:
CircularLinkedList
Konsolės išvestis:
Tom Bob Alice Jack Po pašalinimo: Tom Alice Jack