Różnice między wybraną wersją a wersją aktualną.
|
pl:dydaktyka:asd:cwiczenia:2011-search1 [2011/04/18 23:29] ikaf |
pl:dydaktyka:asd:cwiczenia:2011-search1 [2019/06/27 15:50] |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| - | **Termin zajęć:** 19/20.04.2011 | ||
| - | **Do przygotowania:** | ||
| - | - Znajomość budowy i zasad działania podstawowych struktur danych: | ||
| - | * lista jedno- i dwukierunkowa | ||
| - | * drzewo BST | ||
| - | - Zakres wiadomości: //Cormen - Wprowadzenie do algorytmów, Część III: Wprowadzenie, Rozdział 10 i 12// | ||
| - | - Każdy powinien przynieść na zajęcia zaimplementowane następujące klasy | ||
| - | - lista jednokierunkowa | ||
| - | - lista dwukierunkowa | ||
| - | - drzewo binarne BST | ||
| - | //Poniższe szkielety klas powinny być dla Państwa pomocą, nie są natomiast wiążącą specyfikacją (szczegóły mogą Państwo wykonać wg uznania - to nie zajęcia z programowania).// | ||
| - | |||
| - | {{http://akolacz.tarchomin.pl/images/ListaJednokierunkowa.png}}\\ | ||
| - | {{http://akolacz.tarchomin.pl/images/ListaDwukierunkowa.png}} | ||
| - | |||
| - | Szkielet klasy listy dwukierunkowej: | ||
| - | <code c++> | ||
| - | typedef ElementType int; // typ elementu na liście | ||
| - | |||
| - | class ListNode { | ||
| - | public: | ||
| - | ElementType value; | ||
| - | ListNode *prev, *next; | ||
| - | ListNode(){ | ||
| - | prev = NULL; | ||
| - | next = NULL; | ||
| - | } | ||
| - | }; | ||
| - | |||
| - | class List{ | ||
| - | private: | ||
| - | ListNode *head, *tail; | ||
| - | | ||
| - | public: | ||
| - | List(){ | ||
| - | head = tail = NULL; | ||
| - | } | ||
| - | | ||
| - | //poniższe metody należy zaimplementować samodzielnie | ||
| - | | ||
| - | ~List(); // należy zdefiniować tak, aby usuwał wszystkie elementy | ||
| - | |||
| - | ElementType getValue(int index); | ||
| - | void setValue(const ElementType& element); | ||
| - | | ||
| - | |||
| - | void insert(int index, ElementType value); | ||
| - | bool remove(int index); | ||
| - | bool remove(ElementType value); | ||
| - | ListNode* search(ElementType value); | ||
| - | |||
| - | }; | ||
| - | </code> | ||
| - | |||
| - | |||
| - | Szkielet klas węzła drzewa i samego drzewa: | ||
| - | <code c++> | ||
| - | class TreeNode { | ||
| - | public: | ||
| - | ElementType key; | ||
| - | TreeNode *left, *right; | ||
| - | }; | ||
| - | |||
| - | class TreeBST{ | ||
| - | private: | ||
| - | TreeNode * root; | ||
| - | public: | ||
| - | TreeBST(); | ||
| - | ~TreeBST(); | ||
| - | TreeNode* search(ElementType key); // wyszukaj element o kluczu ''key'' w drzewie | ||
| - | bool insert(ElementType key); // wstaw element o kluczu ''key'' do drzewa | ||
| - | bool remove(ElementType key); // usuń element o kluczu ''key'' z drzewa | ||
| - | bool member(ElementType key); // sprawdź czy element o kluczu ''key'' należy do drzewa | ||
| - | }; | ||
| - | </code> | ||
