yandex rtb 1
ГоловнаЗворотній зв'язок
yande share

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

4.5. Словари

Применение множеств при разработке алгоритмов не всегда требует таких мощных операторов, как операторы объединения и пересечения. Часто достаточно только хранить в множестве "текущие" объекты с периодической вставкой или удалением некоторых из них. Бремя от времени также возникает необходимость узнать, присутствует ли конкретный элемент в данном множестве. Абстрактный тип множеств с операторами INSERT, DELETE и MEMBER называется DICTIONARY (Словарь). Мы также включим оператор MAKENULL в набор операторов словаря — он потребуется при реализации АТД для инициализации структур данных. Далее в этом разделе мы приведем пример использования словарей, а в следующем разделе рассмотрим реализации, подходящие для представления словарей.

Пример 4.2. Общество защиты тунцов (ОЗТ) имеет базу данных с записями результатов самого последнего голосования законодателей по законопроектам об охране тунцов. База данных состоит из двух списков (множеств) имен законодателей, которые названы goodguys (хорошие парни) и badguys (плохие парни). ОЗТ прощает законодателям их прошлые "ошибки", но имеет тенденцию забывать своих "друзей", которые ранее голосовали "правильно". Например, после голосования по законопроекту об ограничении вылова тунца в озере Эри все законодатели, проголосовавшие за этот законопроект, заносятся в список goodguys и удаляются из списка badguys, тогда как над оппонентами этого законопроекта совершается обратная процедура. Законодатели, не принимавшие участие в голосовании, остаются в тех списках, в которых они были ранее.

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

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

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

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

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

 

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

program  tuna   (   input,   output  ) ;

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

type

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

var

command:   char;

legislator:   nametype;

goodguys,   badguys:   DICTIONARY;

procedure  favor   (   friend:   nametype   );

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

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

begin

INSERT(friend,   goodguys);

DELETE(frіend,  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

writeln(subject, ' — это враг')

else

writeln('Heт данных о ', subject,)

end; { report }

 

begin { основная программа }

MAKENULL(goodguys);

MAKENULL(badguys);

read(command) ;

while command <> 'E' do begin

readln(legislator);

if command = 'F' then

favor(legislator)

else if command = 'U' then

unfavor(legislator)

else if command = '?' then

report(legislator)

else

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

read(command)

end

end; { tuna }

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

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

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

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

 

49