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.
 |
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.
 |
 |
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.
|
