Fituica

Peste 1000 de copiute GRATUITE de la useri si de pe Internet la toate materiile.

Lista materii:

Am lansat cel mai tare site de metode si tehnici de copiat!

Liste liniare, Stive, Cozi, Arbori, Arbori binari

LISTE LINIARE
O lista liniara este o colectie de n noduri unde n>=0, ce poate fi si vida.
Listele se pot aloca dinamic sau secvential.
struct nod
{ int info:
nod *adr_urm;
} *v, *sf;

STIVE
O stiva este o structura liniara deschisa ale carei extremitati se numesc baza si varf si in care accesul se face la un singur capat, si anume la varful stivei.
Stiva functioneaza pe principiul LIFO (Last In First Out).
Alocarea dinamica a stivei necesita cunoasterea in orice moment a pointerului pentru varful stivei. Daca stiva este vida varful coincide cu baza si vor avea aceeasi adresa, si anume constanta “Null”.
struct nod
{ int info;
nod *adr_inapoi;
} nod *v;

COADA
O coada este o lista liniara deschisa la care operatiile au loc la ambele capete.
Coada functioneaza pe principiul FIFO (First In First Out)
struct nod
{ int info;
nod *adr_urm;
} *v, *sf;

ARBORI
Un arbore este un graf conex fara nici un ciclu (n varfuri si n-1 arce).
Legaturile existente intr-un arbore sunt de tip parinte-fiu.
Nodul in care nu intra nici un arc se numeste radacina.
Un nod in care intra un arc se numeste succesor sau fiu, iar cel din care iese un arc sau mai multe se numeste predecesor sau parinte.
Nodurile sunt organizate pe nivele, iar cele de pe ultimul nivel se numesc frunze sau noduri terminale.
Nodurile pot contine informatii utile ce poarta denumirea de chei ale arborelui.

ARBORI BINARI
Un arbore cu proprietatea ca fiecare nod cu exceptia frunzelor are cel mult doi descendenti sau succesori se numeste arbore binar.
Intr-un arbore binar, cei doi descendenti daca exista se numesc succesorii stang si drept.
Un arbore binar cu proprietatea ca are exact doi descendenti se numeste arbore binar complet.
Succesorul stang al unui nod se noteaza cu S[i].
Succesorul drept al unui nod se noteaza cu D[i].
Predecesorul unui nod se noteaza cu P[i].
Vectorul T[i] retine:
-1 daca nodul este succesor stang.
1 daca nodul este succesor drept.
Indiferent de for a de reprezentare putem defini un al treilea vector ce va contine informatiile utile ale nodurilor. INF[i]