Home - Rasfoiesc.com
Educatie Sanatate Inginerie Business Familie Hobby Legal
Doar rabdarea si perseverenta in invatare aduce rezultate bune.stiinta, numere naturale, teoreme, multimi, calcule, ecuatii, sisteme




Biologie Chimie Didactica Fizica Geografie Informatica
Istorie Literatura Matematica Psihologie

Informatica


Index » educatie » Informatica
» LISTE CIRCULARE SIMPLU INLANTUITE


LISTE CIRCULARE SIMPLU INLANTUITE


LISTE CIRCULARE SIMPLU INLANTUITE

Continutul lucrarii

Ilustrarea principalelor tehnici de implementare a structurii de date.

Consideratii teoretice



Fie o lista simplu inlantuita ca in figura de mai jos:


Daca in lista de mai sus pointerul ultimului element va indica primul element, se va obtine o lista circulara simplu inlantuita. (ultim -> urm = prim).

Intr-o lista circulara toate nodurile sunt echivalnte, fiecare nod are un urmator si fiecae nod este urmatorul altui nod. Intr-o lista circulara nu exista capete. Pentru a gestiona o lista circulara se va folosi un pointer ptr_nod, acesta indicand un nod oarecare al listei.

Ca si la lista simplu inlantuita, principalele operatii sunt:


crearea;

accesul la un nod;

inserarea unui nod;

stergerea unui nod,

stergerea listei.

Structura unui nod este urmatoarea:

typedef struct nod NOD;

Crearea listei circulare simplu inlantuite

Initial lista este vida:

ptr_nod = 0;

Introducerea in lista a unui nod se va face dupa nodul curent (ptr_nod) astfel:

a)                                               Daca ptr_nod este zero , insemna ca lista este vida si nodul ce va trebui introdus este singurul nod din lista

b)                                               Daca ptr_nod nu este zero, lista contine lemente si introducerea noului nod se va realiza dupa nodul curent (ptr_nod)

/* crearea nodului */

p = (NOD *)malloc(sizeof(NOD));/* rezervarea memorie */

p->info=KEY;

//citire date in nod la adresa p;

if (ptr_nod = = 0)

else

Accesul la un nod

Nodurile se acceseaza secvential pornind de la nodul curent (ptr_nod).

p=ptr_nod;

if(p! = 0) /* lista nu este vida */

do

while (p! = ptr_nod);

Inserarea unui nod

Se pun urmatoarele probleme:

inserarea inaintea unui nod de cheie data;

inserarea dupa un nod de cheie data.

In ambele cazuri se cauta nodul de cheie data avand adresa q; daca exista un astfel de nod ,se creeaza nodul de inserat de adresa p si se fac legaturile corespunzatoare.

a)      Inserarea inaintea unui nod de cheie data

se cauta nodul de cheie data, tinandu-se minte nodul anterior

daca nodul a fost gasit atunci se realizeaza inserarea, nodul anterior va pointa catre noul nod (p), iar nodul p va pointa catre nodul de cheie data (q)

b)      Inserarea dupa un nod de cheie data

se cauta nodul de cheie data:

daca nodul s-a gasit, se insereaza noul nod:

p->urm=q->urm;

q->urm=p;

Stergerea unui nod de cheie data

Stergerea unui nod de cheie data key se va face astfel:

se cauta nodul de cheie data:

q = ptr_nod;

do

while (q! = ptr_nod);

se sterge nodul

if (q-> info == key)

free(q);

Stergerea listei

Stergerea listei circulare simplu inlantuite se va face astfel:

p = ptr_nod;

do

while (p! = ptr_nod);

ptr_nod = 0;





Politica de confidentialitate





Copyright © 2024 - Toate drepturile rezervate