Программная реализация B+-дерева

Выходные данные: иерархия дерева, глубина.

Процессы обработки: рекурсивная  функция, назначающая узлам уровень  в иерархии, глубину. Для корня 0.

Подпрограмма short CB_PLUS_Tree<Data>::AssignWidths(Node* node)

Входные данные: текущий узел.

Выходные данные: ширина текущего узла.

Процессы обработки: рекурсивная  функция, назначающая узлам ширину, то есть количество родственных листьев.

Подпрограмма void CB_PLUS_Tree<Data>::AssignIndents(Node* node)

Входные данные: текущий узел.

Выходные данные: количество неродственных листьев.

Процессы обработки: рекурсивная  функция, назначающая узлам отступы, то есть количество неродственных листьев, стоящих слева.

 

 

Тексты подпрограмм

См. Приложение Б.

6. Тестирование

1. Цель испытаний

Выяснить поведение программы  в различных ситуациях, созданных  пользователем.

2. Тесты

Тест №1

Действия: первый запуск программы.

Реакция программы: если в рабочем каталоге содержится файл «schedule.txt» с базой данных банка, то программа выведет на экран дерево, построенное по данным этого файла. Если файл отсутствует, программа отобразит пустое поле.

Тест №2

Действия: щелчок мыши на конкретном ключе.

Реакция программы: клетка с ключом подсвечивается красным, а поля «Номер счета», «ФИО», «Сумма вклада» и «Длительность (мес - %)» заполнятся из структуры, соответствующей выделенному ключу.

Тест №3

Действия: нажатие кнопки «Добавить»

Реакция программы: если хотя бы одно из полей «Номер счета», «ФИО», «Сумма вклада» и «Длительность (мес - %)» не заполнено, то выдается сообщение о том, что поле пусто. Если введен некорректный номер счета или в дереве уже имеется запись с указанным номером счета, то выдается соответствующее сообщение. Если введены корректные данные, не содержащиеся в дереве, то запись будет добавлена в дерево, после чего дерево будет перерисовано.

Тест №4

Действия: нажатие кнопки «Удалить».

Реакция программы: если поле «Номер счета» пусто, либо в дереве не содержится записи о данном маршруте, либо введено некорректное значение,  то выдается сообщение об ошибке. Если значение поля «Номер счета» корректно и запись с таким ключом содержится в дереве, то запись удаляется из дерева, поля для ввода очищаются, после чего происходит перерисовка дерева.

Тест №5

Действия: нажатие кнопки «Найти».

Реакция программы: если поле «Номер счета» пусто, либо в дереве не содержится записи о данном маршруте, либо введено некорректное значение,  то выдается сообщение об ошибке. Если значение поля «Номер счета» корректно и запись с таким ключом содержится в дереве, то в поля для ввода выводятся данные найденной записи, найденный ключ подсвечивается и фокус перемещается на него.

 

 

 

 

Рисунок 3

 

 

Список использованных источников

1. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ, 2-е издание : Пер. с англ. – М.: “Вильямс”, 2005. – 1296 с.
2. Вирт Н. Алгоритмы и структуры данных. - М.: Мир, 1989.

 

Приложение А.

Листинг файла Form.h

//---------------------------------------------------------------------------

 

#ifndef FormH

#define FormH

//---------------------------------------------------------------------------

#include <Classes.hpp>

#include <Controls.hpp>

#include <StdCtrls.hpp>

#include <Forms.hpp>

#include <ExtCtrls.hpp>

 

#include "BTree.h"

#include "Graphics.hpp"

#include <stdio.h>

#include <mem.h>

#include <AppEvnts.hpp>

 

#define N                                 3     // порядок дерева;

#define NODE_HEIGHT                      17     // высота узла;

#define KEY_WIDTH                        27     // ширина ключа;

#define FONT_SIZE                         8     // высота шрифта;

#define NODE_WIDTH            KEY_WIDTH*2*N     // ширина узла (2N - макс. кол-во ключей);

#define X_INTERVAL              KEY_WIDTH*2     // расстояние между узлами по горизонтали;

#define Y_INTERVAL          NODE_HEIGHT*N*2     // растояние между узлами по вертикали;

#define PERIOD    (NODE_WIDTH + X_INTERVAL)     // период;

#define TEXT_X0 (x1+1)                          // координаты для текста в клетке ключа;

#define TEXT_Y0 (y1+1)

#define NODE_BORDER_COLOR           clBlack     // цвет границ узла;

#define ARC_COLOR                   clPurple    // цвет дуги;

#define SELECTED_COLOR              clRed       // цвет выделенного  ключа;

#define NODE_COLOR                  clNavy      // цвет узла;

#define TEXT_COLOR                  clLime      // цвет текста;

 

struct Bank{

int key;                      // первичный ключ (номер счета);

String FIO;                   // ФИО;

String money;                 // сумма вклада;

String duration;              // длительность и процент;

Bank(): key(0),FIO(""),money(""),duration(""){}

Bank(const Bank& a): key(a.key), FIO(a.FIO), money(a.money),duration(a.duration){}

Bank(const int& a): key(a){}

Bank(const int k, const String f, const String m, const String d): key(k),FIO(f),money(m),duration(d){}

};

 

//---------------------------------------------------------------------------

class TFormMain : public TForm

{

__published: // IDE-managed Components

TPaintBox *PaintBox;

TButton *BtnAdd;

TLabeledEdit *LabEdKey;

TScrollBar *ScrollBarHor;

TScrollBar *ScrollBarVert;

TButton *BtnDelete;

TLabeledEdit *LabEdFIO;

TLabeledEdit *LabEdmoney;

TLabeledEdit *LabEdDuration;

TButton *BtnSearch;

void __fastcall BtnAddClick(TObject *Sender);

void __fastcall PaintBoxPaint(TObject *Sender);

void __fastcall ScrollBarHorScroll(TObject *Sender,

  TScrollCode ScrollCode, int &ScrollPos);

void __fastcall ScrollBarVertScroll(TObject *Sender,

  TScrollCode ScrollCode, int &ScrollPos);

void __fastcall PaintBoxMouseDown(TObject *Sender,

  TMouseButton Button, TShiftState Shift, int X, int Y);

void __fastcall BtnDeleteClick(TObject *Sender);

void __fastcall BtnSearchClick(TObject *Sender);

private: // User declarations

public:  // User declarations

        short count;                         // количество ключей в дереве;

        int X0;                               // смещение системы координат. Нужно

        int Y0;                               // для перерисовки при скроллинге

int X_max;                            // границы рабочей области;

        int Y_max;

        int X_Selected;                       // координаты выделенного узла;

int Y_Selected;

        bool selected;                        // флаг, указывающий на то, что имеется выделенный ключ;

CB_PLUS_Tree<Bank>* Tree;                // дерево;

bool changed;                         // флаг, определяющий необходимость перестраивания дерева;

__fastcall TFormMain(TComponent* Owner);

void DrawTree(CB_PLUS_Tree<Bank>::Node* node);   // главная функция рисования дерева;

void DrawNode(CB_PLUS_Tree<Bank>::Node* node);   // функция рисования отдельного узла;

void FindKey(CB_PLUS_Tree<Bank>::Node* node, int x, int y, Bank & data);  // поиск узла по координатам;

void ReadFromFile(char* filename);    // чтение  данных из файла;

};

//---------------------------------------------------------------------------

extern PACKAGE TFormMain *FormMain;

//---------------------------------------------------------------------------

#endif

Листинг файла Form.cpp

//---------------------------------------------------------------------------

 

#include <vcl.h>

#pragma hdrstop

 

#include "Form.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma resource "*.dfm"

TFormMain *FormMain;

 

 

 

//---------------------------------------------------------------------------

__fastcall TFormMain::TFormMain(TComponent* Owner)

: TForm(Owner)

{

count = 0;

X0 = Y0 = 20;

X_max = PaintBox->Width;

Y_max = PaintBox->Height;

selected = false;

Tree = new CB_PLUS_Tree<Bank>;

Bank bank;

ReadFromFile("shedule.txt");

FormMain->DoubleBuffered = true;

ScrollBarHor->Max = X_max;

ScrollBarVert->Max = Y_max;

changed = true;

PaintBox->Refresh();

}

//---------------------------------------------------------------------------

 

void TFormMain::ReadFromFile(char* filename)

{

FILE* file = fopen(filename,"rb");

if (!file)

return;

int key;

char FIO[150];

char money[250];

char duration[150];

Bank bank;

count = 0;

char str[550];

while (!feof(file)){

fscanf(file,"%d",&key);

fgets(str,550,file);

int i=1, j=0;

while (str[i]!='\t' && str[i]!= '\0'){

FIO[j++] = str[i++];

}

j=0; i++;

while (str[i]!='\t' && str[i]!= '\0'){

money[j++] = str[i++];

}

j=0; i++;

while (str[i]!='\r' && str[i]!= '\0'){

duration[j++] = str[i++];

}

bank.key = key;

bank.FIO = AnsiString(FIO);

bank.money = AnsiString(money);

bank.duration = AnsiString(duration);

memset(FIO,0,150);

memset(money,0,250);

memset(duration,0,150);

memset(str,0,550);

 

Tree->AddKey(bank);

count++;

}

}

//---------------------------------------------------------------------------

 

void __fastcall TFormMain::BtnAddClick(TObject *Sender)

{

try{

Bank bank;

bank.key = LabEdKey->Text.ToInt();

bank.FIO = LabEdFIO->Text;

bank.money = LabEdmoney->Text;

bank.duration = LabEdDuration->Text;

RESULT r;

if (count == 0)

Tree->AddKey(bank);

else

r = Tree->AddKey(bank);

if (r == KEY_ALREADY_EXISTS){

ShowMessage("Запись с указанным ключом уже есть в дереве");

}

else{

count++;

changed = true;

PaintBox->Refresh();

}

}

catch(EConvertError & e){

ShowMessage("Номер счета должен быть целым и положительным");

}

catch(Exception & e){

ShowMessage(e.Message);

}

}

//---------------------------------------------------------------------------

 

void __fastcall TFormMain::BtnDeleteClick(TObject *Sender)

{

try{

Bank bank;

bank.key = LabEdKey->Text.ToInt();

if (bank.key <= 0)

throw Exception("Номер счета должен быть целым и положительным");

if (bank.key >= 100000)

throw Exception("Номер счета может быть не более 99999");

if (Tree->DeleteKey(bank) == NOT_FOUND)

throw Exception("Ключ  не найден");

else{

count--;

changed = true;

selected = false;

LabEdKey->Clear();

LabEdFIO->Clear();

LabEdmoney->Clear();

LabEdDuration->Clear();

PaintBox->Refresh();

}

}

catch(EConvertError & e){

ShowMessage("Номер счета должен быть целым и положительным");

}

catch(Exception & e){

ShowMessage(e.Message);

}

}

//---------------------------------------------------------------------------

 

void __fastcall TFormMain::BtnSearchClick(TObject *Sender)

{

try{

Bank bank;

bank.key = LabEdKey->Text.ToInt();

if (bank.key <= 0)

throw Exception("Номер счета должен быть целым и положительным");

if (bank.key >= 100000)

throw Exception("Номер счета может быть не более 99999");

short index;

CB_PLUS_Tree<Bank>::Node* node = Tree->SearchKey(bank,Tree->root,index);

if (index == -1)

throw Exception("Ключ не найден");

bank = node->item[index];

LabEdKey->Text = IntToStr(bank.key);

LabEdFIO->Text = bank.FIO;

LabEdmoney->Text = bank.money;

LabEdDuration->Text = bank.duration;

ScrollBarHor->Position = node->indent*PERIOD;

ScrollBarVert->Position = node->level*(Y_INTERVAL + NODE_HEIGHT);

X0 = - ScrollBarHor->Position + 20;

Y0 = - ScrollBarVert->Position + 20;

X_Selected = node->indent*PERIOD + index*KEY_WIDTH + 1;

Y_Selected = node->level*(Y_INTERVAL + NODE_HEIGHT) + 1;

selected = true;

PaintBox->Refresh();

}

catch(EConvertError & e){

ShowMessage("Номер счета должен быть целым и положительным");

}

catch(Exception & e){

ShowMessage(e.Message);

}

}

//---------------------------------------------------------------------------

 

void __fastcall TFormMain::PaintBoxPaint(TObject *Sender)

{

PaintBox->Canvas->Brush->Color = clWhite;

PaintBox->Canvas->FloodFill(1,1,clWhite,fsBorder);

PaintBox->Canvas->Pen->Color = NODE_BORDER_COLOR;

if (count != 0 ){

if (changed){

Tree->AssignLevels(Tree->root);

Tree->AssignWidths(Tree->root);

Tree->AssignIndents(Tree->root);

changed = false;

}

DrawTree(Tree->root);

}

}

//---------------------------------------------------------------------------

 

void TFormMain::DrawTree(CB_PLUS_Tree<Bank>::Node* node)

{

DrawNode(node);

if (node->leaf == true)

return;

for (int i=0; i<=node->keys_count ; ++i)

DrawTree(node->ptr[i]);

 

}

//---------------------------------------------------------------------------

 

void TFormMain::DrawNode(CB_PLUS_Tree<Bank>::Node* node)

{

int x1,x2,y1,y2,line_x1,line_x2,line_y1,line_y2;

y1 = Y0 + node->level * (Y_INTERVAL + NODE_HEIGHT);

y2 = y1 + NODE_HEIGHT;

line_y1 = y2;

line_y2 = y1 + Y_INTERVAL + NODE_HEIGHT;

for (int i=0; i<node->keys_count; ++i){

x1 = X0 + node->indent * PERIOD + i*KEY_WIDTH;

x2 = x1 + KEY_WIDTH;

TRect rect(x1,y1,x2,y2);

TRect text_rect(x1+1,y1+2,x2-1,y2-1);

PaintBox->Canvas->Pen->Color = NODE_BORDER_COLOR;

PaintBox->Canvas->Brush->Color = NODE_COLOR;

PaintBox->Canvas->Rectangle(rect);

if (selected)

if (((X_Selected + X0) > x1 ) && ((X_Selected + X0)< x2) && ((Y_Selected + Y0) > y1) && ((Y_Selected + Y0) < y2)){

PaintBox->Canvas->Brush->Color = SELECTED_COLOR;

PaintBox->Canvas->FloodFill(X_Selected+X0,Y_Selected+Y0,NODE_COLOR,fsSurface);

}

PaintBox->Canvas->Font->Color = TEXT_COLOR;

PaintBox->Canvas->TextRect(text_rect,TEXT_X0,TEXT_Y0,IntToStr(node->item[i].key));

if (node->leaf == false){

line_x1 = x1;

line_x2 = X0 + node->ptr[i]->indent * PERIOD;

PaintBox->Canvas->Pen->Color = ARC_COLOR;

PaintBox->Canvas->MoveTo(line_x1,line_y1);

PaintBox->Canvas->LineTo(line_x2,line_y2);

}

if (x2>X_max){

X_max = x2;

ScrollBarHor->Max = X_max;

}

if (y2>Y_max){

Y_max = y2;

ScrollBarVert->Max = Y_max;

}

}

if (node->leaf == false){

line_x1 = x2;

line_x2 = X0 + node->ptr[node->keys_count]->indent * PERIOD;

PaintBox->Canvas->Pen->Color = ARC_COLOR;

PaintBox->Canvas->MoveTo(line_x1,line_y1);

PaintBox->Canvas->LineTo(line_x2,line_y2);

}

}

//---------------------------------------------------------------------------

 

 

void __fastcall TFormMain::PaintBoxMouseDown(TObject *Sender,

  TMouseButton Button, TShiftState Shift, int X, int Y)

{

 

Bank bank = Bank();

int a = 0;

for (int y = Y + 1; y <= Y + NODE_HEIGHT; ++y)

if (PaintBox->Canvas->Pixels[X][y] == NODE_BORDER_COLOR){

a++;

break;

}

for (int y = Y - 1; y >= Y - NODE_HEIGHT; --y)

if (PaintBox->Canvas->Pixels[X][y] == NODE_BORDER_COLOR){

a++;

break;

}

if (PaintBox->Canvas->Pixels[X][Y] == NODE_BORDER_COLOR)

a = 0;

if (a == 2){

X_Selected = X - X0;

Y_Selected = Y - Y0;

selected = true;

PaintBox->Refresh();

FindKey(Tree->root,X-X0,Y-Y0,bank);

LabEdKey->Text = IntToStr(bank.key);

LabEdFIO->Text = bank.FIO;

LabEdmoney->Text = bank.money;

LabEdDuration->Text = bank.duration;

}

else{

selected = false;

PaintBox->Refresh();

}

 

}

//---------------------------------------------------------------------------

 

void TFormMain::FindKey(CB_PLUS_Tree<Bank>::Node* node, int x, int y, Bank & data)

{

   int level = y / (Y_INTERVAL + NODE_HEIGHT);

   if (level == 0){

   int key_index = (x - node->indent*PERIOD) / KEY_WIDTH;

   data = node->item[key_index];

   return;

   }

 

   if (node->level == level-1){

   if (x >= node->indent*PERIOD && x < (node->indent + node->width)*PERIOD){

   for (int i=0; i<=node->keys_count; ++i){

   if (x >= node->ptr[i]->indent*PERIOD && x < (node->ptr[i]->indent + 1)*PERIOD){

   int key_index = (x - node->ptr[i]->indent*PERIOD) / KEY_WIDTH;

   data = node->ptr[i]->item[key_index];

   return;

   }

   }

   }

   else

   return;

   }

   else if (node->level < level-1){

   for (int i=0; i<=node->keys_count; ++i){

   FindKey(node->ptr[i],x,y,data);

   if (data.key != 0)

   return;

   }

   }

   else

   return;

}

//---------------------------------------------------------------------------

 

void __fastcall TFormMain::ScrollBarHorScroll(TObject *Sender,

  TScrollCode ScrollCode, int &ScrollPos)

{

X0 = - ScrollPos + 20;

PaintBox->Refresh();