|
|
pl:dydaktyka:jimp2:2016:part2:ex:ex6 [2016/06/13 20:11] msl utworzono |
pl:dydaktyka:jimp2:2016:part2:ex:ex6 [2019/06/27 15:50] |
====== Ć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: {{:pl:dydaktyka:jimp2:2016:part2:ex:ex6main.zip|}} | |
* Powyższy plik wymaga istnienia pliku ''aghInclude.h'' poprzez który włączane są wszystkie niezbędne pliki. | |
| |
===== Przebieg ćwiczenia ===== | |
- Wykonanie ćwiczenia polega na zaimplementowaniu klasy **''aghTree''**, która będzie reprezentować **binarne drzewo przeszukiwań (BST)** - porównaj drzewo AVL, drzewo czerwono-czarne. | |
- Przyjmujemy że w lewym poddrzewie przechowywane są wartości mniejsze lub równe wartości korzenia danego poddrzewa, natomiast w prawym większe. | |
- Klasa **''aghTree''** dziedziczy klasę abstrakcyjną opisaną w [[ex3|ćwiczeniu 3]] w sposób **publiczny**. | |
- Kolejność (indeksowanie) elementów w drzewie jest określana przez kolejność odwiedzania węzłów metodą **in-order rozpoczynając od lewego poddrzewa**. | |
- Klasa powinna implementować wszystkie opisane w [[ex3|ć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. | |
- Nie ma przymusu tworzenia metod czy też klas specjalizowanych. | |
- Program powinien mieć budowę modułową. | |
- **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**. | |
- Do realizacji ćwiczenia **nie można** wykorzystywać już gotowych rozwiązań (STL, Qt, tip). | |
- Zaistniałe nieprawidłowe sytuacje powinny zostać obsłużone poprzez wyrzucenie wyjątku przy pomocy klasy **''[[..:org:codepolicy#obsluga_wyjatkow|aghException]]''**. | |
- Program powinien się poprawnie kompilować i uruchomić wraz z dostarczonym plikiem {{{{:pl:dydaktyka:jimp2:2016:part2:ex:ex6main.zip|}}|}}. | |