Structurile de alocate dinamic sunt structuri ale caror componente se aloca in timpul executarii programului.
Tipuri de structuri dinamic:
-liniare
-arborescente
-retea.
Variabilele dinamice(pointeri)
Prin variabila dinamica(pointeri ) intelegem o variabila care retine la un moment dat o adresa(*p)
-se numesc liste:-simplu inlantuite
-dublu inlantuite
Liste liniare simplu inlantuite(llsi)
Prin llsi intelegem un sir finit de componente numite noduri.
Obs:O llsi poate fi si vida.
Structura unui nod intr-o llsi.
-este formata din 2 campuri:
-campul in care se retine informatia utila-numeric
-caracter
-sir de caracter
-structurat
-campul de adresa,adresa catre nodul urmator.
Daca campul de adresa nu contine nimic atunci i se va atribui constanta
Operatii cu liste:
-crearea unei liste .
-parcurgerea unei liste .
-adaugarea unui nod nou in lista.
-stergerea unui nod din lista.
Declararea structurii unui nod:
Struct nod
{tip infutila;
nod *urm;
}*p,*u,*l;
Exemplu 1:
1.Sa se declare structura unui nod pentru o llsi care retine in campul pentru informatia utila un numar real.
Ex1:
struct nod
{float x;
nod *urm;}*p,*u,*l;
Exemplu 2:
2.Sa se scrie structura unui nod care retine ca informatie utila un nr intreg si un caracter.
Ex 2:
Struct nod
{int x;char c;
nod*urm;}*p,*u,*l; *l-valoarea curenta ;
l-adresa nodului;
Notatii:
l->x;-variabila de tip real de la adresa l;
p->urm->x;-informatia utila care este retinuta in nodul care urmeaza dupa nodul p.
l=p->urm->urm;-adresa celui de-al treilea nod din lista.
l->x=p->urm->urm->x;-informatia utila pentru cel de-al treilea nod din lista.
Ex 2:
p->x;-informatia de tip intreg.
p->c;-informatia de tip character.
l=new nod;-pentru a adauga adresa sau a crea noduri in lista.
Adaugarea unui nod nou in lista:
-se poate face:
-in fata primului nod din lista
-in interiorul listei
-sau dupa ultimul nod din lista.
La adaugarea unui nod nou in lista sunt posibile urmatoarele situatii:
1.lista este vida si se adauga primul ei element;
2.lista nu este vida,caz in care nodul se poate adauga:
a.inaintea nodului indicat de pointerul p,fiind posibile doua situatii:
i. p indica primul element al listei.
ii.p nu indica primul element al listei.
b.dupa nodul indicat de pointerul p,fiind posibile doua situatii:
i. p indica ultimul element din lista.
ii.p nu indica ultimul element din lista.
Pentru a evita aceste situatii, se poate recurge la un mic artificiu creand lista de la inceput cu doua noduri fictive(in care nu se memoreaza nici o informatie) si astfel nu mai apar atatea cazuri pentru adaugarea unui nod nou.Cele doua noduri fictive se mai numesc santinele.In acest fel ,la adaugarea unui nod nou,nu mai este necesara verificarea cazurilor particulare in care lista e vida sau in care dorim sa adaugam unu nou nod inaintea primului nod din lista sau dupa ultimul nod din lista.
Adaugarea unui nou element dupa un nod oarecare din lista indicat de pointerul p se face astfel:
1.se aloca zona de memorie pentru noul nod;
2.se copiaza in urm din noul nod adresa urm din nodul indicat de p(adica adresa nodului urmator lui p,deci se face legatura cu succesorul noului nod);
3.se memoreaza adresa noul nod in urm din p(deci legatura predecesorului noului nod)
4.se memoreaza informatia in campul inf din noul nod.
Facem observatia ca trebuie respectata cu strictete ordinea operatiilor deoarece ,de exemplu,daca s-ar efectua operatia 3 inaintea operatiei2,s-ar pierde adresa noduluicare urma initial dupa p( in mod iremediabil).Doar operatia4 poate poate fi efectuata oriunde dupa oeratia 1(adica,oricand,dupa ce s-a alocat spatiu pentru noul nod )
Intr-o llsi putem adauga un nou nod si inaitea unui nod indicated un pointer p,insa printr-un mic artificiu.De fapt cream noul nod tot dupa cel indicat de p,mutam in el informatia din nodul indicat de p(aflat in fata noului nod) dupa care noua informatie o depunem in nodul din fata,momentan indicat de p(dupa care p va memora adresa nodului introdus in lista).
Adaugarea in fata primului nod:
l=new nod;
l->urm=p;
p=l;
p->x=p->urm->x;
Adaugarea unui nod in interiorul listei :
-se parcurge lista pana se identifica nodul din lista dupa care se face inserarea.
Cautarea nodului se poate face fie in functie de informatia utila,fie in functie de numarul de ordine al nodului in lista.
q=new nod;
q->urm=l->urm;
l->urm=q;
q->x=q->urm->x;
Stergerea unui element in lista,aflat dupa un nod indicat de pointerul p se face astfel:
1.se memoreaza in pointerul nod_el adresa succesorului lui p(adica adresa nodului ce urmeaza a fi eliminat);
2.se copiaza in urm din nodul indicat de p adresa nodului ce urmeaza dupa nodul ce se va elimina(adica se face legatura cu succesorul nodului ce se va elimina);
3.se elibereaza zona de memorieocupata de nodul ce se elimina.
nod_el=p->urm;
p->urm=p->urm-urm;
delete nod_el;
Ca si la adaugarea unui nod nou in lista,si la stergerea unui nod din lista sunt posibile mai multe situatii.Listele create cu santinele elimina verificarea unor cazuri particulare ca,de exemplu,cel in care dorim sa eliminam ultimul mod din lista sau cel in care dorim eliminarea unui nod aflat dupa cel indicat de p si pointerul p il indica chiar ultimul (deci,dupa el nu mai exista nici un nod care sa poata fi eliminate.)
Problema:
1.Se citesc de la tastatura n numere intregi.Sa se creeze o llsi care sa contina in fiecare nod o valoare intreaga.Sa se numere cate noduri contin valori pare si sa se afiseze lista..
#include<conio.h>
#include<iostream.h>
int main()
{struct nod;
{int x;
nod*urm;}*p,*u,*l,*q;
int i,n,y;
cout<<”n=”;cin>>n;
p=new nod;
cout<<”Introduceti valoarea”;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;
while(l!=NULL)
{if(l->x%2==0)
k++;
l=l->urm;
}
cout<<”k=”<<” ”;
l=p;
while(l!=NULL)
{cout<<l->x<<” ”;
l=l->urm;
}
return 0;
}
Stiva
Stiva este un caz special de lista liniara în care intrarile si iesirile se fac la un singur capat al ei.
Exemple de stive de obiecte sunt lucuri concrete pe care le folosim in vaia de zi cu zi : stive de lemne, de lazi, de baloti de paie, de farfurii, de dosare etc.
Structura de stiva presupune, conform definitiei, o anumita disciplina: totdeauna se adauga un obiect "deasupra" ultimului depus si se extrage totdeauna ultimul obiect adaugat.
Se spune ca accesul la o stiva este de tip LIFO (Last In - First Out).
Astfel putem diferentia doua tipuri de stiva : varianta statica (stanga) si cea dinamica (dreapta jos).
Crearea si afisarea unei stive se face in felul urmator :
# include
int main ()
{ struct nod { int x;
nod*urm; }*vf,*q;
vf=new nod;
vf->urm=NULL;
cin>>vf->x;
for (i=2;i<=n;i++)
{ q=new nod;
q->urm=vf;
vf=q;
cin>>q->x;
}while (vf!=NULL)
{ cout<
vf=vf->urm;
}
return 0;
}
Coada
Coada este lista liniara simplu inlantuita care se construieste pe principiul primul intrat primul iesit. Coada are 2 capete. Prin capatul din dreapta introducem noduri in coada iar la capatul din stanga extragem noduri din coada.
Coada este o structura de tip FIFO.
Tipul acesta de liste, cozile , se utilizeaza mai mult in sistemele de operare ( in rutinele de alocare a resurselor) sau in programe de simulare.
O coada e determinata de:
• capul cozii (arata locul de unde se extrage);
• coada cozii (arata locul unde se adauga);
• lungimea cozii (numarul elementelor din coada).
Cele mai importante operatii care se pot efectua cu coada sunt:
• verificarea daca coada este vida;
• verificarea daca coada este plina;
• inserarea unui element x in coada;
• extragerea unui element x din coada.
Declararea cozii:
#include
#include
int main()
{struct nod
{int inf;
nod *urm;}*p,*u,*q;
int n,i;
p=new nod;
cout<<"n=";cin>>n;
p=u;
cin>>p->int;
u->urm=NULL;
for(i=1;i<=n;i++)
{q=new nod;
cin>>q->inf;
q=u;
u->urm=NULL;
q=q->urm;}
Afisarea cozii:
q=p;
while(q!=NULL)
{cout
q=q->urm;}
return 0;}
Liste liniare simplu inlantuite - Torcea Laviniu;
Stiva - Mitrici Paul;
Coada - Bulboaca Emanuel .
