Файл: Зубов В.С. Математическое обеспечение цифровых вычислительных машин и систем учеб. пособие.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 26.07.2024
Просмотров: 88
Скачиваний: 0
-3 5 -
б) Оператор перехода от задания правильной последователь
ности одноовязным цепным списком к её выражению списком типа
Адля случая равной длины всех записей набора.
Всилу последовательного характера доступа к записям це
почки рациональным способом является способ установки их в список типа А, выражающий правильную последовательность, в
порядке их следования по цепочке. Следовательно, вначале устанавливается на I позицию запись, указанная содержимым фиксатора начала списка. С нею должна обменяться местом за пись, первоначально занимавшая эту позицию, что предполага ет также и изменение в цепном списке адреса связи, указыва ющего на эту запись, поскольку её рассмотрение с целью ус тановки ещё не осуществлялось и поэтому требуется её сохра нение в составе цепочки. Но для этого изменения требуется наличие "встречного” адреса связи: от данной записи к пред шествующей записи цепочки; решение проблемы в целом требует наличия "встречного" цепного списка записей, который может быть построен при однократном проходе по исходному цепному списку (требуется дополнительная память под адреса связи).
Аналогичным образом устанавливается на окончательную позицию 2 -я запись цепочки и т .д . вплоть до обнаружения признака конца цепочки.
Используется также вариант оператора, не требующий по строения "встречного" цепного списка, но равноценный по затратам памяти. В этом варианте при переходе по цепочке к новой запиои проверяется, не изменила ли эта запись сво его положения при установке на окончательные позиции ранее
рассмотренных записей. Для указания такогр случая яспользу-г
ется специальный признак (I бит). Положение такой переме
щённой записи указывается дополнительным адресом связи, ко торый представляет тупиковое ответвление от исходной цепоч ки. Его содержимое в процессе установки записей может изме няться неоднократно, так как до окончательной установки за пись может не один раз вытесняться с позиций, которые в
правильном списке типа А должны быть заняты другими, пред
шествующими ей, записями цепочки. Очевидно, однако, что об щее число обменов записей не больше общего числа записей.
3-й вариант оператора состоит из блока построения пра
вильного оглавления записей и блока - оператора перехода
от правильной последовательности, заданной оглавлением, к
её выражению списком типа А. Этот вариант равноценен пре дыдущим по затратам памяти, но экономичнее по времени в случав громоздких записей, так как обмены записей заменя ются в нём примерно тем же числом перемещений.
в) Оператор перехода от задания правильной последова тельности дихотомическим цепным списком к её выражению списком типа А для случая равной длины всех записей наборё.
Очевидно, данный оператор должен оказаться сложнее предыдущих в силу необходимости замены одного вида абстракт ной упорядоченности - древесного - другим; линейной упоря доченностью. Возможность 'такой замены станет для нас оче видной, если будет найден способ такой индексации элемен тов дерева, чтобы выборка их в порядке возрастания (убыва ния) индексов давала правильную последовательность. Есте ственно связывать значения цифр индекса о тем, какие ад реса связи используются при доступе к элементу (левый ад рес или правый) . Путь к наименьшему (наибольшему) элементу дерева представляет собой наибольшей длины путь, содержащий
|
- 3 5 - |
толъко левые |
(только правые) адреса, или же, если такого пути |
в дереве нет, |
наименьшим.(наибольшим) элементом является ко |
рень дерева. Разрядность индексов установим согласно макси мальной длине пути в дереве. При меньшей длине пути к элемен ту его индекс будем дополнять нулями со стороны младших раз рядов. Если путь начинается с левого адреса, цифрой старшего
разряда индекса будет I (минус единица), если с правого ад реса - то I . Соответственным образом определим и цифры сле
дующих ненулевых разрядов. Следовательно, индекс представля
ет |
число |
в позиционной троичной сиотеме счисления с цифрами |
I , |
О, I . |
Индекс наименьшего элемента имеет в и д :П ...1 П Ю ...О , |
где соотношение числа I и 0 может оказаться произвольным.
Следующим по величине элементом дерева является элемент,
предшествующий рассмотренному (если только рассмотренный элемент не был корнем). Его индекс отличается в одном разря-
де: |
—— |
звёздочкой). Если у второго |
|
I I . ..1 0 0 0 ...0 (он помечен |
|||
элемента есть пепустой правый |
адрес, то очередным по |
величи |
|
не, |
третьим, элементом является тот, путь к которому |
начина |
ется с этого адреса, а далее содержит лишь левые адреса (мо
жет быть, и ни одного), имея при этом наибольшую длину. Сле
довательно, индекс третьего |
элемента содержит I в том разря |
||
де, по |
которому различались |
и рассмотренные |
выше индексы,и |
к тому |
же может содержать подряд идущие I в |
более младших |
разрядах: I I . ..1 1 1 1 ...0 . Если же у второго элемента |
не |
||
было правого адреса, |
то следующим по величине элементом яв |
||
ляется предшествующий |
ему, с индексом |
I I . . . 0 0 0 0 ...0 |
. Не |
трудно убедиться, что |
значения индексов монотонно возрастают. |
||
Пример нумерации элементов дерева |
приводится на рис. 3. |
||
Детализация рассмотренных алгоритмов |
осуществлена в Приложеши. |
-3 6 -
^ In o o j |
1100 |
у\Ш |
/ |
® |
\ |
|
|
|
|||
illo l. |
|
Ш■ ■ . / |
lu lo l |
!ыю 1 |
|
~ Л |
|
|
/ Л |
|
v |
Н И |
|
|
lii ii! |
Inii| |
|
Рис. 3. Пример нумерации элементов |
|
|
|||
.. случайного |
двоичного |
дерева |
|
|
|
В процессе применения средств математического обеспече ния часто возникает необходимость в использовании или обра ботке разнообразных списков и структур, построенных из них,
например; списка команд программы на ассемблере; списка мне мокодов операций; списка имён, использованных в программе;
списков сообщений; магазина символов текста на проблемно-
ориентированном языке; матриц или векторов старшинства, ис пользуемых при компиляции; синтаксических таблиц; списков записей и т .п . При этом часто возникает необходимость в оты скании элемента.списка по его содержимому либо для добавле ния или изменения в нём некоторой информации, либо для ис пользования содержащейся в нём информации, либо для установ ления факта отсутствия в списке указанного элемента.
Следовательно, характеристики операторов поэлементного построения и преобразования правильных структур и поиска в
них на основе анализа содержимого |
элементов данных приобре |
т а в весьма существенное значение. |
Вопросам оптимальной ор |
ганизации указанных операторов применительно к ситуациям кон кретного их использования посвящается содержание следующих впав.
- 5 7 -
ГЛАВА П. УПОРЯДОЧЕНИЕ ДАННЫХ
§ I . Задача упорядочения данных в памяти ЭВМ Предметом упорядочения в' памяти ЭВМ является множество
формуляров - структур данных, имеющих однотипный формат, или множество записей. Формат той части записи, которая содержит элементы управляющего слова, должен быть однотипным для всех записей множества. Формуляры и записи представляют описания некоторых объектов, причём, как привило, не в одном, а в не скольких аспектах. Это описание занимает в памяти некоторое поле, называемое позицией, если описание представлено в виде списка типа А. Позиция служит для размещения кодов составля ющих описание признаков объекта и, возможно, также относя щейся к нему текстовой информации. Позиция в общем случае имеет произвольный объём, выражаемый в битах, байтах или ячейках памяти. Независимо от того, какие элементы являются-
адресуемыми в базовой структуре памяти, будем называть пол ным адресом любого двоичного элемента памяти числовую инфор-
мацию, полностью определяющую его положение в памяти. Полный адрес начального бита позиции назовём адресом позиции. Часть позиции, служащая для размещения признака, именуется полем признака. Поле, занятое признаком, входящим в состав управ ляющего слова, именуется управляющим полем. Упорядочение по управляющему слову, состоящему более, чем из одного управля
ющего поля, а также поиск по нему будем называть многоаспект ным.
Отметим, что начиная упорядочение множества записей или формуляров в памяти ЭШ, мы всегда имеем дело со структурой данных, т .е . с упорядоченным множеством описаний, но эта упорядоченность обычно не соответствует нашему правилу.
Если число записей равно ft , то общее число последователь
ностей, различающихся взаимным порядком хотя бы двух записей,
равно/l/. Какая-то из этих последовательностей является исхо дной, и одна из них является правильной, причём "лицо" прави
льной последовательности выражено используемым при упорядо чении отношением порядка или способом отображения. Рассматри вая последовательность записей обобщённо, как систему, спо
собную находиться во многих состояниях, мы можем использовать шенноновское понятие энтропии как меры неопределённое™ её
состояния. Энтропия такой |
системы |
Нс= |
Pi t y s p i |
, |
где p i - вероятность L- го |
состояния. |
|
|
|
Наибольшей энтропией обладает система, состояния которой равновозмокны. Последовательность, обладающую наибольшей не-
определённостью состояния, будем называть случайной. Если же
все п ! состояний равновозможиы, |
то Р;=1 /п / и |
энтропия случайной |
последовательности Нс- &xj2(n!) |
При условии, |
что все допустимые |
состояния правильной последовательности также равповозможны,
её энтропия Нп-& ^^П (П н ^ ) - ^ - ^ 2 Здесь через
/^обозначены мощности подмножеств записей, между которыми не определено отношение порядка (их взаимное положение произво льно). Суммирование производится по всем таким подмножествам.
Задачей упорядочения случайной последовательности явля
ется |
выяснение того, насколько порядок |
записей в ней соот |
ветствует порядку записей в правильной |
последовательности |
|
(т .е . |
снятие неопределённости лН=Нс~Нп) и трансформация её |
путём перестановки записей в последовательности (их перену мерации) вплоть до получения правильной последовательности.
Если все I (итогом упорядочения является простая правильная последовательность), то
-3 9 -
§2. Метод упорядочения, базирующийся на непосред ственное использование отношения порядка
Задача такого упорядочения может быть детализирована в
виде двух основных вариантов:
а) при неизменной последовательности позиций, заданной
обычно порядком возрастания (убывания) их адресов, путём пе рераспределения записей по позициям добиться выполнения от ношения порядка в последовательности записей, заданной по следовательностью занимаемых ими позиций; результатом тако го упорядочения является правильная последовательность в ви
де списка типа А;
б) при неизменном расположении записей по позициям пу
тём изменения последовательности позиций (их перенумерации),
заданной некоторой системой адресных указаний (например, ог лавлением), добиться выполнения отношения порядка в последо вательности записей, заданной последовательностью занимаемых ими позиций; результатом такого упорядочения является правиль ная структура даншх, основывающаяся на списках типа Б,В или Г.
Отношением порядка для числовых признаков может служить одно из следующих отношений:> , < ( отношенияё и :> являются
соответственно отрицаниями вышеуказанных отношений и поэтому самостоятельной роли не имеют, однако оказываются более удо бными в практическом шине, так как позволяют устранить не которые избыточные действия цри упорядочении последователь ности, содержащей записи с равными значениями управляющих слов; отношения^ и > являются не асимметричными, а антисим метричными (см . Щ ) , но это не имеет существенного значения,
поскольку в празильной^поатедовательности допускается произ вольное взаимное расположение вышеуказанных, записей, а на .