28-06-2010, 08:54 PM
Maturski, seminarski i diplomski radovi iz matematike.
Najznačajnije nelinearne structure podataka su
• -stabla i
• -grafovi.
STABLA:
Svaki element strukture može imati veći broj prethodnika i sledbenika. Stablo predstavlja nelinearnu strukturu sa sledećom osobinom
1. Postoji jedan element koji se zove koren stabla. Na njega ne ukazuje ni jedan drugi element. Koren se nalazi na nivou 0.
2. Na nivou 1 se nalaze elementi na koje ukazuje koren stabla
3. Elementi nivoa 1 ukazuju na elemente nivoa 2,...
4. Elementi nivoa i-1 ukazuju na elemente na nivou i.
5. Elementi koji ne ukazuju na nove elemente čine listove stabla
GRAF:
Čvorovi
-Preslikati čvorove u niz uzastopnih celih brojeva
-Zapamtiti čvorove u polje
-Potezi (grane)
-Matrica susedstva
-Logičke vrednosti -
TRUE (istina) – poteg postoji
FALSE (laž)- nema potega
-Upotreba: U računarskim mrežama,
putnim mrežama, PTT, kablovska televizija,...
1.1. STABLA
1.1.1. DEFINICIJE I KONCEPTI
Graf G=(V,E) se sastoji od nepraznog skupa čvorova G i skupa E koji je skup grana grafa.
Stablo je acikličan, orijentisan graf koji ima jedan čvor koji se zove koren (root) sa ulaznim stepenom 0 dok svi drugi čvorovi imaju ulazni stepen 1. Ako izbrišemo koren i njegove grane dobijamo skup disjunktnih stabala. Svaki čvor kojiima izlazni stepen 0 naziva se terminalni čvor ili list, dok se svi drugi čvorovi nazivaju čvorovi grananja (brunch nodes).
• Nivo čvora je njegova dužina od korena, d.
• Dubina (visina) stabla je maksimalna vrednost nivoa nekog čvora u stablu.
• Za stablo se kaže da je n‐arno (reda n) ako svaki čvor ima najviše n podčvorova.
• Za stablo se kaže da je puno ako se svi listovi nalaze na istom rastojanju od korena, tj. ako od korena do svakog lista odgovara put dužine h‐1.
• Za stablo se kaže da je kompletno ako svi njegovi čvorovi koji ne predstavljaju listove imaju svih n odlaznih potega.
Kompletno i nepotpuno stablo
Kompletno i puno stablo
• Broj čvorova kompletnog punog stabla iznosi C = n0 + n1 + n3 + ... + nh =
• Kapacitet čvora k predstavlja broj elemenata koji se može smestiti u čvor.
• Za stablo se kaže da je balansirano ako za svaki čvor važi da se broj čvorova u svakom njegovom podstablu ne razlikuje za više od 1.
• Za stablo reda n čiji su svi čvorovi na nivoima od 1 do h‐1 kompletni, kaže se da je optimalno balansirano
OPERACIJE NA BINARNIM STABLIMA
Neke od operacija nad binarnim stablom su: prolaz, umetanje, brisanje, pretraživanje i kopiranje.
/* rad sa binarnim stablom - implementacija funkcija koje vrse specificnu obradu nad cvorovima
binarnog stabla */
#include <stdio.h>
#include <stdlib.h>
typedef struct cvor { int broj; struct cvor *levo, *desno; } Cvor;
typedef Cvor *Stablo;
Stablo stvori (void); /* Stavaranje praznog stabla. */
Najznačajnije nelinearne structure podataka su
• -stabla i
• -grafovi.
STABLA:
Svaki element strukture može imati veći broj prethodnika i sledbenika. Stablo predstavlja nelinearnu strukturu sa sledećom osobinom
1. Postoji jedan element koji se zove koren stabla. Na njega ne ukazuje ni jedan drugi element. Koren se nalazi na nivou 0.
2. Na nivou 1 se nalaze elementi na koje ukazuje koren stabla
3. Elementi nivoa 1 ukazuju na elemente nivoa 2,...
4. Elementi nivoa i-1 ukazuju na elemente na nivou i.
5. Elementi koji ne ukazuju na nove elemente čine listove stabla
GRAF:
Čvorovi
-Preslikati čvorove u niz uzastopnih celih brojeva
-Zapamtiti čvorove u polje
-Potezi (grane)
-Matrica susedstva
-Logičke vrednosti -
TRUE (istina) – poteg postoji
FALSE (laž)- nema potega
-Upotreba: U računarskim mrežama,
putnim mrežama, PTT, kablovska televizija,...
1.1. STABLA
1.1.1. DEFINICIJE I KONCEPTI
Graf G=(V,E) se sastoji od nepraznog skupa čvorova G i skupa E koji je skup grana grafa.
Stablo je acikličan, orijentisan graf koji ima jedan čvor koji se zove koren (root) sa ulaznim stepenom 0 dok svi drugi čvorovi imaju ulazni stepen 1. Ako izbrišemo koren i njegove grane dobijamo skup disjunktnih stabala. Svaki čvor kojiima izlazni stepen 0 naziva se terminalni čvor ili list, dok se svi drugi čvorovi nazivaju čvorovi grananja (brunch nodes).
• Nivo čvora je njegova dužina od korena, d.
• Dubina (visina) stabla je maksimalna vrednost nivoa nekog čvora u stablu.
• Za stablo se kaže da je n‐arno (reda n) ako svaki čvor ima najviše n podčvorova.
• Za stablo se kaže da je puno ako se svi listovi nalaze na istom rastojanju od korena, tj. ako od korena do svakog lista odgovara put dužine h‐1.
• Za stablo se kaže da je kompletno ako svi njegovi čvorovi koji ne predstavljaju listove imaju svih n odlaznih potega.
Kompletno i nepotpuno stablo
Kompletno i puno stablo
• Broj čvorova kompletnog punog stabla iznosi C = n0 + n1 + n3 + ... + nh =
• Kapacitet čvora k predstavlja broj elemenata koji se može smestiti u čvor.
• Za stablo se kaže da je balansirano ako za svaki čvor važi da se broj čvorova u svakom njegovom podstablu ne razlikuje za više od 1.
• Za stablo reda n čiji su svi čvorovi na nivoima od 1 do h‐1 kompletni, kaže se da je optimalno balansirano
OPERACIJE NA BINARNIM STABLIMA
Neke od operacija nad binarnim stablom su: prolaz, umetanje, brisanje, pretraživanje i kopiranje.
/* rad sa binarnim stablom - implementacija funkcija koje vrse specificnu obradu nad cvorovima
binarnog stabla */
#include <stdio.h>
#include <stdlib.h>
typedef struct cvor { int broj; struct cvor *levo, *desno; } Cvor;
typedef Cvor *Stablo;
Stablo stvori (void); /* Stavaranje praznog stabla. */