Банк Рефератов - Хэш поиск - скачать рефераты, бесплатно рефераты

Главная: Рефераты

Рефераты. Хэш поиск

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;

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;

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;

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.

Описание 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;

SavaBtn: TBitBtn;

LoadBtn: TBitBtn;

procedure FormActivate(Sender: TObject);

procedure CloseButtonClick(Sender: TObject);

procedure InicialClick(Sender: TObject);

procedure FormCreate(Sender: TObject);

procedure SaveClick(Sender: TObject);

procedure LoadClick(Sender: TObject);

procedure CloseMenuClick(Sender: TObject);

procedure NewClick(Sender: TObject);

procedure OperationGroupClick(Sender: TObject);

procedure SavaBtnClick(Sender: TObject);

procedure LoadBtnClick(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

Implementation

uses ClassHeshProg;

{$R *.dfm}

procedure Output;

var i,j:integer;Cur:TItem;

begin

for i:=1 to 10 do

begin

j:=1;

Hesh.Extract(i,Cur);

While Cur<>nil do

begin

form1.StringGrid1.Cells[i-1, j]:=Cur.GetKey;

Cur:=Cur.Getnext;

inc(j);

end;

procedure TForm1.FormActivate(Sender: TObject);

var i:integer;

begin

for i:=1 to form1.StringGrid1.ColCount do

begin

form1.StringGrid1.Cols[i-1].Add(inttostr(i));

end;

form1.StatusBar1.Panels.Add.Text:='Объектная реализация HESH-поиска.';

form1.OperationGroup.ItemIndex:=0;

form1.AddGroup.ItemIndex:=1;

end;

procedure TForm1.CloseButtonClick(Sender: TObject);

begin

if MessageDlg('Сохранить изменения?',mtConfirmation,[mbYes, mbNo],0)=mrYes then

begin

SaveClick(Sender);

NewClick(Sender);

Close; end else

begin

Hesh.DeleteAll;

Close;

end;

procedure TForm1.InicialClick(Sender: TObject);

var i,j,count:integer;

begin

if Hesh=nil then

begin

MessageDlg('HESH-таблица не создана. Создаю таблицу.',MtError,[mbok],1);

Hesh:=TMas.Create(''); end else

case OperationGroup.ItemIndex of

0:begin {Add}

If Edit1.Text= '' then MessageDlg('Введите значение!',MtError,[mbOK],1) else

if AddGroup.ItemIndex=0 then

begin {AddFirst}

j:=Hesh.Add(Edit1.Text,0);

if j<>0 then MessageDlg('Конфликт в ячейке '+inttostr(j),MtInformation,[mbok],1);

MessageDlg('Ключ с значением '+Edit1.Text+' добавлен.',MtInformation,[mbok],1);

end else

begin {AddLast}

j:=Hesh.Add(Edit1.Text,1);

if j<>0 then MessageDlg('Конфликт в ячейке '+inttostr(j),MtInformation,[mbok],1);

MessageDlg('Ключ с значением '+Edit1.Text+' добавлен.',MtInformation,[mbok],1);

end;

Output;

end;

1:begin {Search}

If Edit1.Text= '' then MessageDlg('Введите значение!',MtError,[mbOK],1) else

if Hesh.Search(Edit1.Text,Count)='0' then

MessageDlg('Элемент не найден!',MtError,[mbok],1) else

begin

MessageDlg('Элемент найден со значением '+Edit1.Text,MtInformation,[mbok],1);

StatusBar1.Panels.Clear;

StatusBar1.Panels.Add.Text:='Количество сравнений : '+inttostr(Count);

end;

2: begin {Clear}

NewClick(Sender);

end;

end;{end case}

Edit1.SetFocus;

end;

procedure TForm1.FormCreate(Sender: TObject);

begin

Hesh:=TMas.Create('');

end;

procedure TForm1.SaveClick(Sender: TObject);

begin

if SaveDialog1.Execute then

if Hesh<>Nil then begin

Hesh.SaveHesh(SaveDialog1.FileName);

NewClick(Sender); end else

MessageDlg('HESH-таблица не создана.',MtError,[mbok],1);

end;

procedure TForm1.LoadClick(Sender: TObject);

begin

NewClick(Sender);

if OpenDialog1.Execute then

begin

Hesh.LoadHesh(OpenDialog1.FileName);

Output;

end;

procedure TForm1.CloseMenuClick(Sender: TObject);

begin

CloseButtonClick(Sender);

end;

procedure TForm1.NewClick(Sender: TObject);

var i,j:integer;

begin

if Hesh<>nil then

begin

Hesh.DeleteAll;

for i:=0 to 10 do for j:=1 to 10 do

begin

stringgrid1.Cells[i,j]:='';

end;

procedure TForm1.OperationGroupClick(Sender: TObject);

begin

case OperationGroup.ItemIndex of

0:begin

Inicial.Caption:='Добавить';

Edit1.Text:='';

end;

1:begin

Inicial.Caption:='Найти';

Edit1.Text:='';

end;

2:begin

Inicial.Caption:='Очистить';

Edit1.Text:='';

end;

procedure TForm1.SavaBtnClick(Sender: TObject);

begin

SaveClick(Sender);

end;

procedure TForm1.LoadBtnClick(Sender: TObject);

begin

LoadClick(Sender);

end;

end.

7. Список использованной литературы.

1. Иванов А.Г., Карпова А.В., Семик В.П., Филинов Ю.Е. Объектно-ориентированная среда программирования. Системы и средства информатики. Вып.2. М.: Наука, 1991.

2. Иванова Г.С., Ничушкина Т.Н., Пугачев Е. «Объектно-ориентированное программирование: Учебник для вузов Изд. 2-е», М: МГТУ им. Н.Э.Баумана

3. Фаронов В.В. Delphi 2005. Язык, среда, разработка приложений. – СПб.: Питер, 2005 г.

4. Вирт Н. Алгоритмы и структуры данных. – Изд. Невский Диалект, 2001 г.

5. Козин А. Н. «Структуры и алгоритмы обработки данных» ТИСБИ, 2003

Страницы: 1, 2, 3