Zadanie 2 – Złożone struktury danych

Zagadnienia

  • Struktura listy jedno- i dwukierunkowej
  • Struktura drzewa poszukiwań binarnych (Binary Search Tree – BST)
  • Tworzenie i usuwanie w/w struktur
  • Wyszukiwanie elementu na liście/ w drzewie
  • Usuwanie pojedynczych elementów listy/ drzewa
  • Przeglądanie drzewa w porządku wzdłużnym (preorder), poprzecznym (inorder) i wstecznym (postorder)
  • Definicja drzewa wyważonego i dokładnie wyważonego

Termin oddawania programów i wyników eksperymentów (+ wykresy): 19.04.2016
Termin dostarczenia sprawozdania (mailem pdf): 26.04.2016

Projekt

Wygeneruj n-elementowe ciągi liczb naturalnych (10 różnych wartości n, które mają być tak dobrane, żeby można było dokonać pomiaru czasu). Liczby mają być losowo ułożone i nie mogą się powtarzać.
Zaimplementuj poszczególne procedury:

  • Tworzenie struktury.
    • Utwórz listę posortowaną wstawiając kolejno elementy w odpowiednie miejsce (sortowanie przez wstawianie).
    • Utwórz drzewo BST wstawiając kolejno elementy do drzewa. Podaj wysokość utworzonego drzewa w postaci tabelki.
    • Skonstruuj wyważone drzewo AVL. Wykorzystaj metodę połowienia binarnego. Podaj wysokość utworzonego drzewa w postaci tabelki.
  • Wyszukiwanie elementu podanego przez użytkownika na liście, w drzewie BST i AVL.
  • Wstawianie elementów podanych przez użytkownika (użytkownik podaje również liczbę elementów do wstawienia) w odpowiednie miejsce na liście, w drzewie BST i AVL. Na koniec wszystkich operacji wstawienia do drzewa AVL wyważ drzewo (odczytaj wszystkie węzły drzewa metodą in-order, usuń stare drzewo, a następnie utwórz nowe metodą połowienia binarnego)
  • Usuwanie elementów podanych przez użytkownika (użytkownik podaje również liczbę elementów do usunięcia) ze wszystkich struktur. Na koniec wszystkich operacji wstawienia do drzewa AVL wyważ drzewo.
  • Wypisywanie elementów struktury w porządku posortowanym.
  • Usuwanie struktur; drzewa usuwane w porządku post-order
  1. Wszystkie procedury mają być uruchamiane w powyższej kolejności (testowanie programu na zajęciach)
  2. Zmierz czas operacji: tworzenia struktur, usuwania x losowo wybranych elementów oraz dodawania x elementów, ale innych niż te, które są już w strukturze. x jest liczbą zależną od n, należy dobrać taki x, aby można było dokonać pomiaru czasu np. x=n/100
  3. Utwórz 3 wykresy t=f(n) (dla każdej operacji osobny) porównując czas działania poszczególnych operacji na różnych strukturach dynamicznych: liście jednokierunkowej, drzewie poszukiwań binarnych (BST) oraz wyważonym drzewie poszukiwań binarnych (AVL).
  4. Sformułuj wnioski dotyczące operacji wykonywanych na różnych strukturach. Oszacuj złożoność obliczeniową poszczególnych operacji dla wszystkich struktur. Jakie zastosowanie mogą znaleźć listy jednokierunkowe, a jakie drzewa BST i AVL? W jakim celu wyważa się drzewa?

Zadanie na zajęciach

  1. Przy użyciu jednokierunkowej listy, napisz program odwracający kolejność wyrazów.
    Tekst należy wczytać ze standardowego wejścia, kolejne wyrazy (oddzielone białym znakiem – można użyć isspace()) dodawać na początek listy, a następnie wypisać zawartość listy.
  2. Zaimplementuj rekurencyjną funkcję void halve(int min, int max), wypisującą ciąg liczb metodą połowienia binarnego
  3. Zaimplementuj drzewo binarne, wstaw elementy do drzewa używając funkcji halve() oraz wypisz jego zawartość, korzystając ze struktury elementu: 
    typedef struct node_t {
 int val;
 struct node_t *parent;
 struct node_t *left, *right;
} node_t;

node_t *head;