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

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

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

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

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

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

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

Вариант I

a_b       a_b+1                                      a_B

ï       ï        ï                                ï        ï

Вариант II

A_b   A_b+1   A_b+2    A_b+3                                 A_B

  ï     ï     ï     ï     ï                             ï     ï

        a_b                 a_b+3             a_B

Вариант III

a_b                  a_b+1                     a_B

  ï     ï                 ï     ï      ï         ï       ï    ï

l(a_b)                   l(a_b+1)                 l(a_B)

Рис. 3.1

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

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

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

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

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

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

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

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

f(a_i) = i - b + 1.

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

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

adr(a_i) = Z(A₀ + D*(f(a_i - 1)).

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

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

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

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

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

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

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

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

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

Рис. 3.2

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

или

.

Здесь b₁ и B₁ – границы для первого индекса, а b₂ и B₂ соответственно нижняя и верхняя граница для второго индекса. В этом случае адрес элемента определяется по формуле:

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