Structura secventa. Tipul de date abstract secventa

Structura secventa. Tipul de date abstract secventa

Caracteristica comuna a structurilor de date prezentate pana in prezent (tablouri, articole, multimi) este aceea ca toate au cardinalitatea finita, respectiv cardinalitatea tipurilor lor componente este finita.

Din acest motiv, implementarea lor nu ridica probleme deosebite.

Cele mai multe dintre asa numitele structuri avansate: secventele, listele, arborii, grafurile, etc, sunt caracterizate prin cardinalitate infinita.

Aceasta diferenta fata de structurile clasice este de profunda importanta avand consecinte practice semnificative.

Spre exemplu structura secventa avand tipul de baza T₀ se defineste dupa cum urmeaza:

S₀=< > (secventa vida)

S_i=<S_i-1,s_i>   unde 0 < i si s_iI T₀

Cu alte cuvinte, o secventa cu tipul de baza T₀ , este:

o      Fie o secventa vida

o      Fie o concatenare a unei secvente (cu tipul de baza T₀) cu o valoare (s_i) a tipului T₀ .

Definirea recursiva a unui tip secventa conduce la o cardinalitate infinita.

o      Fiecare valoare a tipului secventa contine in realitate un numar finit de componente de tip T₀ ,

o      Acest numar este nemarginit deoarece, pornind de la orice secventa se poate construi o secventa mai lunga.

O  consecinta importanta a acestui fapt este:

Volumul de memorie necesar reprezentarii unei structuri avansate, nu poate fi cunoscut in momentul compilarii,

Ca atare, este necesara aplicarea unor scheme de alocare dinamica a memoriei, in care memoria este alocata structurilor care 'cresc' si este eliberata de catre structurile care 'descresc'.

Pentru a implementa  aceasta cerinta, este necesar ca limbajul superior utilizat in implementare sa fie prevazut cu acces la functii sistem care permit:

Alocarea / eliberarea dinamica a memoriei

Legarea / referirea dinamica a componentelor

In aceste conditii cu ajutorul instructiilor limbajului pot fi descrise si utilizate structuri avansate de date.

Tehnicile de generare si de manipulare a unor astfel de structuri avansate sunt prezentate in capitolele urmatoare ale cursului

Structura secventa este din acest punct de vedere o structura intermediara;

Ea este o structura avansata din punctul de vedere al cardinalitatii care este infinita

Este insa atat de curent utilizata incat includerea sa in multimea structurilor fundamentale este consacrata.

Aceasta situatie este influentata si de faptul ca alegerea unui set potrivit de operatori referitori la structura secventa, permite implementatorilor sa adopte reprezentari potrivite si eficiente ale acestei structuri.

Drept consecinta, mecanismele alocarii dinamice a memoriei devin suficient de simple pentru a permite o implementare eficienta, neafectata de detalii, la nivel de limbaj superior.