Liste Liniare C++

I. ALOCAREA DINAMICA A MEMORIEI

1. VARIABILE DE TIP POINTER

Def. MEMORIA interna poate fi privita ca o serie de octeti.Pentru a-i distinge acestia sunt numerotati.Numarul de ordine al unui octet se numeste adresa.

Def. Adresa primului octet al variabilei se numeste adresa variabilei.

=>Variabilele de tip pointer se caracterizeaza prin faptul ca valorile pe care le pot memora sunt adrese ale altor variabile.

Exista adrese ale variabilelor de tip int, adrese ale variabilelor de tip float, adrese ale variabilelor de tip char,etc.Din acest motiv si tipul variabilelor de tip pointer este diferit.

=>Adresa unei variabile se obtine cu ajutorul operatorului de referentiere & , care trebuie sa preceada numele variabilei :

&nume_variabila ;

=>Fiind data o variabila de tip pointer catre variabile de un anumit tip, care memoreaza o adresa a unei varioabile ce acel tip, pentru a obtine continutul adresei a carei adresa este memorata se utilizeazaoperatorul unar *,numit si operator de diferentiere.

2.ALOCAREA DINAMICA A MEMORIEI

Anumite variabile pot fi declarate dinamic.Asta inseamna ca :

- Spatiul necesar memorarii este rezervat intr-un segment special acestui scop, numit HEAP.

-In memorie se rezerva spatiu in timpul executarii programului, atunci cand se utilizeaza un anumit operator.

-Atunci cand variabila respectiva nu mai este utila, spatiul din memorie este eliberat, pentru afi rezervat, daca este cazul, pentru alte variabile.

Mecanismul alocarii dinamice este urmatorul :

=>Se declara o variabila de tip pointer , s-o numim P, care permite memorarea unei adrese.

=>Se aloca variabila dinamica prin operatorul NEW aplicat asupra unui tip,iar rezultatul este atribuit variabilei P.In urma acestei operatii variabila P retine adresa variabilei alocate dinamic.

In C++, pentru alocarea dinamica se utilizeaza urmatorii operatori:

=>Operatorul NEW aloca spatiu in HEAP pentruo variabila dinamica.Dupa alocare adresa variabilei se atribuie lui P,unde P este o variabila de tip pointer catrea tip:

p=new tip

=>Operatorul DELETE elibereaza spatiul rezervat pentru variabila a carei adresa este retinuta in P.Dupa eliberare, continutul variabilei P este nedefinit:

delete p

II. LISTE LINIARE

1. DEFINITIA LISTELOR

O lista liniara este o colectie de n>=0 noduri,x1,x2,.....xn aflate intr-o relatie de ordine.Astfel ,x1 este primul nod al listei, x2 este al doilea nod al listei ,...,xn este ultimul nod al listei.Operatiile permise sunt :

-Accesul la oricare nod al listei in scopul citirii sau modificarii informatiei continute de acesta.

-Adaugarea unui nod,indiferent de pozitia pe care o ocupa in lista.

- Stergerea unui nod, indiferent de pozitia pe care o ocupa in lista.

-Schimbarea pozitiei unui nod in cadrul listei.