Структуры данных и алгоритмы (1021739), страница 34
Текст из файла (страница 34)
ОСНОВНЫЕ ОПЕРАТОРЫ МНОЖЕСТВminimum: Tprocesstype;beginif A.last = 0 thenerror('Очередь пуста')else beginnew(minimum);minimum Т := A.contents[1];A. contents[1]:= A.contents[A.last];A.last:= A.last - 1;i:= 1;while i <= A.last div 2 do begin{ перемещение старого последнего элементавниз по дереву }if (p(A.contents[2*i]) < р(А.contents[2*i + 1]))or (2*i = A . l a s t ) thenelsej : = 2*ij:= 2*i + 1;{ j будет сыном i с наименьшим приоритетом или,если 2*i = A.last, будет просто сыном i }if р(А.contents[i]) > р(А.contents[j]) then begin{ обмен старого последнего элемента с сыном,имеющим наименьший приоритет }temp: = A.contents[i] ;A.contents[i]:= A.contents!j];A.contents[j]:= temp;i: = j;endelsereturn(minimum){ дальше перемещение элемента невозможно }end;return(minimum) { элемент дошел до листа }endend; { DELETEMIN }4.12. Некоторые структуры сложных множествВ этом разделе мы рассмотрим применение двух сложных множеств для представления данных.
В первом примере рассмотрим представление отношений "многиеко-многим", которые встречаются в системах баз данных. Далее мы изучим, как спомощью двух структур данных можно представить какой-либо объект (в нашемслучае — отображение) более эффективно, чем при представлении этого объекта одной структурой.Отношения „многие-ко-многим" и структура мультисписковПример отношения "многие-ко-многим" между множеством студентов и множеством учебных курсов (учебных предметов) показан в табл. 4.3.
Отношение "многие-комногим" называется так потому, что на каждый курс могут записаться много студентов (не один) и каждый студент может записаться на несколько курсов.Время от времени может возникнуть необходимость вставить или удалить студентов с какого-либо курса, определить, какие студенты посещают тот или ной курс,или узнать, какие курсы посещает конкретный студент. Простейшей структурой4:12. НЕКОТОРЫЕ СТРУКТУРЫ СЛОЖНЫХ МНОЖЕСТВ137данных, которая удовлетворяет этим запросам, является двумерный массив, подобный табл. 4.3, где значение 1 (или true) соответствует значку "X", а значение О (илиfalse) — пробелу.Таблица 4.3.
Пример отношения между множеством студентов и множествомучебных курсовCS202CS101AlanAlexAliceCS303XX,AmyX.X.:XAndyXXXAnnXРегистрация (студентов по учебным курсам)Чтобы приписать студента к какому-либо курсу, надо использовать отображение(назовем его MS), которое можно реализовать как хеш-таблицу, для преобразования имени студента в индекс массива, а также еще одно отображение МС, переводящее названиекурса в другой индекс массива. Тогда запись студента s на курс с можно представить ввиде простого присваивания элементу массива Enrollment (Регистрация) значения 1:Enrollment[MS(s), MC(c)] := 1.Открепление студента с курса выполняется путем задания значения О соответствующему элементу массива Enrollment.
Для определения курсов, которые посещаетстудент с именем s, надо просмотреть строку MS(s), а для получения списка студентов, посещающих курс с, надо просмотреть столбец МС(с).Почему для представления подобных данных надо использовать другую, болееподходящую структуру данных? Представим большой университет, где учатся примерно 20 000 студентов и изучается не менее 1 000 учебных курсов, при этом каждый студент одновременно изучает в среднем только три учебных курса. Тогда прииспользовании массива, подобного табл. 4.3, этот массив будет состоять из20 000 000 элементов, из которых только 60 000, или примерно 0.3%, будут иметьзначение I1. Такой массив называют разреженным, так как большинство его элементов имеют нулевые значения.
Можно сберечь значительный объем памяти, если хранить не весь разреженный массив, а только его ненулевые элементы. Более того, вэтом случае можно значительно сократить время просмотра этого массива. Например, вместо просмотра столбца из 20 000 элементов надо просмотреть в среднем всего60 элементов. Просмотр элементов по строкам займет примерно такое же время.Еще один подход к решению исходной задачи состоит в ее переформулировке:вместо представления данных, подобных табл.
4.3, в виде одного множества можносоздать систему поддержки набора множеств и отношений между ними. В нашемслучае очевидны два множества: имен студентов S и названий учебных курсов С.Каждый элемент множества S будет иметь тип studenttype (тип студента), которыйможно представить в виде записей следующего типа:typestudenttype = recordid: integer;лагае: array[1..3 0] of char;end1Если бы это была реальная база данных, то такой массив должен храниться на устройствевнешней памяти. Но такая структура данных слишком расточительна даже для внешней памяти.138ГЛАВА 4.
ОСНОВНЫЕ ОПЕРАТОРЫ МНОЖЕСТВПодобное определение можно сделать для элементов множества С. Для реализацииотношений между элементами множеств необходимо третье множество Е, каждый элемент которого должен соответствовать одной ячейке массива регистрации, где есть знак"X" (см. табл. 4.3). Элементы множества Е должны быть записями фиксированного типа. Мы пока не можем сказать, какие поля должны содержать эти записи1, но далеемы рассмотрим несколько возможных вариантов таких полей.
Сейчас мы просто постулируем, что есть регистрационные записи для каждой ячейки массива, помеченнойзнаком "X", и эти записи каким-то образом отделены одна от другой.Нам также нужны множества, соответствующие ответам на основные вопросы:какие учебные курсы посещает конкретный студент s (это множество обозначим С,) икакие студенты записаны на данный курс с (это множество Sc). Реализации этихмножеств вызывают затруднения, поскольку заранее нельзя сказать, сколько будетэлементов в этих множествах, что, в свою очередь, принуждает усложнять записи,касающиеся студентов и курсов.
Можно сделать множества С, и Sc не множестваминепосредственно записей, а множествами указателей на студенческие и курсовые записи. В этом случае экономится значительная часть пространства памяти и можнобыстро получить ответы на сформулированные выше вопросы.Пока пусть каждое множество С, является множеством регистрационных записей, соответствующих конкретному студенту s и некоторому учебному курсу с.
Если принять зарегистрацию пару (s, с), то множество С, можно определить следующим образом:С, — {(s, с) | студент s записан на курс с}.Аналогично определяется множество Sc:Sc = {(s, с) | студент s записан на курс с}.Отметим различие в определении этих множеств: в первом множестве s является константой, а во втором — с.
Например, основываясь на табл. 4.3, Cjviex = {(Alex, CS101),(Alex, CS202)} и SCSIM = {(Alex, CS101), (Amy, CS101), (Ann, CS101)}.Структуры мультисписковВ общем случае структура мультисписка — это совокупность ячеек, некоторые изкоторых имеют более одного указателя и поэтому одновременно могут принадлежатьнескольким спискам. Для каждого типа ячеек важно различать пбля указателей дляразных списков, чтобы можно было проследить элементы одного списка, не вступаяв противоречие с указателями другого списка.С этой точки зрения можно задать поля указателя в каждой записи для студентаи для курса, которые указывали бы на первые регистрационные записи множеств С,и Sc соответственно.
Каждая регистрационная запись должна иметь два поля указателя, одно из них, назовем его cnext , будет указывать на следующую регистрационную запись списка множества Cs, которому она принадлежит, а второе поле, snext,будет указывать на следующую регистрационную запись списка множества Sc, которому она также принадлежит.Оказывается, что при таком задании полей указателей в регистрационных записях они могут не указывать непосредственно ни на студента, ни на курс, которымона (регистрационная запись) соответствует. Эта информация неявно содержится всписках, которым принадлежит регистрационная запись. Назовем студенческие икурсовые записи, возглавляющие такие списки, собственниками регистрационнойзаписи.
Таким образом, чтобы найти те курсы, которые посещает студент s, надопросмотреть все регистрационные записи из С, и для каждой из них найти собственника среди курсовых записей. Для этого достаточно поместить в каждую регистрационную запись указатели на обоих собственников.1На практике в записях, подобных регистрационным, удобно иметь поля типа метки илистатуса, но наша исходная задача этого не требует.4.12.
НЕКОТОРЫЕ СТРУКТУРЫ СЛОЖНЫХ МНОЖЕСТВ139Благодаря таким указателям можно получить ответы на интересующие нас вопросы за минимально возможное время. Но можно значительно сократить объем памяти, занимаемой такой структурой1, если исключить описанные выше указатели насобственников из регистрационных записей, оставив их только в конечных записяхсписков каждого С, и Sc. Таким образом, каждая запись о студенте или курсе становится частью кольца, включающего все регистрационные записи, для которых данная запись о студенте или курсе является собственником. Такие кольца можно видеть на рис. 4.9 для данных из табл. 4.3. Отметим, что.
на этом рисунке регистрационные записи состоят из поля cnext (левое) и поля snext (правое).записи остудентахAlanAlex| Alice) t | | Amy ^| AndyAnn,1регистрационныезаписизаписи обучебных курсах CS101CS202i|CS303|,Рис. 4.9. Представление данных из табл.
4.3 посредством мультиспискаПример 4.11. Для ответа на вопрос, какие студенты зарегистрированы на курсеCS101, сначала находим запись для этого учебного курса. Как найти эту запись, зависит от организации множества курсов. Например, это может быть хеш-таблица,содержащая все курсовые записи, тогда определить нужную запись можно посредством хеш-функции, примененной к "CS101".Далее следуем за указателем из записи курса CS101 на первую регистрационную запись кольца для этого курса. На рис. 4.9 это вторая слева регистрационная запись. Теперь надо найти собственника-запись студента, которому принадлежит данная регистрационная запись. Для этого мы следуем за указателями cnext (первый указатель в регистрационной записи), пока не достигнем указателя на запись студента .
В данном случаемы остановимся на третьей регистрационной записи, которая указывает на запись студента Alex. Таким образом, мы узнали, что Alex посещает учебный курс CS101.Теперь надо найти следующего студента, посещающего курс CS101. Для этого надо следовать за указателем snext (второй указатель в регистрационной записи), начиная со второй регистрационной записи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
