Хэш поиск (стр. 2 из 3)

end;

Методы, которые не имеют программной реализации, называются абстрактными.

Класс, имеющий хотя бы один абстрактный метод, называется абстрактным. Объекты-экземпляры такого класса создавать нельзя.

3. Композиция классов.

Композиция возникает, когда один или несколько свойств класса представляют из себя объектов каких либо других классов.

Механизм композиции позволяет создавать сложные из более простых объектов. Достоинством композиции является возможность использования ранее созданного кода.

Для создания программы в котом используется композиция надо:

· При описании нового класса включить в набор его свойств хотя бы одно объектное свойство

· При написании нового объекта предварительно должны быть объявлены входящие в его подчинение объекты.

· Использование методов вложенных объектов

Пример:

private

mas:array [1..10] ofTList;

Здесь объявляется массив c объектной переменной mas линейных списков, который относится классу TList.

4. Контейнеры.

Объект, назначением которого является хранение объектов других типов и управление ими, называют контейнером. Иногда содержимое контейнеров называют последовательностями.

Контейнерные классы – распространенный прием разработки классов, использующий механизмы композиции и наполнения для подключения некоторых объектов к управляющему объекту- контейнеру.

Контейнерный класс содержит в своем определении несколько объектных полей и полей-указателей на объекты. Если контейнерный класс использует механизм композиции, то тип и количество управляемых объектов жестко определены типом и количеством объектных полей. Если он использует механизм наполнения, то подключение реализуется через указатели, следовательно, контейнер может управлять как объектами некоторого базового, так и объектами всех потомков этого класса.

Контейнерные классы реализуют некоторые типовые структуры, такие как, массив, стек или список, и типовые операции над данными, которые могут быть записаны в эти структуры или прочитаны из них.

Основная операция контейнерного класса – последовательная обработка объектов. Такая обработка обеспечивается 2 способами:

1. Базируется на создании специальной процедуры просмотра всех элементов контейнера. В эту процедуру в качестве параметра передается имя функции или процедуры, реализующей требуемой обработки элемента контейнера.

2. Реализуется через определение итератора или класса итераторов, подходящего для данного вида контейнера.

Пример контейнерного класса:

TContainer = class

private

Arrs : array [1..100] ofTFigure; // массив полиморфных указателей

// на графические фигуры;

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);

procedureFreeAll;

end;

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

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

· TItem

· TList

· TMas

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

TItem

Элемент списка

Next

Key

TList

Линейный список

Head

TMas

Контейнер

Mas:Array[0..10]ofTList

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. Описание всех классов.

unitClassHeshProg;

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;

varTemp,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;