Книга: Системное программное обеспечение. Лабораторный практикум

Листинг П3.2. Модуль таблицы идентификаторов на основе хэш-адресации в комбинации с бинарным деревом

unit FncTree;

interface

{ Модуль, обеспечивающий работу с комбинированной таблицей

идентификаторов, построенной на основе хэш-функции и

бинарного дерева }

uses TblElem;

{ Функция начальной инициализации хэш-таблицы }

procedure InitTreeVar;

{ Функция освобождения памяти хэш-таблицы }

procedure ClearTreeVar;

{ Функция удаления дополнительной информации в таблице }

procedure ClearTreeInfo;

{ Добавление элемента в таблицу идентификаторов }

function AddTreeVar(const sName: string): TVarInfo;

{ Поиск элемента в таблице идентификаторов }

function GetTreeVar(const sName: string): TVarInfo;

{ Функция, возвращающая количество операций сравнения }

function GetTreeCount: integer;

{ Функция записи всех имен идентификаторов в одну строку }

function IdentList(const sLim,sInp,sOut: string): string;

implementation

const { Минимальный и максимальный элементы хэш-таблицы }

HASH_MIN = Ord(0 )+Ord(0 ); {(охватывают весь диапазон}

HASH_MAX = Ord('z')+Ord('z'); { значений хэш-функции)}

var { Массив для хэш-таблицы }

HashArray: array[HASH_MIN..HASH_MAX] of TVarInfo;

iCmpCount: integer; { Счетчик количества сравнений }

function GetTreeCount: integer;

begin Result:= iCmpCount; end;

function IdentList(const sLim,sInp,sOut: string): string;

{ Функция записи всех имен идентификаторов в одну строку }

var

i: integer; { счетчик идентификаторов }

sAdd: string; { строка для временного хранения данных }

begin

Result:= ; { Первоначально строка пуста }

for i:=HASH_MIN to HASH_MAX do

begin { Цикл по всем идентификаторам в таблице }

{ Если ячейка таблицы пустая, то добавлять не нужно, }

if HashArray[i] = nil then sAdd:=

{ иначе вычисляем добавочную часть строки }

else sAdd:= HashArray[i].GetElList(sLim,sInp,sOut);

if sAdd <> then

begin { Если добавочная часть строки не пуста,

то добавляем ее в общую строку через разделитель }

if Result <> then Result:= Result + sLim + sAdd

else Result:= sAdd;

end;

end{for};

end;

function VarHash(const sName: string): longint;

{ Хэш-функция – сумма кодов первого и среднего символов }

begin

Result:= (Ord(sName[1])

+ Ord(sName[(Length(sName)+1) div 2])

– HASH_MIN) mod (HASH_MAX-HASH_MIN+1)+HASH_MIN;

if Result < HASH_MIN then Result:= HASH_MIN;

end;

procedure InitTreeVar;

{Начальная инициализация хэш-таблицы – все элементы пусты}

var i: integer;

begin for i:=HASH_MIN to HASH_MAX do HashArray[i]:= nil;

end;

procedure ClearTreeVar;

{ Освобождение памяти для всех элементов хэш-таблицы }

var i: integer;

begin

for i:=HASH_MIN to HASH_MAX do

begin

HashArray[i].Free; HashArray[i]:= nil;

end;

end;

procedure ClearTreeInfo;

{ Удаление дополнительной информации для всех элементов }

var i: integer;

begin

for i:=HASH_MIN to HASH_MAX do

if HashArray[i] <> nil then HashArray[i].ClearAllInfo;

end;

function AddTreeVar(const sName: string): TVarInfo;

{ Добавление элемента в хэш-таблицу и дерево }

var iHash: integer;

begin

iCmpCount:= 0; { Обнуляем счетчик количества сравнений }

iHash:= VarHash(Upper(sName)); { Вычисляем хэш-адрес }

if HashArray[iHash] <> nil then

Result:= HashArray[iHash].AddElCnt(sName,iCmpCount)

else

begin

Result:= TVarInfo.Create(sName);

HashArray[iHash]:= Result;

end;

end;

function GetTreeVar(const sName: string): TVarInfo;

{ Поиск элемента в таблице идентификаторов }

var iHash: integer;

begin

iCmpCount:= 0; { Обнуляем счетчик сравнений }

iHash:= VarHash(Upper(sName)); { Вычисляем хэш-адрес }

if HashArray[iHash] = nil then Result:= nil

{ Если ячейка по адресу пуста – элемент не найден, }

else { иначе вызываем функцию поиска по дереву }

Result:= HashArray[iHash].FindElCnt(sName,iCmpCount)

end;

initialization

{Вызов начальной инициализации таблицы при загрузке модуля}

InitTreeVar;

finalization

{ Вызов освобождения памяти таблицы при выгрузке модуля }

ClearTreeVar;

end.

Оглавление книги