Иллюстрированный самоучитель по задачам и примерам Assembler

Массив. Описание массивов.

Все истинно великое совершается медленным, незаметным ростом.

Сенека

Как структура представления массив является упорядоченным множеством элементов определенного типа. Упорядоченность массива определяется набором целых чисел, называемых индексами, которые связываются с каждым элементом массива и однозначно определяют его расположение среди других элементов массива. Локализация конкретного элемента массива – ключевая задача при разработке любых алгоритмов, работающих с массивами. Ее сложность прямо зависит от размерности массива.

Наиболее просто представляются одномерные массивы. Соответствующая им структура хранения – это вектор. Она однозначна и представляет собой просто последовательное расположение элементов в памяти. Чтобы локализовать нужный элемент одномерного массива, достаточно знать его индекс. Так как ассемблер не имеет средств для работы с массивом как структурой данных, то для использования элемента массива необходимо вычислить его адрес. Для вычисления адреса i-ro элемента одномерного массива можно использовать формулу:

А_i=АБ+i*lеn.

Здесь АБ – адрес первого элемента массива размерностью n, i – индекс (i=0. .n-1), len – размер элемента массива в байтах. Заметьте, что при таком определении можно не говорить о типе элементов массива. В общем случае они также могут быть структурированными объектами данных.

Представление двумерных массивов немного сложнее. Здесь мы имеем случай, когда структуры хранения и представления различны. О структуре представления говорить излишне – это матрица. Структура хранения остается прежней – вектор. Но теперь его нельзя без специальных оговорок интерпретировать однозначно. Все зависит от того, как решил разработчик программы "вытянуть" массив – по строкам или по столбцам. Наиболее естествен порядок расположения элементов массива – по строкам. При этом наиболее быстро изменяется последний элемент индекса. К примеру, рассмотрим представление на логическом уровне двумерного массива Ац размерностью nxm, где 0 < i < n -I, 0 < j < m-1:

А₀₀ а₀₁ а₀₂ а₀₃
а₁₀ а₁₁ а₁₂ а₁₃
а₂₀ а₂₁ а₂₂ а₂₃
а₃₀ а₃₁ а₃₂ а_33.

Соответствующее этому массиву физическое представление в памяти – вектор – будет выглядеть так: а₀₀ а₀₁ а₀₂ а₀₃а₁₀ а₁₁ а₁₂ а₁₃а₂₀ а₂₁ а₂₂ а₂₃а₃₀ а₃₁ а₃₂ а_33.

Номер конкретного элемента массива в этой, уже как бы ставшей линейной, последовательности определяется адресной функцией, которая устанавливает положение (адрес) в памяти этого элемента исходя из значения его индексов: a_ij=n*i + j.

Для получения адреса элемента массива в памяти необходимо полученное значение умножить на размер элемента и сложить с базовым адресом массива.

Аналогично осуществляется локализация элементов в массивах большей размерности. На рис. 2.1 показан трехмерный массив Aijz размерностью n x m x к, где n = 4, m = 4, к = 2.

Рис. 2.1. Пример логической структуры трехмерного массива

Соответствующий этому массиву вектор памяти будет выглядеть так: а₁₂₀ а₀₀₀ а₀₀₁ а₀₁₀а₀₁₁а₀₂₀ а₀₂₁ а₀₃₀ а₀₃₁а₁₀₀ а₁₀₁ а₁₁₁ а₁₂₀ … а_331.

Соответственно номер элемента определяется так: a_ijz=n*m*i + m*j + z, где 0 < i < n-1, 0 < j < m-1, 0 < z < k-1.