Both sides previous revision
Poprzednia wersja
Nowa wersja
|
Poprzednia wersja
|
pl:dydaktyka:asd:cwiczenia:2011-search1 [2011/04/18 09:07] ikaf update |
pl:dydaktyka:asd:cwiczenia:2011-search1 [2019/06/27 15:50] (aktualna) |
* lista jedno- i dwukierunkowa | * lista jedno- i dwukierunkowa |
* drzewo BST | * 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).// | //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/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 |