Массив, как простейшая программно-реализуемая структура данных

Страницы работы

Содержание работы

Лекция 3. МАССИВ, КАК ПРОСТЕЙШАЯ ПРОГРАММНО-РЕАЛИЗУЕМАЯ СТРУКТУРА ДАННЫХ

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

Одномерный массив – конечный, упорядоченный набор однородных элементов. Упорядоченность предполагает, что все элементы массива имеют номера, которые их однозначно идентифицируют. Свойство однородности предусматривает принадлежность элементов к одному типу данных. Над одномерным массивом можно выполнять две базовые операции:

-  извлечение элемента из массива,

-  помещение элемента в массив.

Исходным параметром для обеих операций является индекс элемента массива. Наименьшее  и наибольшее значения индекса массива b и B называется соответственно нижней и верхней границей индекса. Размер массива равен B - b + 1. При реализации одномерных массивов обычно массиву в памяти ЭВМ отводится B - b + 1 последовательных участков памяти   (рис 3.1а). Практически все языки

Вариант I

ab       ab+1                                      aB

ï       ï        ï                                ï        ï

Вариант II

Ab   Ab+1   Ab+2    Ab+3                                 AB

  ï     ï     ï     ï     ï                             ï     ï

        ab                 ab+3             aB

Вариант III

ab                  ab+1                     aB

  ï     ï                 ï     ï      ï         ï       ï    ï

l(ab)                   l(ab+1)                 l(aB)

Рис. 3.1

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

Можно привести ряд других вариантов структуры хранения одномерного массива :

вариант 1 - выделение B - b + 1 последовательно расположенных участков одинаковой длины для хранения элементов массива ai (рис 3.1а);

вариант 2 - хранение адресных ссылок Ai на поля, где расположены элементы массива ai (рис 3.1б), которые в этом случае уже не обязательно занимают непрерывный участок памяти;

вариант 3 - выделение B - b + 1 последовательных участков памяти переменной длины с заголовками, содержащими по крайней мере значения l(ai) длины поля занимаемого соответствующим элементом.

В первом и последнем вариантах имеет место последовательная структура хранения одномерного массива, а во втором – последовательная структура хранения для адресов элементов. В большинстве случаев последовательная структура хранения позволяет организовать к элементу путем непосредственного вычисления его адреса по индексу. При этом используется либо вычисляемый адрес непосредственно либо, как в случае варианта 2, сохраняемый в памяти адрес. Но в том и другом случае такой подход опирается на использование функции адресации.

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

Для одномерного массива естественной функцией адресации является следующая:

f(ai) = i - b + 1.

При фиксированной длине элементов массива это позволяет свести операции выбора и размещения элемента ai к операциям над соответствующим типом данных с базовым адресом

adr(ai) = A0 + d*(f(ai - 1), или для структуры хранения, использующей второй вариант:

adr(ai) = Z(A0 + D*(f(ai - 1)).

В приведенных формулах использовались следующие обозначения:

A0  – адрес последовательной области хранения соответственно либо для значений массива, либо для сохраняемых адресов;

D,d – длина ячейки для хранения соответственно либо указателей на элементы массива, либо самих элементов;

Z(а) - значение указателя, расположенного в ячейке с адресом а.

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

При этом логическая концепция структуры данных изменяется, а физическая может оставаться прежней, то есть последовательной структурой хранения. Двумерный массив представляет собой логическую структуру данных удобную для программирования и решения задач, которые описывают объекты двумерные физически. Полезен он бывает и для организации набора значений, зависящих от двух целочисленных параметров. Так как память ЭВМ имеет линейную организацию, за счет использования концепции функции адресации в большинстве случаев для двумерных массивов используется последовательная структура хранения. При этом компилятор является посредником между физическим представлением данных и их логической моделью (рис. 3.2).

            Структура                    Логическая              

ЭВМ       хранения      Компилятор      модель        Прикладной

                                        стр. Данных     программист

Рис. 3.2

Естественный вид функции адресации для двумерного массива aij c   ,   :

или

.

Здесь b1 и B1 – границы для первого индекса, а b2 и B2 соответственно нижняя и верхняя граница для второго индекса. В этом случае адрес элемента определяется по формуле:

Аналогично определяются массивы с более высокими размерностями. В качестве упражнения предлагается построить функцию адресации для k-мерного массива с нижней границей 0 по всем индексам и с верхней границей Bi по i-ому индексу массива.

Похожие материалы

Информация о работе