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

данных, которая удовлетворяет этим запросам, является двумерный массив, подобный табл. 4.3, где значение 1 (или true) соответствует значку "X", а значение О (или false) - пробелу.

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

CSlOl

CS202

CS303

Alan

Alex

Alice

Andy

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

Чтобы приписать студента к какому-либо курсу, надо использовать отображение (назовем его MS), которое можно реализовать как хеш-таблицу, для преобразования имени студента в индекс массива, а тагсже еще одно отображение МС, переводящее название курса в другой индекс массива. Тогда запись студента s на курс с можно представить в виде простого присваивания элементу массива Enrollment (Регистрация) значения 1:

Enrollrnent[MS(s),MC(c)-\ - 1.

Открепление студента с курса выполняется путем задания значения О соответствующему элементу массива Enrollment Для определения курсов, которые посещает студент с именем s, надо просмотреть строку MS(s), а для получения списка студентов, посещающих курс с, надо просмотреть столбец МС(с).

Почему для представления подобных данных надо использовать другую, более подходящую структуру данных? Представим большой университет, где учатся примерно 20 ООО студентов и изучается не менее 1 ООО учебных курсов, при этом каждый студент одновременно изучает в среднем только три учебных курса. Тогда при использовании массива, подобного табл. 4.3, этот массив будет состоять из 20 ООО ООО элементов, из которых только 60 ООО, или примерно 0.3%, будут иметь значение l. Такой массив \\йз,ъ\йдхут разреженным, так как большинство его элементов имеют нулевые значения. Можно сберечь значительный объем памяти, если хранить не весь разреженный массив, а только его ненулевые элементы. Более того, в этом случае можно значительно сократить время просмотра этого массива. Например, вместо просмотра столбца из 20 ООО элементов надо просмотреть в среднем всего 60 элементов. Просмотр элементов по строкам займет примерно такое же время.

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

type

studenttype = record id: integer;

name: array[1..3 0] of char;

Если бы это бьша реальная база данных, то такой массив должен храниться на устройстве внешней памяти. Но такая структура данных слишком расточительна даже для внешней памяти.



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

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

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

С, - {(s,c) I студент s записан на курс с).

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

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

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

Структуры мультисписков

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

С этой точки зрения можно задать поля указателя в каждой записи для студента и для курса, которые указывали бы на первые регистрационные записи множеств С, и Sc соответственно. Каждая регистрационная запись должна иметь два поля указателя, одно из них, назовем его cnext, будет указывать на следующую регистрационную запись списка множества С„ которому она принадлежит, а второе поле, snext, будет указывать на следующую регистрационную запись списка множества которому она таюке принадлежит.

Оказывается, что при таком задании полей указателей в регистрационных записях они могут не указывать непосредственно ни на студента, ни на курс, которым она (регистрационная запись) соответствует. Эта информация неявно содержится в списках, которым принадлежит регистрационная запись. Назовем студенческие и курсовые записи, возглавляющие такие списки, собственниками регистрационной записи. Таким образом, чтобы найти те курсы, которые посещает студент s, надо просмотреть все регистрационные записи из С, и для каждой из них найти собственника среди курсовых записей. Для этого достаточно поместить в каждую регистрационную запись указатели на обоих собственников.

На практике в записях, подобных регистрационным, удобно иметь поля типа метки или статуса, но наща исходная задача этого не требует.



Благодаря таким указателям можно получить ответы на интересующие нас вопросы за минимально возможное время. Но можно значительно сократить объем памяти, занимаемой такой структурой, если исключить описанные выще указатели на собственников из регистрационных записей, оставив их только в конечных записях списков каждого С, и S. Таким образом, каждая запись о студенте или курсе становится частью кольца, включающего все регистрационные записи, для которых данная запись о студенте или курсе является собственником. Такие кольца можно видеть на рис. 4.9 для данных из табл. 4.3. Отметим, что. на этом рисунке регистрационные записи состоят из поля cnext (левое) и поля snext (правое).

записи о студентах

регистрационные записи


записи об учебных курсах

CS101

CS202

CS303

Рис. 4.9. Представление данных из табл. 4.3 посредством мультисписка

Пример 4.П. Для ответа на вопрос, какие студенты зарегистрированы на курсе CS101, сначала находим запись для этого учебного курса. Как найти эту запись, зависит от организации множества курсов. Например, это может быть хещ-таблица, содержащая все курсовые записи, тогда определить нужную запись можно посредст-вомхещ-функции, примененной к "CS101".

Далее следуем за указателем из записи курса CS101 на первую регистрационную запись кольца для этого курса. На рис. 4.9 это вторая слева регистрационная запись. Теперь надо найти собственника-запись студента, которому принадлежит данная регистрационная запись. Для этого мы следуем за указателями cnext (первый указатель в регистрационной записи), пока не достигнем указателя на запись студента . В данном случае мы остановимся на третьей регистрационной записи, которая указывает на запись студента Alex. Таким образом, мы узнали, что Alex посещает учебный курс CS101.

Теперь надо найти следующего студента, посещающего курс CS101. Для этого надо следовать за указателем snext (второй указатель в регистрационной записи), начиная со второй регистрационной записи. В данном случае он приведет к пятой регистрационной записи. В этой записи указатель cnext непосредственно указывает на собственника-запись студента, которая соответствует студенту Ашу. Таким образом, студент Ашу также посещает курс CS101. Следуя далее за указателем snext пятой регистрационной записи, мы перейдем к восьмой регистрационной записи. Кольцо указателей cnext приведет от этой записи к девятой регистрационной записи, собственником которой является запись, соответствующая студентке Ann, также посещающей курс CS101. Указатель snext восьмой регистрационной записи возвращает нас на запись курса CS101. Это означает, что множество исчерпано. □

Отметим, что, как правило, регистрационных записей значительно больще, чем записей о студентах и учебных курсах, поэтому, даже незначительно сокращая пространство, занимаемое одной регистрационной записью, мы существенно сокращаем общее требуемое пространство памяти.

Чтобы отличить указатель на регистрационную запись от указатеж на запись студента, надо как-то определять тип записей. Этот вопрос мы рассмотрим немного ниже.





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.0019