Ringikujuline üksiknimekiri. Dünaamiliste andmestruktuuride probleemide lahendamine. Sõlme lisamine CSC-sse

Viimane uuendus: 25.10.2016

Ringloendid (ringikujulised, tsüklilised) on omamoodi lingitud loendid. Need võivad olla ühe- või topeltlingitud. Nende eripära on see, et tingimuslik viimane element salvestab viite esimesele elemendile, seega on loend suletud või ringikujuline.

Näiteks kui meie loend koosneb ühest peaelemendi peast, siis saame sellise loendi sulgeda järgmiselt:

pea.next = pea;

Rakendamiseks võtame elemendiklassi, mida kasutatakse üksikult lingitud loendis:

Avalik klass Node ( avalik sõlm(T andmed) ( Andmed = andmed; ) avalikud T andmed ( hanki; määra; ) avalik sõlm Järgmine ( hangi; määra; ) )

Nüüd määratleme helinanimekirja klassi:

System.Collections kasutamine; kasutades System.Collections.Generic; nimeruum SimpleAlgorithmsApp(avalik klass CircularLinkedList :IEloendatav // ringikujuline lingitud loend ( Node pea; // pea/esimene element Sõlm saba; // viimane/saba element int count; // elementide arv loendis // elemendi lisamine public void Add(T data) ( Node sõlm = uus sõlm (andmed); // kui loend on tühi if (head == null) ( head = node; tail = node; tail.Next = head; ) else ( node.Next = head; tail.Next = node; tail = node; ) count++ ; ) public bool Eemalda(T andmed) ( Node vool = pea; sõlm eelmine = null; if (IsEmpty) return false; do ( if (current.Data.Equals(data)) ( // Kui sõlm on keskel või lõpus if (eelmine != null) ( // eemalda praegune sõlm, nüüd eelnev viitab mitte praegusele, vaid praeguseks.Järgmine eelmine .Järgmine = praegune.Järgmine; // Kui sõlm on viimane, // muutke saba muutujat if (praegune == saba) saba = eelmine; ) else // kui esimene element on eemaldatud ( // kui loendis on ainult üks element if(count= =1) ( head = tail = null; ) else ( head = praegune.Järgmine; saba.Järgmine = praegune.Järgmine; ) ) count--; return true ; ) eelmine = praegune; praegune = praegune.Järgmine; ) while ( praegune != pea); tagastama vale; ) public int Count ( get ( return count; ) ) public bool IsEmpty ( get ( return count == 0; ) ) public void Clear() ( head = null; tail = null; count = 0; ) public bool Sisaldab (T andmed) ( Sõlm vool = pea; if (praegune == null) return false; do ( if (current.Data.Equals(data)) return true; current = current.Next; ) while (praegune != pea); tagastama vale; ) IEnumerator IEnumerable.GetEnumerator() ( return ((IEnumerable)this).GetEnumerator(); ) IEnumerator IEloendatav .GetEnumerator() ( Node vool = pea; do ( if (praegune != null) ( tootlus tagasivool.Andmed; praegune = praegune.Järgmine; ) ) while (praegune != pea); ) ) )

Lisamine taandub tegelikult sellele, et kursor lähtestatakse saba viimasele elemendile ja uus element asetatakse saba ja pea vahele:

Public void Add(T data) ( sõlm sõlm = uus sõlm (andmed); // kui loend on tühi if (head == null) ( head = node; tail = node; tail.Next = head; ) else ( node.Next = head; tail.Next = node; tail = node; ) count++ ; )

Kustutamisel lähtestame kursori eelmise elemendi järgmisele elemendile, võrreldes kustutatavaga:

Avalik bool Eemalda (T andmed) ( Node vool = pea; sõlm eelmine = null; if (IsEmpty) return false; do ( if (current.Data.Equals(data)) ( // Kui sõlm on keskel või lõpus if (eelmine != null) ( // eemalda praegune sõlm, nüüd eelnev viitab mitte praegusele, vaid praeguseks.Järgmine eelmine .Järgmine = praegune.Järgmine; // Kui sõlm on viimane, // muutke saba muutujat if (praegune == saba) saba = eelmine; ) else // kui esimene element on eemaldatud ( // kui loendis on ainult üks element if(count= =1) ( head = tail = null; ) else ( head = praegune.Järgmine; saba.Järgmine = praegune.Järgmine; ) ) count--; return true ; ) eelmine = praegune; praegune = praegune.Järgmine; ) while ( praegune != pea); tagastama vale; )

Rõnganimekirja rakendamine:

CircularLinkedList circularList = uus CircularLinkedList (); ringloend.Add("Tom"); ringloend.Add("Bob"); ringloend.Add("Alice"); ringloend.Add("Jack"); foreach (var item in circularList) ( Console.WriteLine(item); ) circularList.Remove("Bob"); Console.WriteLine("\n Pärast kustutamist: \n"); foreach (var item in circularList) ( Console.WriteLine(item); )

Konsooli väljund:

Tom Bob Alice Jack eemaldatud: Tom Alice Jack

Lineaarse loendi soovitud elemendile juurdepääsu saamiseks peate loendit sirvima selle algusest, olenemata algse vaatepunkti asukohast. See aeglustab juurdepääsutoiminguid loendis olevatele elementidele. Loendi elementide rõngasse sulgemine kõrvaldab selle puuduse. Sellist loendit nimetatakse tsükliliseks loendiks. Tsüklilise loendi vaatamist on võimalik alustada mis tahes elemendist, mitte ainult selle algusest ning loendi alguseks võib olla ükskõik milline selle element. Tsüklilise loendi loogiline struktuur:

Toimingud tsüklilises loendis

Tsüklilise loendi kohal Koos teostada saab kõiki lineaarse loendi jaoks määratletud toiminguid. Pange tähele, et tsüklilise loendi loogilises struktuuris on mõisted "algus" ja "lõpp" tingimuslikud ja need on määratud loendi mõne elemendi, milleks on päis, kursori asukoht.

Tsüklilise loendi jaoks võetakse kasutusele ka uus operatsioon - kahe tsüklilise loendi ühendamine - concat(Koos 1,Koos 2).

Üksiklingitud ringloendi rakendamine

Tsüklilise loendi rakendamine dünaamiliste muutujate abil:

Sellist nimekirja nimetatakse üksikult seotud tsükliline loend. Loendi mis tahes elemendile pääseb juurde mis tahes muust elemendist. Pange tähele, et tsüklilisel loendil pole esimest ja viimast elementi. Väline pointerHead on kasulik osutajana loendi praegusele elemendile. Konkreetsete probleemide lahendamisel võib tinglikult lugeda, et see käsitleb viimane list element, mis muudab sellele järgneva elemendi automaatselt esimeseks.

Klassi tCircleList saab kirjeldada järgmiselt:

tValue=Reaalne; // loendielemendi väärtuse tüüp - real

pItem= ^tItem; // kursori tüüp loendielemendile

ese= rekord// loendiüksuse tüüp

Väärtus: tValue; // loendielemendi sisu

Järgmine: ese; // osutab loendi järgmisele elemendile

lõpp; // rekord üksus

tCircleList= klass // Klass - tsükliline nimekirja

kaitstud

fHead:pItem; // väli - osutipraegune elementnimekirja

fSize:Word; // väli - loendi elementide arv

avalik

// Atribuut – loendielementide arv (lugemis- ja kirjutamisjuurdepääs)

vara Suurus: Word lugeda fSize kirjutada fSize;

// Atribuut – kursor loendi algusesse (lugemis- ja kirjutamisjuurdepääs)

vara Pea: Sõna lugeda fPea kirjutada pea;

vpärast aadressiga elementiadr

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

// Luba väärtusega elementvenne elementi aadressigaadr

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

// Välista elemendile järgnev element aadressiga Adr

funktsiooni KustutaAfter(Addr: pItem): tVäärtus;

// Välista element kursorigaadr

funktsiooni Kustuta(Addr:pItem):tValue;

// Luba väärtusega elementvnimekirja tippu

menetlust InsertHead(v:tValue);

// Luba väärtusega elementvnimekirja lõppu

menetlust InsertRear(v:tValue);

// Elemendi eemaldamine loendi algusest

funktsiooni DeleteHead:tValue;

// Elemendi väljajätmine loendi lõpust

funktsiooni DeleteRear:tValue;

menetlust Concat( var CList2: tCircleList); // sidur co nimekirjaCList2

// Otsige loendist väärtusega elementivja tagastage oma aadress

funktsiooni Otsing(v: tValue): pItem;

funktsiooni Tühi: Boolean; // tagasitõsi,kui nimekirja tühi

menetlust selge; // selge nimekiri

konstruktor luua; // konstruktor - tühja loendi loomine

hävitaja Hävitada; alistama; // hävitaja - eemaldus nimekirja

lõpp; // klasstCircleList

Klassi tCircleList ei kuulutata klassi tList järglaseks, kuna peaaegu kõigi selle meetodite rakendamine erineb mitteringikujulise loendi samanimeliste meetodite rakendamisest. Erinevused on peamiselt järgmised:

– operatsioonide InsertAfter ja InsertBefore puhul toimub elemendi lisamine tühja nimekirja ning tsüklilise loendi algusesse ja lõppu erinevalt;

– toimingu DeleteAfter rakendamine ühest elemendist koosneva tsüklilise loendi puhul ei tohiks kaasa tuua selle elemendi enda väljajätmist;

– meetodid DeleteAfter ja Delete taastavad kursori tsüklilise loendi viimasele elemendile, kui see nende toimingute käigus välja jäetakse;

– Otsingu- ja tühjendusmeetodites on tsüklilise loendi sirvimise lõpetamise indikaator selle elemendi abiosuti poolt saavutatud saavutus, millest sirvimine algas.

Ja ainult Create konstruktor ja Destroy destructor realiseeritakse samamoodi nagu samanimelise klassi tList meetodeid.

Ilmselgelt sooritavad aktiivsest elemendist paremal ja vasakul asuvad kaasamise ja väljajätmise toimingud (InsertHead, InsertRear, DeleteHead, DeleteRear) samu toiminguid, mis mittetsüklilise loendi samanimelised toimingud. Erinevus seisneb selles, et uued toimingud muudavad kursori väärtust tsüklilise loendi viimasele elemendile, kui loend on vasakule või paremale laienenud või vasakule või paremale kitsenenud.

Loengu tekst.

Struktureeritud andmetüübid, nagu massiivid, komplektid ja kirjed, on staatilised struktuurid, kuna nende suurused ei muutu kogu programmi täitmise ajal. Sageli nõutakse, et andmestruktuurid muudaksid ülesande lahendamise käigus oma suurusi. Selliseid andmestruktuure nimetatakse dünaamilisteks, need hõlmavad virnasid, järjekordi, loendeid, puid ja muud. Dünaamiliste struktuuride kirjeldamine massiivide, kirjete ja failide abil viib mälu raiskamiseni ja suurendab probleemide lahendamise aega.

Struktuuritüüpide, osutite ja dünaamiliste muutujate abil saate luua mitmesuguseid dünaamilisi mälustruktuure. Osutite omadused C++ keeles võimaldavad teil luua dünaamilisi mälustruktuure, mis põhinevad staatiliselt deklareeritud muutujatel või staatiliste ja dünaamiliste muutujate segul. Kõigi dünaamiliste struktuuride korraldamise idee on sama. Määratletakse mõni struktuuritüüp S, mille üks või mitu välja on deklareeritud osutiteks samale või mõnele muule struktuuritüübile. Programm deklareerib S-tüüpi muutuja d või täielikult dünaamilise struktuuri loomise korral S-tüüpi muutuja. Selle muutuja nime kasutatakse programmi täitmise ajal dünaamilise struktuuri "juure" (vanemanime) nimena. Programmi käivitamisel, dünaamilise struktuuri ülesehitamisel, küsitakse vastavat tüüpi dünaamilisi muutujaid, mis seotakse viidetega, alustades muutujast d või esimesest dünaamilisest muutujast, mille osuti sisaldub muutujas d. See lähenemisviis võimaldab teil luua dünaamilise struktuuri mis tahes topoloogiaga.

Tsükliline (rõngas) nimekiri on andmestruktuur, mis on elementide jada, mille viimane element sisaldab kursorit loendi esimesele elemendile ja esimene (kahesuunalise loendi puhul) viimasele.

Sellise organisatsiooni põhijooneks on see, et selles loendis pole ühtegi nullpunkti sisaldavat elementi ja seetõttu on võimatu valida äärmuslikke elemente.

Ringikujulised loendid, nagu ka lineaarsed loendid, võivad olla ühe- või kahesuunalised.

Ringikujuline üksiknimekiri sarnane lineaarsele üksikult lingitud loendile, kuid selle viimane element sisaldab kursorit, mis seob selle esimese elemendiga (joonis 1).

Sellise loendi täielikuks läbimiseks piisab, kui teil on kursor suvalisele elemendile, mitte esimesele, nagu lineaarses ühesuunalises loendis. "Esimese" elemendi mõiste on siin pigem tingimuslik ega ole alati nõutav. Kuigi mõnikord on kasulik mõni element "esimeseks" esile tõsta, seades sellele spetsiaalse osuti. See on vajalik näiteks loendi vaatamisel "looping" vältimiseks.

Riis. 1. Tsükliline ühesuunaline loend

Põhitoimingud, mida tehakse tsüklilise ühesuunalise loendiga:

nimekirja koostamine;

nimekirja trükkimine (vaatamine);

Elemendi lisamine loendisse

otsige loendist elementi;

Kontrollige, kas loend on tühi

nimekirja kustutamine.

Nende põhitoimingute algoritmide kirjeldamiseks kasutame samu deklaratsioone, mis lineaarse üksikult lingitud loendi puhul.

Tutvustame loetletud põhitoimingute funktsioone tsüklilise ühesuunalise loendiga töötamisel.

//loo ümmarguse ühesuunalise loendi

void Make_Circle_Single_List(int n,

Circle_Single_List** Head,Circle_Single_List* Loop)(

(*Head) = new Circle_Single_List();

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

cin >> (*Pea)->Andmed;

(*Pea)->

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

//ringikujulise ühesuunalise loendi printimine

void Print_Circle_Single_List(Circle_Single_List* Head) (

Circle_Single_List* ptr=Pea;

//abiosuti

cout<< ptr->Andmed<< "\t";

ptr=ptr->Järgmine;

) while (ptr!=Pea);

cout<< "\n";

/*sisestab elemendi antud numbri järel ringikujulisse üksikult lingitud loendisse*/

Circle_Single_List* Insert_Item_Circle_Single_List(Circle_Single_List* Head,

int Number, int DataItem)(

//seisa esimesel elemendil

Ring_üks_loend *Uus üksus = new(Circle_Single_List);

//loos uue elemendi

NewItem->Data = Andmeüksus;

Uus punkt->Järgmine = Uus üksus;

else (// nimekiri ei ole tühi

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

Praegune = Praegune->Järgmine;

Uuspunkt->Järgmine = Praegune->Järgmine;

Praegune->Järgmine = Uus üksus;

/*eemaldage antud numbriga element tsüklilisest ühesuunalisest loendist*/

Circle_Single_List* Kustuta_üksus_Circle_Single_List

(Circle_Single_List* Head, int Number)(

if (pea != NULL)(

Circle_Single_List *Praegune = Pea;

if (Pea->Järgmine != Pea)(

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

Praegune = Praegune->Järgmine;

while (ptr->Järgmine != Praegune)

ptr = ptr->Järgmine;

//elemendi kohene eemaldamine

ptr->Järgmine = Praegune->Järgmine;

if (Pea = Praegune) Pea = Praegune->Järgmine;

kustuta (praegune);

//Otsige elementi ringikujulisest ühesuunalisest loendist

bool Find_Item_Circle_Single_List(Circle_Single_List* Head,

Circle_Single_List *ptr = Pea;

//abiosuti

if (DataItem == ptr->Data) tagastab tõene;

else ptr = ptr->Järgmine;

while (ptr != Pea);

//kontrollib, kas tsükliline üksikloend on tühi

bool Empty_Circle_Single_List(Circle_Single_List* Head)(

//ringikujulise ühesuunalise loendi kustutamine

void Kustuta_Circle_Single_List(Circle_Single_List* Head)(

if (pea != NULL)(

Head = Kustuta_üksus_ring_üks_loend(pea, 1);

Delete_Circle_Single_List(Head);

Ringikujuline topeltnimekiri sarnane lineaarsele kahesuunalisele loendile, kuid selle mis tahes elemendil on kaks osutit, millest üks osutab loendi järgmisele elemendile ja teine eelmisele elemendile (joonis 2).

Joonis 2. Ringikujuline topeltnimekiri

Peamised toimingud, mida tehakse tsüklilise topeltlingitud loendiga:

nimekirja koostamine;

nimekirja trükkimine (vaatamine);

Elemendi lisamine loendisse

elemendi eemaldamine loendist;

otsige loendist elementi

Kontrollige, kas loend on tühi

nimekirja kustutamine.

Nende põhitoimingute algoritmide kirjeldamiseks kasutame samu deklaratsioone, mis lineaarse kahesuunalise loendi puhul.

Tutvustame loetletud põhitoimingute funktsioone tsüklilise kahesuunalise loendiga töötamisel.

//loob tsüklilise kahesuunalise loendi

Circle_Double_List* Make_Circle_Double_List(int n,

Ring_topeltloend** Head,Circle_Double_List* Silmus)(

Circle_Double_List* ptr;//abikursor

(*Head) = new Circle_Double_List();

//eraldavad uuele elemendile mälu

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

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

cin >> (*Pea)->Andmed;

//sisestage teabevälja väärtus

(*Head)->Next=NULL;//aadressivälja nullimine

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

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

(*Pea)->Järgmine->Eelmine = (*Pea);

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

(*Pea)->Eelnev = ptr;

if (ptr == NULL)

else return ptr;

//ringikujulise kahesuunalise loendi printimine

void Print_Circle_Double_List(Circle_Double_List* Head) (

Circle_Double_List* ptr=Pea;

//abiosuti

cout<< ptr->Andmed<< "\t";

ptr=ptr->Järgmine;

) while (ptr!=Pea);

cout<< "\n";

/*sisesta ringikujulisse topeltloendisse antud numbri järel olev element*/

Circle_Double_List* Insert_Item_Circle_Double_List

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

//seisa esimesel elemendil

Ring_topeltloend *Uus üksus = new(Circle_Double_List);

//loos uue elemendi

NewItem->Data = Andmeüksus;

if (Head == NULL) (//loend on tühi

Uus punkt->Järgmine = Uus üksus;

Uuspunkt->Eelnev = Uuspunkt;

else (// nimekiri ei ole tühi

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

Praegune = Praegune->Järgmine;

Uuspunkt->Järgmine = Praegune->Järgmine;

Praegune->Järgmine = Uus üksus;

Uuspunkt->Eelnev = Praegune;

Uus üksus->Järgmine->Eelmine = Uus üksus;

/*eemalda tsüklilisest topeltloendist antud numbriga element*/

Circle_Double_List* Delete_Item_Circle_Double_List(Circle_Double_List* Head,

if (pea != NULL)(

Circle_Double_List *Praegune = Pea;

if (Pea->Järgmine != Pea)(

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

Praegune = Praegune->Järgmine;

Circle_Double_List *ptr = Praegune->Järgmine;

Praegune->Eelmine->Järgmine = Praegune->Järgmine;

Praegune->Järgmine->Eelmine = Praegune->Eelmine;

if (Head = Current) //eemaldage esimene

Head = Praegune->Järgmine;

kustuta (praegune);

//otsige elementi ringikujulisest topeltloendist

bool Find_Item_Circle_Double_List(Circle_Double_List* Head,

Circle_Double_List *ptr = Pea;

//abiosuti

if (DataItem == ptr->Andmed)

else ptr = ptr->Järgmine;

while (ptr != Pea);

// kontrollib, kas ringikujuline topeltloend on tühi

bool Tühi_ring_topeltloend(Circle_Double_List* Head)(

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

//eemaldame ringikujulise topeltloendi

void Kustuta_Circle_Double_List(Circle_Double_List* Head)(

if (pea != NULL)(

Head = Kustuta_üksus_Circle_Double_List(Head, 1);

Delete_Circle_Double_List(Head);

Ringikujuline üksiknimekiri. Dünaamiliste andmestruktuuride probleemide lahendamine. Sõlme lisamine CSC-sse

Toimingud tsüklilises loendis

Üksiklingitud ringloendi rakendamine