Файл: Зубов В.С. Математическое обеспечение цифровых вычислительных машин и систем учеб. пособие.pdf

- 5 6 -

при поиска в дереве. Деревья такого рода именуются подрав-

ненннми.

Алгоритмы упорядочения путём построения дихотомичес­ кого дерева записей на основе их сопоставления будем имено­ вать сопоставительными алгоритмами включения в дихотомиче­ ское дерево.

§ 4. Метод упорядочения, базирующийся на отображении множества записей на вектор памяти

Вектор памяти является естественным упорядоченным мно­ жеством .объектов в ЭВМ, пригодным для осуществления упоря­ дочения записей путём отображения их множества на упорядо­ ченное множество объектов ( " отобразительное" упорядочение).

Идея такого упорядочения в случае отсутствия ограни­ чений на размер вектора - проста. С помощью некоторой фун­ кции соответствия устанавливается соответствие элементов вектора и записей по значению их управляющих слов. В даль­ нейшем используемый вектор будем именовать вектором значе­ ний. Один элемент вектора соответствует обычно ассоциации записей с определённым значением управляющего слова, т .е .

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

Рассмотрим некоторые аспекты, позволяющие классифици­ ровать отобразительные алгоритмы упорядочения.

- 5 7 -

I . Функция соответствия. В простейшем случае ~,,1упорядо-

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

■>, , а для другого ^ , значение одного из них должно заме­ няться (например, вычитанием из наибольшего возможного значения этого поля) с целью сведения к единому отношению порядка. Значение поля, представленное числом с плавающей запятой, должно быть однозначно и в соответствии с его ве­ личиной отображено на последовательность целых чисел, ка­ ковыми являются номера элементов вектора. Для этого поле рассматривается как составное, старшей частью которого яв­ ляется порядок (кодировка его знака должна быть следующей:

плюс - " I " , минус - "О "), а младшей мантисса. Значения отрицательных порядков должны заменяться на значения, по­ лученные вычитанием модуля исходных из наибольшего модуля порядка.д0 ошс ПОр П0 лагал0 сь , что правильная последова­ тельность управляющих полей представлена монотонно возра­ стающей или убывающей последовательностью значений. Испо­ льзование нетривиальной функции соответствия при упорядо­ чении отображением позволяет сделать исключение из этого правила, расширяя возможности упорядочения.

Здесь возможны два варианта:

а)Таблично задана функция соответствия: она имеет

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

тора, служит посредником между последним и значением поля

при его отображении на вектор. Пооледукхций за отображением записей просмотр элементов вектора производится в порядке монотонного изменения адресов элементов.

б) Полные адреса элементов вектора линейно зависят от

значений управляющих полей,но просмотр элементов вектора,

осуществляемый после -отображения всех записей, выполняется

в порядке,заданном списком типа Б - оглавлением вектора.

Например, в случае упорядочения слов, заданных в коде

"М2", по первым их буквам, слова, начинающиеся с буквы А,

элемент и, следовательно, попадут в начало правильной по­ следовательности. При использовании варианта б) слова, на­ чинающиеся с А, отображаются на 70-й по номеру элемент ве­ ктора, но поскольку 1 -й элемент оглавления, используемого при просмотре элементов вектора, содержит указание именно этого элемента вектора, все слова, начинающиеся с А, ока­ зываются опять-таки первыми в правильной последовательно­

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

П. Тип результирующего списка. Если результат упоря­ дочения должен быть представлен списком типа В и в исход­ ном списке допустимо существование записей с одинаковым значением управляющего слова ( записей—"синонимов" ) . отоб­ ражением каждой ассоциации таких записей является односш -

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

Первоначально списки пусты, т .е , содержимым каждого фикса­ тора конца является адрес фиксатора начала списка. В про­ цессе отображения записей на вектор они включаются в соот­ ветствующие списки, содержимое фиксатора конца которых со ­ ответственно изменяется. Такое задание ассоциаций записей предельно упрощает процесс последующего распределения мест в правильной последовательности: конец описка, соответст­ вующего начальной ассоциации записей, связывается с нача­ лом списка, соответствующего 2 -й по порядку ассоциации,

его конец - с началом следующего списка и т .д . В этом про-

цессе используется содержимое фиксаторов (происходит по­ следовательный просмотр вектора фиксаторов).

Если результат упорядочения должен быть задан списком тина А или Б, отображением ассоциаций записей являются счётчики числа записей в каждой ассоциации. Первоначально счётчики пусты. При отображении каждой записи на вектор к содержимому соответствующего счётчика прибавляется I . Про­ цесс распределения мест в правильной последовательности,

выполняемый после отображения всех записей, более сложен,

- 6 0 -

чем в предыдущем случае. Он выполняется в 2 этапа, первым

из которых является определение номера начальной позиции каждой из ассоциаций в правильной последовательности. Этот номер определяется суммой размеров всех ассоциаций, кото­ рые предшествуют данной в правильной последовательности.

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

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

В случае использования списка типа А отображение за­ писи на вектор позволяет извлечь номер её позиция в прави­ льной последовательности из соответствующего элемента век­ тора. При этом содержимое последнего увеличивается на I ,

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

алгоритм переходит к записи, находящейся на следующей по­ зиции. Поскольку однако найденная позиция в общем случае занята другой записью, производится обман местами в памяти этой записи и отображаемой записи. На> исходной позиции те­ перь оказалась запись, которая ещё не отображалась на век­ тор и в общем случае не занимает ещё окончательного поло­ жения. С нею осуществляются те же манипуляции, что и с ра­ цее находивгейся на данной позиции записью. Цепочка переме­ щений записей продолжается до тех пор, пока не будет уста­

- 6 f -

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

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

рения.

В случае использования списка типа Б вышеописанная

процедура выполняется лишь с тем отличием, что вычисляют­

Обращение к записям для их размещения в правильной после­ довательности происходит через оглат пение. Положение за­ писей в памяти остаётся неизменным.

Ш. Отобразительное упорядочение, результатом которо-

го является разбросанная таблица. При неограниченных ре­

сурсах оперативной памяти записи из любого набора записей

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

как совокупность укрупненных позиций- ( надпозиций) . каждая

из которых может вместить количество записей, равное макси­

мальной кратности. Для помещения в надпозицшо очередной записи находится ближайшая к началу надпозиция пустая по­

зиция. Дрд ограничении ресурсов оперативной памяти для по- <•

лучения номера позиции может быть использована старшая

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

заш оей, может оказаться одинаковым. Такие записи также

именуются синонимами. В частности, синонимами оказываются

заш ей с полностью одинаковыми управляющими словами. Для

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

бует, чтобы число позиций было не меньше числа размещаемых

записей и чтобы занятые позиции отмечались специальным зна­ ком (совокупность этих элементов по всем записям образует двоичный вектор занятости позиций).

Разбросанные таблицы удобны для представления дйцрмя-

ческих правильных последовательностей.(Сравни с дихотомиче­ скими деревьями).

1У. Представление элементов вектора. Характер элемен­

тов вектора значений, *с одной стороны, определяется типом

используемого списка, а с другой стороны, характером расп­

ределения значений управляющих слов по числовой оси, харак­ тером элементов данных. Рассмотрим несколько случаев.

а) Имеется взаимно однозначное соответствие между

- 6 3 -

имеют одинаковый размер,

В этом случае полный адрес записи является линейной

функцией её номера и в качестве вектора значений можно ис­ пользовать вектор позиций записей в исходном поле данных.

Для 1-й записи исходного списка определяется её номер в

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

позиции списка, определяется её номер в правильной после­ довательности и происходит обмен позициями между соответ­ ствующими записями и т . д . , вплоть до тех пор, пока вычис­ ленный номер не совпадёт с номером позиции, где уже нахо­ дится запись, т .е . с единицей. Аналогичные действия выпол­ няются затем для 2 -й позиции списка и т . д . , вплоть до предпоследней (включительно). Данный алгоритм не треоует использования резерва памяти, но во: можен также вариант с формированием правильной последовательности на свобод- .

значение записи является полным адресом элемента. В нача­ ле работы алгоритма элементы вектора приводятся в нулевое состояние. В результате отображения каждой запиои в соот­ ветствующий ей элемент вектора заносится I . При последую­ щем просмотре элементов вектора для каждого его единично­ го элемента с помощью функции, обратной функции соответст­ вия, воспроизводится значение записи и помещается на оче-