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 ;конец программы

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


 

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

81329. Повернення виконавчого документу до суду або іншого органу (посадовій особі), який його видав 22.35 KB
  Виконавчий документ прийнятий державним виконавцем до виконання повертається до суду який його видав у разі відновлення судом строку для подання апеляційної скарги на рішення за яким видано виконавчий документ та прийняття такої апеляційної скарги до розгляду крім виконавчих документів що підлягають негайному виконанню.
81330. Оголошення розшуку боржника, дитини та розшуку транспортних засобів боржника 26.22 KB
  Підставами для оголошення розшуку є відсутність в ході виконавчого провадження відомостей про місце проживання місцезнаходження боржника його майна а також дитини. У разі відсутності відомостей про місце проживання місцезнаходження боржника за виконавчими документами про стягнення аліментів...
81331. Поворот виконання 28.31 KB
  Поворот виконання це спосіб захисту майнових прав відповідача який полягає у поверненні позивачем стягувачем відповідачу боржнику всього одержаного за скасованим рішенням. Загальних правил які б передбачали поворот виконання немає що примушує знову звертатися до процесуального процедурного чи іншого законодавства яке передбачає винесення і виконання юрисдикційного рішення яке підлягає виконанню у порядку ст. Питання про поворот виконання вирішує суд який переглядає судові рішення постанови і до компетенції якого входить...
81332. Виконавчий збір 28.08 KB
  Виконавчий збір не стягується із страховиків які здійснюють державне обовязкове особисте страхування при виконанні державними виконавцями рішень про стягнення коштів за державним обовязковим особистим страхуванням та з осіб звільнених від його сплати згідно з законодавством а також за виконавчими документами про конфіскацію майна стягнення періодичних платежів стягнення виконавчого збору накладення арешту на майно для забезпечення позовних вимог. Постанова про стягнення виконавчого збору виноситься при першому надходженні виконавчого...
81333. Витрати на здійснення виконавчих дій та їх види 26.9 KB
  До інших витрат на організацію виконавчих дій належать витрати на виплату винагороди державним виконавцям відповідно до статті 47 Закону; придбання службових житлових приміщень; придбання службових приміщень; страхування державних виконавців; забезпечення державних виконавців форменим одягом
81334. Розподіл стягнутих з боржника грошових сум і черговість задоволення вимог стягувачів 27.72 KB
  Розподіл стягнутих державним виконавцем з боржника за виконавчим провадженням грошових сум у тому числі одержаної від реалізації майна боржника здійснюється у такому порядку: у першу чергу повертається авансовий внесок сторін та інших осіб на організацію та проведення виконавчих дій...
81335. Закінчення та відновлення виконавчого провадження 27.23 KB
  Про закінчення виконавчого провадження державний виконавець виносить постанову, яка затверджується начальником відповідного органу державної виконавчої служби. Копія постанови у триденний строк надсилається сторонам та суду або іншому органу (посадовій особі), які видали виконавчий документ, або за належністю до іншого органу державної виконавчої служби
81337. Порядок звернення стягнення на грошові кошти та інше майно боржника 28.14 KB
  Звернення стягнення на майно боржника полягає в його виявленні шляхом надіслання запитів до органів державної податкової інспекції банків дорожньої автомобільної інспекції бюро технічної інвентаризації нотаріату тощо описі арешті вилученні та примусовій реалізації. Стягнення за виконавчими документами в першу чергу звертається на кошти боржника в гривнях та іноземній валюті інші цінності в тому числі кошти на рахунках та вкладах боржника в установах банків та інших кредитних організаціях на рахунки в цінних паперах у депозитаріях...