Muxammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti qarshi filiali

Дастур матни:

Файл main.cpp:
#include

#pragma hdrstop

#include "Main.h"

#pragma package(smart_init)

#pragma resource "*.dfm"
TfrmMain *frmMain;

class ID //Описание класса

{

public:

AnsiString Name;

int Right;

int Left;

ID()

{

Right = 0;

Left = 0;

}

int Hash()

{

char *str;

str = Name.c_str();

return (str[0]|str[1]);

}

};

ID *IDTbl;

int *HashTbl;

int CollisionQuantity=0;

int CompareQuantity=0;

void MakeTreeNode(ID *IDTable, int HashIndex, int IDIndex)

{ //Построение бинарного дерева

if (IDTable[HashIndex].Name>IDTable[IDIndex].Name)

{

if (!IDTable[HashIndex].Right)

IDTable[HashIndex].Right = IDIndex;

else

MakeTreeNode(IDTable,IDTable[HashIndex].Right,IDIndex);

}

if (IDTable[HashIndex].Name

{

if (!IDTable[HashIndex].Left)

IDTable[HashIndex].Left = IDIndex;

else

MakeTreeNode(IDTable,IDTable[HashIndex].Left,IDIndex);

}

}

void HashTreeBuild(ID *IDTable, int *HashTable, int N)

{

for (int i=0; i<=N; i++)

{

if (!HashTable[IDTable[i].Hash()])

HashTable[IDTable[i].Hash()] = i;

else

{

CollisionQuantity++;

MakeTreeNode(IDTable, HashTable[IDTable[i].Hash()],i);

}

}

}

__fastcall TfrmMain::TfrmMain(TComponent* Owner)

: TForm(Owner)

{

//Загрузка исходных данных из файла

mmOut->Lines->LoadFromFile("Input.txt");

int N = mmOut->Lines[0].Count;

ID *IDTable;

IDTable = new ID [N+1];

for (int i=1; i<=N; i++)

IDTable[i].Name = mmOut->Lines[0][i-1];

//Заполнение хэш-таблицы нулевыми значениями

int *HashTable;

HashTable = new int [256];

for (int i=0; i<=255; i++)

HashTable[i]=0;
HashTreeBuild(IDTable,HashTable,N);
//Вывод на экран таблицы идентификаторов

for (int i=1;i<=N;i++)

mmDebug->Lines->Add(IntToStr(i)+" "+

IDTable[i].Name+" "+

IntToStr(IDTable[i].Hash())+" "+

IntToStr(IDTable[i].Left)+" "+

IntToStr(IDTable[i].Right));

mmOut->Clear();

mmOut->Lines->Add("Введите имя искомого идентификатора");

mmOut->Lines->Add("Коллизий:"+IntToStr(CollisionQuantity));

IDTbl = IDTable;

HashTbl = HashTable;

}

int GetIDIndex(ID SearchID, ID *IDTable, int HashIndex)

{

//0-если не нашел, или индекс в IDTable

int IDIndex = 0;

if (IDTable[HashIndex].Name==SearchID.Name)

{

CompareQuantity++;

return HashIndex;

}

if (IDTable[HashIndex].Name>SearchID.Name)

{

CompareQuantity++;

if (IDTable[HashIndex].Right)

return GetIDIndex(SearchID,IDTable,IDTable[HashIndex].Right);

else return 0;

}

else

{

CompareQuantity++;

if (IDTable[HashIndex].Left)

return GetIDIndex(SearchID,IDTable,IDTable[HashIndex].Left);

else return 0;

}

}

void __fastcall TfrmMain::Button1Click(TObject *Sender)

{ //Поиска идентификатора и выдача результата

AnsiString SearchString = edtSearch->Text;

ID SearchID;

SearchID.Name = SearchString;

int Hash = SearchID.Hash();

int HashIndex;

int IDIndex;

HashIndex = HashTbl[Hash];

CompareQuantity=0;

IDIndex = GetIDIndex(SearchID,IDTbl,HashIndex);
mmOut->Clear();

if (IDIndex)

{

mmOut->Lines->Add("Идентификатор найден, его индекс в таблице идентификаторов:"+IntToStr(IDIndex));

mmOut->Lines->Add("Сравнений:"+IntToStr(CompareQuantity));

}

else

{

mmOut->Lines->Add("Идентификатор не найден");

mmOut->Lines->Add("Сравнений:"+IntToStr(CompareQuantity));

}

}