AIwiki

To jest stara wersja strony!

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

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

Szkielet klas węzła drzewa i samego drzewa:

class TreeNode {
  public:
	ElementType key;
	TreeNode *left, *right;
};
 
class TreeBST{
	private:
		TreeNode * root;
	public:
		TreeBST();
		~TreeBST();
		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
};