Cercetarea și Implementarea Listelor în C++

1.Introducere:

Limbajul de programare C++ este limbajul C extins cu clase, functii inline, operator de supraincarcare, nume de functie supraincarcat, tipurile constant, referinta, operatorii de gesti- une a memoriei libere, verificarea argumentelor functiei si o sintaxa noua de definire a functiilor. Limbajul C este descris in "The C Programming Language" de Brian W. Kernighan si Dennis M. Richie, Prentice Hall, 1978. Acest manual a fost derivat din sistemul UNIX V "The C Programming Language - Reference Manual" cu permisiunea lui AT&T Ball Laboratories. Diferentele dintre C++ si C sint rezumate in &15. Manualul descrie limbajul C++ din iunie 1985.

Lista este o structura dinamica, situata in memoria centrala, in care toate elementele sunt de acelasi tip; numarul de elemente este variabil, chiar nul.

De remarcat diferentele fata de definitia tabloului: tabloul este o structura statica, situata in memoria centrala, in care toate elementele sunt de acelasi tip; numarul de elemente este constant.

O alta definire a listei este:

O lista L este o secventa de zero sau mai multe elemente, numite noduri, toate fiind de acelasi tip de baza T.

L=a1,a2, ,an (n>=0)

Daca n>=1, a1 se spune ca este primul nod al listei, iar an, ultimul nod. Daca n=0, lista este vida.

Numarul de noduri se numeste lungimea listei.

Un nod al listei liniare care apare ca o structura recursiva, avand o componenta de tip pointer la structura, reprezentand legatura ( inlantuirea ) spre nodul urmator. Lista in care fiecare nod are o sinfura inlantuire se numeste lista simplu inlantuita.

2.Liste Simple

Lista simplă este o structura de date liniară, formată din elemente denumite noduri. Un nod este compus din două categorii de cîmpuri:

*Cîmpul cu informația necesară prelucrării;

*Cîmpul cu informația de legătură cu nodul succesor în cadrul structurii de tip lista simplă; se definește sub forma de pointer către structura nodului pentru a reține adresa nodului care urmează in cadrul listei simple.

Particularitați ale structurii de tip listă simplă:

Informația de legatură a ultimului nod este nulă: cei 4 octeți rezervați în memorie conțin valori nule;

Gestionarea structurii se realizează printr-o variabilă de tip pointer spre structura declaratăa nodului; adresa primului nod și cîmpurile cu informațiile de legătură asigură referirea și utilizarea nodurilor din lista simplă;

Declararea structurii unui nod este:

struct ElementMR{

unsignedint l,c;

double val;

};

struct NodMR{

ElementMR tuplu;

NodMR *next;

};