Algoritmi de programare
Structura arborescenta(ierarhica, descendenta)
Este definita atunci cind intfre elementele colectiei de date exista o relatie de ordine caracterizata prin urmatoarea:
exista un element special unic numit radacina, celelalte elemente pot fi grupate in m-multimi di 13113b16n sjuncte, fiecare din aceste multimi fiind o structura arborescenta, aceste submultimi se numesc subarbori, putem spune ca orice element a unui arbore este un subarbore component al arborelui. Numarul de subarbori a unui anumit element dintr-o structura arborescenta este numit gradul elementului respectiv.
Elementele unui arbore se mai numesc si noduri. Nod - care nu e radacina, are un predecesor imediat unic(are sigur un sef direct si numai unu)
Observatie: Intr-o structura arborescenta elementele de grad "0", sint denumite si elemente terminale ale structurii respective. Un arbore ordonat de gradul 2 se numeste arbore binar, forma particulara a structurii arborescente, extrem de utila in prelucrarea datelor in informatica(un arbore de grad mai mare decit 2, poate fi structurat sub forma de arbori binari, un arbore cu ordinul mai mare decit 2, se numeste arbore multicai)
Drumul de lungime maxima(numarul de elemete) se numeste inaltimea arborelui.
Arborii binari, datorita specificaului, admit o reprezentare simetrica, axa de simetrie trecind prin radacina arborelui, elementele unui arbore binar fiind notate si denumite "virf", si datorita acestei simetrii putem stabili subarborele "sting", si subarborele "drept".
Pentru aplicatiile de prelucrare automata a datelor, care utilizeaza structuri arborescente, si pentru reprezentarea pe suport a acestor date, o problema deosebit de importanta o constituie parcurgerea elementelor structurii intr-o anumita ordine.
Exista 3 tipuri de parcurge arborilor:
preordine
inordine
postordine
La parcurgerea in preordine, se viziteaza virful, urmind arborele sting, si dupa asta subarborele drept
Inordine - arborele sting, virful, subarborele drept
Postordine(finordine) - arborele sting, arborele drept, virful
Preordine: a,b,d,e,h,m,c,f,i,n,j,g,k,o,l,p
Inordine: d,b,h,m,h,e,i,f,j, etc
Postordine: d,m,h,e,b,n,i,j,f,o,k,p,q,l,g
Structura din retea: definita atunci cind intre elementele colectiei de date exista o relatie de preordine, cu urmatoarele caracteristici:
este practic un graf care are intre 2 noduri legaturi bidirectionale
exista unu sau mai multe noduri initiale (cardinalul multimii oridinii initiale este >=1)
exista unul sau mai multe noduri finale(cardinalul multimii nodurilor finale este >=1)
orice nod poate avea mai multi predecesori, el putind fi predecesorul propriului predecesor
un ciclu se defineste atunci cind nodul initial 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 pentru a asigura conditiile de integritate si unicitate a datelor si a elimina astfel anomaliile la actualizari. In principal, structurile relationale vizeaza bazele de date.
SQL - Standard Query Language 1..13
O structura care corespunde regulii 1..13 se numeste calea normale.
Normalizarea se face in 5, etape, la fiecare etapa indeplinindu-se anumite reguli din standarde
De obicei se executa 3 etape din 5 ca compromis intre cost timp - impotriva eficientei si standardelor.
Structuri de date interne:
Masive(tablou, matrice)
Articole
|
