Работа с массивами и стеком на языке ассемблера
Общие сведения о массивах
Как структура представления, массив является упорядоченным множеством элементов определенного типа. Упорядоченность массива определяется набором целых чисел, называемых индексами, которые связываются с каждым элементом массива и однозначно конкретизируют его расположение среди других элементом массива. Локализация конкретного элемента массива - ключевая задача при разработке любых алгоритмов, работающих с массивами.
Наиболее просто представляются одномерные массивы. Соответствующая им структура хранения — это вектор. Она однозначна и есть не что иное, как просто последовательное расположение элементов в памяти. Чтобы локализовать нужный элемент одномерного массива, достаточно знать его индекс. Так как ассемблер не имеет средств для работы с массивом как структурой данных, то для доступа к элементу массива необходимо вычислить его адрес.
Представление двумерных массивов немного сложнее. Здесь мы имеем случай, когда структуры хранения и представления различны. О структуре представления говорить излишне — это матрица. Структура хранения остается прежней — вектор. Но теперь его нельзя без специальных оговорок интерпретировать однозначно. Все зависит от того, как решил разработчик программы «вытянуть» массив — по строкам или по столбцам. Наиболее естествен порядок расположения элементов массива — по строкам. При этом наиболее быстро изменяется последний элемент индекса.
Вывод массива
Пример вывода массива:
;процедура вывода без знакового двухзначного элемента массива
out_elem proc far; AX – входной параметр, т.е. элемент массива
pusha;помещаем основные регистры в стек
div ten; после деления первая цифра в AL, а вторая в AH
mov dx,ax; сохраним первую и вторую цифры
mov ah,0Eh
mov bh,00h; обнулим регистр
mov al,dl; первую цифру отправляем в AL
add al,'0'; получаем ASCII символ цифры
int 10h; вывод цифры на экран, вызовом соответствующего прерывания
mov al,dh
add al,'0'
int 10h; вывод второй цифры
popa
ret
out_ elem endp
…
;вызов процедуры в цикле для вывода всех значений массива
xor si,si;обнуляем счетчик
mov cx,n; n – размерность массива
out_massiv:
xor ax,ax
mov AL,Z[si]; Z – исходный массив
call out_elem;
inc si
loop massiv
…
Способы сортировки массивов.
Метод пузырька
Процедура bubble_sort
; сортирует массив слов методом пузырьковой сортировки
; ввод: DS:DI = адрес массива
; DX = размер массива (в словах)
bubble_sort proc near
pusha
cld
cmp dx,1
jbe sort_exit; выйти, если сортировать нечего
dec dx
sb_loop1:
mov cx,dx; установить длину цикла
xor bx,bx; BX будет флагом обмена
mov si,di; SI будет указателем на
; текущий элемент
sn_loop2:
lodsw; прочитать следующее слово
cmp ax,word ptr [si]
jbe no_swap; если элементы не
; в порядке,
xchg ax,word ptr [si]; поменять их местами
mov word ptr [si-2],ax
inc bx; и установить флаг в 1,
no_swap:
loop on_loop2
cmp bx,0; если сортировка не закончилась,
jne sn_loop1; перейти к следующему элементу
sort_exit:
popa
ret
bubble_sort endp
Пузырьковая сортировка осуществляется так медленно потому, что сравнения выполняются лишь между соседними элементами. Чтобы получить более быстрый метод сортировки перестановкой, следует выполнять сравнение и перестановку элементов, отстоящих далеко друг от друга. На этой идее основан алгоритм, который называется «быстрая сортировка». Он работает следующим образом: делается предположение, что первый элемент является средним по отношению к остальным. На основе такого предположения все элементы разбиваются на две группы - больше и меньше предполагаемого среднего. Затем обе группы отдельно сортируются таким же методом. В худшем случае быстрая сортировка массива из N элементов требует N2 операций, но в среднем случае - только 2n*log2n сравнений и еще меньшее число перестановок.
Метод быстрой сортировки:
; Процедура quick_sort
; сортирует массив слов методом быстрой сортировки
; ввод: DS:BX = адрес массива
; DX = число элементов массива
quicksort proc near
cmp dx,1; Если число элементов 1 или 0,
jle qsort_done; то сортировка уже закончилась
xor di,di; индекс для просмотра сверху (DI = 0)
mov si,dx; индекс для просмотра снизу (SI = DX)
dec si; SI = DX-1, так как элементы нумеруются с нуля,
shl si,1; и умножить на 2, так как это массив слов
mov ax,word ptr [bx]; AX = элемент X1, объявленный средним
step_2:; просмотр массива снизу, пока не встретится
; элемент, меньший или равный Х1
cmp word ptr [bx][si],ax; сравнить XDI и Х1
jle step_3; если XSI больше,
sub si,2; перейти к следующему снизу элементу
jmp short step_2; и продолжить просмотр
step_3:; просмотр массива сверху, пока не встретится
; элемент меньше Х1 или оба просмотра не придут
; в одну точку
cmp si,di; если просмотры встретились,
je step_5; перейти к шагу 5,
add di,2; иначе: перейти
; к следующему сверху элементу,
cmp word ptr [bx][di],ax; если он меньше Х1,
jl step_3; продолжить шаг 3
steр_4:
; DI указывает на элемент, который не должен быть
; в верхней части, SI указывает на элемент,
; который не должен быть в нижней. Поменять их местами
mov cx,word ptr [bx][di]; CX = XDI
xchg cx,word ptr [bx][si]; CX = XSI, XSI = XDI
mov word ptr [bx][di],cx; XDI = CX
jmp short step_2
step_5:; Просмотры встретились. Все элементы в нижней
; группе больше X1, все элементы в верхней группе
; и текущий - меньше или равны Х1 Осталось
; поменять местами Х1 и текущий элемент:
xchg ах,word ptr [bx][di]; АХ = XDI, XDI = X1
mov word ptr [bx],ax; X1 = AX
; теперь можно отсортировать каждую из полученных групп
push dx
push di
push bx
mov dx,di; длина массива X1...XDI-1
shr dx,1; в DX
call quick_sort; сортировка
pop bx
pop di
pop dx
add bx,di; начало массива XDI+1...XN
add bx,2; в BX
shr di,1; длина массива XDI+1...XN
inc di
sub dx,di; в DX
call quicksort; сортировка
qsort_done: ret
quicksort endp
Кроме того, что быстрая сортировка - самый известный пример алгоритма, использующего рекурсию, то есть вызывающего самого себя. Это еще и самая быстрая из сортировок «на месте», то есть сортировка, использующая только ту память, в которой хранятся элементы сортируемого массива. Можно доказать, что сортировку нельзя выполнить быстрее, чем за n*log2n операций, ни в худшем, ни в среднем случаях; и быстрая сортировка достаточно хорошо приближается к этому пределу в среднем случае. Сортировки, достигающие теоретического предела, тоже существуют — это сортировки турнирным выбором и сортировки вставлением в сбалансированные деревья, но для их работы требуется резервирование дополнительной памяти Так что, например, работа со сбалансированными деревьями будет происходить медленно из-за дополнительных затрат на поддержку сложных структур данных в памяти.
Примеры обработки массивов:
;1) Переменной Max присвоить значение максимального элемента одномерного массива.
.model small; задание модели памяти
.stack 200h; задание сегмента стека размером 512 байт
.data; начало сегмента данных
; выделение 10 байт под массив из 5 элементов (по 2 байта
; каждый) с начальной инициализацией
A dw 5 dup (5,2,8,3,1)
Max dw?; выделение 2 байт под переменную
MaxStr dw?; значение Max в символьном виде
db ‘$’; символ конца строки
.code; начало сегмента кода
Begin:
mov ax, @Data; настройка регистра сегмента данных
mov ds, ax
mov ax, A
mov Max, ax
; в регистр si заносится смещение элемента массива относительно
; базового адреса массива(т.к. один элемент массива занимает
; 2 байта, то для второго элемента смещение равно 2 байтам,
; для третьего элемента - 4 байтам и т.д.)
mov si, 2
; команда цикла loop работает с регистром сх, в который
; заносится необходимое количество итераций
mov cx, 4
for_cycle: mov ax, A[si]; команде дано символическое имя - метка for_cycle
cmp ax, Max
jle do_else
mov Max, ax
do_else: add si, 2
loop for_cycle
;вывод значения переменной Max на экран (для примера считаем
;Max числом, состоящим из одного знака)
add ax, 48; получаем код символа значения Max
mov MaxStr, ax
mov dx, offset MaxStr
mov ax, 09h
int 21h
mov ax, 4C00h; корректное завершение программы
int 21h
end Begin
;2) Задан массив A[N] из элементов типа Byte (целое 8-разрядное без знака).
; Составить программу нахождения максимального и минимального элемента.
; Разместить индексы минимального и максимального элемента в отдельных ячейках
; памяти. Подсчитать среднее арифметическое минимума и максимума.
; Индекс максимального элемента разместим в ячейке IndMax, а индекс;минимального элемента разместим в ячейке IndMin.
;Среднее арифметическое минимума и
; максимума разместим в ячейке Mean.
.model small
.386
.stack 100h
.data
N dw 10; Размерность массива.
A db 3, 120, 2, 6, 11, 5, 4, 34, 15, 10
IndMax dw?; Номер максимального элемента в A.
IndMin dw?; Номер минимального элемента в A.
Mean db?; Среднее арифметическое минимума и максимума.
.code
;процедура очистки экрана
cls_all proc;
pusha
mov ax,0003h;устанавливаем графический режим 03h (80х25)
int 10h; вызываем соответствующее прерывание
popa
ret
cls_all endp
Start:
mov ax, @data
mov ds, ax
mov si, 0; Инициализируем счётчик цикла.
mov ch, -128; Инициализируем максимальное значение массива.
mov cl, 127; Инициализируем минимальное значение массива.
M1: mov al, A[si]
cmp al, ch; Поиск максимума.
jle M2
mov ch, al; Текущий элемент больше максимума.
mov IndMax, si; Запоминаем его номер.
inc IndMax; Корректировка номера, т.к. si=i-1.
M2: cmp al, cl; Поиск минимума.
jge M3
mov cl, al; Текущий элемент меньше минимума.
mov IndMin, si; Запоминаем его номер.
inc IndMin; Корректировка номера, т.к. si=i-1.
M3: inc si; Команды завершения тела цикла.
cmp si, N
jb M1
; Ищем среднее арифметическое минимума(CL) и максимума(CH).
mov al, cl; AL = Min
add al, ch; AL = Min+Max
shr al, 1; AL = AL / 2 среднее арифметическое.
mov Mean, al; Записываем результат.
mov ax, 4c00h
int 21h
end Start
