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

Листинг П3.1. Описание структуры данных для элементов таблицы идентификаторов

unit TblElem;

interface

{ Модуль, описывающий структуру данных элементов

таблицы идентификаторов }

type

TAddVarInfo = class(TObject) { Класс для описания базового

типа данных, связанных с элементом таблицы идентификаторов}

public

procedure SetInfo(iIdx: integer; iInfo: longint);

virtual; abstract;

function GetInfo(iIdx: integer): longint;

virtual; abstract;

property Info[iIdx: integer]: longint

read GetInfo write SetInfo; default;

end;

TVarInfo = class(TObject)

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

sName: string; { Имя элемента }

pInfo: TAddVarInfo; { Дополнительная информация }

minEl,maxEl: TVarInfo; { Ссылки на меньший и больший

элементы для организации бинарного дерева }

public

{ Конструктор создания элемента хэш-таблицы }

constructor Create(const sN: string);

{ Деструктор для освобождения памяти, занятой элементом }

destructor Destroy; override;

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

procedure SetInfo(pI: TAddVarInfo);

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

procedure ClearInfo;

procedure ClearAllInfo;

{ Свойства «Имя элемента» и «Дополнительная информация» }

property VarName: string read sName;

property Info: TAddVarInfo read pInfo write SetInfo;

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

function AddElCnt(const sAdd: string;

var iCnt: integer): TVarInfo;

function AddElem(const sAdd: string): TVarInfo;

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

function FindElCnt(const sN: string;

var iCnt: integer): TVarInfo;

function FindElem(const sN: string): TVarInfo;

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

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

end;

function Upper(const x: string): string;

implementation

uses SysUtils;

{ Условная компиляция: если определено имя REGNAME,

то имена переменных считаются регистронезависимыми,

иначе – регистрозависимыми }

{$IFDEF REGNAME}

function Upper(const x: string): string;

begin Result:= UpperCase(x); end;

{$ELSE}

function Upper(const x: string): string;

begin Result:= x; end;

{$ENDIF}

constructor TVarInfo.Create(const sN: string);

{ Конструктор создания элемента хэш-таблицы }

begin

inherited Create; {Вызываем конструктор базового класса}

{ Запоминаем имя элемента и обнуляем все ссылки }

sName:= sN; pInfo:= nil;

minEl:= nil; maxEl:= nil;

end;

destructor TVarInfo.Destroy;

{ Деструктор для освобождения памяти, занятой элементом }

begin

{Освобождаем память по каждой ссылке, при этом в дереве

рекурсивно будет освобождена память для всех элементов}

ClearAllInfo;

minEl.Free; maxEl.Free;

inherited Destroy; {Вызываем деструктор базового класса}

end;

function TVarInfo.GetElList(const sLim{разделитель списка},

sInp,sOut{имена, не включаемые в строку}: string): string;

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

var sAdd: string;

begin

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

{ Если элемент таблицы не совпадает с одним

из невключаемых имен, то его нужно включить в строку }

if (Upper(sName) <> Upper(sInp))

and (Upper(sName) <> Upper(sOut)) then Result:= sName;

if minEl <> nil then { Если есть левая ветвь дерева }

begin { Вычисляем строку для этой ветви }

sAdd:= minEl.GetElList(sLim,sInp,sOut);

if sAdd <> then { Если она не пустая, }

begin { добавляем ее через разделитель }

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

else Result:= sAdd;

end;

end;

if maxEl <> nil then { Если есть правая ветвь дерева }

begin { Вычисляем строку для этой ветви }

sAdd:= maxEl.GetElList(sLim,sInp,sOut);

if sAdd <> then { Если она не пустая, }

begin { добавляем ее через разделитель }

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

else Result:= sAdd;

end;

end;

end;

procedure TVarInfo.SetInfo(pI: TAddVarInfo);

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

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.

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