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) |
- 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> |