Structuri de date

Structuri de date

Prelucrarea automata a datelor necesita, pe langa activitatiile legate de formularea problemei, de analiza acesteia in vederea gasirii algoritmului de rezolvare si o alta activitate deosebit de importanta, legata de organizarea datelor.

Organizarea datelor este un proces care cuprinde urmatoarele activitati:

identificarea datelor;

clasificarea si descrierea propietatiilor, a caracteristicilor datelor;

gruparea datelor in colectii de date destinate prelucrarii automate;

reprezentarea externa pe suporturi tehnice;

identificarea, definirea si descrierea procedurilor de prelucrare automata.

Eficienta prelucrarii automate a datelor, succesul acesteia depind in mare masura, de organizarea interna si externa a datelor, de stabilirea unor structuri de date care sa corespunda cerintelor de prelucrare.

Concepte de baza

Odata cu aparitia bazelor de date, in terminologia curenta au fost introduse si utilizare 3 concepte de baza in organizarea datelor, si anume: entitate, atribut si valoare.

Entitatea reprezinta un obiect concret sau abstract, reprezentat prin proprietatiile lui. Pe de alta parte orice proprietatea a unui obiect poate fi descrisa printr-o pereche ( Atribut, Valoare ); prin urmare o entitate poate fi reprezentata prin mai multe proprietati, deci mai multe perechi de forma ( Atribut, Valoare ).

De exemplu, un student X se poate reprezenta prin perechi ( Nume, Ion ), ( Facultate, Informatica ), ( Telefon, 435 34 76 ), ( Grupa 601 ) etc.

Practic, multimea atributelor, Nume, Facultate, Telefon, Grupa, poate fi asociata mai multor studenti; aceasta inseamna ca un atribut nu caracterizeaza doar o entitate, ci o clasa de entitati, numita entitate grup.

In exemplul nostru, entitatea grup se poate numi STUDENTI.

Notiunea de atribut este cunoscuta si sub numele de camp     sau caracteristica.

Notiunea de data

In informatica prin data, se intelege un model de reprezentare a informatiilor despre obiectele supuse prelucrarii automate, accesibil atat utilizatorului cat si componentelor calculatorului.

In functie de obiectele pe care le reprezinta datele se pot clasifica in:

date elementare sau scalare care se prezinta sub forma de entitati indivizibile

colectii de date, care se prezinta sub forma unor multimi de date elementare intre care se definesc si se descriu anumite relatii.

Componentele unei structuri se pot identifica si selecta prin numele de identificare sau prin pozitia pe care o ocupa in cadrul structurii, potrivit relatiei de ordine stabilita.

Dupa tipul componentelor, structurile de date se pot grupa in:

structuri de date omogene, care contin elemente de acelasi tip;

structuri de date eterogene, care contin componente de tipuri diferite.

OBSERVATIE:Daca o structura se poate descompune in structuri de acelasi tip, atunci structura respectiva este recursiva.

In mod corespunzator, structurile de date vor putea fi:

structuri de date interne , avand caracter temporar, deoarece sunt realizate in memoria interna de tip RAM ( volatila );

structuri de date externe, care au un caracter relativ permanent, deoarece sunt memorate pe suport extern. Aceste structuri pot curpinde:

o       fisiere de date

o       baze de date

o       banci de date

Din punct de vedere al modului de alocare a zonelor de memorie, structurile de date pot fi grupate astfel:

structuri de date statice, la care alocarea zonelor de memorie necesare pastrarii temporare a datelor este facuta in momentul compilarii programului si ramane aceasi pe toata durata de executie a programului respectiv;

structuri de date dinamice, la care alocarea zonelor de memorie se face numai in momenutl executiei programului, la momentul necesar, ele putand fi modificate, eliberate, sau realocate pe toata durata de executie a programului respectiv.

Dupa nivelul de structurare a datelor se poate face gruparea:

structura logica, care se refera la modul de ordonare a datelor, la operatorii de prelucrare a datelor;

structura fizica, reprezentand modul de implementare, de reprezentare a datelor, pe suport magnetic de date.

Tipuri de structuri de date

Am vazut ca o structura de date reprezinta practic o colectie de date intre care s-au definit o serie de relatii care duc la un anumit mecanism de selectie si identificare a datelor.

Aceste relatii pot fi de tipul:

de echivalenta

de ordine

de ordine totala

de preordine

Se numeste tip de structura de date o multime ordonata de date, intre care s-au stabilit anumite relatii si care folosesc, pentru realizarea operatiilor un grup de operatori de baza cu o anumita semantica.

Principalele tipuri de structuri de date ( logice ) sunt:

structura punctuala

structura liniara

a1 a2 a3 a4

Structura liniara simpla

Principalele caracteristici ale acestui tip de structura sunt:

cardinalul multimii elementelor initiale este egal cu 1

cardinalul multimii elementelor terminale este egal cu maxim 1

orice element neterminal are un succesor imediat unic

primul element nu are predecesori

ultimul element nu are succesori

relatiile stabilite intre date sunt de tip 1 la 1

daca exista un cuplu in relatie de forma ( u, v ), unde v este ultimul element al structurii, iar u este primul element, atunci structura se numeste structura liniara inelara sau circulara.

intre date se stabilesc relatii de tipul 1 la 1

structura liniara se numeste structura liniara cu elemente structurate arborescent, daca componentele ei sunt structuri arborescente

structura liniara se numeste structura liniara cu elemente structurate retea, daca componentele ei sunt structuri de tip retea

structura arborescenta, sau descendenta, sau ierarhica este definita atunci cand intre elementele colectiei de date exista o relatie de ordine.

Arbori binari

Datorita specificului lor, arborii binari admit o reprezentare grafica simetrica, axa de simetrie trecand prin radacina arborelui. De aceea, subarborii unui element oarecare sunt denumiti subarbore stang, si respectiv subarbore drept, functie de pozitia relativa a acestora fata de elementul respectiv.

Astfel pentru arborii binari s-au identificat si s-au descris 3 modalitati de parcurgere a elementelor arborelui denumite:

parcurgere in preordine

parcurgere in inordine

parcurgere in finordine ( postordine )

structura retea, definita atunci cand intre elementele colectiei de date exista o relatie de preordine. Ea are urmatoarele caracteristici:

este practic un graf care are, intre doua noduri, legaturi budirectionale;

exista unul sau mai multe noduri initiale (cardinalul miltimii este egal sau mai mare cu 1);

exista unul sau mai multe noduri finale (cardinalul mltimii nodurilor finale este egal sau mai mare cu 1);

orice nod poate avea mai multi predecesori, el putand fi predecesorul propriului predecesor. Atunci apar in retea cicluri. Un ciclu se defineste atunci cand nodul initial este acelasi cu nodul final;

intre elementele structurii de tip retea se regasesc relatii de tip m la n.

Structura relationara este formata din mai multe tabele de date elementare, numite tablori sau relatii, obtinute prin metoda normalizarii, pentru a asigura conditiile de integritate si unicitate a datelor si a elimina astfel nomaliile la actualizari.

Despre acest tip de structura vom invata mai mult la S.G.B.D.-uri, adica la sisteme de gestiune a bazelor de date, special realizate pentru operatii cu colectii de date memorate pe suporti externi.

Informatii despre cantitatile de produse finite care trebuie realizate

Informatii despre structura produselor finite respective.

Fisierul se defineste ca o multime de date omogene din punct de vedere al semnificatiei lor si al cerintelor de prelucrare. Aceasta multime este organizata ca o lista liniara, cu elemente structurale arborescente.

Baza de date se defineste ca o colectie de date aflate in interdependenta, memorata pe suport impreuna cu descrierea datelor si a relatiilor dintre ele.

Banca de date reprezinta un sistem de organizare si prelucrare respectiv tele-prelucrare a datelor constituit din:

baza de date

un sistem de programe pentru gestiunea datelor.

Structuri de date interne

Cele mai frecvent utilizate structuri statice de date sunt:

masive (tablouri )

articole ( inregistrari logice )

Limbajele de programare permit implementarea acestor structuri statice de date.

Masivul reprezinta o structura de date omogena cu una, doua sau n dimensiuni. Masivul cu o dimensiune se numeste in mod uzual vector, iar cu doua matrice.

Exemplu:

Fie vectorul X cu elementele x₁, x₂, x₃, ,x_n un tablou unidimensional cu n elemente componente de acelasi tip.

In memoria interna el va fi memorat astfel:

X

1 2 . n

Adresa    Adresa Adresa Adresa

de de de de

baza baza+1 baza+2*1 baza+(n-1)*1

Reprezentarea elementelor unui vector in memoria interna

Articole.Fisiere de date

Articolul sau inregistrarea logica reprezinta o structura de date interna, eterogena de tipul " structura arborescenta ".

Un articol este format din campuri de date care se identifica in mod unic printr-un identificator sau nume asociat.

Fisierul de date este format din articole sau inregistrari logice care descriu aceleasi entitati si formeaza o colectie de date omogene din punct de vedere al semnificatiei si al cerintelor de prelucrare.

Metodele de organizare a fisierelor definesc regulile care stau la baza constituirii articolelor in fisiere si se stabilesc la operatia de creare a fisierelor. Astfel fisierele pot avea:

Organizare secventiala care memoreaza articolele de date secvential in ordinea introducerilor iar accesul la articole poate fi doar secvential.

Organizare secvential-indexata care presupune crearea fisierului de date cu articolele ordonate crescator dupa valoarea unui camp de date numit cheie de indexare.

Organizare directa care presupune memorarea si apoi identificarea articolelor printr-o cheie care poate fi un camp de date, sau nu, dar a carei valoare se asociaza fiecarui articol in parte.

Metodele de acces la articolele unui fisier stabilesc modalitatile prin care se localizeaza un articol in fisierul de date.

Tipuri de acces:

Acces secvential

Acces direct

Programare orientata spre obiecte

Programare orientata spre obiecte reprezinta un stil de programare nou, care utilizeaza concepte si constructii noi, modalitati noi de structurare a datelor, de tratare a colectiilor de date si programare.

La programarea orientata spre obiecte procedurile de prelucrare si datele sunt incapsulate in obiecte, asupra carora se aplica mesaje care modeleaza comportamentul sistemului.

Date si expresii

Asupra datelor elementare sau memorate in structuri de date statice sau dinamice, interne sau externe, in cadrul prelucrarii atutomate, se pot aplica diferiti operatori, rezultand astfel constructii sintactice denumite expresii.

Expresiile sunt deci grupuri alcatuite din operanzi si operatori. Din evaluarea unei expresii rezulta o valoare, care reprezinta rezultatul ei.

Operatorii pot fi grupati in:

operatori aritmetici

operatori logici

operatori de comparare

operatori pe siruri de caractere

Toate limbajele de programare permit implementarea acestor tipuri de operatori si constructia unor tipuri de expresii corespunzatoare.

In toate limbajele de programare, operatorii aritmetici au reprezentarea:

+ pentru adunare

- pentru scadere

* pentru inmultire

/ pentru impartire

^n pentru ridicarea la putere n

) pentru gruparea operatiilor si schimbarea ordinii normale de executie a acestora.

Este permisa includerea unor paranteze in altele, ordinea de desfacere a acestora fiind dinspre interior spre exterior.