| CATEGORII DOCUMENTE |
Tipuri de liste liniare:
Stiva - (LIFO) - lista asimetrica pentru care adaugarea, stergerea si consultarea se fac la un singur capat - la sfarsitul ei
Coada - (FIFO) - lista asimetrica la care consultarea si stergerea se fac la sfarsitul ei, iar adaugarea la inceput
Decoada - lista dubla - simetrica, la care consultarea, adaugarea si stergerea se pot face atat la inceput cat si la sfarsit.
Lista circulara - lista in care in partea de legatura a ultimului element se afla adresa adresa primului element; deoarece asa dispare diferenta intre varf si baza listei, se introduce un element special (cap de lista) care nu contine date; el devine primul si ultimul elementsi asigura posibilitatea parcurgerii in ambele sensuri.
Lista circulara dublu inlantuita - imbina calitatile celor precedenta.
Alocarea listelor in spatiul de memorie poate fi :
a) alocare secventiala
b) alocare dispersata
c) alocare dublu inlantuita
a) Alocare secventiala - memorarea elementelor listei in locatii succesive de memorie conform ordinii elementelor in cadrul listei. Se memoreaza si adresa de baza (a primului element).
b) Alocarea dispersata - fiecare element este inlocuit cu o celula de forma
|
|
LEG |
Partea de legatura ce contine adresa urmatorului element |
c) Alocarea dublu inlantuita
diferita de alocarea dispersata prin faptul ca elementul va fi de forma :
|
|
INF |
LEG 2 |
Fiecare tip de alocare prezinta avantaje si dezavantaje :
Necesita spatiu de memorie suplimentar fata de cea secventiala
Usurarea realizarii operatiilor de adaugare si de stergere, acestea realizabdu-se prin modificarea legaturilor intre elemente
Permite realizarea unei structuri de date foarte complexeprin faptul ca elementele listei pot fi la randul lor liste (elementele listei au in partea de informatie utila adresele de inceput ale altor liste)
Posibilitatea folosirii unui spatiu de memorie comun pentru mai multe liste
Permite refacerea cu usurinta a drunului invers de la un element oarecare la inceputul listei
Alegerea unui mod de alocare sau altul se face in functie de tipul listei, de operatiile la care va fi supusa lista, de caracteristicile suportului si de facilitatile oferite la realizarea algoritmilor de prelucrare.
Arborii (binari)
Sunt in general structuri dinamice cu ordine ierarhica si au incluse prin definitie informatiile de legatura.
Un arbore binar - arbore orientat in care fiecare varf are maxim un succedant si 0,1 sau 2 succesori
Forma generala de prezentare a arborilor binari este dispersata sau dublu inlantuita .
- legaturile - arce
se indica
Nodul radacina si pentru fiecare din celelalte noduri succesorul sau stang si drept.
1
2 7
3 5 8 9
4 6 10
Ex:
|
i | ||||||||||
|
Rad=1 |
| |||||||||
|
St(i) | ||||||||||
|
Dr(i) |
Reprezentarea tata: pentru fiecare nod se indica nodul parinte :
|
i | ||||||||||
|
Tata(i) |
1(2(3(l,4)5(6,l),7(8,9(10,l)))
Modalitati de parcurgere a arborilor dinamici
Preordine - RSD
Inordine - SRD
Postordine - SDR
Se prelucreaza informatia din radacina, apoi se trece la subarborele stang, iar ;a sfarsit subarborele drept.
in cadrul fiecarui subarbore se respecta aceeasi regula.
1
2 7
3 5 8 9
4 6 10
Se identifica radacina, se prelucreaza arborele stang, apoi radacina, apoi arborele drept.
3, 4, 2, 6, 5, 1, 8, 7, 10, 9
Se identifica radacina, se prelucreaza arborele stang, apoi arborele drept, apoi radacina.
4, 3, 6, 5, 2, 8, 10, 9, 7, 1
|
Politica de confidentialitate | Termeni si conditii de utilizare |
Vizualizari: 2006
Importanta: 
Termeni si conditii de utilizare | Contact
© SCRIGROUP 2024 . All rights reserved
