Babutia Ruth

Structurii de date alocate dinamic
Structurile da date alocate dinamic sunt structuri ale caror componente se aloca in timpul executarii programului.
Tipuri de strcuturii dinamice
-liniare
-arborescente
-retea
Structurile de date liniare se numesc:
- liste: liste liniare simplu inlantuite
liste liniare dublu inlantuite
Operatiile cele mai inportante ale unei liste sunt:
- crearea unei liste
- adaugarea sau inserarea unui nod in lista
- stergerea sau eliminarea unui nod din lista
- parcurgerea unei liste.

Structura unui nod este:
struct nod
{
tip informatibila;
nod *urm;
}
*p, *l, *u;

Crearea, parcurgerea, si afisarea unei liste:
int main( )
{ struct nod
{ int x;
nod *urm;} *p, *u, *l, *q;
int n, i, y;
cout<<"n=";cin>>n;
p=new nod;
cout<<" citeste o valoare:"; cin>>p->x;
u=p;
u->urm=NULL;
for(i=2;i<=n;i++) { l=new nod; cin>>l->x;
u->urm=l;
u=l;
u->urm=NULL;
l=p;
k=0;
whike( l!=NULL)
{ if(l->%2==0)
k++;
l=l->urm;}
{ cout<x<<" "; l=l->urm; }
return o;}

Adaugarea unui nod in lista:
l=new nod;
l->urm=p;
p=l;
p->x=p->urm->x;

Adăugarea la sfârşitul listei

Dacă dorim ca nodurile listei să fie parcurse după un anumit criteriu (de exemplu crescător după câmpul cuvant), trebuie ca introducerea unui nou nod în listă să se facă astfel încât să nu se strice ordinea listei (altfel spus, îl vom introduce la locul lui); pentru exemplul considerat, vom introduce noul nod înaintea primului nod cu câmpul cuvant mai mare decât câmpul său cuvant.

Adăugarea la începutul listei

Adăugarea la sfârşitul listei

Adăugarea după nodul p al listei

Ştergerea dintr-o listă simplu înlănţuită ordonată

Dacă dorim să eliminăm un nod din listă, memoria pe care acesta o ocupa va trebui eliberată, pentru a fi folosită la adăugarea de alte noduri; dacă nu o eliberăm explicit cu funcţia free, ea va rămâne marcată ca fiind ocupată pe durata execuţiei programului şi nu va putea fi folosită. De aceea, înainte de a reface legăturile pentru ca nodul de şters să fie eliminat din listă, adresa lui va fi memorată într-o varialbilă pentru a fi eliberată ulterior zona de memorie dedicată lui.

Ştergerea ultimului nod

Ştergerea nodului de după nodul p