ALGORITMI I STRUKTURE PODATAKA
Laboratorijske vježbe 


1. Vježba

Napisati funkcije za generiranje Fibonaccijevih brojeva:
a) rekurzivno
b) iterativnim postupkom.

Mjeriti vremena izvođenja za različite duljine redova te usporediti dobivene rezultate za oba postupka s pomoću odgovarajuće tablice.

Vrijeme izvođenja može se mjeriti funkcijom
void ftime(struct timeb *buf); ili
time_t time(time_t *timer);

Dodatak:
Usporediti vremena izvođenja rekurzivne i nerekurzivne funkcije za traženje najveće zajedničke mjere dva realna broja, koristeći jednu od funkcija:
double fmod(double x, double y);
long double fmod(long double (x), long double (y));


2. Vježba

Uporabom funkcije int rand(void);
i makro naredbe void randomize(void);
načiniti općenitu funkciju za generiranje polja s n pseudoslučajnih brojeva čija se vrijednost nalazi između zadane donje i gornje granice. Prototip funkcije je:
gen_arr (long *polje, int n, long donja, long gornja);

Načiniti funkcije za izračunavanje moda sortiranog cjelobrojnog polja:
a) izravno
b) rekurzivno
c) nerekurzivno

Treba generirati i sortirati polje (koristiti proizvoljni algoritam za sort) te izmjeriti vremena traženja moda za svaki od tri navedena postupka.

Generiranje polja i vremena ponoviti za najgori slučaj (svi elementi isti) i najbolji slučaj (svi elementi različiti). Dobivene rezultate prikazati u tabličnom obliku.

Dodatak:
Pokušati poboljšati postupak c).
3. 
Vježba

Napraviti funkcije za rad s uređenom jednostruko povezanom listom struktura u radnoj memoriji (dodavanje, traženje, brisanje, ispis).  Strukturu zapisa i dio zapisa koji predstavlja ključ definirati po volji.

Napisati potprograme za izmjenu ključa elementa liste uz očuvanje uređenja:
a) zamjenom sadržaja elemenata
b) uporabom funkcija za brisanje i dodavanje elementa

U glavnom programu treba kreirati uređenu listu podataka prethodno pohranjenih u slijednoj formatiziranoj datoteci, a zatim interaktivno tražiti elemente i mijenjati vrijednost ključa uz provjeru sadržaja liste.

Dodatak:
Prilagoditi podatkovne strukture i napisati potprogram koji postojeću listu, uz osnovni ključ, uređuje po nekom drugom ključu (lista s više ključeva).


4. Vježba

Napisati program koji će podatke iz slijedne formatizirane datoteke proizvoljnog sadržaja prepisati u uređeno binarno stablo struktura smješteno u direktnoj neformatiranoj datoteci. Ključ zapisa odrediti samostalno.

Napisati i isprobati sljedeće funkcije:
a) funkciju za traženje elementa stabla sa zadanim ključem
b) funkciju za izračun razine čvora sa zadanim ključem
c) funkciju za izračun dubine stabla

Dodatak:
Napisati funkciju za brisanje elementa stabla sa zadanim ključem.
5. 
Vježba

Mjeriti i usporediti vrijeme sortiranja istog polja struktura proizvoljno odabranim algoritmom za sort i koristeći ugrađenu funkciju qsort nad:
a) poljem s ključem generiranim funkcijom gen_arr iz jedne od prethodnih vježbi
b) poljem s rastućim vrijednostima ključa (sortirano polje)

Dodatak:
Napisati program merge koji spaja dva ili više sortiranih polja u jedno sortirano polje. Alternativno, napisati program koji spaja dvije ili više prethodno sortiranih datoteka u sortirani rezultat koji se zapisuje na standardni izlaz. Poziv programa je:
merge file1 file2 ...


6. Vježba

Učinkovitost postupka raspršenog adresiranja značajno ovisi o četiri parametra:
a) Veličina pretinca
b) Gustoća pakiranja
c) Postupak pretvorbe ključa u adresu
d) Postupci u slučaju preljeva

Ukoliko postoji uzorak podataka, parametri se mogu odrediti eksperimentalno, simuliranjem punjenja datoteke s različitim vrijednostima odabranih parametara.

Napisati program za simuliranje punjenja datoteke uz uporabu različitih vrijednosti veličine pretinca i veličine primarnog područja, koristeći različite postupke pretvorbe ključa u adresu. Program kao ishod simulacije daje gustoću pakiranja i postotak preljeva.

Rezultate treba prikazati u obliku dijagrama ovisnosti postotka preljeva o veličini pretinca, gustoći pakiranja i postupku pretvorbe ključa u adresu.

Za uzorak podataka koristiti podatke iz datoteke adrese.txt.