Структуры данных и алгоритмы (1021739), страница 35
Текст из файла (страница 35)
В данном случае он приведет к пятой регистрационной записи. В этой записи указатель cnext непосредственно указывает насобственника-запись студента, которая соответствует студенту Amy. Таким образом,студент Amy также посещает курс CS101. Следуя далее за указателем snext пятойрегистрационной записи, мы перейдем к восьмой регистрационной записи. Кольцоуказателей cnext приведет от этой записи к девятой регистрационной записи, собственником которой является запись, соответствующая студентке Ann, также посещающей курс CS101.
Указатель snext восьмой регистрационной записи возвращаетнас на запись курса CS101. Это означает, что множество Sc исчерпано. ПОтметим, что, как правило, регистрационных записей значительно больше, чем записей о студентах и учебных курсах, поэтому, даже незначительно сокращая пространство,занимаемое одной регистрационной записью, мы существенно сокращаем общее требуемоепространство памяти.2Чтобы отличить указатель на регистрационную запись от указателя на запись студента,надо как-то определять тип записей.
Этот вопрос мы рассмотрим немного ниже.140ГЛАВА 4. ОСНОВНЫЕ ОПЕРАТОРЫ МНОЖЕСТВВ обобщенном виде операторы, реализующие действия, описанные в примере 4.11, можно записать следующим образом:for для каждой записи регистрации из множества Sc курса CS101 dobegin.s: = студент-собственник регистрационной записи;print(s)endЗдесь оператор присваивания можно детализировать так:f: = е;repeatf:= ft.cnextuntilf — указатель на запись студента;s:= значению поля studentname в записи, на которую указывает f;где е — указатель на первую регистрационную запись в множестве Sc курса CS101.Для реализации структуры, подобной показанной на рис.
4.9, на языке Pascal необходим только тип record (запись) в различных вариантах для записей, относящихся к именам студентов, названиям курсов и регистрации. Но возникают трудности,связанные с тем, что указатели полей cnext и snext могут указывать записи разныхтипов. Эти трудности можно обойти, если определять тип записи циклически. В листинге 4.14 показаны такие объявления типов, а также процедура printstudents вывода на печать имен студентов, посещающих определенный учебный курс.Листинг 4.14.
Реализация поиска в мультиспискеtypestype = array[1..20] of char;ctype = array[1..5] of char;recordkinds = (student, course, enrollment);recordtype = recordcase .kind : recordkinds ofstudent: (studentname: stype;firstcourse: trecordtype);course:(coursename: ctype;firststudent: trecordtype);enrollment: (cnext, snext: trecordtype)end;procedure printstudents ( cname: ctype );varc, e, f: trecordtype;beginc:= указатель на запись курса, где ct.coursename = спале;{ последний оператор зависит от того,как реализовано множество записей курсов }е:= ct.firststudent;{ е пробегает по кольцу указателейрегистрационных записей }while et.Jcind = enrollment do beginf:= e;repeatf:= ft.cnextuntil4.12.
НЕКОТОРЫЕ СТРУКТУРЫ СЛОЖНЫХ МНОЖЕСТВ141ft. kind = student;{ сейчас f — указатель на студента-собственникарегистрации et }.studentname);е:= et.snextendend; { printstudents }Эффективность двойных структур данныхЧасто кажущаяся простота представления множеств или отображений на самомделе оборачивается трудной проблемой выбора подходящей структуры данных. Какая-либо структура данных, представляющая множество, позволяет легко выполнятьопределенные операторы, но на выполнение других приходится затрачивать значительное время.
По-видимому, не существует одной структуры данных, позволяющейвсем операторам выполняться быстро и просто. В этом случае решением может статьиспользование двух или больше структур данных для представления одного и тогоже множества или отображения.Предположим, что мы хотим создать "теннисную лестницу" (т.е. квалификационную таблицу), где каждый игрок располагается на своей "ступеньке" (рейтинге).
Новыеигроки добавляются в самый низ, т.е. на ступеньку с самым большим номером. Игрокможет вызвать на поединок игрока, стоящего на более высокой ступени, и если он выиграет матч, то они меняются ступенями. Эту "лестницу" можно рассматривать как абстрактный тип данных, где базовой моделью будет отображение из множества имен игроков (строки символов) в множество номеров ступеней (целые числа 1, 2, ...). Необходимы также три оператора, выполняемые над этим ЛТД.1.АХУО(имя) добавляет новое имя в квалификационную лестницу на свободнуюступеньку с наибольшим номером, т.е.
в самый низ лестницы.2.CHALLENGE(wjiwi) возвращает имя игрока, стоящего на ступени i - 1, если игрокимя стоит на ступени i, i > 1.EXCHANGE(i)1 меняет местами игроков, стоящих на ступенях i и i - 1, i> 1.Для реализации описанных данных и их операторов можно использовать массивLADDER (Лестница), где LADDER[i] — имя игрока, стоящего на ступени i. Вместе сименем игрока можно хранить и его номер (т.е. номер ступени, на которой он стоит).В этом случае нового игрока можно просто добавить за малое фиксированное время всвободную ячейку массива.Оператор EXCHANGE реализуется легко — меняются местами два элемента массива. Но выполнение функции CHALLENGE в процессе поиска заданного имени требует времени порядка О(п) для просмотра всего массива (здесь и далее и — общеечисло игроков).С другой стороны, мы можем применить хеш-таблицу для задания отображения измножества имен в множество номеров ступеней.
Количество сегментов в хеш-таблицепримерно равно количеству игроков. Оператор ADD выполняется в среднем за времяО(1)- Функция CHALLENGE тратит в среднем О(1) времени на поиск заданного имени, нотребует О(п) времени для поиска имени соперника, стоящего на более высокой ступени,поскольку в этом случае надо просмотреть всю хеш-таблицу. Оператор EXCHANGE требует О(п) времени для поиска имен игроков, стоящих на ступенях i и i - 1.Теперь рассмотрим применение комбинации двух структур.
Пусть ячейки хештаблицы содержат имя игрока и его номер ступени, а в массиве LADDER элементLADDER[(\ будет указателем на ячейку игрока в хеш-таблице, стоящего на i-й ступени, как показано на рис. 4.10.3.1Названия операторов переводятся соответственно как "Добавить", "Вызов" (на поединок)и "Обмен". — Прим. перев.142ГЛАВА 4. ОСНОВНЫЕ ОПЕРАТОРЫ МНОЖЕСТВЗаголовкисегментовnextrungLADDERРис. 4.10. Комбинированная структура высокой производительностиПри такой организации данных добавление нового игрока требует в среднем О(1)времени для записи его атрибутов в хеш-таблицу, а также создания указателя на егоячейку в хеш-таблице из ячейки массива LADDER, которая помечена курсоромnextrung (следующая ступень) (см.
рис. 4.10). При выполнении функцииCHALLENGE надо сначала найти заданное имя в хеш-таблице (на это требуется всреднем О(1) времени), получить его номер ступени i и далее, следуя за указателемиз ячейки LADDER[i - 1] в ячейку хеш-таблицы, получить имя игрока-соперника.Все последние описанные действия в среднем требуют не более О(1) времени, поэтомувсе время выполнения функции CHALLENGE имеет в среднем порядок О(1).Оператор EXCHANGE(i) требует времени порядка О(1) для нахождения имен игроков с рангами i и i - 1, для обмена содержимым двух ячеек хеш-таблицы и обменауказателями в двух ячейках массива LADDER. Таким образом, даже в самом худшемслучае время выполнения оператора EXCHANGE не будет превышать некоторойфиксированной величины.Упражнения4.1.*4.2.Пусть заданы два множества А — {1, 2, 3} и В {3, 4, 5}.
Каков будет результат выполнения следующих операторов?а) UNION(A, В, С);б) INTERSECTION^, Б, С);в) DIFFERENCES, В. С);r)MEMBER(l,A);д) INSERT(1, А);e)DELETE(l.A);ж) МШ(А).Напишите процедуру в терминах базовых операторов множеств для печативсех элементов произвольного конечного множества. Предполагается, что элементы множества имеют тип, допустимый для печати. Процедура печати недолжна разрушать исходное множество. Какова в данном случае наиболее подходящая структура данных для реализации множества?143УПРАЖНЕНИЯ-•4.3.Реализацию множеств посредством двоичных векторов можно использовать тогда, когда "универсальное множество" преобразовано в последовательность целых чисел от 1 до N.
Опишите такое преобразование для следующих универсальных множеств:а) множество целых чисел О, 1, ..., 90;б) множество целых чисел от п до т, где га < от;в) множество целых чисел п, п + 2, п + 4, ..., га + 2k для любых п и fe;г) множество символов 'а', Ъ', ..., V;д) массив двухсимвольных строк, каждый символ может быть любым символом из множества 'а', Ъ', ..., V.4.4. Напишите процедуры MAKENULL, UNION, INTERSECTION, MEMBER, MIN,INSERT и DELETE для множеств, представленных посредством списков, используя обобщенные операторы АТД сортированных списков.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
