yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->4.12. Некоторые структуры сложных множеств

Алгоритмы структуры данных

4.12. Некоторые структуры сложных множеств

В этом разделе мы рассмотрим применение двух сложных множеств для представления данных. В первом примере рассмотрим представление отношений "многие-ко-многим", которые встречаются в системах баз данных. Далее мы изучим, как с помощью двух структур данных можно представить какой-либо объект (в нашем случае — отображение) более эффективно, чем при представлении этого объекта одной структурой.

Отношения „многие-ко-многим" и структура мультисписков

Пример отношения "многие-ко-многим" между множеством студентов и множеством учебных курсов (учебных предметов) показан в табл. 4.3. Отношение "многие-ко-многим" называется так потому, что на каждый курс могут записаться много студентов (не один) и каждый студент может записаться на несколько курсов.

Время от времени может возникнуть необходимость вставить или удалить студентов с какого-либо курса, определить, какие студенты посещают тот или ной курс, или узнать, какие курсы посещает конкретный студент. Простейшей структурой данных, которая удовлетворяет этим запросам, является двумерный массив, подобный табл. 4.3, где значение 1 (или true) соответствует значку "X", а значение 0 (или false) — пробелу.

 

 

Таблица 4.3. Пример отношения между множеством студентов и множеством учебных курсов

 

CS101

CS202

CS303

Alan Alex Alice Amy Andy Ann

 

X

 

X

 

X

 

X

 

 

X

X

 

X

 

X

X

Регистрация (студентов по учебным курсам)

Чтобы приписать студента к какому-либо курсу, надо использовать отображение (назовем его 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%, будут иметь значение 1. Такой массив называют разреженным, так как большинство его элементов имеют нулевые значения. Можно сберечь значительный объем памяти, если хранить не весь разреженный массив, а только его ненулевые элементы. Более того, в этом случае можно значительно сократить время просмотра этого массива. Например, вместо просмотра столбца из 20 000 элементов надо просмотреть в среднем всего 60 элементов. Просмотр элементов по строкам займет примерно такое же время.

Еще один подход к решению исходной задачи состоит в ее переформулировке: вместо представления данных, подобных табл. 4.3, в виде одного множества можно создать систему поддержки набора множеств и отношений между ними. В нашем случае очевидны два множества: имен студентов S и названий учебных курсов С. Каждый элемент множества S будет иметь тип studenttype (тип студента), который можно представить в виде записей следующего типа:

type

Studenttype = record

id: integer;

name:             [1..30]   of char;

end

 

Подобное определение можно сделать для элементов множества С. Для реализации отношений между элементами множеств необходимо третье множество Е, каждый элемент которого должен соответствовать одной ячейке массива регистрации, где есть знак "X" (см. табл. 4.3). Элементы множества Е должны быть записями фиксированного типа. Мы пока не можем сказать, какие поля должны содержать эти записи, но далее мы рассмотрим несколько возможных вариантов таких полей. Сейчас мы просто постулируем, что есть регистрационные записи для каждой ячейки массива, помеченной знаком "X", и эти записи каким-то образом отделены одна от другой.

Нам также нужны множества, соответствующие ответам на основные вопросы: какие учебные курсы посещает конкретный студент s (это множество обозначим Сs) и какие студенты записаны на данный курс с (это множество Sc). Реализации этих множеств вызывают затруднения, поскольку заранее нельзя сказать, сколько будет элементов в этих множествах, что, в свою очередь, принуждает усложнять записи, касающиеся студентов и курсов. Можно сделать множества С, и Sc не множествами непосредственно записей, а множествами указателей на студенческие и курсовые записи. В этом случае экономится значительная часть пространства памяти и можно быстро получить ответы на сформулированные выше вопросы.

Пока пусть каждое множество Сs является множеством регистрационных записей, соответствующих конкретному студенту s и некоторому учебному курсу с. Если принять за регистрацию пару (s, с), то множество С, можно определить следующим образом:

Cs = {(s, с) | студент s записан на курс с}.

Аналогично определяется множество Sc:

Sc = {(s, с) | студент s записан на курс с}.

Отметим различие в определении этих множеств: в первом множестве s является константой, а во втором — с. Например, основываясь на табл. 4.3, сAleх = {(Alex, CS101), (Alex, CS202)} и Scs101 = {(Alex, CS101), (Amy, CS101), (Ann, CS101)}.

 

63