Главная Промышленная автоматика. в обобщенном виде операторы, реализующие действия, описанные в примере 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. Названия операторов переводятся соответственно как "Добавить", "Вызов" (на поединок) и "Обмен". - Прим. перее.
Заголовки 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 |