Tipuri de Structuri de Date (logice)

Tipuri de Structuri de Date (logice)

Principalele tipuri de structuri de date (logice) sunt :

Structura punctuala

Structura liniara

Structura arborescenta

Structura retea

Structura relationala

Masive (tablouri)

Articole (inregistrari logice)

Structura Punctuala

Structura punctuala este structura entitatilor izolate.

Entitate :Un obiect concret / abstract care il reprezentam prin proprietai sau caracteristici.

Structura Liniara (simpla)

-Este definita atunci cand intre elementele unei colectii de date exista o relatie de ordine totala.

Principalele caracteristi 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 successor imediat unic.

Primul element nu are predecesori.

Ultimul element nu are succesori.

Relatiile stabilite intre date sunt de tip unu la unu.

Structura Liniara Inelara

Daca intr-o structura liniar exista un cuplu in relatia de ordine 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.

Caracteristici :

Intre date se stabilesc relaltii de tipul 1 la 1.

Structura liniara se numeste structura liniara cu elemente structurate arborescent, daca componentele ei sunt structrui arborescente.

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

Structura arborescenta, sau descedenta sau ierarhica este definita atunci cand intre elementele colectiei de date exista o relatie de ordine ce se carcaterizeaza prin urmatoarele:

Exista un element special, unic, numit radacina.

Celelalte elemente pot fi grupate in m submultimi disjuncte, fiecare submultime de acest fel este un arbore . Aceste submultimi se numesc subarbori. Putem spune atunci ca orice element al arborelui este, la randul sau, un subarbore component al arborelului.

Orice nod care nu e radacina are un predecessor imediat, unic.

Orice nod care nu e terminal are un numar de succesori imediati, finit.

Intre noduri se stabilesc relatii de tip 1 la m.

Notiuni Generale

Numarul de subarbori ai unui anumit element al unei structuri arborescente este numit gradul elementului respective.

Observatie :

Intr-o structura arborescenta, elemtele de grad zero sunt denumite si elemente terminale ale structurii respective.

Un arbore ordonat de gradul 2 se numeste arbore binar (forma particulara a structurii arborescente).

Un arbore care are ordinal mai mare decat 2 se numeste arbore multicai.

Drumul de lungime maxima se numeste inaltimea arborelui.

ARBORI BINARI

Arborii binari admit o reprezentare grafica simetrica, axa de simetrie trecand prin radacina arborelui. De aceea, subarborii unui element oarecare sunt denumiti functie de pozitie relativa a acestora fata de elementul respectiv :

subarbore stang

subarbore drept

Parcurgerea Elementelor arborelui binar.

Orice arbore poate fi reprezentat prin intermediul unui arbore binar.

S-au identificat si s-au descries trei modalitati de parcurgere, denumite:

parcurgere in preordine (VSD)

parcurgere in inordine (SVD)

parcurgere in finordine (postordine) (SDV).

STRUCTURA RETEA

Este definita atunci cand intre elementele colectiei de date exista o relatie de preordine (partiala, antisimetrica si tranzitiva).

Are urmatoarele caracteristici:

Este practi un graf care are, intre doua noduri, legaturi bidirectionale.

Exista unul sau mai multe noduri initiale ( cardinalul multimii nodurilor initiale este egal sau mai mare cu 1).

Exista unul sau mai multe noduri finale ( cardinalul multimii 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 este acelasi cu nodul final.

Intre elementele structurii de tip retea se stabilesc relatii de tip m la n.

STRUCTURA RELATIONALA

Este formata din mai multe tabele de date elementare, numite tablouri sau relatii, obtinute prin metoda normalizarii , prentru a asigura conditiile de integrate si unicitate a datelor si a elimina astfel anomaliile la actualizari.

Observatie: Despre acest tip de strcutura vom invata mai mult la sisteme de gestiune a bazelor de date (S.G.B.D), special realizate pentru operatii cu colectii mari de date memorate pe suporti externi.

S.G.B.D = Sistem de gestiune a bazei de date.

FISIERUL

Fisierul se defineste ca o multime de date omogene din puncte de vedere al semnificatiei lor si al cerintelor de prelucrare. Aceasta multime este organizata ca o lista liniara, cu elemente structurate arborescente. Aceste elemente ale fisierului este considerat ca lista liniara, se numesc inregistrari sau articole.

Inregistrarile au o structura arborescenta, elementele structurii fiind numite campuri.

BAZA DE DATE

Baza de date se defineste ca o colectie de date (tabele si fisiere) aflate in interdependeta, memorata pe support extern impreuna cu descrierea datelor si a relatiilor dintre ele.

Ea are sens ca element al unei banci de date.

Banca de date reprezinta un sistem de organizare si prelucrare, respectiv teleprelucrare a datelor, constituit din :

Una sau mai multe baze date;

Un sistem de Gestiune a Bazei de Date (SGBD) care asigura independenta programelor aplicative fata de modul de structurare a datelor, o redundanta minima, controlata, in memorarea acestora, precum si timp minim de raspuns la solicitarile utilizatorilor in ansamblul lor. Acest sistem de programe asigura gestiunea bazei de date sau a sistemului de baze de date asociate bancii de date.

STRUCTURI DE DATE INTERNE

Cele mai frecvent utilizate structuri statice de date sunt :

Masive (tablouri)

Articole (inregistrari logice)

MASIVUL sau TABLOUL

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

Fie vectorul X, cu x1, x2, .. xn, un tablou unidimensional cu n elemente componente de acelasi tip.

Fiecare element al unui tablou se identifica prin pozitia pe care o ocupa in cadrul tabloului ( rangul elementului in tablou) cu ajutorul unui indice. Prin urmare, pentru a referi un element, vom preciza numele tabloului, urmat de un indice care precizeaza pozitia elementului respective in cadrul tabloului. Astfel, in cadrul vectorului X, indicele = 3 va referi elementului de pe pozita trei din cadrul vectorului, adica pe x3.