ГоловнаЗворотній зв'язок
Главная->Математика і інформатика->Содержание->Листинг 4.9. Реализация словаря посредством закрытого хеширования

Алгоритмы структуры данных

Листинг 4.9. Реализация словаря посредством закрытого хеширования

const

empty = '         '; { 10 пробелов }

deleted =  '**********';  { 10 СИМВОЛОВ * }

type

DICTIONARY = array[0..B-l] of nametype;

 

procerude MAKENULL ( var A: DICTIONARY );

var

i: integer,

begin

for i:= 0 to В - 1 do

A[і]:= empty

end; { MAKENULL }

function locate ( x: nametype; A: DICTIONARY ): integer;

{ Функция просматривает А начиная от сегмента h(x) до тех

пор, пока не будет найден элемент х или не встретится

пустой сегмент или пока не будет достигнут конец таблицы

(в последних случаях принимается, что таблица не содержит

элемент х). Функция возвращает позицию, в которой

остановился поиск. }

var

initial, i: integer;

begin

initial:= h(x) ;

i:= 0;

while (i < B) and (A[(initial + i) mod В] <> x) and

(A[(initial + i) mod B] <> empty) do

i:= і + 1;

return((initial + i) mod B)

end; { locate }

 

function locate1 ( x: nametype; A: DICTIONARY ): integer;

{ To же самое, что и функция locate, но останавливается и при

достижении значения deleted }

function MEMBER ( х: nametype; var A: DICTIONARY ) : boolean

begin

if A[locate(x)] = x then

return(true)

else

return(false)

end; { MEMBER }

 

procedure INSERT ( x: nametype; var A: DICTIONARY );

var

bucket: integer;

begin  

if A[locate(x)] = x then return; { x уже есть в А }

bucket:= locate1(x);

if (A[bucket] = empty) or (A[bucket] = deleted)  then

A[bucket]:= x

else

error('Операция INSERT невозможна: таблица полна'}

end; { INSERT }

 

procedure DELETE ( x: nametype; var A: DICTIONARY );

var

bucket: integer;

begin

bucket:= locate(x);

if A[locate(x)] = x then

A[bucket]:= deleted

end; { DELETE }

 

54