Termin zajęć: 24/25.04.2012

Listy i drzewa BST

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 - omawiana tematyka
  3. Każdy powinien przynieść na zajęcia zaimplementowane szkielety następujących struktur (struct, not class)
    1. lista jednokierunkowa
    2. lista dwukierunkowa
    3. drzewo binarne BST

Dodatek

Struktury w postaci klas:

Przykładowy 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
};
pl/dydaktyka/asd/cwiczenia/2012-search1.txt · ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0