Действия с матрицами
Рассмотренные выше операции над массивами были реализованы исходя из предположения, что массивы имеют одну размерность. Но существует группа задач, в которой работа осуществляется с массивами большей размерности. Прежде всего это действия с матрицами. Кстати, такая структура данных, как сеть (или граф) представляется с помощью матрицы.
Транспонирование прямоугольной матрицы
Приемы работы с массивами размерностью больше 1 удобно рассматривать на типовой задаче, например, такой как транспонирование матрицы.
Суть задачи транспонирования матрицы А = {аij} заключается в замене строк столбцами и столбцов строками в соответствии с формулой а 'ij= аij, где а 'ij – элементы транспонированной матрицы А' = {аij}. Максимальная величина индексов i и j задается константами m (количество строк) и т (количество столбцов), соответственно диапазон их значений составляет: i = 0..m-1, j ~ 0..n-1. Элементы матрицы задаются статически – в сегменте данных.
Выше уже отмечалось то, каким образом производится локализация в памяти элемента многомерного массива исходя из его логического номера при условии, что размерность элементов – 1 байт. Локализация элемента матрицы А относительно базового адреса производится по формуле: аij = n*i+j. (2.1)
Соответствующий элемент в транспонируемой матрице будет расположен по адресу: A'ij-m*i+j. (2.2)
Например, рассмотрим матрицу 3x4:
02h 04h 06h 08h 16h 24h 38h 45h 47h 48h 57h 56h
Эта матрица в памяти будет выглядеть так:
02h. 04h, 06h. 08h. 16h. 24h. 38h. 45h. 47h. 48h, 57h. 56h
Транспонированный вариант матрицы:
02h 16h 47h 04h 24h 48h 06h 38h 57h 08h 45h 56h
Транспонированный вариант матрицы в памяти будет выглядеть следующим образом:
02h. 16h. 47h. 04h. 24h. 48h. 06h. 38h, 57h. 08h. 45h. 56h
Для решения задачи "в лоб" по формулам 1 и 2 требуется выделять в памяти область для хранения транспонированной матрицы, совпадающую по размеру с исходной.
;prg29_102.asm – программа на ассемблере транспонирования матрицы. :Вход: mas[n] – матрица mxn. :Выход: _mas[n] – транспонированная матрица nxm. .data m dw 3: i =0.. 2 n dw 4;j=0..3 :задаем матрицу 3x4 (mxn): mas db 02h.04h.06h.08h.l6h.24h,38h.45h.47h,48h.57h,56h s_mas=$-mas _mas db sjnas dup (Offh) temp db 0 'code' mov cx.m xorsi.si:i: = 0 ml: push ex:цикл по i xordiidi;J:-0 локализуем masij по формуле: masij=n*i+j m2: mov ax.n mul si предполагаем, что результат в рамках ах add ax.di: n*i+j mov bx.ax mov al,mas[bx] movtemp.al локализуем место-приемник в jnasij по формуле: _masij=masji=m*i+j mov ax.m mul di предполагаем, что результат в рамках ах add ax,si mov al.temp mov _mas[bx].al incdi:j: = j+l loop rn2 inc si pop ex восстанавливаем счетчик внешнего цикла loop ml
Отметим, что для транспонирования прямоугольной матрицы необязательно ее моделировать так, как это сделано в предыдущей программе. Кнут приводит соотношение, которое позволяет транспонировать матрицу в линейном порядке, зная только значения тип. Для этого используется соотношение, при котором значение из ячейки i (для 0<i<N = mn-1) исходной матрицы переводится в ячейку m*x (mod N) транспонированной матрицы.