[[
✎ pl:dydaktyka:asd:cwiczenia:2012-search1
]]
aiWiki
Pokaż stronę
Ostatnie zmiany
Indeks
Zaloguj
Ta strona jest tylko do odczytu. Możesz wyświetlić źródła tej strony ale nie możesz ich zmienić.
**Termin zajęć:** 24/25.04.2012 ====== Listy i drzewa BST ====== ===== 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 - omawiana tematyka - Każdy powinien przynieść na zajęcia zaimplementowane szkielety następujących struktur (struct, not <del>class</del>) - lista jednokierunkowa - lista dwukierunkowa - drzewo binarne BST ===== Dodatek ===== **Struktury w postaci klas:** Przykładowy 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>
pl/dydaktyka/asd/cwiczenia/2012-search1.txt
· ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)
Pokaż stronę
Poprzednie wersje
Menadżer multimediów
Do góry