LISTE DUBLU ĪNLĂNŢUITE
Continutul lucrarii
Īn lucrare sunt prezentate principalele operatii asupra listelor dublu īnlantuite: crearea, inserarea unui nod, stergerea unui 555i85f nod, stergerea listei.
Consideratii teoretice
Lista dublu īnlantuita este lista dinamica īntre nodurile careia s-a definit o dubla relatie: de succesor si de predecesor.
Modelul listei dublu īnlantuite, pentru care se vor da
explicatiile īn continuare, este prezentat īn figura 2.1.
Tipul unui nod dintr-o lista dublu īnlantuita este definit astfel:
typedef struct tip_nod TIP_NOD;
Ca si la lista simplu īnlantuita, principalele operatii sunt:
crearea;
accesul la un nod;
inserarea unui nod;
stergerea unui 555i85f nod,
stergerea listei.
Lista dublu īnlantuita va fi gestionata prin pointerii prim si ultim:
TIP_NOD *prim, *ultim;
prim -> prec = 0;
ultim -> urm = 0;
Crearea unei liste dublu īnlantuite
Initial lista este vida:
prim = 0; ultim = 0;
Dupa alocarea de memorie si citirea datelor īn nod, introducerea nodului de pointer īn lista se va face astfel:
if(prim= =0)
else
Accesul la un nod
Accesul la un nod se poate face:
secvential īnainte (de la "prim" spre "ultim"):
p = prim;
while (p != 0)
secvential īnapoi ( 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 īnlantuita (lucrarea 1, par. 2.2.).
Inserarea unui nod
Inserarea unui nod īntr-o lista dublu īnlantuita se poate face astfel:
a) īnaintea primului nod:
if (prim == 0)
else
b) dupa ultimul nod:
if (prim == 0)
else
c) īnaintea unui nod de cheie data key:
Dupa cautarea nodului de cheie key, presupunānd 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, presupunānd 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 555i85f 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 īntregii liste se realizeaza stergānd 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
avānd modelul din fig.3.1.
Sa se scrie functiile pentru realizarea operatiilor de
creare, inserare, stergere pentru o lista dublu
īnlantuita circulara avānd modelele din fig.3.2.
De la tastatura se citesc n cuvinte ;sa se creeze o lista dublu īnlantuita, care sa contina īn noduri cuvintele distincte si frecventa lor de aparitie. Lista va fi ordonata alfabetic. Se vor afisa cuvintele si frecventa lor de aparitie a) īn ordine alfabetica crescatoare si b) īn ordine alfabetica descrescatoare.
Folosind o lista circulara dublu īnlantuita sa se simuleze urmatorul joc: n copii, ale caror nume se citesc de la tastatura, stau īn cerc. Īncepānd cu un anumit copil (numele sau se citeste), se numara copiii īn sensul acelor de ceasornic. Fiecare al m-lea copil (m se citeste) iese din joc. Numaratoarea continua īncepānd cu urmatorul copil din cerc. Cāstiga jocul ultimul copil ramas īn cerc.
Aceeasi problema ca la 3.4., dar numaratoarea se face īn sens contrar cu cel al acelor de ceasornic.
|
