(* Таблица - набор записей, каждая из которых однозначно *)
(* определяется значением ключа. *)
(* Соглашение. Будем считать, что ключ - целое число. *)
type pElem = ^Elem;
Elem = record Key : integer; ... end;
(* Операции : Поиск по ключу FindT *)
(* Включение новой записи с ключом K FormT *)
(* Удаление записи с ключом K KillT *)
(* + Инициализация таблицы *)
(* + Проверка наличия записей *)
|
(* Подходы к программной реализации таблиц *)
(* 1 Деревья поиска *)
(* 2 Масивы: 2.1 Масивы записей > array [...] of Elem; *)
(* 2.2 Масивы указателей на записи > рассмотрим *)
Const So = 1024; (* Max записей в таблице *)
Var Ko : integer; (* Количество записей в таблице *)
T : array [1..So] of pElem; (* Таблица *)
(* Ko:=0; - инициализация таблицы *)
(* So-Ko - запас для пополнения *)
(* Если 0 < Ko, то в таблице есть записи *)
(* Будем различать
(* таблицы с неупорядоченными записями: FindTno, FormTno, KillTno *)
(* и *)
(* таблицы с упорядоченными записями: FindTor, FormTor, KillTor *)
|
(* FindTno : поиск в таблице T с неупорядоченными записями *)
(* записи со значением ключа K *)
(* FindTno(K) = 0, если такой записи нет *)
(* иначе FindTno(K) = номер искомой записи в таблице *)
function FindTno(K : integer) : integer;
var I : integer;
begin for I:=1 to Ko do
if T[I]^.Key = K then begin
FindTno:=I;
Exit
end;
FindTno:=0 end;
|
(* FormTno : включить в таблицу T с неупорядоченными записями *)
(* запись с ключом K *)
(* X:=FormTno(K); *)
(* Если X = 0, то отсутствие запаса не позволяет вып.операцию *)
(* Иначе
(* Если T[X] = nil, то для новой записи выделен номер X *)
(* Если T[X]<> nil, то в таблице уже есть запись с ключом K *)
function FormTno(K : integer) : integer;
var M : integer;
begin M:=FindTno(K);
if 0 < M then FormTno:=M
else if So <= Ko then FormTno:=0
else begin
Ko:=Ko+1;
T[Ko]:=nil; FormTno:=Ko
end end;
|
(* KillTno : удалить из таблицы T с неупорядоченными записями *)
(* запись с ключом K *)
procedure KillTno(K : integer);
var N : integer;
begin N:=FindTno(K);
if 0 < N then begin
Dispose(T[N]);
T[N]:=T[Ko];
Ko:=Ko-1
end end;
|
(* В таблице T с упорядоченными записями выполняется свойство: *) (* T[I]^.Key < T[J]^.Key, если 1 <= I <= J <= Ko *) |
(* BFO : вспомогательная функция, которая *)
(* по заданной таблице T с упорядоченными записями и *)
(* по заданному ключу K *)
(* вычисляет количество+1 записей в таблице, *)
(* ключи которых меньше K. *)
(* Если N = BFO(K) и 1 < N <= Ko, *)
(* то T[N-1]^.Key < K <= T[N]^.Key *)
function BFO(K : integer) : integer;
var HH,KK,M : integer;
begin if Ko < 1 then begin BFO:= 1; Exit end;
if K <= T[1]^.Key then begin BFO:= 1; Exit end;
if T[Ko]^.Key < K then begin BFO:=Ko+1; Exit end;
HH:=1; (* начало области поиска *)
KK:=Ko; (* конец области поиска *)
(* в обл.поиска: T[HH]^.Key < K <= T[KK]^.Key *)
while 2 < KK-HH+1 do begin (* в обл. более 2-х записей *)
M:=(HH+KK) div 2; (* середина *)
if T[M]^.Key < K then HH:=M
else KK:=M
end;
BFO:=K;
end;
|
(* FindTor : поиск в таблице T с неупорядоченными записями *)
(* записи со значением ключа K *)
(* FindTor(K) = 0, если такой записи нет *)
(* иначе FindTor(K) = номер искомой записи в таблице *)
(* FindTor реализует метод дихотомического поиска *)
function FindTor(K : integer) : integer;
var N : integer;
begin FindTor:=0;
N:=BFO(K);
if N <= Ko then
if T[N]^.Key = K then FindTor:=N end;
|
(* FormTor : включить в таблицу T с упорядоченными записями *)
(* запись с ключом K *)
(* X:=FormTor(K); *)
(* Если X = 0, то отсутствие запаса не позволяет вып.операцию *)
(* Иначе
(* Если T[X] = nil, то для новой записи выделен номер X *)
(* Если T[X]<> nil, то в таблице уже есть запись с ключом K *)
function FormTor(K : integer) : integer;
var I,R : integer;
begin R:=BFO(T,K);
FormTor:=R;
if (1 <= R) and (R <= Ko) then (* K уже есть *)
if K = T[R]^.Key then Exit;
(* Включить новую запись на место R *)
if Ko < So then begin (* <=== Есть резерв *)
for I:=Ko downto R do T[I+1]:=T[I]; (* Свиг *)
T[R]:=nil;
Ko:=Ko+1
end else FormTor:=0; (* <=== Нет резерва *)
end;
|
(* KillTor : удалить из таблицы T с упорядоченными записями *)
(* запись с ключом K *)
procedure KillTor(K : integer);
var I,N : integer;
begin N:=FindTor(T,K);
if 0 < N then begin
Dispose(T[N]);
for I:=N to Ko-1 do T[I]:=T[I+1];
Ko:=Ko-1
end end;
|