Różnice między wybraną wersją a wersją aktualną.
| Nowa wersja | Poprzednia wersja | ||
|
pl:dydaktyka:asd:cwiczenia:2011-search1 [2011/04/17 14:20] ikaf utworzono |
pl:dydaktyka:asd:cwiczenia:2011-search1 [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| Linia 4: | Linia 4: | ||
| - Znajomość budowy i zasad działania podstawowych struktur danych: | - Znajomość budowy i zasad działania podstawowych struktur danych: | ||
| * lista jedno- i dwukierunkowa | * lista jedno- i dwukierunkowa | ||
| - | * drzewo (binarne) | + | * drzewo BST |
| - | - Implementacja (szczegóły zostaną podane wkrótce): | + | - Zakres wiadomości: //Cormen - Wprowadzenie do algorytmów, Część III: Wprowadzenie, Rozdział 10 i 12// |
| - | - lista | + | - Każdy powinien przynieść na zajęcia zaimplementowane następujące klasy |
| - | - drzewo | + | - 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 (rodzica danego węzła można zrealizować jako pole klasy ''TreeNode'' lub wskaźnik na niego pozyskiwać za pomocą odpowiedniej metody ''parent(TreeNode x)'' klasy TreeBST): | ||
| + | |||
| + | <code c++> | ||
| + | class TreeNode { | ||
| + | public: | ||
| + | ElementType key; | ||
| + | TreeNode *left, *right, *parent; | ||
| + | }; | ||
| + | |||
| + | 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> | ||
