Listă circulară cu sens unic. Rezolvarea problemelor privind structurile dinamice de date. Adăugarea unui nod la OCS
Ultima actualizare: 25.10.2016
Listele inelare (circulare, ciclice) sunt un tip de liste legate. Ele pot fi conectate simplu sau dublu conectate. Lor trăsătură distinctivă este că ultimul element condiționat stochează o referință la primul element, astfel încât lista se dovedește a fi închisă sau circulară.
De exemplu, dacă lista noastră constă dintr-un element head, head, atunci putem închide o astfel de listă după cum urmează:
Head.next = cap;
Pentru implementare, să luăm o clasă de elemente care este utilizată într-o listă legată individual:
Nod de clasă publică
Acum să definim o clasă de listă circulară:
Utilizarea System.Collections; folosind System.Collections.Generic; namespace SimpleAlgorithmsApp (clasa publică CircularLinkedList
) IEnumerator IEnumerable.GetEnumerator() ( return ((IEnumerable)this).GetEnumerator(); ) IEnumerator
IEnumerabil
curent = cap;
do ( if (curent != null) ( yield return current.Data; current = current.Next; ) ) while (current != head);
Adăugarea înseamnă, în esență, resetarea indicatorului la ultimul element de coadă și plasarea noului element între coadă și cap:
Public void Add(T data) (Nod
La ștergere, resetam indicatorul la următorul element din elementul anterior în raport cu cel care este șters:
Public bool Remove(T data) (Nod
Pentru a accesa elementul dorit al unei liste liniare, trebuie să vizualizați lista de la început, indiferent de poziția punctului de vizualizare original. Acest lucru încetinește operațiunile de acces la elementele din listă. Închiderea elementelor listei într-un inel elimină acest dezavantaj. O astfel de listă se numește ciclică. Puteți începe să vizualizați o listă circulară din orice element, nu doar de la începutul acesteia, iar începutul listei poate fi oricare dintre elementele sale. Structura logică a unei liste circulare:
Operații pe o listă ciclică
Deasupra unei liste circulare Cu pot fi efectuate toate operaţiile definite pentru o listă liniară. Rețineți că în structura logică a unei liste ciclice, conceptele de „început” și „sfârșit” sunt condiționate și sunt determinate de poziția pointerului către un element al listei, care este antetul.
Pentru o listă ciclică, este introdusă și o nouă operație - concatenarea a două liste ciclice - Сoncat(Cu 1,Cu 2).
Implementarea individuală a unei liste circulare
Implementarea unei liste circulare folosind variabile dinamice:
O astfel de listă se numește listă circulară legată individual. Din orice element al listei puteți ajunge la orice alt element. Rețineți că o listă circulară nu are primul și ultimul element. Indicatorul extern Head este convenabil de utilizat ca indicator către elementul curent al listei. Când rezolvăm probleme specifice, putem presupune în mod convențional că se adresează dura list element, care face automat ca elementul să-l urmeze primul.
Clasa tCircleList poate fi descrisă după cum urmează:
tValue= Real; // tipul valorii elementului de listă - real
pItem= ^tItem; // tipul de indicator către elementul de listă
tItem= înregistra// listează tipul de element
Valoare: tValue; // conținutul elementului listă
Următorul: pItem; // pointer către următorul element al listei
Sfârşit; //înregistra tItem
tCircleList= clasă // Clasă - ciclic listă
protejat
fHead:pItem; // câmp - arătator cătreelement curentlistă
fSize:Word; // câmp - numărul de elemente ale listei
public
// Proprietate - numărul de elemente ale listei (acces de citire și scriere)
proprietate Dimensiune: Word citire fDimensiune scrie fDimensiune;
// Proprietate – indicator la începutul listei (acces de citire și scriere)
proprietate Cap: Cuvânt citire fCap scrie fCap;
vdupă elementul adresaAdr
procedură InsertAfter(Addr: pItem; v: tValue);
// Include un element cu o valoarevînainte de elementul adresaAdr
procedură InsertBefore(Addr: pItem; v: tValue);
// Excludeți elementul care urmează elementului cu adresa Adr
funcţie DeleteAfter(Addr: pItem): tValue;
// Excluderea unui element cu un pointerAdr
funcţie Delete(Addr:pItem):tValue;
// Include un element cu o valoarevpână la începutul listei
procedură InsertHead(v:tValue);
// Include un element cu o valoarevpână la sfârșitul listei
procedură InsertRear(v:tValue);
// Excluderea unui element de la începutul listei
funcţie DeleteHead:tValue;
// Excluderea unui element de la sfârșitul listei
funcţie DeleteRear:tValue;
procedură Concat( var CList2: tCircleList); // ambreiaj cu listăCList2
// Căutați în listă un element cu o valoarevși returnându-și adresa
funcţie Căutare(v: tValue): pItem;
funcţie Gol: boolean; // reveniadevărat,Dacă listă gol
procedură Clar; // ștergerea listei
constructor Crea; // constructor - creează o listă goală
distrugător Distruge; suprascrie; // distrugător - ştergere listă
Sfârşit; // clasătCircleList
Clasa tCircleList nu este declarată descendentă a clasei tList, deoarece implementarea aproape tuturor metodelor sale diferă de implementarea metodelor cu același nume pentru o listă neciclică. Diferențele sunt în principal după cum urmează:
– pentru operațiunile InsertAfter și InsertBefore, includerea unui element într-o listă goală și includerea la începutul și sfârșitul unei liste ciclice se realizează diferit;
– aplicarea operației DeleteAfter la o listă ciclică constând dintr-un element nu ar trebui să conducă la excluderea acestui element în sine;
– metodele DeleteAfter și Delete trebuie să restaureze un pointer către ultimul element al listei ciclice dacă acesta este eliminat în timpul acestor operații;
– în metodele Search și Clear, un semn de finalizare a parcurgerii unei liste ciclice este atunci când pointerul auxiliar ajunge la elementul de la care a început navigarea.
Și numai constructorul Create și destructorul Destroy sunt implementate în același mod ca și metodele cu același nume din clasa tList.
Evident, operațiunile de includere și excludere din dreapta și stânga elementului curent (InsertHead, InsertRear, DeleteHead, DeleteRear) efectuează aceleași acțiuni ca și operațiunile cu același nume pentru o listă neciclică. Diferența este că noile operații modifică valoarea indicatorului la ultimul element al unei liste circulare dacă lista s-a extins la stânga sau la dreapta, sau s-a restrâns la stânga sau la dreapta.
Textul prelegerii.
Tipurile de date structurate, cum ar fi matrice, seturi, înregistrări, sunt structuri statice, deoarece dimensiunile lor rămân neschimbate pe toată durata execuției programului. Structurile de date sunt adesea necesare pentru a-și schimba dimensiunea pe măsură ce se rezolvă o problemă. Astfel de structuri de date sunt numite dinamice, ele includ stive, cozi, liste, arbori și altele. Descrierea structurilor dinamice folosind matrice, înregistrări și fișiere duce la utilizarea necorespunzătoare a memoriei și crește timpul necesar pentru rezolvarea problemelor.
Folosind tipuri de structuri, pointeri și variabile dinamice, puteți crea o varietate de structuri de memorie dinamică. Caracteristicile pointerilor în limbajul C++ vă permit să construiți structuri dinamice de memorie bazate pe variabile declarate static sau pe un amestec de variabile statice și dinamice. Ideea de a organiza toate structurile dinamice este aceeași. Este definit un anumit tip de structură S, unul sau mai multe dintre ale cărui câmpuri sunt declarate ca pointeri către același tip de structură sau către alt tip de structură. Programul declară o variabilă d de tip S sau o variabilă de tip pointer către S în cazul creării complet dinamice a structurii. Numele acestei variabile este folosit în timpul execuției programului ca numele „rădăcinii” (numele părintelui) structurii dinamice. În timpul execuției programului, pe măsură ce se construiește structura dinamică, variabilele dinamice de tipuri adecvate sunt solicitate și legate prin referințe, începând cu variabila d sau prima variabilă dinamică la care variabila d conține un pointer. Această abordare vă permite să creați o structură dinamică cu orice topologie.
Lista circulară (inelă). este o structură de date care este o secvență de elemente, al cărui ultimul element conține un pointer către primul element al listei, iar primul (în cazul unei liste bidirecționale) conține un pointer către ultimul.
Caracteristica principală a acestei organizații este că nu există elemente în această listă care să conțină pointeri nuli și, prin urmare, elementele cele mai exterioare nu pot fi selectate.
Listele circulare, ca și cele liniare, pot fi unidirecționale sau bidirecționale.
Listă circulară cu sens unic este similar cu o listă liniară unidirecțională, dar ultimul său element conține un indicator care îl leagă de primul element (Figura 1).
Pentru a parcurge complet o astfel de listă, este suficient să aveți un pointer către un element arbitrar, și nu către primul, ca într-o listă liniară unidirecțională. Conceptul de „primul” element aici este destul de arbitrar și nu este întotdeauna necesar. Deși uneori este util să evidențiezi un element ca fiind „primul” prin plasarea unui indicator special pe el. Acest lucru este necesar, de exemplu, pentru a preveni „bucla” atunci când vizualizați o listă.
Orez. 1. Listă circulară unidirecțională
Operații de bază efectuate cu o listă circulară unidirecțională:
· crearea unei liste;
· imprima (vezi) lista;
· inserarea unui element într-o listă;
· căutarea unui element din listă;
· verificarea dacă lista este goală;
· ștergerea listei.
Pentru a descrie algoritmii pentru aceste operații de bază, vom folosi aceleași declarații ca și pentru lista liniară unidirecțională.
Să prezentăm funcțiile operațiilor de bază enumerate atunci când lucrăm cu o listă unidirecțională ciclică.
//creați o listă circulară unidirecțională
void Make_Circle_Single_List(int n,
Circle_Single_List** Head, Circle_Single_List* Loop)(
(*Cap) = noua Lista_Cerc_Single();
cout<< "Введите значение ";
cin >> (*Cap)->Date;
(*Cap)->
Make_Circle_Single_List(n-1,&((*Head)->Next),Loop);
//tipărește o listă circulară unidirecțională
void Print_Circle_Single_List(Circle_Single_List* Head) (
Circle_Single_List* ptr=Cap;
//indicator auxiliar
cout<< ptr->Date<< "\t";
ptr=ptr->Următorul;
) în timp ce (ptr!=Cap);
cout<< "\n";
/*inserați un element după un anumit număr într-o listă circulară unidirecțională*/
Circle_Single_List* Insert_Item_Circle_Single_List(Circle_Single_List* Head,
int Număr, int DataItem)(
//stă pe primul element
Circle_Single_List *NewItem = new(Circle_Single_List);
//a creat un nou element
NewItem->Date = DataItem;
NewItem->Next = NewItem;
else (//lista nu este goală
pentru (int i = 1; i< Number; i++)
Current = Current->Next;
NewItem->Next = Current->Next;
Current->Next = NewItem;
/*eliminarea unui element cu un număr dat dintr-o listă circulară unidirecțională*/
Circle_Single_List* Delete_Item_Circle_Single_List
(Circle_Single_List* Head, int Number)(
if (Cap != NULL)(
Listă_Cerc_Single *Current = Head;
dacă (Cap->Următorul != Cap)(
pentru (int i = 1; i< Number; i++)
Current = Current->Next;
while (ptr->Next != Current)
ptr = ptr->Next;
//eliminarea directă a elementului
ptr->Next = Current->Next;
if (Head = Current) Head = Current->Next;
şterge (Actual);
şterge (Actual);
//căutați un element într-o listă circulară unidirecțională
bool Find_Item_Circle_Single_List(Circle_Single_List* Head,
Circle_Single_List *ptr = Head;
//indicator auxiliar
if (DataItem == ptr->Data) returnează adevărat;
else ptr = ptr->Next;
în timp ce (ptr != Cap);
//verificați golul unei liste circulare unidirecționale
bool Empty_Circle_Single_List(Circle_Single_List* Head)(
//eliminarea unei liste circulare unidirecționale
void Delete_Circle_Single_List(Circle_Single_List* Head)(
if (Cap != NULL)(
Head = Delete_Item_Circle_Single_List(Head, 1);
Delete_Circle_Single_List(Head);
Listă circulară dublă este similar cu o listă dublă liniară, dar fiecare element are doi pointeri, unul indicând următorul element din listă și al doilea indicând elementul anterior (Figura 2).
Fig.2. Listă circulară dublă
Operații de bază efectuate cu o listă circulară bidirecțională:
· crearea unei liste;
· imprima (vezi) lista;
· inserarea unui element într-o listă;
· eliminarea unui element din listă;
· căutați un element din listă
· verificarea dacă lista este goală;
· ștergerea listei.
Pentru a descrie algoritmii pentru aceste operații de bază, vom folosi aceleași declarații ca și pentru lista bidirecțională liniară.
Să prezentăm funcțiile operațiilor de bază enumerate atunci când lucrăm cu o listă bidirecțională ciclică.
//creează o listă circulară dublă
Listă_dublă_cerclă* Face_Lista_dublă_cerclă(int n,
Circle_Double_List** Head, Circle_Double_List* Loop)(
Circle_Double_List* ptr;//indicator auxiliar
(*Cap) = noua Lista_Cerc_dubla();
//aloca memorie pentru noul element
if (Loop == NULL) Loop = (*Cap);
cout<< "Введите значение ";
cin >> (*Cap)->Date;
//introduceți valoarea câmpului de informații
(*Head)->Next=NULL;//reducerea la zero a câmpului de adresă
ptr = Make_Circle_Double_List(n-1,&((*Head)->Next),Loop);
if ((*Head)->Next != NULL)
(*Cap)->Următorul->Înainte = (*Cap);
if ((*Cap)->Anterior == NULL)
(*Head)->Prior = ptr;
dacă (ptr == NULL)
else return ptr;
//tipărește o listă circulară dublă
void Print_Circle_Double_List(Circle_Double_List* Head) (
Circle_Double_List* ptr=Cap;
//indicator auxiliar
cout<< ptr->Date<< "\t";
ptr=ptr->Următorul;
) în timp ce (ptr!=Cap);
cout<< "\n";
/*inserați un element după un anumit număr într-o listă circulară bidirecțională*/
Circle_Double_List* Inserați_Item_Circle_Double_List
(Circle_Double_List* Head, int Number, int DataItem)(
//stă pe primul element
Circle_Double_List *NewItem = new(Circle_Double_List);
//a creat un nou element
NewItem->Date = DataItem;
if (Head == NULL) (//lista este goală
NewItem->Next = NewItem;
NewItem->Prior = NewItem;
else (//lista nu este goală
pentru (int i = 1; i< Number; i++)
Current = Current->Next;
NewItem->Next = Current->Next;
Current->Next = NewItem;
NewItem->Prior = Current;
NewItem->Next->Prior = NewItem;
/*eliminarea unui element cu un număr dat dintr-o listă circulară bidirecțională*/
Circle_Double_List* Delete_Item_Circle_Double_List(Circle_Double_List* Head,
if (Cap != NULL)(
Listă_dublă_cercului *Current = Head;
dacă (Cap->Următorul != Cap)(
pentru (int i = 1; i< Number; i++)
Current = Current->Next;
Circle_Double_List *ptr = Current->Next;
Current->Primor->Next = Current->Next;
Current->Next->Prior = Current->Prior;
if (Cap = Curent) //ștergeți primul
Head = Current->Next;
şterge (Actual);
şterge (Actual);
//căutați un element într-o listă circulară bidirecțională
bool Find_Item_Circle_Double_List(Circle_Double_List* Head,
Circle_Double_List *ptr = Head;
//indicator auxiliar
if (DataItem == ptr->Data)
else ptr = ptr->Next;
în timp ce (ptr != Cap);
//verifică dacă o listă circulară dublă este goală
bool Empty_Circle_Double_List(Circle_Double_List* Head)(
return (Cap != NULL ? fals: adevărat);
//eliminarea unei liste circulare duble
void Delete_Circle_Double_List(Circle_Double_List* Head)(
if (Cap != NULL)(
Head = Delete_Item_Circle_Double_List(Head, 1);
Delete_Circle_Double_List(Cap);
