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

-2 6 -

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

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

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

ментов в виде адресной цепочки без разветвлений и циклов,

именуемый односвязным цепным списком. Каждый из К-элемен-

тов содержит адрес следующего. Замыкает список К-элемент,

содержащий не адрес, а специальный признак конца. Адрес первого К-элемента указывается в специально выделенном эле­ менте памяти, называемом фиксатором начала (подобным обра­ зом можно также фиксировать конец списка). Содержимое К-эле-

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

-2 7 -

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

ковой структурой. Возможны и более сложные случаи.

Г. Многоовязный список типа дерева. В случае, если каж­ дый К-элемент содержит адреса двух других К-элементов, обра­ зуется разветвлённый список, имеющий вид двоичного дерева и называемый дихотомическим цепным списком. Узел древовидного цепного списка является списком, содержащим более одного ад­ реса связи и, возможно, собственную информацию. Содержимым адреса связи (К-элемента) является база адресуемого им узла.

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

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

этот описок.

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

- 2 8 -

ной информации. Характерным примером комбинированного испо­ льзования списков типа А и В являются гнездовые описки, в

которых составные части последовательности данных заданы в

виде списков типа А ( "гнёзд") , связанных в единую последо­ вательность адресами связи.

Ввиду ограниченного объёма настоящего пособия здесь

не рассматривается общая структура памяти ЭВМ.

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

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

Новым содержимым фиксатора становится адрес этого К-элемен-

та. Совместно с новым К-элементом в списке типа А размещает­ ся' либо включаемый элемент данных, либо адрес последнего.

При исключении элемента адрес связи из К-элемеита, указанно­

- 2 9 -

го фиксатором начала, заменяет прежнее содержимое фиксатора. Если неиспользуемые, резервные К-элементы фиксируются специ­

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

б) Массив. Массив может быть уподоблен иерархически упо­ рядоченному множеству, если в его подмножества высшего уров­

ня объединять все элементы с одинаковым первым индексом, а в составляющие их подмножества - элементы с одинаковым вторым

индексом и т.д.(последовательность рассмотрения индексов мо­ жет быть и обратной). Такое представление позволяет отобра­ зить массив на вектор памяти в виде последовательности эле- ■

ментов, имеющей в нашем восприятии сложную структуру: в ней

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

дующего уровня и т .д . Иерархия индексов может.быть задана

произвольно. Если старшинство индексов соответствует величи­

стной обработки элементов массива общие затраты на определе­ ние положения элементов в последовательности могут быть зяа-

- Зна­

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

Здесь нет умножений, а размерность массива определяет число адресных операций при доступе к элементу. Ячейка с адресом с фиксирует корень дерева.

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

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

Пронумеруем элементы каждого частного подмножества, на­ чиная с I . Положение любого элемента любого яруса в после­ довательности определяется тем, какие номера в соответству­ ющих частных подмножествах имеют элементы, лежащие на пути от корня к данному элементу, и его собственным частным но­ мером. Обозначим эти номера как i m , где Ш - номер яруса.

-31-

Тогда номер места в последовательности элемента, лежащего на (1 -м ярусе, определится по формуле Если последовательность построена с использованием списка

типа А или Б, возможно прямое обращение к любому элементу такого дерева по его индексам.

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

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

хранилищ идентификаторов, ибо именно в этом случае номера элементов - букв - в частных подмножествах легко определи­ мы, а для каждого узла дерева достаточно иметь 2 бита:

один-для выделения действительных элементов среди пустых,

другой - для выделения концевых букв идентификаторов.

§ 6 .Примеры операторов изменения средств выражения некоторых простейших абстрактных структур данных

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

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

Наиболее экономным по затратам времени способом пере-

можные значения этого числа равны I и П .

Действительно, при установке некоторой записи на окон­

чательное место в правильной последовательности типа А воз­

тельное место приведёт к перемещению "вакантной" позиции и стереотипному продолжению процесса перемещения записей.

Для получения начальной "вакантной" позиции одна из записей должна перемещаться в буфер, содержащий I позицию.

Цикл перемещений завершается установкой этой записи на окончательное место в правильной последовательности, задан­ ной списком типа А. Поскольку МО числа циклов перемещений рав­ ной? п, окончательно установленные записи должны помечаться специальным признаком (I бит). Для инициации следующего цикла перемещений отыскивается и перемещается в буфер пер­ вая непомеченная запись. Процесс перемещений завершается,

как только не останется ни одной непомечзнной записи.

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