В некоторых случаях имеет значение, как мы рассматриваем матрицу — как строку, элементами которой являются столбцы, или как столбец, элементами которого являются строки (чаще всего это проявляется при передаче матрицы в качестве фактического параметра подпрограмме, написанной на другом языке). Более распространенным является взгляд на матрицу как на структуру, представляющую столбец строк, то есть вектор, каждый элемент которого также является вектором, представляющим один ряд исходной матрицы. Такое представление матрицы называется ее развертыванием по строкам. Вообще говоря, массив любой размерности организован развертыванием по срокам, причем сначала массив рассматривается как вектор по первому индексу, и элементами этого вектора являются массивы, размерность которых на единицу меньше размерности исходного массива. Затем каждый из этих массивов на единицу меньшей размерности (для каждого элемента вектора) снова рассматривается как вектор по второму индексу (относительно исходного массива), причем размерности получившихся его элементов-массивов снова уменьшаются на единицу и т. д. Развертывание по столбцам — это такое представление матрицы, когда она рассматривается как одна строка, элементами которой являются столбцы.
|
253 |
6.1. Структурированные типы данных
Представление многомерного массива в памяти следует из представления вектора. В случае, если матрица развертывается по строкам, сначала располагаются объекты данных, представляющие первую строку, затем следуют объекты данных, входящие во вторую строку и т. д. В результате получается единый блок данных, организованный последовательно, в котором поочередно расположены все компоненты массива. Дескриптор массива отличается от дескриптора вектора только тем, что в случае массива требуется указание верхней и нижней границ диапазонов изменения индексов каждого измерения. На рис. 6.5 схематически изображено представление матрицы в памяти.
Рис. 6.5. Представление в памяти двухмерного массива
254
Глава 6. Инкапсуляция
Операция индексации использует формулу доступа для вычисления смещения местоположения компонента от базового адреса в массиве, аналогичную той, которая определена для векторов: для получения l-значения компонента A[I,J] сначала нужно определить количество строк, которые следует пропустить, (I-LB1), и умножить это число на длину строки, что даст местоположение начала строки с индексом I, а затем найти в этой строке компонент под номером J аналогично тому, как это делается для вектора. Таким образом, если А -матрица с М строками и N столбцами и А представлена при помощи развертывания по строкам, то местоположение элемента A[I, J] определяется следующим образом:
7-значение(А[I,J]) - а + (I - LB1) x S + CJ - LB2) x E
где а — базовый адрес; S — длина строки = (UB2 - LB2 + 1) x E; LBi — нижняя граница диапазона значений первого индекса; LB2, UB2 — нижняя и верхняя границы диапазона значений второго индекса.
Приведенную формулу можно упростить, выделяя постоянные члены при помощи следующих замен:
S = (UB2 - LB2 + 1) x E VO = a - LBi x S - LB2 x E 7-значение(А[I,J]) = VO+IxS + JxE
Как и в случае вектора, через Е обозначен размер каждого компонента, а через S — длина каждой строки матрицы. Это позволяет легко вычислить VO.
Обратите внимание на то, что VO, S, a и Е определяются еще при создании массива и, следовательно, их нужно вычислить только один раз и сохранить. Как и в случае вектора, VO является виртуальным начальным адресом и представляет собой местоположение в памяти компонента А[0, 0], если таковой существует в данном массиве. Тогда в самом худшем случае для доступа к компоненту массива придется провести следующее вычисление:
7-значение(А[I,J]) = VO+IxS + JxE
Массивы более высоких размерностей. Обобщение приведенных формул на случай массивов более высоких размерностей достаточно очевидно. Можно использовать следующий общий алгоритм для размещения дескрипторов при создании массива и для доступа к его элементам.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.