Доделать лабу по С++

  • Автор темы GreenTerrapin
  • Дата начала
G

GreenTerrapin

#1
Помогите доделать,есть похожая программа нужно ее переделать под мое условие(до понедельника 28.12)
МОИ КОНТАКТЫ: icq 354510135, gira21@mail.ru
Лабораторная работа
Поиск и сортировка.
Напишите программу, создающую таблицу идентификаторов с помощью хэш-функций на основе метода простого рехэширования. В качестве исходных данных для заполнения дерева возьмите любой текстовый файл, считая, что все слова в нем являются идентификаторами. Организуйте программу таким образом, чтобы в ней можно было легко подменять используемую хэш-функцию. Подсчитывая число коллизий и среднее количество сравнений для поиска идентификатора, сравните результаты для различных хэш-функций. В качестве исходных данных для хэш-функции использовать коды первых двух букв идентификатора.

Похожая программа
Задание: Написать программу, которая получает на входе набор идентификаторов, организует таблицу по заданному методу и позволяет осуществить многократный поиск идентификатора в этой таблице. Список идентификаторов считать заданным в виде текстового файла. Длина идентификатора ограничена 32 символами.
Тип хеш-функции-Сумма кодов первой и второй букв,
Способ разрешения коллизий-Бинарное дерево
Требуется, чтобы программа сообщала среднее число коллизий и среднее количество сравнений, выполняемых для поиска идентификатора.

Файл main.cpp:

#include <vcl.h>
#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<IDTable[IDIndex].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.Hash()])
HashTable[IDTable.Hash()] = i;
else
{
CollisionQuantity++;
MakeTreeNode(IDTable, HashTable[IDTable.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.Name = mmOut->Lines[0][i-1];

//Заполнение хэш-таблицы нулевыми значениями
int *HashTable;
HashTable = new int [256];
for (int i=0; i<=255; i++)
HashTable=0;

HashTreeBuild(IDTable,HashTable,N);

//Вывод на экран таблицы идентификаторов
for (int i=1;i<=N;i++)
mmDebug->Lines->Add(IntToStr(i)+" "+
IDTable.Name+" "+
IntToStr(IDTable.Hash())+" "+
IntToStr(IDTable.Left)+" "+
IntToStr(IDTable.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));
}
}