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

Тема в разделе "C/C++/C#", создана пользователем GreenTerrapin, 23 дек 2010.

  1. GreenTerrapin

    GreenTerrapin Гость

    Помогите доделать,есть похожая программа нужно ее переделать под мое условие(до понедельника 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));
    }
    }
     
Загрузка...
Похожие Темы - Доделать лабу по
  1. Fatality93
    Ответов:
    0
    Просмотров:
    1.368
  2. psychologist
    Ответов:
    0
    Просмотров:
    923
  3. Hallelujah
    Ответов:
    0
    Просмотров:
    1.287

Поделиться этой страницей