1.1. Definiția bidirectional list
O listă dinamică în care fiecare element (cu excepția primei și ultimei) este asociat cu elementele anterioare și următoare este numit dublu conectat. Fiecare element al unei astfel de liste are două câmpuri cu indicatori: un câmp conține o referință la elementul următor, alt câmp este un link către elementul anterior și al treilea câmp este un câmp de informații. Prezența link-uri pe link-ul de lângă anterior și vă permite să se deplaseze prin lista de fiecare link în ambele sensuri: de la nivelul la sfârșitul listei sau din link-ul de la partea de sus a listei, astfel încât această listă este de asemenea, numit bidirecțională.
Fig.1. șirul de caractere BETA este reprezentat de o listă dublată
Prima legătură nu are nicio referire la cea precedentă, ultima legătură nu are nicio referire la linkul următor (vezi Fig. 2).
Fig.2. Șirul de caractere BETA este reprezentat de o listă ciclică
O astfel de listă (a se vedea Fig. 2) este numită circulară (ciclică). Aici primul link are o legătură cu ultima și ultima legătură cu prima. Prin urmare, puteți începe să procesați o astfel de listă din primul link sau din ultima. O listă dublu conectată poate avea un link antet (vezi Fig.3).
Figura 3. Linia de titlu a listei duble conectate
Linkul titlului vă permite să procesați prima și ultima legătură, precum și altele.
Sunt posibile și alte structuri ale listelor duble conectate.
Configurarea unei liste dublu legate:
list2 * next, * pred;;
Aici tip este tipul câmpului de informații al articolului din listă. Variabila headlist2 specifică lista ca un obiect de program unic, valoarea ei fiind un pointer la primul (sau mai mare) element al listei (a se vedea Fig.3).
Exemplul 2. Formarea unei liste bidirecționale
list2 * next, * pred;;
l -> următor = l; // lista de apeluri
l -> pred = l; // cu o legătură de capital
în timp ce ((sym = getchar ())! = '\ n')
x -> elem = sym; // Crearea următorului link
x -> next = r -> următor; // Câmpul următor - indicatorul pentru următorul link
// a primit valoarea indicatorului la primul link din listă
x -> pred = r; // pre-pointerul câmpului la legătura precedentă primită
// valoarea indicatorului la ultimul link curent din listă
r -> următoarea = x; // Câmpul următor al ultimului element curent - un indicator la
// elementul următor are valoarea unui pointer la unul nou
// element, astfel încât noua legătură este adăugată la sfârșit
r -> următoarea -> pred = x; // Câmp antet - pointer
// ultimul link din listă a primit valoarea indicelui
// la elementul adăugat la sfârșitul listei,
// lista de date este generată
// Pointerul curent a primit valoarea linkului
// ultimul element nou din listă
Operațiile de bază efectuate pe o listă dublu conectată sunt aceleași ca pentru o listă pur și simplu conectată. Din moment ce o listă dublu legată este mai flexibilă decât o listă pur și simplu conectată, atunci când includeți un element în listă, puteți utiliza indicatorul atât ca element urmat de includerea, cât și cu pointerul la elementul înaintea căruia se face includerea. Dacă excludeți un articol din listă, puteți utiliza atât un indicator pentru elementul însuși, cât și un indicator pentru elementul care precede sau urmează elementul exclutat. Dar, deoarece elementul unei liste dublu conectate are două indicatoare, atunci când efectuați operațiile de includere / excludere a unui element, trebuie să schimbați mai multe linkuri decât într-o listă pur și simplu conectată.
Puteți căuta un element dintr-o listă dublu legată:
a) care examinează elementele de la începutul până la sfârșitul listei,
b) trecând prin elementele de la sfârșitul listei la început,
c) vizualizarea listă în ambele direcții simultan: de la începutul până la mijlocul listei și de la sfârșitul la mijloc (considerând că elementele din listă pot fi un număr par sau impar).
Exemplul 3. Fragmente ale programelor care efectuează diferite acțiuni cu o listă dublu conectată:
// lista fără un link de titlu
dacă returnul (p = NULL);
// p nu este egal cu pointerul până la începutul listei - ph
// listați cu o legătură de capital
dacă (p -> următor = = p) retur;
pr = p -> pred; // Indicatorul curent pr a primit o valoare de referință
// la ultimul element din listă
// nu este egal cu pointerul la link-ul de titlu al listei - p
x = noua listă2; // Include un element nou (în lista cu
x -> pred = p -> pred; // link-ul titlu) în fața elementului, pe
x -> next = p; // care se referă la p
p -> pred -> next = x;
p -> pred -> next = p -> următor; // Excludeți din listă cu capital
p -> următoarea -> pred = p -> pred; // legătura elementului cu care
șterge p; // indicatorul de referință p
Articole similare
Trimiteți-le prietenilor: