Выбор, размещение и задание свойств компонентов.
Коды классов, функций и обработчиков событий
Сохраните модуль главной формы под именем LR_8, а проект – под именем PR_LR_8.
Для размещения классов в проекте использованы модули, не связанные с формой. Класс для узла дерева объявлен и определен в файле f_8_1, а класс для бинарного дерева – в модуле f_8_2. Ниже приведены заголовочные файлы и файлы реализации этих модулей.
Заголовочный файлf_8_1.h модуля f_8_1 (без формы)
//---------------------------------------------------------------------------
#ifndef f_8_1H
#define f_8_1H
#include <iostream.h> // для константы NULL
//---------------------------------------------------------------------------
//BinSTree зависит от TreeNode
class BinSTree;
// объявление класса для узла бинарного дерева
class TreeNode
{
// сделать класс BinSTree дружественным,
// поскольку функциям-элементам класса BinSTree
// необходим доступ к полям left и right класса TreeNode
friend class BinSTree;
public:
// открытый элемент
int data;
// конструктор
TreeNode(const int& item, TreeNode *lptr=NULL,
TreeNode *rptr=NULL);
// функции-элементы доступа к полям указателей
TreeNode* Left() const{return left;}
TreeNode* Right() const{return right;}
private:
// указатели левого и правого дочерних узлов
TreeNode *left;
TreeNode *right;
};
#endif
Файл реализацииf_8_1.cpp модуля f_8_1 (без формы)
//---------------------------------------------------------------------------
#pragma hdrstop
#include "f_8_1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
// конструктор инициализирует поля данных и указателей
|
|
|
// значение NULL соответствует пустому поддереву
TreeNode::TreeNode(const int& item, TreeNode *lptr,
TreeNode *rptr):data(item), left(lptr), right(rptr)
{}
Заголовочный файлf_8_2.h модуля f_8_2 (без формы)
//---------------------------------------------------------------------------
#ifndef f_8_2H
#define f_8_2H
#include "f_8_1.h"
//------------------------------------------------------------------------
// класс - бинарное дерево
class BinSTree
{
public:
// конструкторы и деструктор
BinSTree();
BinSTree(const BinSTree& tree);
~BinSTree();
// оператор присваивания
BinSTree& operator=(const BinSTree& rhs);
// функции-элементы обработки данных
int Find(int& item); // есть или нет узла с item
void Insert(const int& item); // вставить узел с item
void Delete(const int& item); // удалить узел с item
void ClearTree(); // уничтожить дерево
TreeNode *CopyTree(TreeNode *t); // копировать дерево
int Depth(TreeNode *t); // получить глубину дерева
// получить количество листьев в дереве
void CountLeaf(TreeNode *t,int& count);
// получить корень дерева
TreeNode *GetRoot() const {return root;}
// получить количество узлов в дереве
int GetSize() const {return size;}
private:
// указатель на корень
TreeNode *root;
// количество узлов в дереве
int size;
// выделить память под узел дерева
TreeNode *GetTreeNode(const int& item,
TreeNode *lptr, TreeNode *rptr);
// удалить все узлы дерева
void DeleteTree(TreeNode* t);
// получить указатели - на узел с item и его родителя
|
|
|
TreeNode *FindNode(const int& item,
TreeNode* &parent)const;
};
#endif
Файл реализацииf_8_2.cpp модуля f_8_2 (без формы)
//---------------------------------------------------------------------------
#pragma hdrstop
#include <iostream.h> // для константы NULL
#include "f_8_2.h"
#include "LR_8.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
//---------------------------------------------------------------------------
// конструктор
BinSTree::BinSTree()
{
root=NULL;
size=0;
}
//---------------------------------------------------------------------------
// конструктор копирования
BinSTree::BinSTree(const BinSTree& tree)
{
// скопировать дерево в создаваемое дерево
root=CopyTree(tree.root);
// скопировать размер дерева
size=tree.size;
}
//---------------------------------------------------------------------------
// деструктор
BinSTree::~BinSTree()
{
ClearTree();
size=0;
}
//---------------------------------------------------------------------------
// оператор присваивания
BinSTree& BinSTree::operator = (const BinSTree& rhs)
{
// нельзя копировать дерево в самоё себя
if(this == &rhs)
return *this;
// очистить текущее дерево, скопировать новое дерево в текущий
// объект
ClearTree();
root=CopyTree(rhs.root);
// задать размер дерева
size=rhs.size;
// возвратить ссылку на текущий объект
return *this;
}
//----------------------------------------------------------------------
// искать элемент данных на дереве; если найден, возвратить адрес
|
|
|
// совпавшего узла и указатель на его предка; иначе возвратить NULL
TreeNode *BinSTree::FindNode(const int& item,
TreeNode* &parent) const
{
// пробежать по узлам дерева, начиная с корня
TreeNode *t=root;
// у корня нет родителя
parent=NULL;
// прерваться на пустом поддереве
while (t!=NULL)
{
// остановиться по совпадению
if(item==t->data)
break;
else
{
//обновить родительский указатель и идти налево или направо
parent=t;
if(item<t->data)
t=t->left;
else
t=t->right;
}
}
// возвратить указатель на узел; NULL, если не найден
return t;
}
//----------------------------------------------------------------------
// искать item. если найден, присвоить данные узла параметру item
int BinSTree::Find(int& item)
{
// используем FindNode, который принимает параметр parent
TreeNode *parent, *current;
// искать item, назначить совпавший узел текущим
current = FindNode(item,parent);
// если найден, присвоить данные узла и возвратить true
if(current!=NULL)
{
item=current->data;
return 1;
}
else
// item не найден, возвратить false
return 0;
}
//--------------------------------------------------------------------------
// создать объект TreeNode с указательными полями lptr и rptr.
// по умолчанию указатели содержат NULL.
TreeNode *BinSTree::GetTreeNode(const int& item,
|
|
|
TreeNode *lptr, TreeNode *rptr)
{
TreeNode *p;
// вызвать new для создания нового узла.
// передать туда параметры lptr и rptr.
p=new TreeNode (item, lptr, rptr);
// если памяти недостаточно, завершить программу
// сообщением об ошибке
if(p==NULL)
{
MessageBox(NULL,"Недостаточно памяти!","Ошибка",0);
return NULL;
}
// вернуть указатель на выделенную память
return p;
}
//----------------------------------------------------------------------
// вставить item в дерево
void BinSTree::Insert(const int& item)
{
// t - текущий узел, parent - предыдущий узел
// newNode - новый узел
TreeNode *t=root, *parent=NULL, *newNode;
newNode = GetTreeNode(item, NULL, NULL);
// закончить на пустом поддереве
while (t!=NULL)
{
// если item равно данному в текущем узле, не вставлять
if(item==t->data) return;
// обновить указатель parent и идти налево или направо
parent=t;
if(item<t->data)
t=t->left;
else
t=t->right;
}
// если родителя нет, вставить в качестве корневого узла
if(parent==NULL)
root=newNode;
// если item меньше данного в родительском узле,
// вставить в качестве левого сына
else if(item<parent->data)
parent->left=newNode;
else
// если item больше данному в родительском узле,
// вставить в качестве правого сына
parent->right=newNode;
// увеличить size на единицу
size++;
}
//------------------------------------------------------------------------
// если элемент находится на дереве, удалить его
void BinSTree::Delete(const int& item)
{
// DNodePtr - указатель на удаляемый узел D
// PNodePtr - указатель на родительский узел P узла D
// RNodePtr - указатель на узел R, замещающий узел D
TreeNode *DNodePtr, *PNodePtr, *RNodePtr;
// найти узел, данные в котором совпадают с item.
// получить его адрес и адрес его родителя
if((DNodePtr=FindNode(item,PNodePtr))==NULL)
return;
// если узел D имеет NULL-указатель, то заменяющим
// узлом является тот, что находится на другой ветви
if(DNodePtr->right==NULL)
RNodePtr=DNodePtr->left;
else if(DNodePtr->left==NULL)
RNodePtr=DNodePtr->right;
// узел D имеет двух сыновей
else
{
// найти и отсоединить заменяющий узел R для узла D.
// в левом поддереве узла D найти узел с максимальным данным
// из всех узлов с меньшими данными, чем в узле D.
// отсоединить этот узел от дерева.
// PofRNodePtr - указатель на родителя заменяющего узла
TreeNode *PofRNodePtr=DNodePtr;
// первой возможной заменой является левый сын узла D
RNodePtr=DNodePtr->left;
// спуститься вниз по правому поддереву левого сына узла D,
// сохраняя записи текущего узла и его родителя.
// остановившись, будем иметь заменяющий узел
while (RNodePtr->right!=NULL)
{
PofRNodePtr=RNodePtr;
RNodePtr=RNodePtr->right;
}
if(PofRNodePtr==DNodePtr)
// левый сын удаляемого узла является заменяющим
// присоединить правое поддерево узла D к узлу R
RNodePtr->right=DNodePtr->right;
else
{
// спустились вниз по правой ветви как минимум на один узел.
// удалить заменяющий узел из дерева,
// присоединив его левую ветвь к его родительскому узлу
PofRNodePtr->right=RNodePtr->left;
// присоединить правую и левую ветви удаляемого узла
// к правой и левой ветвям соответственно заменяющего узла
RNodePtr->right=DNodePtr->right;
RNodePtr->left=DNodePtr->left;
}
}
// завершить присоединение заменяющего узла к родительскому узлу.
// удалить корневой узел. назначить новый корень.
if(PNodePtr==NULL)
root=RNodePtr;
// присоединить узел R к узлу P с правильной стороны
else
if(DNodePtr->data<PNodePtr->data)
PNodePtr->left=RNodePtr;
else
PNodePtr->right=RNodePtr;
// удалить узел из памяти и уменьшить размер дерева
delete DNodePtr;
DNodePtr=NULL;
size--;
}
//---------------------------------------------------------------------
// эта функция при обходе дерева подсчитывает его листья.
// функция использует обратный метод обхода дерева.
// во время посещения узла проверяется, является ли он листом.
void BinSTree::CountLeaf(TreeNode *t,int& count)
{
// использовать обратный метод прохождения
if(t!=NULL)
{
CountLeaf(t->left, count); // пройти левое поддерево
CountLeaf(t->right, count); // пройти правое поддерево
// проверить, является ли данный узел листом.
// если да, то произвести приращение переменной count
if( t->left==NULL && t->right==NULL)
count++;
}
}
//----------------------------------------------------------------------
// эта функция использует обратный метод обхода дерева для
// вычисления глубины левого и правого поддеревьев узла и
// возвращает результирующее
// значение глубины, равное 1+max(depthLeft,depthRight).
// глубина пустого дерева равна -1
int BinSTree::Depth(TreeNode *t)
{
int depthLeft, depthRight, depthval;
if(t==NULL)
depthval=-1;
else
{
depthLeft=Depth(t->left);
depthRight=Depth(t->right);
depthval=1+(depthLeft>depthRight?depthLeft:depthRight);
}
return depthval;
}
//-----------------------------------------------------------------------
// создать дубликат нового дерева t и возвратить корень нового дерева
TreeNode *BinSTree::CopyTree(TreeNode *t)
{
// переменная newnode указывает на новый узел, создаваемый
// посредством вызова GetTreeNode и присоединяемый в дальнейшем
// к новому дереву. указатели newlptr и newrptr адресуют сыновей
// нового узла и передаются в качестве параметров в GetTreeNode
TreeNode *newlptr, *newrptr, *newnode;
// остановить рекурсивное прохождение при достижении пустого дерева
if(t==NULL)
return NULL;
// CopyTree строит новое дерево в процессе прохождения узлов дерева t.
// в каждом узле этого дерева функция CopyTree проверяет наличие
// левого сына.
// если он есть, создается его копия. в противном случае возвращается
// NULL.
// CopyTree создает копию узла с помощью GetTreeNode
// и подвешивает к нему копии сыновей
if(t->Left()!=NULL)
newlptr=CopyTree(t->left);
else
newlptr=NULL;
if(t->Right()!=NULL)
newrptr=CopyTree(t->right);
else
newrptr=NULL;
// построить новое дерево снизу вверх, сначала создавая
// двух сыновей, а затем их родителя
newnode=GetTreeNode(t->data, newlptr, newrptr);
// вернуть указатель на вновь созданное дерево
return newnode;
}
//------------------------------------------------------------------------
// использовать обратный алгоритм для прохождения узлов дерева
// и удалить каждый узел при его посещении
void BinSTree::DeleteTree(TreeNode* t)
{
if(t)
{
DeleteTree(t->left);
DeleteTree(t->right);
delete t;
size--;
}
}
//--------------------------------------------------------------------------
// вызвать функцию DeleteTree для удаления узлов дерева.
// затем сбросить указатель на его корень в NULL
void BinSTree::ClearTree()
{
DeleteTree(root);
root=NULL;
// теперь корень пуст, дерево уничтожено
}
//------------------------------------------------------------------------
Достаточно полную информацию для размещения компонентов на форме и задания их свойств можно получить из представленных ниже рис.8.3, рис.8.4 и заголовочного файла модуля LR_8.
Рис.8.3 – форма по окончании проектирования
Рис.8.4 – меню
Заголовочный файл LR_8.hмодуля LR_8
//---------------------------------------------------------------------------
#ifndef LR_8H
#define LR_8H
//---------------------------------------------------------------------------
#include <Classes.hpp>
#include <Controls.hpp>
#include <StdCtrls.hpp>
#include <Forms.hpp>
#include "CSPIN.h"
#include <ComCtrls.hpp>
#include <ActnCtrls.hpp>
#include <ActnList.hpp>
#include <ActnMan.hpp>
#include <ActnMenus.hpp>
#include <ImgList.hpp>
#include <ToolWin.hpp>
#include <ExtCtrls.hpp>
#include <Buttons.hpp>
//---------------------------------------------------------------------------
class TForm1 : public TForm
{
__published: // IDE-managed Components
TMemo *Memo1;
TLabel *Label1;
TImageList *ImageList1;
TActionManager *ActionManager1;
TAction *SaveFileAs;
TAction *SaveFile;
TAction *OpenFile;
TAction *OutMemo;
TAction *Depth;
TAction *CountLeaf;
TAction *Find;
TAction *ClearTree;
TAction *Exit;
TGroupBox *GroupBox1;
TRadioButton *RadioButton2;
TRadioButton *RadioButton1;
TCSpinEdit *CSpinEdit1;
TButton *Button1;
TButton *Button2;
TLabeledEdit *LabeledEdit1;
TAction *Insert;
TAction *Delete;
TBitBtn *BitBtn1;
TActionMainMenuBar *ActionMainMenuBar1;
TActionToolBar *ActionToolBar1;
TAction *ClearMemo;
TLabeledEdit *LabeledEdit2;
TLabel *Label2;
void __fastcall RadioButton2Click(TObject *Sender);
void __fastcall RadioButton1Click(TObject *Sender);
void __fastcall ExitExecute(TObject *Sender);
void __fastcall OutMemoExecute(TObject *Sender);
void __fastcall InsertExecute(TObject *Sender);
void __fastcall BitBtn1Click(TObject *Sender);
void __fastcall ClearMemoExecute(TObject *Sender);
void __fastcall ClearTreeExecute(TObject *Sender);
void __fastcall CountLeafExecute(TObject *Sender);
void __fastcall DepthExecute(TObject *Sender);
void __fastcall FindExecute(TObject *Sender);
void __fastcall DeleteExecute(TObject *Sender);
private: // User declarations
public: // User declarations
__fastcall TForm1(TComponent* Owner);
};
//---------------------------------------------------------------------------
extern PACKAGE TForm1 *Form1;
//---------------------------------------------------------------------------
#endif
Перенесем на форму компоненты и зададим их свойствам значения. Со страницы Дополнительно – LabeledEdit1 (EditLabel->Caption – Ключ, Text- 10), диспетчер действий ActionManager1и полосу главного меню ActionMainMenuBar1. По умолчанию полоса главного меню ActionMainMenuBar1расположится вверху, на всю ширину формы. Задайте её свойство Align = alNone, чтобы придать ей нужные размеры и расположить в нужном месте.
Затем со страницы Win32 перенесите на форму ImageList1, со страницы Стандарт - Label1(Caption – ДЕРЕВО), Memo1, GroupBox1(Caption – Формирование дерева). На панель GroupBox1 перенесите: со страницы Стандарт - две радиокнопки – RadioButton1(Caption - вручную,Checked – true, Enabled - true) и RadioButton2 (Caption - автоматически,Checked – false,Enabled - true), Label2(Caption – количество узлов), Button1 (Caption – Добавить узел), Button2 (Caption – Удалить узел ), со страницы Примеры – CSpinEdit1 (MaxValue -100, MinValue – 1, Value – 10), со страницы Дополнительно – BitBtn1 (Caption – ПУСК), LabeledEdit2 (EditLabel->Caption – целое число, Text- 10).
Загрузите в компонент ImageList1 пиктограммы из файлов fldropen, filesave, floppy, find, insert, clear, delete, arrow2d, erase, dooropen, directry. В компоненте ActionManager1 установим свойство Images равным ImageList1, связав тем самым диспетчер действий со списком изображений.
Добавьте на форму с помощью диспетчера действий ActionManager1 инструментальную панель ActionTollBar1, задайте для нее Align = alNone, Constraints->MaxHeight =230, Constraints->MinHeight =230 и расположите ее на форме согласно рис.8.3.
В диспетчере действий ActionManager1 создайте три категории действий: Файл, Дерево, Выход.
По категориям объектам действий даны следующие надписи (Caption) - имена (Name): Файл: Сохранить как - FileSaveAs, Сохранить - FileSave, Открыть - FileOpen; Дерево: Уничтожить дерево - ClearTree, Поиск узла по ключу - Find, Кол-во листьев - CountLeaf, Глубина дерева - Depth, Вывести дерево в окно - OutMemo, Удалить узел - Delete, Добавить узел - Insert, Очистить окно - ClearMemo. В свойство ImageIndexперечисленных объектов действий занесите соответствующие значения.
В свойство Action кнопок Button1 (Caption – Добавить узел) и Button2 (Caption – Удалить узел ) занесите соответственно значения Insert и Delete.
Действия по активации и инициализации компонентов и обработчики событий приведены в файле реализации LR_8.cppмодуля LR_8.
Файл реализации LR_8.cpp модуля LR_8
//---------------------------------------------------------------------------
#include <vcl.h>
#pragma hdrstop
#include "LR_8.h"
#include "f_8_2.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma link "CSPIN"
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
Memo1->Text="";
RadioButton1->Checked=true;
RadioButton2->Checked=false;
CSpinEdit1->Enabled=false;
Label2->Enabled=false;
BitBtn1->Enabled=false;
Button1->Enabled=true;
Button2->Enabled=true;
LabeledEdit2->Enabled=true;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::RadioButton2Click(TObject *Sender)
{
if(RadioButton2->Checked)
{
Label2->Enabled=true;
CSpinEdit1->Enabled=true;
LabeledEdit2->Enabled=false;
BitBtn1->Enabled=true;
Button1->Enabled=false;
Button2->Enabled=false;
}
}
//---------------------------------------------------------------------------
void __fastcall TForm1::RadioButton1Click(TObject *Sender)
{
if(RadioButton1->Checked)
{
Label2->Enabled=false;
CSpinEdit1->Enabled=false;
BitBtn1->Enabled=false;
LabeledEdit2->Enabled=true;
Button1->Enabled=true;
Button2->Enabled=true;
}
}
//---------------------------------------------------------------------------
void __fastcall TForm1::ExitExecute(TObject *Sender)
{
Close();
}
//---------------------------------------------------------------------------
// вывод дерева в окно с обходом справа-налево
void PrintTree(TreeNode *t, int level)
{
AnsiString s="";
// обходить дерево справа-налево, пока t!=NULL
if(t!=NULL)
{
// обходить правое поддерево узла t
PrintTree(t->Right(), level+1);
// вывести данное в узле t
for(int i=0; i<level; i++) s += "****";
s += IntToStr(t->data);
Form1->Memo1->Lines->Add(s);
// обходить левое поддерево узла t
PrintTree(t->Left(), level+1);
}
}
//-------------------------------------------------------------------------
// создать объект класса - бинарное дерево
BinSTree AI;
//-------------------------------------------------------------------------
void __fastcall TForm1::OutMemoExecute(TObject *Sender)
{
TreeNode *t= AI.GetRoot();
if(t==NULL)
{
MessageBox(NULL,"Дерево пусто!","",0);
return;
}
Form1->Memo1->Lines->Add("");
PrintTree(t,0);
Form1->Memo1->Lines->Add("Количество узлов - " +
IntToStr(AI.GetSize()));
Form1->Memo1->Lines->Add("");
}
//---------------------------------------------------------------------------
void __fastcall TForm1::InsertExecute(TObject *Sender)
{
AI.Insert(StrToInt(LabeledEdit2->Text));
Form1->Memo1->Lines->Add("Узел "+LabeledEdit2->Text+" добавлен!");
}
//---------------------------------------------------------------------------
void __fastcall TForm1::BitBtn1Click(TObject *Sender)
{
AI.ClearTree();
for(int i=0; i<CSpinEdit1->Value; i++)
AI.Insert(random(101)-random(101));
}
//---------------------------------------------------------------------------
void __fastcall TForm1::ClearMemoExecute(TObject *Sender)
{
Memo1->Clear();
}
//---------------------------------------------------------------------------
void __fastcall TForm1::ClearTreeExecute(TObject *Sender)
{
if(AI.GetRoot()==NULL)
{
MessageBox(NULL,"Дерево пусто!","",0);
return;
}
AI.ClearTree();
if(AI.GetRoot()==NULL)
MessageBox(NULL,"Дерево уничтожено!","",0);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::CountLeafExecute(TObject *Sender)
{
TreeNode* t=AI.GetRoot();
int count=0;
AI.CountLeaf(t, count);
Form1->Memo1->Lines->Add("Количество листьев - "+IntToStr(count));
}
//---------------------------------------------------------------------------
void __fastcall TForm1::DepthExecute(TObject *Sender)
{
TreeNode* t=AI.GetRoot();
int d=AI.Depth(t);
Form1->Memo1->Lines->Add("Глубина дерева - "+IntToStr(d));
}
//---------------------------------------------------------------------------
void __fastcall TForm1::FindExecute(TObject *Sender)
{
int key = StrToInt(LabeledEdit1->Text);
if(AI.Find(key))
Form1->Memo1->Lines->Add("Узел с ключом "+IntToStr(key)+" есть!");
else
Form1->Memo1->Lines->Add("Узла с ключом "+IntToStr(key)+" нет!");
}
//---------------------------------------------------------------------------
void __fastcall TForm1::DeleteExecute(TObject *Sender)
{
int k = StrToInt(LabeledEdit2->Text);
if(AI.Find(k))
{
AI.Delete(k);
Form1->Memo1->Lines->Add("Узел "+IntToStr(k)+" удален!");
}
else
Form1->Memo1->Lines->Add("Узла "+IntToStr(k)+" нет!");
}
//---------------------------------------------------------------------------
Дата добавления: 2018-05-13; просмотров: 370; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!