Różnice między wybraną wersją a wersją aktualną.
| Both sides previous revision Poprzednia wersja Nowa wersja | Poprzednia wersja | ||
|
pl:dydaktyka:asd:cwiczenia:2011-search1 [2011/04/17 22:49] ikaf |
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 |
| + | - 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 | - Każdy powinien przynieść na zajęcia zaimplementowane następujące klasy | ||
| - lista jednokierunkowa | - lista jednokierunkowa | ||
| - lista dwukierunkowa | - lista dwukierunkowa | ||
| - | - drzewo binarne | + | - 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/ListaJednokierunkowa.png}}\\ | ||
| {{http://akolacz.tarchomin.pl/images/ListaDwukierunkowa.png}} | {{http://akolacz.tarchomin.pl/images/ListaDwukierunkowa.png}} | ||
| - | Szkielet klasy listy jednokierunkowej: | + | Szkielet klasy listy dwukierunkowej: |
| <code c++> | <code c++> | ||
| - | class ElementType; // typ elementu na liście | + | typedef ElementType int; // typ elementu na liście |
| - | class ListElement1{ | + | class ListNode { |
| - | protected: | + | public: |
| - | ListElement * pNext; | + | ElementType value; |
| - | ElementType value; | + | ListNode *prev, *next; |
| - | public: | + | ListNode(){ |
| - | ListElement(){ pNext = NULL; } | + | prev = NULL; |
| - | Element(const Element &element); | + | next = NULL; |
| - | ~ListElement(); | + | } |
| + | }; | ||
| - | ElementType getValue(){ return value; } | + | class List{ |
| - | void setValue(const ElementType& element){ value = element; } | + | 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 | ||
| - | ListElement * getNext(){ return pNext; } | + | ElementType getValue(int index); |
| - | void setNext(ListElement *pNext){ pNext = pNext; } | + | void setValue(const ElementType& element); |
| | | ||
| - | void push_back(const ElementType& element){...} // dołóż element na końcu listy | ||
| - | void pop_back(){...} // usuń element z końca listy | ||
| - | void push_front(const ElementType& element){...}// dołóż element na początku listy | ||
| - | void pop_front(){...} // usuń element z początku listy | ||
| - | void insert_after(ListElement * pElement, const ElementType& element){...} //wstaw element o wartości ''element'' za elementem pElement w liście | + | void insert(int index, ElementType value); |
| - | void clear() usuń wszystkie elementy z listy | + | bool remove(int index); |
| - | void remove(ListElement * pElement, const ElementType& element){...} | + | bool remove(ElementType value); |
| + | ListNode* search(ElementType value); | ||
| }; | }; | ||
| </code> | </code> | ||
| - | Listę dwukierunkową należy zaimplementować samodzielnie, analogicznie do listy jednokierunkowej. | ||
| - | Szkielet klas węzła drzewa i samego drzewa: | + | 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++> | <code c++> | ||
| - | class Node { | + | class TreeNode { |
| + | public: | ||
| ElementType key; | ElementType key; | ||
| - | Node *left, *right, *parent; | + | TreeNode *left, *right, *parent; |
| }; | }; | ||
| - | class TBst{ | + | class TreeBST{ |
| private: | private: | ||
| - | Node * root; | + | TreeNode * root; |
| public: | public: | ||
| - | TBst(); | + | TreeBST(); |
| - | ~TBst(); | + | ~TreeBST(); |
| + | TreeNode* search(ElementType key); // wyszukaj element o kluczu ''key'' w drzewie | ||
| bool insert(ElementType key); // wstaw element o kluczu ''key'' do drzewa | bool insert(ElementType key); // wstaw element o kluczu ''key'' do drzewa | ||
| bool remove(ElementType key); // usuń element o kluczu ''key'' z drzewa | bool remove(ElementType key); // usuń element o kluczu ''key'' z drzewa | ||
