Liste dublu inlantuite - laborator

LISTE DUBLU INLANTUITE - LABORATOR

Continutul lucrarii

In lucrare sunt prezentate principalele operatii asupra listelor dublu inlantuite: crearea, inserarea unui nod, stergerea unui nod, stergerea listei.

Consideratii teoretice

Lista dublu inlantuita este lista dinamica intre nodurile careia s-a definit o dubla relatie: de succesor si de predecesor.

Modelul listei dublu inlantuite, pentru care se vor da explicatiile in continuare, este prezentat in figura 2.1.

Tipul unui nod dintr-o lista dublu inlantuita este definit astfel:

typedef struct tip_nod TIP_NOD;

Ca si la lista simplu inlantuita, principalele operatii sunt:

crearea;

accesul la un nod;

inserarea unui nod;

stergerea unui nod,

stergerea listei.

Lista dublu inlantuita va fi gestionata prin pointerii prim si ultim:

TIP_NOD  *prim, *ultim;

prim -> prec = 0;

ultim -> urm = 0;

Crearea unei liste dublu inlantuite

Initial lista este vida:

prim = 0; ultim = 0;

Dupa alocarea de memorie si citirea datelor in nod, introducerea nodului de pointer in lista se va face astfel:

if(prim= =0)

else

Accesul la un nod

Accesul la un nod se poate face:

secvential inainte (de la "prim" spre "ultim"):

p = prim;

while (p != 0)

secvential inapoi ( de la "ultim" spre "prim"):

p = ultim;

while (p != 0)

pe baza unei chei. Cautarea unui nod de cheie data key se va face identic ca la lista simplu inlantuita (lucrarea 1, par. 2.2.).

Inserarea unui nod

Inserarea unui nod intr-o lista dublu inlantuita se poate face astfel:

a) inaintea primului nod:

if (prim == 0)

else

b) dupa ultimul nod:

if (prim == 0)

else

c) inaintea unui nod de cheie data key:

Dupa cautarea nodului de cheie key, presupunand ca acesta exista si are adresa q, nodul de adresa p va fi inserat astfel:

p -> prec = q -> prec; p -> urm = q;

if (q -> prec != 0) q -> prec -> urm = p;

q -> prec = p;

if (q == prim) prim = p;

d) dupa un nod de cheie data key:

Dupa cautarea nodului de cheie key, presupunand ca acesta exista si are adresa q, nodul de adresa p va fi inserat astfel:

p -> prec = q; p -> urm = q -> urm;

if (q -> urm != 0) q -> urm -> prec = p;

q -> urm = p;

if (ultim == q) ultim = p;

Stergerea unui nod

Exista urmatoarele cazuri de stergere a unui nod din lista:

a) stergerea primului nod; acest lucru se poate face cu secventa de program:

p = prim;

prim = prim -> urm; /* se considera lista nevida */

elib_nod(p); /* eliberarea nodului */

if (prim == 0) ultim = 0; /* lista a devenit vida */

else prim -> prec = 0;

b) stergerea ultimului nod:

p = ultim;

ultim = ultim -> prec; /* se considera ca lista nu este vida */

if (ultim == 0) prim = 0; /* lista a devenit vida */

else ultim -> urm = 0;

elib_nod(p); /* stergerea nodului */

c) stergerea unui nod precizat printr-o cheie key. Presupunem ca nodul de cheie key exista si are adresa p (rezulta din cautarea sa):

if ((prim == p) && (ultim = =p))

else if(p == prim)

else if (p == ultim)

else

Stergerea listei

Stergerea intregii liste se realizeaza stergand nod cu nod astfel:

TIP_NOD *p;

while (prim != 0)

ultim = 0;

Mersul lucrarii

Sa se defineasca si sa se implementeze functiile pentru structura de date:

struct LISTA

avand modelul din fig.3.1.

Sa se scrie functiile pentru realizarea operatiilor de creare, inserare, stergere pentru o lista dublu inlantuita circulara avand modelele din fig.3.2.

De la tastatura se citesc n cuvinte ;sa se creeze o lista dublu inlantuita, care sa contina in noduri cuvintele distincte si frecventa lor de aparitie. Lista va fi ordonata alfabetic. Se vor afisa cuvintele si frecventa lor de aparitie a) in ordine alfabetica crescatoare si b) in ordine alfabetica descrescatoare.

Folosind o lista circulara dublu inlantuita sa se simuleze urmatorul joc: n copii, ale caror nume se citesc de la tastatura, stau in cerc. Incepand cu un anumit copil (numele sau se citeste), se numara copiii in sensul acelor de ceasornic. Fiecare al m-lea copil (m se citeste) iese din joc. Numaratoarea continua incepand cu urmatorul copil din cerc. Castiga jocul ultimul copil ramas in cerc.

Aceeasi problema ca la 3.4., dar numaratoarea se face in sens contrar cu cel al acelor de ceasornic.