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

begin pInfo:= pI; end;

procedure TVarInfo.ClearInfo;

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

begin pInfo.Free; pInfo:= nil; end;

procedure TVarInfo.ClearAllInfo;

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

begin

if minEl <> nil then minEl.ClearAllInfo;

if maxEl <> nil then maxEl.ClearAllInfo;

ClearInfo;

end;

function TVarInfo.AddElCnt(const sAdd: string;

var iCnt: integer): TVarInfo;

{ Функция добавления элемента в бинарное дерево

с учетом счетчика сравнений }

var i: integer;

begin

Inc(iCnt); { Увеличиваем счетчик сравнений }

{ Сравниваем имена элементов (одной функцией!) }

i:= StrComp(PChar(Upper(sAdd)), PChar(Upper(sName)));

if i < 0 then

{ Если новый элемент меньше, смотрим ссылку на меньший }

begin { Если ссылка не пустая, рекурсивно вызываем

функцию добавления элемента }

if minEl <> nil then

Result:= minEl.AddElCnt(sAdd,iCnt)

else

begin { Если ссылка пустая, создаем новый элемент

и запоминаем ссылку на него }

Result:= TVarInfo.Create(sAdd);

minEl:= Result;

end;

end

else

{ Если новый элемент больше, смотрим ссылку на больший }

if i > 0 then

begin { Если ссылка не пустая, рекурсивно вызываем

функцию добавления элемента }

if maxEl <> nil then

Result:= maxEl.AddElCnt(sAdd,iCnt)

else

begin { Если ссылка пустая, создаем новый элемент

и запоминаем ссылку на него }

Result:= TVarInfo.Create(sAdd);

maxEl:= Result;

end;

end { Если имена совпадают, то такой элемент уже есть

в дереве – это текущий элемент }

else Result:= Self;

end;

function TVarInfo.AddElem(const sAdd: string): TVarInfo;

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

var iCnt: integer;

begin Result:= AddElCnt(sAdd,iCnt); end;

function TVarInfo.FindElCnt(const sN: string;

var iCnt: integer): TVarInfo;

{ Функция поиска элемента в бинарном дереве

с учетом счетчика сравнений }

var i: integer;

begin

Inc(iCnt); { Увеличиваем счетчик сравнений }

{ Сравниваем имена элементов (одной функцией!) }

i:= StrComp(PChar(Upper(sN)), PChar(Upper(sName)));

if i < 0 then

{Если искомый элемент меньше, смотрим ссылку на меньший}

begin {Если ссылка не пустая, рекурсивно вызываем для нее

функцию поиска элемента, иначе – элемент не найден}

if minEl <> nil then Result:= minEl.FindElCnt(sN,iCnt)

else Result:= nil;

end

else

if i > 0 then

{Если искомый элемент больше, смотрим ссылку на больший}

begin {Если ссылка не пустая, рекурсивно вызываем для нее

функцию поиска элемента, иначе – элемент не найден}

if maxEl <> nil then Result:= maxEl.FindElCnt(sN,iCnt)

else Result:= nil;

end { Если имена совпадают, то искомый элемент найден }

else Result:= Self;

end;

function TVarInfo.FindElem(const sN: string): TVarInfo;

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

var iCnt: integer;

begin Result:= FindElCnt(sN,iCnt); end;

end.

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

Листинг П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;