AIwiki

Termin zajęć: 19/20.04.2011

Do przygotowania:

1. Znajomość budowy i zasad działania podstawowych struktur danych:
   • lista jedno- i dwukierunkowa
   • drzewo BST
2. Zakres wiadomości: Cormen - Wprowadzenie do algorytmów, Część III: Wprowadzenie, Rozdział 10 i 12
3. Każdy powinien przynieść na zajęcia zaimplementowane następujące klasy
   1. lista jednokierunkowa
   2. lista dwukierunkowa
   3. 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).

Szkielet klasy listy dwukierunkowej:

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

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

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
};