2015-05-13
586
# include <vector>
using namespace std;
template <class T>
class THeap
{
private:
vector<T> Items;
int FSize;
void MoveUp(int i);
void MoveDown(int i);
public:
int Size(){ return FSize;};
void Insert(T Value);
T Delete();
bool Empty(){ return FSize==0;};
void Clear(){Items.clear();};
};
Класс TTreeNode содержит поля FParent для хранения указателя на родительский узел, список дочерних узлов Items и количество FCount, уровень узла дерева FLevel и его данные FData. Конструктор присваивает новые данные узлу, включая родителя, а методы AddChild, InsertChild, DeleteChild добавляют, вставляют и удаляют дочерние узлы. Деструктор класса не только освобождает память от самого объекта, но и удаляет все его дочерние узлы.
В модуле с данным классом можно определить класс исключительных ситуаций EQueueError для обработки ошибок, которые могут возникать при работе с узлами дерева.
#define ETreeNodeError Exception
Чтобы использовать эти классы, в заголовочном разделе модуля с расширением h необходимо подключить модуль SysUtils.hpp, в котором хранить базовый класс исключительных ситуаций Exception.
После объявления класса TTreeNode необходимо определить все его методы в заголовочном разделе модуля с расширением h в соответствии с ADT – форматом.
|
|
|
После объявления класса необходимо определить все его методы в разделе implementation в соответствии с ADT – форматом.
1. Перемещение элемента вверх для выполнения пирамидальной сортировки
template < class T>
void THeap<T>::MoveUp(int i)
{
int CurrentPos, ParentPos;
T Result;
CurrentPos = i;
ParentPos = (i-1)/2;
Result = Items[i];
while (CurrentPos!= 0) && (Result < Items[ParentPos])
{
Items[CurrentPos] = Items[ParentPos];
CurrentPos = ParentPos;
ParentPos = CurrentPos-1;
};
Items[CurrentPos]= Result;
}
В данном методе узел с переданной позицией или будет передаваться вверх по структуре дерева, пока не достигнет корня, или пока его значение не окажется больше ил равным значению родительского узла. В результате структура пирамиды восстановится.
2. Вставка узла
template < class T>
void THeap<T>::Insert(T Value)
{
Items.push_back(Value);
FSize++;
MoveUp(FSize-1);
}
Вначале новое значение вставляется в конец пирамиды, и ее размер увеличивается на 1, а затем вставленный узел перемещаем вверх для выполнения пирамидального упорядочивания.
3. Перемещение узла вниз
template < class T>
void THeap<T>::MoveDown(int i)
{
int CurrentPos, ChildPos;
T Result;
CurrentPos = i;
ChildPos = 2*i+1;
Result = Items[i];
while (CurrentPos<FSize)
{
if (ChildPos+1 < FSize && Items[ChildPos+1] <
Items[ChildPos])
ChildPos = ChildPos+1;
if (Result <= Items[ChildPos])
break;
Else
{
Items[CurrentPos] = Items[ChildPos];
CurrentPos = ChildPos;
ChildPos = 2*CurrentPos+1;
};
};
Items[CurrentPos] = Result;
}
Если правый наследник существует, и его значение меньше левого наследника, то ветвь для перемещения будет выбрана для правого наследника. Если текущий узел больше любого наследника, то он меняется с наименьшим наследником, и поиск продолжается для новых наследников.
|
|
|
4. Удаление узла
template < class T>
T THeap<T>::Delete()
{
T Result;
Result = Items[0];
Items[0] = Items[FSize-1];
Items.pop_back();
FSize--;
MoveDown(0);
return Result;
}
Метод удаляет узлы только из корня. Вместо корня помещается последний элемент в структуре пирамиды. После освобождения памяти размер пирамиды уменьшается на 1. Для сохранения пирамидального упорядочивания для нового корня выполняется метод MoveDown. Только потом возвращается корню первоначальное значение.
После того, как определен класс THeap, его можно использовать в любом месте программы, подключив соответствующий модуль с классом THeap.
void __fastcall TForm1::Button1Click(TObject *Sender)
{
THeap<char> Heap;
THeap
THeap <char> Heap;
Heap.Insert('П');
Heap.Insert('И');
Heap.Insert('Р');
Heap.Insert('А');
Heap.Insert('M');
Heap.Insert('И');
Heap.Insert('Д');
Heap.Insert('А');
Edit1->Text = ‘’’’;
while (!Heap.Empty())
Edit1->Text = Edit1->Text + Heap.Delete();
}
