4496

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

Лекция

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

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

Русский

2012-11-21

33.53 KB

36 чел.

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

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

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

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

Если последовательность однотипных элементов в памяти трактуется как двухмерный массив, расположенный по строкам, то адрес элемента (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 ;конец программы

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


 

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

48435. РИТОРИКА ЯК НАУКА І НАВЧАЛЬНА ДИСЦИПЛІНА. ПРЕДМЕТ РИТОРИКИ, ЇЇ ОСНОВНІ ПОНЯТТЯ, ЗАКОНИ 30.68 KB
  ПРЕДМЕТ РИТОРИКИ ЇЇ ОСНОВНІ ПОНЯТТЯ ЗАКОНИ План: Визначення риторики як науки і навчальної дисципліни. Мета курсу красномовства предмет риторики. Модуси публічного виступу основні поняття риторики. Етапи розвитку риторики.
48437. Политология в системе наук об обществе 41.71 KB
  Обобщая различные характеристики можно констатировать что политика это деятельность в сфере отношений между большими социальными группами классами нациями государствами по поводу обретения организации использования политической власти и управления социальными процессами в интересах реализации их общественнозначимых запросов и потребностей. Из этого определения вытекает и структура политики основными компонентами которой являются: политический интерес представляющий собой внутренний осознанный источник политического поведения...
48438. Найдавніші часи. Початки людської цивілізації на території України 723.91 KB
  Початки людської цивілізації на території України Історія України це наука що вивчає розвиток людського суспільства на території України та його закономірності. Джерела вивчення історії України: усні міфи легенди казки народні пісні; писемні літописи документи щоденники мемуари; речові залишки жител знаряддя праці посуд одяг; антропологічні залишки людських поховань; мовні явища які відображають процес розвитку мови; етнографічні побут і звичаї народу; фоно й фотодокументи.На територію сучасної України люди прийшли...
48439. Учет основных средств 52.38 KB
  УЧЕТ СТОИМОСТИ ОСНОВНЫХ СРЕДСТВ Основные средства переносят свою стоимость на готовый продукт постепенно в течение длительного времени охватывающего несколько производственно-технологических циклов. Поэтому учет основных средств и отражение их в балансе организованы таким образом чтобы одновременно можно было показать сохранение ими первоначальной вещной формы и постепенную потерю стоимости. Следует различать первоначальную остаточную восстановительную стоимость основных средств. Первоначальная стоимость отражает фактические затраты на...
48441. Прикметник як частина мови 38.59 KB
  Мета: навчальна' поглибити знання з теми прикметник як частини мови; навчити застосовувати їх у практичній діяльності навчити класифікувати прикметники виокремлювати їх з інших частин мови; розвивальна: розвивати мовне чуття студентів їхнє уміння сприймати й засвоювати новий матеріал вміння диференційовано підходити до аналізу мовних явищ; виховна: виховувати інтерес до мовного матеріалу. Студенти мають уміти: виділяти прикметники в окремі розряди вміти правильно використовувати ступеньовані форми. Якісні прикметники їх семантичні групи...
48442. Психологія особистості. Конспект лекцій 296.83 KB
  Каратьян Психологія особистості Конспект лекцій Видавництво: Ексмо 2008р. Проблема опису структури особистості ЛЕКЦІЯ № 3. Спори про верховенство впливів середовища і спадковості на розвиток особистості ЛЕКЦІЯ № 4. Уявлення про структуру особистості в різних психологічних теоріях.
48443. Социальная психология. Конспект лекций 137.87 KB
  Поскольку психологическая наука в нашей стране в определении своего предмета исходит из принципа деятельности можно условно обозначить специфику социальной психологии как изучение закономерностей поведения и деятельности людей обусловленных включением их в социальные группы а также психологических характеристик самих этих групп. Социальная психология изучает социальные группы в обществе. Большинство современных социальных психологов считают что социальная психология изучает и личность и группы и социальную психику но в определенном...