1.1 Structuri de date

Structura de date este format din una sau mai multe colecii de date ntre elementele creia s-au stabilit mai multe relaii de apartenen sau legtur (organic, tehnologic, funcional, etc.) care conduc la un anumit mecanism de selecie i identificare a componentelor.

Modele de structuri de date au fost inspirate din modul de structurare i organizare din lumea real unde legturile i schimburile materiale i energetice sunt fizice.

n cadrul unei structuri se pot regsi elementele unei singure entiti sau mai multor entiti situaie ce conduce la obinerea unei structuri mai simple sau mai complexe.

Componentele structuri i elementele acestora pot fi individualizate i identificate prin nume sau identificatori sau prin poziia pe care o ocup n structur. Componentele structurii pot fi colecii sau elementele acestora.

Accesul la un element sau localizarea unei componente din structur poate fi realizat:

secvenial prin parcurgerea tuturor componentelor care se afl naintea sa, necunoscnd poziia n structur i atunci structura are un acces secvenial;

direct cnd componenta poate fi selectat direct fr a ine cont de celelalte componente i atunci structura are un acces direct;

mixt cnd localizarea unei componente se face direct urmat de o parcurgere secveniala a structurii.

Rapiditatea i sigurana procesul de cutare depinde de modul n care sunt aranjate n colecie documentele astfel : dac sunt aranjate ntr-o ordine atunci este posibil cutarea direct, dac colecia mai are i un index dup criteriul de cutare;

dac nu sunt ordonate, se recurge la o cutare secvenial pn se localizeaz documentul dorit.

De aici rezult necesitatea unui index corespunztor criteriului de cutare, iar combinaia criteriilor de cutare este egal cu 2n, unde n este numrul de atribute din colecie.

Exemplu.

Fie colecia NIR (Notelor de Intrare Recepie) dintr-o unitate economic care formeaz o colecie de documente i care poate fi tratat ca o structur independent unde cutarea poate fi direct, secvenial sau mixt.

Dependena dintre modul de organizare, aranjare i modul de acces la informaie rezult din exemplele urmtoare :

dac NIR-urile sunt aranjate (ordonate sau indexate) dup numrul acestuia care este unic, atunci se poate face o cutare direct dup numr n caz contrar se face o cutare secvenial;

dac se dorete o cutare dup Furnizor pentru confirmarea facturii, atunci se face o cutare secvenial sau se reordoneaz NIR-urile dup furnizor i numr recepie dup care se face o cutare mixt.

Fie colecia FACTURI de la furnizori, care n momentul primirii de la furnizor se cere confirmarea de la contabilitate sau magazie dac s-a fcut recepia la marfa primit i care este numrul documentului de recepie deci se stabilete o legtur ntre FACTURA i NIR-uri.

Fie colecia DOC-PLA documente de plata care conine documentele de plat a obligaiilor ctre furnizori i care conin o legtur ctre factura / facturile achitate cu acest document prin obiectul plii.

ntre cele trei colecii se poate defini o structur pe baza relaiei de coresponden ca n figura de mai jos n care sunt evideniate legturile.

Relaiile pot fi unidirecionale de la o colecie la alta sau bidirecionale i n cellalt sens. Relaia dintre componentele unei structuri de date poate fi fcut pe baza :

unui atribut de legtur (cod, atribut, valoare, poziie, pointer) cuprins n cadrul fiecrui element din colectivitate;

unei colecii de legtur separate care conine atributele de legtur ale celor dou colecii i alte atribute specifice legturii utilizat n descrierea structurii mainilor, etc.

FACTURI NIR factura conine numrul NIR ului corespunztor, dar dac sunt mai multe NIR-uri atunci este vorba de o list de recepii.

DOC-PL FACTURI documentul de plat conine numrul facturii achitate sau lista de facturi achitate.

Dac relaia este bidirecional atunci i pe documentul corespondent se trece numrul documentului (factura sau documentul de plat).

Fig. 1 Structur de date

1.2 Operaii specifice structurilor

Odat conceput structura de date asupra ei se pot efectua o mulime de operaii care se refer la valori, structur sau coresponden.

Definirea structuri de date presupune :

definirea structurii coleciei de date ( atributele, tipul atributului i mrimea);

fixarea cheilor de identificare unic a elementelor;

definirea relaiilor dintre colecii.

Cele mai frecvente operaii ntlnite sunt:

crearea sau definirea structurii de date n concordan cu facilitile suportului;

actualizarea adugarea de noi elemente, modificarea celor existente sau tergerea unora;

filtrarea cutarea i extragerea elementelor care ndeplinesc o condiie dat;

sortarea aranjarea elementelor structurii dup diferite criterii;

fuziunea - reunirea mai multor colecii de acelai tip;

interclasarea reunirea n ordine a dou colecii de acelai tip;

centralizarea unor valori ale elementelor selectate dup unul sau mai multe criterii;

prelucrarea operaie complex care presupune generarea de noi date sau colecii;

consultarea - operaie complex care presupune extragerea, ordonarea, centralizarea i prezentarea rezultatelor sub o form inteligibil omului (tabel, raport, list, grafic, indicator);

copierea realizarea de copii pentru siguran sau necesare comunicrii;

Din structura de mai sus pe baza relaiei de coresponden se pot afla rspunsuri la ntrebri (query) care implic o colecie sau mai multe, ntre care exist o relaie ca n urmtoarele exemple :

Care sunt NIR urile pentru care nu s-au primit facturi ?

Care este factura corespunztoare unei recepii ?

Care sunt facturile nedecontate , care nu au document de plat ?

Care sunt facturile pltite n avans i cu ce document ?

Care sunt facturile pltite de dou ori i cu ce documente ?

Care este factura i documentul de plat cu care s-a achitat o recepie ?

1.3 Clasificarea structurilor de date

Structurile de date pot fi clasificate dup mai multe criterii. Cunoaterea tipurilor de structuri este necesar n vederea alegerii tipului cel mai apropiat de fenomenul real n vederea unei bune modelri i utilizri.

Principalele criterii dup care se clasific structurile de date sunt :

1. dup tipul componentelor :

structuri omogene n care componentele sunt de acelai fel;

structuri eterogene n care componentele aparin unor tipuri diferite.

2. Dup posibilitatea de modificare a valorilor sau structurii:

structuri statice, care pe parcursul existenei au acelai numr de componente; structuri dinamice, care permit modificarea valorilor i structurii prin aplicarea operatorilor.3. Dup nivelul de structurare al datelor ele sunt:

Structur logic, ce se refer la descrierea modului de ordonare al elementelor, relaiile dintre colecii i operatorii de tratare a datelor;

Structur fizic, se refer la modul de implementare i de reprezentare fizic pe suport;

4. Dup relaiile existente ntre componentele structurii ele se clasific astfel :

Structur punctual, cnd elementele unei colecii sunt izolate ntre ele i cu exteriorul. Este structura fundamental ce st la baza celorlalte structuri, are form tabelar corespunztoare registrelor n care elementele sunt rnduri sau fiierelor unde elementele sunt fie.

Structur liniar, cnd ntre elementele coleciei exist o relaie care indic urmtorul element, precedentul sau primul i ultimul element i corespunde unei liste. Este o structur punctual mbuntit cu atribute de legtur ntre elemente. Ea este o transpunere fidel a conceptului de list, coad, stiv.

Coada este o list de obiecte ce ateapt s fie servite / prelucrate dup principiul : primul sosit primul servit ( FIFO = First Input First Output), identic cu coada din sistemul real.

Stiva este o list de obiecte n care prelucrarea sau servirea se face dup principiul ultimul sosit primul servit (LIFO = Last Input Fist Output). n realitate obiectele sunt aranjate unele peste altele i prelucrarea comod nu se poate face dect aa.

Fig. 2 Structur liniar simpl

Structur arborescent, care are un singur element rdcin, care are ramuri, cu subramuri, etc. , dar legtura dintre ele asigur c fiecare element are un singur predecesor. Este o structur liniar generalizat cnd dintr-un element pornesc mai multe legturi ctre altele din aceiai colecie. A fost inspirat de structura arborilor utilizat n multe domenii de activitate : organigrama unitii, structura mainilor, structura crilor multivolum, arborele genealogic, structura administrativ - teritorial, etc.

Fig. 3 Structur arborescent

Structur reea, cnd ntre elementele coleciei exist o relaie de legtur chiar bidirecional care conduce la un graf generalizat. Ea a fost inspirat de procesele tehnologice, structura social, organizarea teritorial, sistemul de alimentare cu energie electric, sistemul hidrologic cu nodurile : lacurile, mrile, oceanele i legturile prin ruri,fluvii, etc.

Fig. 4 Structur reea cu o intrare i o ieire

Structur relaional, cnd ntre mai multe colecii fr nici o legtur fizic ntre ele se poate stabili o relaie de coresponden pe baza unor atribute de legtur incluse n elementele coleciilor.

FacturaDataNumrNIRFurnizorValoare

24015029.10.2006112F1200.20

24015329.10.2006114F1305.30

56401029.10.2006113F2150.25

56401106.10.2006119F2168.20

NumrNIRDataFurnizorValoare

11228.10.2006F1200.20

11329.10.2006F2150.25

11429.10.2006F1305.30

11501.11.2006F5403.10

11601.112006F1106.50

11702.11.2006F1600.00

11802.11.2006F3 78.00

11905.11.2006F2168.20

20005.11.2006F1250.00

Fig. 5 Structur relaional ntre Notele de Recepie i Facturi

NIR

DOC-PLA

FACTURI

CORESPONDEN

c

e1

e2

e3

e4

e5

a

a2

a1

d

e

c

b

A

B

C

D

F

F

E

G

H

J

I

K

Nod intrare

Nod ieire