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

в обобщенном виде операторы, реализующие действия, описанные в примере 4.11, можно записать следующим образом:

for для каждой записи регистрации из множества Sc курса CS101 do begin

s: = студент-собственник регистрационной записи; print (s)

Здесь оператор присваивания можно детализировать так:

f: = е; repeat

f:= ft. cnext until

/ - указатель на запись студента; 3:= значению поля studentname в записи, на которую указывает /;

где е - указатель на первую регистрационную запись в множестве курса CS101.

Для реализации структуры, подобной показанной на рис. 4.9, на языке Pascal необходим только тип record (запись) в различных вариантах для записей, относящихся к именам студентов, названиям курсов и регистрации. Но возникают трудности, связанные с тем, что указатели полей cnext и snext могут указывать записи разных типов. Эти трудности можно обойти, если определять тип записи циклически. В листинге 4.14 показаны такие объявления типов, а также процедураprirafsaderats вывода на печать имен студентов, посещающих определенный учебный курс.

Листинг 4.14. Реализация поиска в мультисписке type

stype = array[1..20] of char; ctype = array[1..5] of char;

recordkinds = (student, course, enrollment) ; recordtype = record

case kind : recordkinds of

student: (.studentname: stype;

firstcourse: trecordtype); course:(coursename: ctype;

firststudent: trecordtype); enrollment: (cnext, snext: trecordtype)

end;

procedure printstudents ( cname: ctype ) ; var

c, e, f: trecordtype; begin

c:= указатель на запись курса, где ct.coursename = cname; { последний оператор зависит от того,

как реализовано множество записей курсов } е:= ct.f irststudent; { е пробегает по колысу указателей

регистрационных записей } while et.kind = enrollment do begin

f:= e;

repeat

f:= ft.cnext

until



ft. kind = student;

{ сейчас / - указатель на студента-собственника регистрации et } wiitelnt,f\.studentname) ; e:= ё\. snext

end; { printstudents }

Эффективность двойных структур данных

Часто кажущаяся простота представления множеств или отображений на самом деле оборачивается трудной проблемой выбора подходяшей структуры данных. Какая-либо структура данных, представляющая множество, позволяет легко выполнять определенные операторы, но на выполнение других приходится затрачивать значительное время. По-видимому, не сушествует одной структуры данных, позволяюшей всем операторам выполняться быстро и просто. В этом случае решением может стать использование двух или больше структур данных для представления одного и того же множества или отображения.

Предположим, что мы хотим создать "теннисную лестницу" (т.е. квалификационную таблицу), где каждый игрок располагается на своей "ступеньке" (рейтинге). Новые игроки добавляются в самый низ, т.е. на ступеньку с самым большим номером. Игрок может вызвать на поединок игрока, стояшего на более высокой ступени, и если он выиграет матч, то они меняются ступенями. Эту "лестницу" можно рассматривать как абстрактный тип данных, где базовой моделью будет отображение из множества имен игроков (строки символов) в множество номеров ступеней (целые числа 1, 2, ...). Необходимы также три оператора, выполняемые над этим АТД.

1. АВВ(ил«я) добавляет новое имя в квалификационную лестницу на свободную ступеньку с наибольшим номером, т.е. в самый низ лестницы.

2. CHALLENGE(ujta) возврашает имя игрока, стояшего на ступени / - 1, если игрок имя стоит на ступени /, / > 1.

3. EXCHANGE(i) меняет местами игроков, стояших на ступенях i и i - 1, i> 1. Для реализации описанных данных и их операторов можно использовать массив

LADDER (Лестница), где LADDEBIii\ имя игрока, стояшего на ступени i. Вместе с именем игрока можно хранить и его номер (т.е. номер ступени, на которой он стоит). В этом случае нового игрока можно просто добавить за малое фиксированное время в свободную ячейку массива.

Оператор EXCHANGE реализуется легко - меняются местами два элемента массива. Но выполнение функции CHALLENGE в процессе поиска заданного имени требует времени порядка 0(га) для просмотра всего массива (здесь и далее и - обшее число игроков).

С другой стороны, мы можем применить хеш-таблицу для задания отображения из множества имен в множество номеров ступеней. Количество сегментов в хеш-таблице примерно равно количеству игроков. Оператор ADD выполняется в среднем за время 0(1). Функция CHALLENGE тратит в среднем 0(1) времени на поиск заданного имени, но требует 0(п) времени для поиска имени соперника, стояшего на более высокой ступени, поскольку в этом случае надо просмотреть всю хеш-таблицу. Оператор EXCHANGE требует 0(га) времени для поиска имен игроков, стояших на ступенях / и / - 1.

Теперь рассмотрим применение комбинации двух структур. Пусть ячейки хеш-таблицы содержат имя игрока и его номер ступени, а в массиве LADDER элемент ЬАВВЕИЩ будет указателем на ячейку игрока в хеш-таблице, стояшего на j-й ступени, как показано на рис. 4,10.

Названия операторов переводятся соответственно как "Добавить", "Вызов" (на поединок) и "Обмен". - Прим. перее.



Borg

Connors

• Hopcroft

Lloyd

Hartmanis


Заголовки nextrung

сегментов

Рис. 4.10. Комбинированная структура высокой производительности

LADDER

При такой организации данных добавление нового игрока требует в среднем 0(1) времени для записи его атрибутов в хеш-таблицу, а также создания указателя на его ячейку в хеш-таблице из ячейки массива LADDER, которая помечена курсором nextrung (следуюшая ступень) (см. рис. 4.10). При выполнении функции CHALLENGE надо сначала найти заданное имя в хеш-таблице (на это требуется в среднем 0(1) времени), получить его номер ступени i и далее, следуя за указателем из ячейки LADDEFt[i- 1] в ячейку хеш-таблицы, получить имя игрока-соперника. Все последние описанные действия в среднем требуют не более 0(1) времени, поэтому все время выполнения функции CHALLENGE имеет в среднем порядок 0(1).

Оператор EXCHANGE(i) требует времени порядка 0(1) для нахождения имен игроков с рангами i и i - 1, для обмена содержимым двух ячеек хеш-таблицы и обмена указателями в двух ячейках массива LADDER. Таким образом, даже в самом худшем случае время выполнения оператора EXCHANGE не будет превышать некоторой фиксированной величины.

Упражнения

4.1. Пусть заданы два множества у1 - {1, 2, 3} и В - {3, 4, 5}. Каков будет результат выполнения следующих операторов?

а) UNION(A, В, С);

б) lNTERSECTION(A. Б, С);

в) DIFFERENCE(A, В. С);

г) MEMBER(1, А);

д) INSERT(1, А);

е) DELETE(1, А);

ж) MIN(A).

*4.2. Напишите процедуру в терминах базовых операторов множеств для печати всех элементов произвольного конечного множества. Предполагается, что элементы множества имеют тип, допустимый для печати. Процедура печати не должна разрушать исходное множество. Какова в данном случае наиболее подходящая структура данных для реализации множества?





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