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. 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 jednokierunkowej:

class ElementType; // typ elementu na liście
 
class ListElement1{
protected:
        ListElement * pNext;
        ElementType value;
public:
        ListElement(){ pNext = NULL; }
        Element(const Element &element);
        ~ListElement();
 
        ElementType getValue(){ return value; }
        void setValue(const ElementType& element){ value = element; }
 
        ListElement * getNext(){ return pNext; }
        void setNext(ListElement *pNext){ pNext = pNext; } 
 
        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 clear()	usuń wszystkie elementy z listy
        void remove(ListElement * pElement, const ElementType& element){...}	
};

Listę dwukierunkową należy zaimplementować samodzielnie, analogicznie do listy jednokierunkowej.

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

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