Главная Промышленная автоматика.

конодатели, не принимавшие участие в голосовании, остаются в тех списках, в которых они были ранее.

Для управления описываемой базы данных при вводе имен законодателей будем применять односимвольные команды, за символом команды будет следовать 10 символов с именем законодателя. Каждая команда располагается в отдельной строке. Используем следующие односимвольные команды.

1. F (законодатель голосовал "правильно").

2. и (законодатель голосовал "неправильно").

3. ? (надо определить статус законодателя).

Мы также будем использовать символ Е для обозначения окончания процесса ввода списка законодателей. В листинге 4.5 показан эскиз программы tuna (тунец), написанный в терминах пока не определенного АТД DICTIONARY (Словарь), который в данном случае можно представить как множество символьных строк длиной 10. □

Листинг 4.8. Профамма управления базой данных ОЗТ

program tuna ( input, output ) ;

{ База данных законодателей (legislator) } type

nametype = array[1. .10] of char;

command: char; legislator: nametype; goodguys, badguys: DICTIONARY;

procedure favor ( friend: nametype ) ;

{ заносит имя friend (друг) в список goodguys

и вычеркивает из списка badguys } begin

INSERT (friend, goodguys); DELETE (friend, badguys) end; { favor ]

procedure unfavor ( foe: nametype ) ;

{ заносит имя foe (враг) в список badguys

и вычеркивает из списка goodguys } begin

INSERT ( foe, badguys) ; DELETE(foe, goodguys) end; { unfavor \

procedure report ( subject: nametype );

{печать имени subject с соответствующей характеристикой} begin

if MEMBER (subject, goodguys) then

writeln(subject, - это друг) else if MEMBER (subject, badguys) then

writeJn(subject, - это враг)

else

(Нет данных о , subject,)

end; { report }

begin { основная программа } MAKENULL(goodguys);



MAKENULL(badguys); read( command] ;

while command <> E do begin readln{legislator) ; if command = E then

favor (legislator) else if command = U then

un favor (legislator) else if command = ? then

report (legislator)

else

report(Неизвестная команда) read (command)

end; { tuna }

4.6. Реализации словарей

Словари можно представить посредством сортированных или несортированных связанных списков. Другая возможная реализация словарей использует двоичные векторы, предполагая, что элементы данного множества являются целыми числами 1, для некоторого или элементы множества можно сопоставить с таким

множеством целых чисел.

Третья возможная реализация словарей использует массив фиксированной длины с указателем на последнюю заполненную ячейку этого массива. Эта реализация выполнима, если мы точно знаем, что размер множества не превысит заданную длину массива. Эта реализация проще реализации посредством связанных списков, но имеет следующие недостатки: множества могут расти только до определенной фиксированной величины; медленно выполняются операции удаления элементов из множества (так как требуется перемещение оставщихся элементов массива) и невозможность эффективно организовать пространство массивов (особенно если множества имеют различные размеры).

Так как мы рассматриваем реализации именно словарей (и вследствие последнего приведенного недостатка), то не будем затрагивать возможности выполнения в реализации посредством массивов операций объединения и пересечения множеств. Вместе с тем, поскольку массивы, так же, как и списки, можно сортировать, то читатель вправе рассматривать реализацию с помощью массивов (которую мы здесь применяем только для представления словарей) в качестве приемлемой реализации множеств произвольной структуры. В листинге 4.6 приведены объявления и процедуры, являющиеся необходимым дополнением программы листинга 4.5, - вместе с этими дополнениями программа должна работать.

Листинг 4.6. Объявления типов и процедуры реализации словаря посредством массива •

const

maxsize = { некое число, максимальный размер массива }

type

DICTIONARY = record last: integer;

data: array [1. ./naxsize] of name type

end;

procedure MAKENULL ( var A: DICTIONARY ) ; begin

4.6. РЕАЛИЗАЦИИ СЛОВАРЕЙ 115



. , . А. last-- = {) end; { makenull }

function MEMBER { x: nametype; var A: DICTIONARY ) : boolean; var

i: integer;

begin

for i:= 1 to A. last do

if A.data[i] - x then retum(true); return(fale) { элемент x не найден } end; { MEMBER }

procedure INSERT { x: nametype; var A: DICTIONARY ); begin

if not member(x, A) then

if A. last < maxsize then begin A.last:= A.last + 1; A.data[A. last] := x

else error(База данных заполнена) end; { INSERT }

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

i:= integer; begin

if A. last > 0 then begin i:= 1;

while (.data[i] <> x) and (i < A.last) do i:= i + 1;

if A.datali] = x then begin

A.data[i] = A. data[A. last] ;

{ перемещение последнего элемента на место

элемента х; если i = А.last, то удаление х происходит на следующем шаге } А.last:= А.last - I

end; { DELETE }

4.7. Структуры данных, основанные на хеш-таблицах

в реализации словарей с помощью массивов выполнение операторов INSERT, DELETE и MEMBER требует в среднем 0(N) выполнений элементарных инструкций для словаря из N элементов. Подобной скоростью выполнения операторов обладает и реализация с помощью списков. При реализации словарей посредством двоичных векторов все эти три оператора выполняются за фиксированное время независимо от размера множеств, но в этом случае мы ограничены множествами целых чисел из некоторого небольшого конечного интервала.

Существует еще один полезный и широко используемый метод реализации словарей, который называется хешированием. Этот метод требует фиксированного времени (в среднем) на выполнение операторов и снимает ограничение, что множества должны быть подмножествами некоторого конечного универсального множества. В самом худшем случае этот метод для вьшолнения операторов требует времени, пропорцио-





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 [34] 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0018