книги из ГПНТБ / Зубов В.С. Математическое обеспечение цифровых вычислительных машин и систем учеб. пособие

-2 0 -

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

началом всех последовательностей будет общий элемент, име­ нуемый корнем. Уровнем или ярусом дерева будем именовать подмножество элементов, имеющих одинаковый номер в последо­ вательностях, называемый номером яруса. Последние элементы последовательностей называются листьями дерева. Листья мо­ гут представлять внешние по отношению к дереву структуры данных, т .е . иметь природу, отличную от природы других эле­ ментов дерева, называемых узлами или вершинами. Согласно нашему определению, любой узел , (а также корень) связан с несколькими узлами или листьями, следующими непосредствен­ но за ним в последовательностях и именуемыми его частным подмножеством. В двоичном дереве частные подмножества со­ держат не более, чем 2 элемента. Все элементы, следующие за некоторым узлом, образуют вместе с ним поддерево, корневой точкой которого является этот узел.

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

Структуры данных не подвергаются изменениям внутри ЭВМ лишь при простейшем использовании исходных данных. Для ши­ рокого круга задач обращение к данным по их месту в исход­

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

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

ичасто именуемыми таблицами. информационными массивами ищп

§4 .Структура оперативной памяти ЭВМ; её надстройка

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

-2 2 -

ДЛИНЫ, как их длины, так и адреса их начальной компоненты.

Некоторые единицы данных постоянной длины при этом также оказываются состоящими из нескольких компонент, например,

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

свою очередь, векторы более мелких адресуемых единиц.

Структуры более высокого уровня надстраиваются над этой базовой структурой памяти путём использования программ и

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

При наиболее общем рассмотрении следует,до-ввдимоцу,

различать 3 способа адресации: способы подразумеваемой,

прямой и косвенной адресации (классификация видов адресации в машинно-ориентированных языках более обширна). При под­

разумеваемой адресации местоположение операнда некоторым

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

манда. Такие операнда именуются буквальными или литералами.

На использование подразумеваемых адресов указывает либо спе­

-2 3 -

НОМврОМ адресуемого элемента памяти, где операнд размещён.

При косвенной адресации в коде команды указывается адрес

не самого операнда, а элемента, где хранится адрес операнда.

Назовём его К-элементом. Если множество К-элементов имеет

меньшую мощность, чем множество элементов адресуемой памяти,

применение косвенной адресации ведёт к сокращению длины ад­ ресной части команды. При обработке данных, расположенных в

памяти последовательно, одним и тем же блоком команд испо­

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

а) Относительная базовая адресация. Прямой адрес опреде­ ляет базу - начало (конец) отсчёта адресов, содержимое К-

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

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

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

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

При этом программа и обрабатываемые данные могут быть загру­ жены, возможно отдельными сегментами, в любые свободные зо­

ны памяти без переработки адресов в программе. Содержимое

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

Характерным случаем оовместного использования прямой и

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

и адреса, содержащегося внутри неё.

Реальное представление списка, под которым в общем олу-

чае понимается организованная совокупность последовательно­

стей, а чаще - единственная последовательность, определяет­ ся способом получения адресов его элементов. Рассмотрим

типичные случаи.

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

Следствием используемого способа задания адресов является возможность прямого обращения к элементам списка типа А по ах номерам и необходимость реорганизации списка при добавле-

-2 6 -

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

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

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

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

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

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

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

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

-2 7 -

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

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

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

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

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

этот описок.

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

- 2 8 -

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

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

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

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

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

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

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

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

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

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

- 2 9 -

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

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

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

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

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

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

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

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

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

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