4496

Двухмерные массивы. Типовые операции с массивами на языке ассемблер

Лекция

Информатика, кибернетика и программирование

Двухмерные массивы. Типовые операции с массивами на языке ассемблер С представлением одномерных массивов в программе на ассемблере и организацией их обработки все достаточно просто. А как быть если программа должна обрабатывать двухмерный массив? Вс...

Русский

2012-11-21

33.53 KB

31 чел.

Двухмерные массивы. Типовые операции с массивами на языке ассемблер

С представлением одномерных массивов в программе на ассемблере и организацией их обработки все достаточно просто. А как быть если программа должна обрабатывать двухмерный массив? Все проблемы возникают по-прежнему из-за того, что специальных средств для описания такого типа данных в ассемблере нет. Двухмерный массив нужно моделировать. На описании самих данных это почти никак не отражается — память под массив выделяется с помощью директив резервирования и инициализации памяти.

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

При этом вы вольны в выборе того, как понимать расположение элементов двухмерного массива в памяти: по строкам или по столбцам.

Если последовательность однотипных элементов в памяти трактуется как двухмерный массив, расположенный по строкам, то адрес элемента (i, j) вычисляется по формуле

(база + количество_элементов_в_строке * размер_элемента * i+j) 

Здесь i = 0...n–1 указывает номер строки, а j = 0...m–1 указывает номер столбца.

Например, пусть имеется массив чисел (размером в 1 байт) mas(i, j) с размерностью 4 на 4

(i= 0...3, j = 0...3):

23 04 05 67

05 06 07 99

67 08 09 23

87 09 00 08

В памяти элементы этого массива будут расположены в следующей последовательности:

23 04 05 67 05 06 07 99 67 08 09 23 87 09 00 08 

Если мы хотим трактовать эту последовательность как двухмерный массив, приведенный выше, и извлечь, например, элемент

mas(2, 3) = 23, то проведя нехитрый подсчет, убедимся в правильности наших рассуждений:

Эффективный адрес mas(2, 3) = mas + 4 * 1 * 2 + 3 = mas + 11 

Посмотрите на представление массива в памяти и убедитесь, что по этому смещению действительно находится нужный элемент массива.

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

  1.  сочетание прямого адреса, как базового компонента адреса, и двух индексных регистров для хранения индексов:

mov ax,mas[ebx][esi]

 

  1.  сочетание двух индексных регистров, один из которых является и базовым и индексным одновременно, а другой — только индексным:

mov ax,[ebx][esi]

В программе это будет выглядеть примерно так:

;Фрагмент программы выборки элемента

;массива mas(2,3) и его обнуления

.data

mas db

23,4,5,67,5,6,7,99,67,8,9,23,87,9,0,8

i=2

j=3

.code

...

mov si,4*1*i

mov di,j

mov al,mas[si][di] ;в al элемент mas(2,3)

...

В качестве законченного примера рассмотрим программу поиска элемента в двухмерном массиве чисел (листинг 5). Элементы массива заданы статически.

Листинг 5. Поиск элемента в двухмерном массиве

;prg_11_4.asm

MASM

MODEL small

STACK 256

.data

;матрица размером 2x5 — если ее не инициализировать,

;то для наглядности она может быть описана так:

;array dw 2 DUP (5 DUP (?))

;но мы ее инициализируем:

array dw 1,2,3,4,5,6,7,3,9,0

;логически это будет выглядеть так:

;array= {1 2}

; {3 4}

; {5 6}

; {7 3}

; {9 0}

elem dw 3 ;элемент для поиска

failed db 0ah,0dh,'Нет такого элемента в массиве!','$'

success db 0ah,0dh,'Такой элемент в массиве присутствует ','$'

foundtime db ? ;количество найденных элементов

fnd db ' раз(а)',0ah,0dh,'$'

.code

main:

mov ax,@data

mov ds,ax

xor ax,ax

mov si,0 ;si=столбцы в матрице

mov bx,0 ;bx=строки в матрице

mov cx,5 ;число для внешнего цикла (по строкам)

external:  ;внешний цикл по строкам

mov ax,array[bx][si] ;в ax первый элемент матрицы

push cx ;сохранение в стеке счётчика внешнего цикла

mov cx,2 ;число для внутреннего цикла (по столбцам)

mov si,0

iternal:  ;внутренний цикл по строкам

inc si  ;передвижение на следующий элемент в строке

;сравниваем содержимое текущего элемента в ax с искомым элементом:

cmp ax,elem

;если текущий совпал с искомым, то переход на here для обработки,

;иначе цикл продолжения поиска

je here

;иначе — цикл по строке cx=2 раз

 loop iternal

here:

jcxz move_next ;просмотрели строку?

 inc foundtime ;иначе увеличиваем счётчик совпавших

move_next:   ;продвижение в матрице

pop cx   ;восстанавливаем CX из стека (5)

add bx,1  ;передвигаемся на следующую строку

loop external ;цикл (внешний)

cmp foundtime,0h ;сравнение числа совпавших с 0

ja eql   ;если больше 0, то переход

not_equal: ;нет элементов, совпавших с искомым

mov ah,09h ;вывод сообщения на экран

 mov dx,offset failed

int 21h

 jmp exit ;на выход

eql: ;есть элементы, совпавшие с искомым

mov ah,09h ;вывод сообщений на экран

 mov dx,offset success

int 21h

mov ah,02h

mov dl,foundtime

add dl,30h

int 21h

mov ah,09h

mov dx,offset fnd

int 21h

exit:    ;выход

mov ax,4c00h ;стандартное завершение программы

int 21h

end main   ;конец программы

При анализе работы программы не забывайте, что в языке ассемблера принято элементы массива нумеровать с 0. При поиске определенного элемента массив просматривается от начала и до конца.

Приведенная программа сохраняет в поле foundtime количество вхождений искомого элемента в массив. В качестве индексных регистров используются si и bx.

Типовые операции с массивами

Для демонстрации основных приемов работы с массивами лучше всего подходят программы поиска или сортировки.

Рассмотрим одну такую программу, выполняющую сортировку массива по возрастанию (листинг 6).

Листинг 6. Сортировка массива

<1> ;prg_12_5.asm

<2> MASM

<3> MODEL small

<4> STACK 256

<5> .data

<6> mes1 db 0ah,0dh,'Исходный массив — $',0ah,0dh

<7> ;некоторые сообщения

<8> mes2 db 0ah,0dh,'Отсортированный массив — $',0ah,0dh

<9> n equ 9   ;количество элементов в массиве, считая с 0

<10> mas dw 2,7,4,0,1,9,3,6,5,8  ;исходный массив

<11> tmp dw 0  ;переменные для работы с массивом

<12> i dw 0

<13> j dw 0

<14> .code

<15> main:

<16> mov ax,@data

<17> mov ds,ax

<18> xor ax,ax

<19> ;вывод на экран исходного массива

<20> mov ah,09h

<21> lea dx,mes1

<22> int 21h   ;вывод сообщения mes1

<23> mov cx,10

<24> mov si,0

<25> show_primary: ;вывод значения элементов

<26> ;исходного массива на экран

<27> mov dx,mas[si]

<28> add dl,30h

<29> mov ah,02h

<30> int 21h

<31> add si,2

<32> loop show_primary

<33>

<34> ;строки 40-85 программы эквивалентны следующему коду на языке С:

<35> ;for (i=0;i<9;i++)

<36> ; for (j=9;j>i;j--)

<37> ; if (mas[i]>mas[j])

<38> ; {tmp=mas[i];

<39> ; mas[i]=mas[j];

<40> ; mas[j]=tmp;}

<41> mov i,0   ;инициализация i

<42> ;внутренний цикл по j

<43> internal:

<44> mov j,9   ;инициализация j

<45> jmp cycl_j  ;переход на тело цикла

<46> exchange:

<47> mov bx,i  ;bx=i

<48> shl bx,1

<49> mov ax,mas[bx] ;ax=mas[i]

<50> mov bx,j  ;bx=j

<51> shl bx,1

<52> cmp ax,mas[bx] ;mas[i] ? mas[j] — сравнение элементов

<53> jle lesser  ;если mas[i] меньше, то обмен не нужен и

 ;переход на продвижение далее по массиву

<54> ;иначе tmp=mas[i], mas[i]=mas[j], mas[j]=tmp:

<55> ;tmp=mas[i]

<56> mov bx,i  ;bx=i

<57> shl bx,1  ;умножаем на 2, так как элементы — слова

<58> mov tmp,ax  ;tmp=mas[i]

<59>

<60> ;mas[i]=mas[j]

<61> mov bx,j  ;bx=j

<62> shl bx,1  ;умножаем на 2, так как элементы — слова

<63> mov ax,mas[bx] ;ax=mas[j]

<64> mov bx,i  ;bx=i

<65> shl bx,1  ;умножаем на 2, так как элементы — слова

<66> mov mas[bx],ax ;mas[i]=mas[j]

<67>

<68> ;mas[j]=tmp

<69> mov bx,j  ;bx=j

<70> shl bx,1  ;умножаем на 2, так как элементы — слова

<71> mov ax,tmp  ;ax=tmp

<72> mov mas[bx],ax ;mas[j]=tmp

<73> lesser:   ;продвижение далее по массиву во внутреннем цикле

<74> dec j   ;j--

<75>;тело цикла по j

<76> cycl_j:

<77> mov ax,j  ;ax=j

<78> cmp ax,i  ;сравнить j ? i

<79> jg exchange ;если j>i, то переход на обмен

<80> ;иначе на внешний цикл по i

<81> inc i   ;i++

<82> cmp i,n   ;сравнить i ? n — прошли до конца массива

<83> jl internal ;если i

<85> ;вывод отсортированного массива

<86> mov ah,09h

<87> lea dx,mes2

<88> int 21h

<89> prepare:

<90> mov cx,10

<91> mov si,0

<92> show:   ;вывод значения элемента на экран

<93> mov dx,mas[si]

<94> add dl,30h

<95> mov ah,02h

<96> int 21h

<97> add si,2

<98> loop show

<99> exit:

<100> mov ax,4c00h ;стандартный выход

<101> int 21h

<102> end main ;конец программы

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


 

А также другие работы, которые могут Вас заинтересовать

63917. Различия в социально-психологической адаптации городской и сельской молодежи в период учебной деятельности в ВУЗе 47.5 KB
  Самой главной опасностью по признанию самих студентов является незнакомая среда в которой приезжий студент предоставлен сам себе. В студенческих общежитиях где проживает большинство приезжих студентов у ребят может отсутствовать место где они могут спокойно подготовиться к занятиям.
63918. Трансформация коммуникативных практик в контексте социокультурных изменений (на примере посткризисного региона Чечня) 76.5 KB
  Между тем изучение коммуникации посткризисного региона может помочь не только вникнуть в суть самого кризиса но и проникнуть в психологию общества ведь каждый человек и общество в целом отражает в коммуникации свое видение вещей. На сегодняшний день не существует ясности...
63919. Социальная солидарность и социальное отчуждение в перспективе общественного воспроизводства 69 KB
  Человек не способный понимать всего социально-экономического значения взаимной солидарности никогда не будет истинно свободным истинно честным и истинно благородным человеком. Такие понятия как социальная солидарность и социальное отчуждение достаточно знакомы нашему обществу...
63920. Влияние Интернета на социально-политические процессы в государстве: «твиттерные революции» в арабском мире 53 KB
  Вместе с этим меняются и методы воздействия на сознание людей и даже способы ведения войны. Продукт современной операции информационно-психологической войны это сводка новостей СМИ в формате журналистского репортажа...
63921. Государственная служба в современной России: природа, виды, проблемы регулирования 22.87 KB
  Среди задач которые необходимо решить в процессе реформирования социально-политической системы страны особое место занимает реформирование государственной службы. Цель реформирования повышение эффективности государственной службы в интересах развития гражданского общества...
63922. Черты немецкого характера в вербализации концепта «порядок» 85 KB
  Особое направление в лингвистике изучающее соотношения языка и сознания когнитивная лингвистика рассматривает каждый язык как познавательный механизм. Забегая вперёд мы предположим что существует и устойчивая ассоциативная связь между немецкий и порядок.
63923. Технология сдачи отчетности бухгалтером ООО «РусЕвроТех» 35.12 MB
  Формирование и сдача бухгалтерской налоговой и управленческой отчетности финансово-хозяйственной деятельности Компании. Формирование учетной и налоговой политики в соответствии с действующим законодательством и потребностями Компании...
63924. Защита коммерческой тайны ООО «Астра-ком» 526 KB
  Сегодня сведения связанные с коммерческой деятельностью приобретают безусловную ценность если они касаются конфиденциальной информации потенциального конкурента. Как известно в деловом мире сложились традиционные приемы и методы получения информации о клиентах.
63925. Проблема миграционной политики современной России 4.11 MB
  Таким образом, целью курсовой работы является проблема миграционной политики современной России. Для детального изучения данной цели мы выделяем следующие задачи для раскрытия темы: рассмотреть место России в международных миграционных процессах; исследовать методы управления миграционными потоками; дать характеристику политики в отношении возвращающихся мигрантов...