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

-18-

ниыаемый характер упорядоченности множества объектов и дос­ тупа к отдельным его объектам (вне связи с "физической"

упорядоченностью описывающих их данных и средствами их хра­ нения и обработки). Рассмотрим их примеры.

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

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

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

разбиение строки на части, поэлементное сравнение строк.

Массив - это множество элементов, расположенных таким образом, что упорядоченное множество целых чисел ( индексов)

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

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

-1 9 -

ру уравнений, их систем ), имеющих, зачастую, физическую сущ­

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

его положением, но положение элемента в массиве обычно пол­

ностью определяет его роль в вычислительном процессе. К та­

ким элементам можно применить лишь небольшое количество про­ стых операций: сравнение, арифметические операции. Иногда

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

щихся к тому же объекту.

Очередь и магазин представляют собой динамические по

составу и размеру структуры данных, соответствующие строке.

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

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

Стеком назовём динамическую структуру, отличающуюся от магазина лишь тем, что в стеке доступ к любому элементу при чтении осуществляется как в векторе (одномерном массиве),

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

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

-2 0 -

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

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

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

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

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

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

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

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

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

-2 2 -

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

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

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

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

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

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

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

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

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

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

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

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

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

-2 3 -

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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