Ćwiczenie 6: Pojemniki - drzewo

Ćwiczenie to jest częścią większego zadania, które będzie polegać na zaprojektowaniu szablonów kilku rodzajów klas pojemnikowych z wykorzystaniem mechanizmu dziedziczenia oraz iteratora dla tych klas.
Ćwiczenie 6. polegać będzie na zaprojektowaniu szablonu pojemnika typu drzewo.

Po co

  • Doskonalenie umiejętności definiowania szablonów.
  • Utrwalenie umiejętności posługiwania się mechanizmami dziedziczenia, polimorfizmu.
  • Zapoznanie się z podstawowymi strukturami danych.

Oddawanie ćwiczenia

  • Przed oddaniem ćwiczenia, program należy przetestować używając następującego pliku main: ex6main.zip
  • Powyższy plik wymaga istnienia pliku aghInclude.h poprzez który włączane są wszystkie niezbędne pliki.

Przebieg ćwiczenia

  1. Wykonanie ćwiczenia polega na zaimplementowaniu klasy aghTree, która będzie reprezentować binarne drzewo przeszukiwań (BST) - porównaj drzewo AVL, drzewo czerwono-czarne.
  2. Przyjmujemy że w lewym poddrzewie przechowywane są wartości mniejsze lub równe wartości korzenia danego poddrzewa, natomiast w prawym większe.
  3. Klasa aghTree dziedziczy klasę abstrakcyjną opisaną w ćwiczeniu 3 w sposób publiczny.
  4. Kolejność (indeksowanie) elementów w drzewie jest określana przez kolejność odwiedzania węzłów metodą in-order rozpoczynając od lewego poddrzewa.
  5. Klasa powinna implementować wszystkie opisane w ćwiczeniu 3. metody, które powinny działać tak samo jak w przypadku poprzednich pojemników (aghVector, aghSlist, aghDlist). Ze względu na ustalony sposób wstawiania elementów do drzewa, implementacja następujących metod jest nieco inna:
    • Metoda insert - parametr określający miejsce wstawienia elementu będzie w tej klasie ignorowany.
    • Metoda replace - usuwa (określony jako parametr metody) element a następnie wstawia nową wartość. Wstawianie odbywa się w typowy dla tego rodzaju drzewa sposób.
  6. Nie ma przymusu tworzenia metod czy też klas specjalizowanych.
  7. Program powinien mieć budowę modułową.
  8. Nie dublujemy kodu, tzn. nie piszemy dwa i więcej razy kodu, który wykonuje podobne zadania - ta kwestia będzie ważnym kryterium oceny.
  9. Do realizacji ćwiczenia nie można wykorzystywać już gotowych rozwiązań (STL, Qt, tip).
  10. Zaistniałe nieprawidłowe sytuacje powinny zostać obsłużone poprzez wyrzucenie wyjątku przy pomocy klasy aghException.
  11. Program powinien się poprawnie kompilować i uruchomić wraz z dostarczonym plikiem ex6main.zip.
pl/dydaktyka/jimp2/2016/part2/ex/ex6.txt · ostatnio zmienione: 2017/07/17 08:08 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0