Operatii cu liste

Operatii cu liste

In literatura de specialitate exista o multitudine de operatii cu liste (vezi si capitolul trei, paragraful doi). In aceasta lucrare se vor studia doar operatiile de compunere si descompunere a listelor.

Operatiile de compunere si descompunere actioneaza asupra listelor liniare si circulare, cu ambele tipuri de legaturi: simple si duble. Vom studia aceste operatii aplicate pe rind asupra listelor linare si circulare.

Vom considera deocamdata ca in structura acestor liste, in afara de cimpurile de legatura ale elementelor nu intervine decit cimpul cheii de identificare. Cimpul aferent informatiilor utile se va aplica doar in cazurile problemelor concrete.

Fie deci structurile de liste:

- pentru lista liniara simplu lagata:

typedef struct Listals

Plistls;

- pentru lista liniara dublu legata:

typedef struct Listald

Plistld;

- pentru lista circulara simplu legata:

typedef struct Listcs

Plistcs;

- pentru lista circulara dublu legata:

typedef struct Listcd

Plistcd;

1. Compunerea listelor

Fie L1, L2 doua liste. A compune listele L1 si L2 in aceasta ordine inseamna a genera o lista L care va contine toate elementele listei L1 urmate de elementele listei L2.

a) Compunerea listelor liniare

Fie doua liste liniare simplu legate L1 si L2 (ca in figura de mai sus). Notam cu 'P01' si 'P02' variabele referinta spre antetele celor doua liste.

Daca notam cu L lista rezultata din compunerea lui L1 si L2 cu 'P0' variabila referinta spre capul listei, in urma compunerii, va rezulta:

unde P0=P1.

Operatia de compunere presupune deci urmatoarele actiuni:

- se cauta ultimul element al listei L1;

- cimpul 'next' al ultimului element va indica spre primul element al listei L2 (ca si P02);

- P0=P01 .

Algoritmul de compunere va fi simplu:

P0=P01;

P=P0;

while (P->next<>NULL) P=P->next;

P->next=P02;

unde 'P' va fi variabila referinta de tipul 'Plistls'.

Fie acum doua liste liniare dublu legate L1 si L2, unde variabilele referinta spre primul, respectiv ultimul element le notam 'Pp1', 'Pu1', 'Pp2', 'Pu2'.

Notam cu L lista rezultata din compunerea lui L1 cu L2, cu 'Pp' si 'Pu' variabilele referinta spre primul si ultimul al listei si vom avea:

Pp:=Pp1;

Pu:=Pu2;

si, de asemenea, cimpul 'right' al ultimului element din L1 va indica spre primul element din L2, iar cimpul 'left' al primului element din L2 va indica spre ultimul element din L1.

Actiunea de compunere poate fi descrisa astfel:

Pp=Pp1;

Pu=Pu2;

Pu1->right=Pp2;

Pp2->left=Pu1;

b) Compunerea listelor circulare

Fie L1 si L2 doua liste circulare simplu legate si 'P01', 'Po2' variabilele referinta spre ultimul element al celor doua liste. A compune listele L1 si L2 inseamna a genera o lista circulara L, unde variabila 'P0' ce indica spre ultimul element al acasteia va fi tocmai 'P02', ultimul element din lista L1 find legat la primul element din lista L2.

Actiunea de compunere a celor doua liste se poate descrie astfel:

P01->next=P02->next;

P0=P02;

Fie acum L1 si L2 doua liste circulare dublu inlantuite si variabilele referinta 'Pp1' si 'Pp2' ce indica spre primul element din fiecare lista.

A compune listele L1 si L2 inseamna a genera o lista circulara L dublu inlantuita in care primul ei element va fi primul element al listei L1 iar elementele listei L2 se vor insera la dreapta ultimului element al listei L1.

Actiunea de compunere a listelor L1 si L2 poate fi descrisa astfel:

P=Pp1->left;

Pp1->left=Pp2->left;

Pp2->left->right=Pp1;

P->right=Pp2;

Pp2->left=P;

Pp=Pp1;

2. Descompunerea listelor

Fiind data o lista L si un nod al acesteia specificat prin cheia sa de identificare X, a descompune lista L dupa elementul dat inseamna a genera trei liste :

- prima, L1, continind elementele din stinga elementului specificat;

- a doua, L2, care contine doar elementul specificat;

- ultima, L3, ce contine elementele din dreapta elementului specificat.

a) Descompunerea listelor liniare

Fiind data o lista liniara simplu legata L, notind cu 'P0' variabila referinta ce indica spre primul element al acesteia si cu 'P' o variabila referinta auxiliara folosita pentru parcurgerea elementelor listei, prima operatie care se efectueaza este cautarea elementului cu cheia de identificare X.

In acest moment, variabilele referinta spre capetele celor doua liste, notate 'P01', 'P02', 'P03' vor fi:

P01=P0;

P02=P;

P02=P->next;

Actiunile ce se executa pentru descompunerea listei L sunt:

P=P0;

while (P->next->key!=X || P->next->next!=NULL)

P=P->next;

if (P->next->key==NULL)

Se observa ca variabila 'P' este in urma elementului curent cautat, cu un element; aceasta deoarece cind s-a descoperit elementul cu cheia X (P^.next^.key) pointerul 'P' indica spre ultimul element al listei L1, in care va trebui modificat cimpul 'next'la valoarea NIL.

Daca L este o lista dublu legata, operatia de cautare decurge similar ca in cazul anterior, deosebirile constau in modificarea celui de-al doilea cimp de legatura 'left'. Daca notam cu 'Pp' si 'Pu' pointerii spre primul respectiv spre ultimul element al listei L, 'Pp1', 'Pu1', 'Pp2', 'Pu2', 'Pp3' si 'Pu3' pointerii spre primul si ultimul element al noilor liste L1, L2, L3 si cu 'P' o variabila auxiliara folosita pentru parcurgerea listei, vom avea figura de mai jos:

In acest caz pointerul 'P' indica chiar spre elementul cu cheia X (elementul anterior se detecteaza cu ajutorul legaturii 'left'); se va modifica cimpull 'right' al elementului anterior lui 'P', cimpul 'left' al elementului urmator lui 'P'si amindoua cimpurile de legatura ale elementului indicat de 'P'.

P=Pp;

while (P->key!=X || P->right!=NULL) P=P->right;

if (P->key==X)

Observatie :

S-a presupus ca elementul cu cheia X este in interiorul listei; daca el este chiar primul element, sau ultimul element din lista L, atunci lista L1 in primul caz, respectiv lista L2 in al doilea caz vor fi vide.

Pentru a tine seama si de aceste cazuri algoritmii vor trebui sa fie modificati astfel:

- pentru listele simplu inlantuite:

P=P0;

if (P->key==X)

else

}

- pentru lista dublu inlantuita:

P=Pp;

if (P->key==X)

else

}

}

b) Descompunerea listelor circulare

Dindu-se o lista circulara L si un element al sau cu cheia de identificare X, a descompune lista L dupa elementul specificat inseamna a genera doua liste circulare L1 si L2, unde L2 este lista formata doar din elementul specificat, iar lista L1 este chiar lista L din care s-a scos elementul specificat.

Operatia de descompunere in acest caz presupune cautarea in lista initiala L a elementului cu cheia X, extragerea acestui element si crearea listei L2 cu un singur element, cel extras din lista L.

Probleme propuse

1. Sa se scrie un program care creaza 4 liste liniare simplu inlantuite si apoi le compune intr-una singura, listind elementele listei obtinute.

2. Acelasi program ca mai sus pentru liste liniare dublu inlantuite.

3. Sa se scrie un program care creaza o lista circulara simplu inlantuita si apoi o descompune succesiv dupa trei elemente cu cheile specificate ; cele trei liste rezultate cu un singur element le compune intr-o singura lista circulara.

4. Aceeasi problema ca mai sus pentru liste circulare dublu legate.

5. Se considera urmatorul tip de date:

type

listpointer=^listnode;

listnode=record

link:listpointer;

case tag:boolean of

false:(data:char);

true:(dlink:listpointer);

end;

end;

Acest tip de date permite definirea unei structuri de tip lista generalizata. Vom intelege prin lista generalizata o structura de tip lista ale carei elemente pot fi atomi sau, la rindul lor, liste generalizate.

Spre exemplu A = (a, (b, c)) este o lista de lungime 2, primul element fiind atomul "a", iar al doilea lista (b, c). Analog B = (A, A, ()) este o lista de lungime 3 ale carei elemente sint listele A, A si lista vida.

Listele A si B se numesc nerecursive. Fie C = (a, C). Lista C este o lista recursiva de lungime doi.

Sa se scrie o procedura care creaza o copie exacta a unei liste nerecursive in care nu exista subliste partajate (ca de exemplu in lista B de mai sus). Sa se conceapa atit o versiune recursiva cit si una nerecursiva a acestei proceduri.

6. Sa se scrie o procedura care testeaza egalitatea a doua liste generalizate nerecursive avind structura de mai sus. Doua liste sint egale daca au aceeasi structura si aceleasi informatii memorate in cimpurile de date.

7. Adincimea unei liste generalizate S se poate defini recursiv astfel:

/ 0 , daca S este atom

depth(S)=

1+max(depth(x1),..,depth(xn)), daca S=(x1,..,xn) si n

Sa se scrie o procedura pentru determinarea adincimii unei liste generalizate nerecursive.

8. Scrieti o procedura care primeste o lista generalizata nerecursiva care nu are subliste partajate si inverseaza aceasta lista si toate sublistele componente. Spre exemplu, daca l=(a, (b, c)) atunci inversa lui l va fi ((c, b), a).

9. Scrieti o procedura care construieste reprezentarea unei liste generalizate data sub forma unui sir de atomi, virgule, blocuri si paranteze. Se presupune pentru simplificare ca atomii sint litere.

10. O modalitate de reprezentare a listelor generalizate este utilizarea unei reprezentari inlantuite de tipul celor prezentate impreuna cu o tabela de simboluri.

Orice sublista precedata de o litera va avea numele dat de litera respectiva. Se observa ca reprezentarea de mai sus permite tratarea atit a listelor recursive cit si a celor care au subliste partajate. Intrarile din tabela de simboluri au 3 cimpuri: ''name'', ''tag'', ''address''. Cimpul ''name'' indica numele sublistei careia ii corespunde intrarea respectiva, cimpul ''tag'' indica daca intrarea corespunde unei subliste sau unui atom (tag=1 respectiv tag=0) si cimpul 'address'' pointeaza catre sublista respectiva care este nil pentru atom. Sa se scrie o procedura care citeste o secventa de reprezentari cu paranteze separate prin virgula ale unor liste generalizate si construieste o reprezentare a listelor respective de tipul celei de mai sus. Fiecare lista din secventa are obligatoriu un nume. Se presupune ca numele sint litere, iar literele ce apar si nu au fost atribuite altor liste sau subliste se considera atomi. Tabela de simboluri se va implementa printr-o lista simplu inlantuita ordonata alfabetic dupa cimpul 'name''.

11. Sa se creeze o lista circulara simplu legata si sa se inverseze elementele acesteia descompunind-o in liste mai mici care se ordoneaza si apoi se recompun in lista initiala.

12. Sa se creeze o lista circulara simplu legata cu elemente numere intregi si sa se extraga apoi din aceasta lista elementele cu chei negative. Cele doua liste se ordoneaza si in final se concateneaza intr-o lista ordonata.