Структуры данных и алгоритмы (1021739), страница 28
Текст из файла (страница 28)
Элементы заносятся в список Сдо тех пор, пока не исчерпается список А (логическое условие в строке 5).Оператор ASSIGN (А, В) копирует список А в список В. Отметим, что этот оператор нельзя реализовать простым переопределением заголовка списка В на заголовоксписка А, поскольку при последующих изменениях в списке В надо будет делатьаналогичные изменения в списке А, что, естественно, может привести к нежелательным коллизиям.
Оператор MIN реализуется легко — просто возвращается первыйэлемент списка. Операторы DELETE и FIND можно реализовать, применив общиеметоды поиска заданного элемента в списках, в случае оператора DELETE найденныйэлемент (точнее, ячейка, в которой он находится) удаляется.Реализовать оператор вставки нового элемента в список также несложно, но ондолжен стоять не в произвольной позиции в списке, а в "правильной" позиции, учитывающей взаимный порядок элементов. В листинге 4.4 представлен код процедурыINSERT (Вставка), которая в качестве параметров имеет вставляемый элемент и указатель на ячейку заголовка списка, куда вставляется элемент. На рис.
4.2 показаныключевые ячейки и указатели до и после вставки элемента (старые указатели обозначены сплошными линиями, а новые — пунктирными).Листинг 4.4. Процедура вставки элементаprocedure INSERT ( x: elementtype; p: tcelltype ) ;varcurrent, newcell: Tcelltype;begincurrent:= p;while current?.next <> nil do beginif currentt.ne.xtT. element = x thenreturn; { элемент х уже есть в списке }if current?.лextt. element > x then112ГЛАВА 4.
ОСНОВНЫЕ ОПЕРАТОРЫ МНОЖЕСТВgoto add; { далее останов процедуры }current:= current!.nextend;add: {здесь current — ячейка, после которой надо вставить х}new(newcell);newcellT'. element:= х;newcellT.next:= currentt.next;currentt.next:= newcellend; { INSERT }iicurrentnewcellX—Рис. 4.2. Схема вставки нового элемента4.5. СловариПрименение множеств при разработке алгоритмов не всегда требует таких мощных операторов, как операторы объединения и пересечения. Часто достаточно толькохранить в множестве "текущие" объекты с периодической вставкой или удалениемнекоторых из них.
Время от времени также возникает необходимость узнать, присутствует ли конкретный элемент в данном множестве. Абстрактный тип множеств соператорами INSERT, DELETE и MEMBER называется DICTIONARY (Словарь). Мытакже включим оператор MAKENULL в набор операторов словаря — он потребуетсяпри реализации АТД для инициализации структур данных.
Далее в этом разделе мыприведем пример использования словарей, а в следующем разделе рассмотрим реализации, подходящие для представления словарей.Пример 4.2. Общество защиты тунцов (ОЗТ) имеет базу данных с записями результатов самого последнего голосования законодателей по законопроектам об охранетунцов. База данных состоит из двух списков (множеств) имен законодателей, которые названы goodguys (хорошие парни) и badguys (плохие парни). ОЗТ прощает законодателям их прошлые "ошибки", но имеет тенденцию забывать своих "друзей",которые ранее голосовали "правильно". Например, после голосования по законопроекту об ограничении вылова тунца в озере Эри все законодатели, проголосовавшие заэтот законопроект, заносятся в список goodguys и удаляются из списка badguys, тогда как над оппонентами этого законопроекта совершается обратная процедура.
За4.5. СЛОВАРИ113конодатели, не принимавшие участие в голосовании, остаются в тех списках, в которых они были ранее.Для управления описываемой базы данных при вводе имен законодателей будемприменять односимвольные команды, за символом команды будет следовать 10 символов с именем законодателя. Каждая команда располагается в отдельной строке.Используем следующие односимвольные команды.1.2.3.F (законодатель голосовал "правильно").U (законодатель голосовал "неправильно").? (надо определить статус законодателя).Мы также будем использовать символ 'Е' для обозначения окончания процесса ввода списка законодателей.
В листинге 4.5 показан эскиз программы tuna (тунец), написанный в терминах пока не определенного АТД DICTIONARY (Словарь), который вданном случае можно представить как множество символьных строк длиной 10. ПЛистинг 4.8. Программа управления базой данных ОЗТprogram tuna ( input, output ) ;{ База данных законодателей (legislator) }typenametype = array[1..10] of char;varcommand: char;legislator: nametype;goodguys, badguys: DICTIONARY;procedure favor ( friend: nametype ) ;{ заносит имя friend (друг) в список goodguysи вычеркивает из списка badguys }beginINSERT(friend, goodguys);DELETE(friend, badguys)end; { favor }procedure unfavor ( foe: nametype ) ;•{ заносит имя foe (враг) в список badguysи вычеркивает из списка goodguys }beginINSERT(foe, badguys) ;DELETE(foe, goodguys)end; { unfavor }procedure report ( subject: nametype ) ;{печать имени subject с соответствующей характеристикой)beginif MEMBER(subject, goodguys) thenwrite In(subject, ' — это друг')else if MEMBER(subject, badguys) thenwriteln(subject, ' — это в р а г 1 )elsewriteln ('Нет данных о ' , subj'ect,)end; { report }begin { основная программа }MAKENULL(goodguys) ;114ГЛАВА 4.
ОСНОВНЫЕ ОПЕРАТОРЫ МНОЖЕСТВMAKENULL(badguys) ;read(command);while command <> 'E' do beginreadln(legislator);if command = 'F' thenfavor(legislator)else if command = 'U1 thenunfavor(legislator)else if command = '?' thenreport(legislator)elsereport('Неизвестная команда')read(command)endend; { tuna }4.6. Реализации словарейСловари можно представить посредством сортированных или несортированныхсвязанных списков. Другая возможная реализация словарей использует двоичныевекторы, предполагая, что элементы данного множества являются целыми числами1, ..., N для некоторого N или элементы множества можно сопоставить с такиммножеством целых чисел.Третья возможная реализация словарей использует массив фиксированной длиныс указателем на последнюю заполненную ячейку этого массива. Эта реализация выполнима, если мы точно знаем, что размер множества не превысит заданную длинумассива.
Эта реализация проще реализации посредством связанных списков, но имеет следующие недостатки: множества могут расти только до определенной фиксированной величины; медленно выполняются операции удаления элементов из множества (так как требуется перемещение оставшихся элементов массива) и невозможностьэффективно организовать пространство массивов (особенно если множества имеютразличные размеры).Так как мы рассматриваем реализации именно словарей (и вследствие последнегоприведенного недостатка), то не будем затрагивать возможности выполнения в реализации посредством массивов операций объединения и пересечения множеств.
Вместе с тем, поскольку массивы, так же, как и списки, можно сортировать, то читательвправе рассматривать реализацию с помощью массивов (которую мы здесь применяем только для представления словарей) в качестве приемлемой реализации множествпроизвольной структуры. В листинге 4.6 приведены объявления и процедуры, являющиеся необходимым дополнением программы листинга 4.5, — вместе с этимидополнениями программа должна работать.Листинг 4.6.
Объявления типов и процедуры реализации словаря посредством•..массива.-,, ; . '-ц- йАг-'г.-' •constmaxsize = { н*екое число, максимальный размер массива }typeDICTIONARY = recordlast: integer;data: array[1..maxsize] of nametypeend;procedure MAKENULL ( var A: DICTIONARY );begin4.6. РЕАЛИЗАЦИИ СЛОВАРЕЙ115.,. A.last:= 0end; { MAKENULL }function MEMBER ( x: nametype; var A: DICTIONARY ): boolean;vari: integer,beginfor i:= 1 to A.last doif A.data[i] - x then return(true);return(fale) { элемент x не найден }end; { MEMBER }procedure INSERT ( x: nametype; var Л: DICTIONARY );beginif not MEMBER(x, A) thenif A.last < maxsize then beginA.last:= A.last + 1;A.data[A.last]:= xendelse error('База данных заполнена')end; { INSERT }procedure DELETE ( x: nametype; var A: DICTIONARY );vari:= integer;beginif Л-iast > 0 then begini:= 1;while (A.data[i] <> x) and (i < A.last) doi:= i + 1;if A.datali] = x then beginA.data[i] = A.data[A.last];{ перемещение последнего элемента на местоэлемента х; если i = A.last, то удаление хпроисходит на следующем шаге }A.last:= A.last - Iendendend; { DELETE }4.7.
Структуры данных, основанные на хеш-таблицахВ реализации словарей с помощью массивов выполнение операторов INSERT,DELETE и MEMBER требует в среднем O(N) выполнений элементарных инструкцийдля словаря из N элементов. Подобной скоростью выполнения операторов обладает иреализация с помощью списков.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
