49414 (Хэш поиск), страница 2

count : integer; // текущее число объектов в контейнере

public

constructor Create;

function GetCount : integer;

function Add (aFig : TFigure; ai : integer) : integer;

function Delete (ai : integer) : integer;

function Search (aFig : TFigure) : integer;

procedure ShowAll;

procedure MoveAll (dx, dy : integer);

procedure FreeAll;

end;

5.Описание классов

В данной объектной программе используется 3 класса:

• TItem

• TList

• TMas

Класс TItem хранит элемент вспомогательного линейного списка. Имеет в своем составе 2 закрытых свойства: Key – содержит ключ, Next – адрес на следующий элемент. Описание методов класса:

Constructor Create(aNext:TItem;aKey:string) - создание 1 элемента

function Getnext:TItem - дать адрес на след. элемент

procedure SetNext(aNext:TItem) - изменение адреса

Function GetKey:string – возврат ключа

Класс TList представляет собой набор объектов класса TItem. Имеет в своем составе 1 свойство – Head, который является заголовком линейного списка.

Описание методов класса:

constructor Create(aKey:string) - создание пустого списка с заголовком

function AddFirst(aKey:string):Boolean - добавление в начало списка. Возвращает true при успешном добавлении.

function AddLast(aKey:string):boolean - добавление в конец списка. Возвращает true при успешном добавлении.

function GetHead:TItem - дать заголовка

Класс TMas является контейнерным классом. Имеет в своем составе 1 свойство – объявление 10ти элементного массива типа TList. Иначе говоря объявляем массив списков. Описание методов класса:

Constructor Create(aKey:string) - создание масива указателей на списков

function HeshFunction(aKey:string):integer;virtual - HESH-функция с возможностью переопределения. Возвращает ячейку массива.

function Add(aKey:string;found:byte):byte – Функция добавления. Типы добавления: Found:0- в начало списка,1-в конец списка. Возвращает: 0 - без конфликтное добавление, иначе ячейку j

function Search(aKey:string;var aCount:integer):string – Функция поиска заданного элемента Hesh-таблицы. aCount – количество сравнений. Возвращает: ‘0’ – элемент найден, иначе сам ключ.

procedure DeleteAll - удаление всей структуры

Procedure SaveHesh(FileName:String) - сохранение контейнера в текстовом файле с именем файла

Procedure LoadHesh(FileName:String)- загрузка контейнера из текстового файла

Procedure Extract(var aIndex:integer;var aCur:TItem) – Процедура извлечения матрицы элементов для использования в Demo Unit. Используется для вывода структуры на экран. Вывод :aIndex - текущий индекс массива, aCur - текущий элемент линейного списка

UML – диаграмма взаимодействия классов:

4. Описание пользовательского интерфейса.

В данной программе используются следующие компоненты Label, Edit, StringGrid, Menu, BitBtn, RadioGroup, StatusBar.

Текстовой компоненты Label, Edit, StringGrid:

Метки(Label) предназначены для размещения на экране текстовой информации, содержащей различные пояснения, названия, заголовки и т.д.

Строка ввода Edit позволяет вводить и редактировать одну строку текста.

Таблица StringGrid представляет собой сетку в которой содержаться строки и столбцы.

RadioGroup – это набор зависимых между собой переключателей.

Кнопка Button: основное назначение кнопки – формирование события при нажатии на неё. Кнопка может быть размещена в любом месте формы, где есть необходимость выполнить какие-либо действия при её нажатии.

Кнопка BitBtn: на этой кнопке в отличие от Button можно размещать значки.

Добавление ключа: вводим в редактор Edit ключ, нажимаем кнопку «Добавить», в зависимости от значения ключа получаем результат в виде сообщения MessageDlg:

Поиск: задаем искомый ключ в редактор ввода Edit, нажимаем кнопку«Найти», выдается сообщение об успешности поиска, если элемент найден, то в панели задач указывается количество сравнений .

1. Листинг и описание всех классов библиотеки на DP.

6.1. Описание всех классов.

unit ClassHeshProg;

interface

type

TItem=class{класс-элемент списка}

private

key: string;

next: TItem;

public

Constructor Create(aNext:TItem;aKey:string);//создание 1 элемента

function Getnext:TItem;//дать адрес на след. элемент

procedure SetNext(aNext:TItem);//изм. адрес

Function GetKey:string;//дать ключ

end;

{***********************************}

TList=class {класс списка}

private

Head:TItem;//заголовок списка

public

constructor Create(aKey:string);//создание списка

function AddFirst(aKey:string):boolean;//добавление перед заголовком

function AddLast(aKey:string):boolean;//добавление после заголовка

function GetHead:TItem;// дать заголовка

end;

{***********************************}

TMas=class {класс-контейнер массива списков}

private

mas:array [1..10]of TList;

public

Constructor Create(aKey:string);//создание масива указателей списков

function HeshFunction(aKey:string):integer;virtual;//HESH-функция с возможностью переопределения

function Add(aKey:string;found:byte):byte;//Found:0-до,1-перед, Возвращает:0-без конфликта,j-ячейка

function Search(aKey:string;var aCount:integer):string;//поиск элемента Hesh-таблицы

procedure DeleteAll;//удаление всей таблицы

Procedure SaveHesh(FileName:String);//сохранение контейнера в файле

Procedure LoadHesh(FileName:String);//загрузка контейнера из файла

Procedure Extract(var aIndex:integer;var aCur:TItem);//Вывод:aIndex-текуший индекс массива,aCur-текущий эл-т списка

end;

{***********************************}

var Hesh:TMas;

implementation

uses Main,SysUtils,Dialogs;

constructor TItem.Create(aNext:TItem;aKey:string);

begin

next:=aNext;

Key:=aKey;

end;

function TItem.Getnext:TItem;

begin

Result:=next;

end;

procedure TItem.SetNext(aNext:TItem);

begin

next:=aNext;

end;

Function TItem.GetKey:string;

begin

Result:=Key;

end;

{*************************************}

constructor TList.Create(aKey:String);

begin

Head:=TItem.Create(nil,aKey);

end;

function TList.AddFirst(aKey:string):boolean;

var Temp,Current,Previos:TItem;

begin

previos:=Head;

current:=Head.Getnext;

Temp:=TItem.Create(current,aKey);

Temp.next:=current;

previos.next:=Temp;

result:=true;

end;

function TList.AddLast(aKey:string):boolean;

var Temp,Current:TItem;

begin

// Внесение нового элемента в список

Current:=Head.Getnext;

Temp:=TItem.Create(Head.next,aKey);

Head.next:=Temp;

result:=true;

end;

function TList.GetHead:TItem;

begin

Result:=Head;

end;

{*************************************}

constructor TMas.Create(aKey:string);

var i:integer;

begin

for i:=1 to 10 do mas[i]:=TList.Create(aKey);

end;

function TMas.HeshFunction(aKey:string):integer; //Hesh-функция

var x,i,j:integer;

begin

x:= 0;

for i:=1 to length(aKey) do x:=ord(aKey[i])+x; // Определение значения строки

j:=(x mod 10)+1; //Определение элемента

result:=j;

end;

function TMas.Add(aKey:string;found:byte):byte;

var j:integer;

begin

j:=HeshFunction(aKey);

if Found=0 then

begin

if mas[j].Head.next<>nil then result:=j else result:=0;

mas[j].AddFirst(aKey);

end else

if found=1 then

begin

if mas[j].Head.next<>nil then result:=j else result:=0;

mas[j].AddLast(aKey);

end;

end;

function Tmas.Search(aKey:string;var aCount:integer):string;

var j:integer; Cur:TItem;

begin

//Поиск в списке

j:=HeshFunction(aKey);

aCount:=1;

Cur:= mas[j].GetHead.Getnext;

while (Cur<>nil) and (Cur.key<>aKey) do

begin

inc(aCount);

Cur:= Cur.next;

end;

if Cur=nil then

begin

result:='0';

Exit;

end else

begin

result:=Cur.key;

exit;

end;

end;

procedure TMas.DeleteAll;//удаление контейнера

var i:integer; Cur:TItem;

begin

for i:=1 to 10 do

begin

cur:=mas[i].Head.Getnext;

While Cur<>nil do

begin

mas[i].Head.next:=Cur.next;

Cur.Destroy;

cur:=mas[i].Head.next;

end;

end;

Hesh.Destroy;

Hesh:=nil;

end;

Procedure TMas.Extract(var aIndex:integer;var aCur:TItem);//Вывод:aIndex-текуший индекс массива,aCur-текущий эл-т списка

begin

aCur:=mas[aIndex].Head.next;

end;

Procedure Tmas.SaveHesh(FileName:String);//сохранение контейнера в файле

var Current:TItem;tf:TextFile;i:integer;

begin

AssignFile(tf,FileName);

rewrite(tf);

for i:=1 to 10 do

begin

Current:=mas[i].Head.Getnext;

while Current<>Nil do

begin

Write(tf,Current.key+' ');

Current:=Current.next;

end;

Writeln(tf);

end;

CloseFile(tf);

end;

Procedure TMas.LoadHesh(FileName:String);//Загрузка контейнера из файла

var tf:TextFile;s,si,Key:string;b,bf:Boolean;i:integer;

begin

b:=False;

AssignFile(tf,FileName);

Reset(tf);

while Not Eof(tf) do

begin

Readln(tf,s);

bf:=False;

si:='';

for i:=1 to Length(s) do

if s[i]<>' ' then si:=si+s[i] else

if b=False then

begin

b:=True;

Key:=si;

Hesh:=TMas.Create(Key);

bf:=true;

si:='';

end else

begin

if bf=False then

begin

bf:=True;

Key:=si;

end else

begin

Hesh.Add(SI,0);

end;

si:='';

end; {end For}

end;{end While}

CloseFile(tf);

end;

end.

1. Описание Demo-программы.

unit Main;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, Grids, StdCtrls, Buttons, ExtCtrls, Menus, ComCtrls;

type

TForm1 = class(TForm)

Panel1: TPanel;

OperationGroup: TRadioGroup;

Edit1: TEdit;

Inicial: TBitBtn;

CloseButton: TBitBtn;

StringGrid1: TStringGrid;

MainMenu1: TMainMenu;

SaveDialog1: TSaveDialog;

OpenDialog1: TOpenDialog;

AddGroup: TRadioGroup;

N5: TMenuItem;

Save: TMenuItem;

Load: TMenuItem;

CloseMenu: TMenuItem;

StatusBar1: TStatusBar;

New: TMenuItem;