Ассемблер под Windows для чайников. Часть 13
В прошлый раз мы познакомились с массивами и научились выводить простейший одномерный массив в окне программы. Сегодня — научимся производить поиск в массиве и сортировку элементов по их значению.
Сортировка элементов массива — достаточно сложная тема даже если речь идет о высокоуровневом языке. А уж если говорить об ассемблере, то здесь новички боятся сортировки как огня. Но лишь в самом начале. Потом приходит понимание вопроса, и выясняется, что бояться, собственно, и нечего. Остается лишь вопрос: что же было сложного в изучении сортировки? Основная сложность понимания сортировки — это цикл в цикле. Существует несколько основных способов сортировки, но все они состоят из вложенных один в один циклов. И вот, когда в учебнике или в ВУЗе вам ни с того ни с сего представляют к изучению такой двойной цикл, у вас сначала очень быстро глаза разбегаются, а потом достаточно медленно, но верно пропадает желание что-либо понимать. Чтобы такого не произошло, мы наглядно разобьем сортировку на два этапа, и, лишь детально изучив их по отдельности, соединим воедино. А до этого давайте пока в качестве развлечения быстренько научимся производить поиск! Что искать-то будем? Просто искать заданное значение неинтересно — мы этим уже занимались в 10-й и 11-й частях. Ну и что, что мы искали пробел в текстовой строке? Пробел — это вполне конкретное значение (20h), как и любой другой символ, а строка состоит как раз из нескольких элементов одного типа, так что представляет собой не что иное, как одномерный массив. Так что увольте, но искать определенное значение надо было раньше. Сейчас мы будем искать максимальное и минимальное значения в массиве.
Стратегия поиска такова:
1. Определяем две ячейки размером с элемент массива: одну под минимальное значение, вторую — под максимальное.
2. Помещаем в обе этих ячейки значение первого элемента массива.
3. Сравниваем в цикле каждый элемент массива (начиная уже со второго) с нашими минимумом и максимумом, и, если элемент больше максимума, заменяем им значение максимума, а если элемент окажется меньше минимума, заменяем им значение минимума. Возьмем за шаблон программу вывода массива из прошлого занятия и немного ее доработаем:
…
;секция данных
_cstatic db 'STATIC',0
_tmin db 'MIN:',0
_tmax db 'MAX:',0
mas db 123,23,3,4,5,0,0
hmas rd MASSIZE
hmin rd 1
hmax rd 1
…
;секция кода
…
.wmcreate:
;создаем поле под каждый элемент массива mas
;и помещаем дескриптор каждого поля в массив hmas
mov esi,5
mov edi,5
xor ebx,ebx
.create_cycl:
invoke CreateWindowEx,0,_cedit,0,WS_VISIBLE+WS_CHILD+WS_BORDER+ ES_READONLY+ ES_RIGHT,esi,edi,40,20,[hwnd],ebx,[wc.hInstance],0
test eax,eax
jz error
mov [hmas+ebx*4],eax
add esi,50
inc ebx
cmp ebx,MASSIZE
jne .create_cycl
;создаем другие элементы
invoke CreateWindowEx,0,_cstatic,_tmin,WS_VISIBLE+WS_CHILD+ES_RIGHT, 5,30,40,20,[hwnd],ebx,[wc.hInstance],0
invoke CreateWindowEx,0,_cedit,0,WS_VISIBLE+WS_CHILD+WS_BORDER+ ES_READONLY+ES_RIGHT,55,30,40,20,[hwnd],ebx,[wc.hInstance],0
test eax,eax
jz error
mov [hmin],eax
invoke CreateWindowEx,0,_cstatic,_tmax,WS_VISIBLE+WS_CHILD+ES_RIGHT, 105,30,40,20,[hwnd],ebx,[wc.hInstance],0
invoke CreateWindowEx,0,_cedit,0,WS_VISIBLE+WS_CHILD+WS_BORDER+ ES_READONLY+ES_RIGHT,155,30,40,20,[hwnd],ebx,[wc.hInstance],0
test eax,eax
jz error
mov [hmax],eax
.find_minmax:
mov al,[mas]
mov ah,al
mov ebx,1
.find_cycl:
cmp [mas+ebx],ah
jna @f
mov ah,[mas+ebx]
@@:
cmp [mas+ebx],al
jnb @f
mov al,[mas+ebx]
@@:
inc ebx
cmp ebx,MASSIZE
jne .find_cycl
mov word [mas+MASSIZE],ax
.out_mas:
;заполняем поля значениями элементов массива
xor ebx,ebx
.masout_cycl:
mov ah,[mas+ebx]
lea edi,[buf+BUFSIZE]
.dec:
mov al,ah
aam
or al,30h ;можно заменить на add al,30h
dec edi
mov byte [edi],al
test ah,ah
jnz .dec
invoke SendMessage,[hmas+ebx*4],WM_SETTEXT,0,edi
inc ebx
cmp ebx,MASSIZE+2
jne .masout_cycl
jmp .finish
…
Как вы могли заметить, и в mas, и в hmas внесено два дополнительных элемента. Причем в mas они добавлены явно, а в hmas — неявно, а как отдельные переменные hmin и hmax. Тем не менее, они определены сразу следом за hmas и условно считаются продолжением массива. Такое решение является оптимальным для вывода в окно значений минимума и максимума. Нам не придется отдельно вызывать преобразование значений элементов min и max — оно будет выполнено сразу в цикле вывода элементов массива. Только для этого следует при проверке окончания вывода указать значение MASSIZE+2, чтобы были выведены не только значения массива, но и два дополнительных элемента. Естественно, следует предварительно еще при создании окна создать поля для этих элементов и поместить их дескрипторы в соответствующие ячейки hmas, имеющие для удобства чтения кода личные псевдонимы — hmin и hmas. Это проще сделать сразу после цикла создания полей под элементы массива. Минимальное значение будет у нас сохраняться в AL, а максимальное — в AH. Поэтому перед началом поиска мы копируем значение первого элемента в AL и в AH. EBX мы будем использовать в качестве счетчика, поэтому загружаем в него единицу: mas+1 укажет как раз на второй элемент, с которого мы начнем сравнение. В цикле сравниваем очередной элемент с AH, и, если он не больше текущего максимума, то переходим к сравнению с минимумом. Иначе, если значение оказалось больше, помещаем его в AH. Подобным же образом поступаем с минимумом, только минимум заменяем значением текущего элемента лишь в случае, если элемент окажется меньше. Увеличиваем EBX, сравниваем его с количеством элементов, повторяем цикл, если еще не все элементы были проверены. По окончании поиска минимума и максимума нам необходимо сохранить их значения в два дополнительных байта за массивом: AL — по адресу mas+MASSIZE, AH — по адресу mas+MASSIZE+1. А лучше это сделать за один раз, сохранив двухбайтовый AX по адресу mas+MASSIZE. В таком случае содержимое AL уляжется по младшему адресу, а AH — по старшему точно так, как требуется. Вот и все. Остается только вывести все значения, а это мы уже умеем. Только не забудьте про MASSIZE+2.
Сделайте передышку. Если чего-то не поняли — перечитайте разок-другой. Теперь приступим к покорению алгоритмов сортировки. Существует много способов сортировки. Не знаю, имеет ли смысл сейчас рассматривать их все, но три базовых мы уж точно осилим. Начнем с метода сортировки прямым обменом. В народе его еще называют методом пузырьковой сортировки, потому что на каждом этапе наибольшее из еще несортированных значений как бы "всплывает" над меньшими. Это, конечно, в том случае, если сортировка производится в порядке возрастания значений, с коей мы и начнем. На первом этапе самое большое число занимает свое крайнее правое место, на втором — второе по значимости занимает второе место справа, на третьем — третье и т.д. Причем на каждом этапе не только самое большое из несортированных чисел становится на свое место, но и могут "всплывать" некоторые "пузырьки" чуть меньшего размера. Начнем с реализации первого этапа, а остальные потом просто повторим в цикле. Не волнуйтесь: все разберем детально и разложим по полочкам! Для того, чтобы самое большое число массива заняло крайнее правое место, нам необходимо будет выполнить небольшой цикл операций:
1. Обнуляем счетчик элементов, чтобы адрес [mas+счетчик] указывал на первый элемент массива.
2. Сравниваем текущий элемент (по адресу mas+счетчик) со следующим за ним, и, если выясняется, что текущий элемент имеет большее значение, чем следующий, то меняем местами текущий и следующий элементы. Если же текущий элемент не больше следующего (меньше или равен), то сразу переходим к третьему пункту.
3. Увеличиваем счетчик, и, если он еще не указывает на последний элемент (за последним элементом уже не будет следующего, с которым можно сравнивать текущий), повторяем цикл со второго пункта.
Если мы возьмем за шаблон программу, написанную в предыдущей части статьи, то для реализации первого этапа сортировки нам будет достаточно добавить кнопку "сортировка по возрастанию" и преобразовать вышеуказанный алгоритм в ассемблерный код обработки нажатия этой кнопки: …
ID_SV =1001
…
_cbutton db 'BUTTON',0
_tsvbut db 'Сортировать по возрастанию',0
…
cmp [wmsg],WM_COMMAND
je .wmcommand
…
.wmcommand:
cmp [wparam],ID_SV
je .sv
jmp .finish
.sv:
call Sortirovka
jmp .out_mas
…
proc Sortirovka
xor ebx,ebx
.cycl:
mov ah,[mas+ebx]
cmp ah,[mas+ebx+1]
jna .next
;если текущий элемент больше следующего
;меняем местами текущий и следующий
mov al,[mas+ebx+1]
mov word [mas+ebx],ax
.next:
inc ebx
cmp ebx,MASSIZE-1
jne .cycl
ret
endp
…
Здесь я вынес этап сортировки в отдельную процедуру (функцию), чтобы заодно напомнить вам, что в ассемблере также можно использовать вызовы функций, как и в высокоуровневых языках. Вставьте тело функции Sortirovka сразу за окончанием (endp) процедуры обработки сообщений WindowProc. Теперь при каждом нажатии на кнопку сортировки наибольший из еще несортированных элементов будет становиться на свое место. Убедитесь в этом, запустив программу и нажав несколько раз на кнопку сортировки. Для того, чтобы окончательно автоматизировать процесс сортировки, нам необходимо заставить этот цикл исполниться столько раз, сколько у нас элементов в массиве. Даже на один раз меньше ввиду того, что, когда все элементы, кроме последнего, будут стоять на своих местах, последний оставшийся уж точно будет стоять на своем месте. Для этого мы организуем внешний цикл, который будет повторять внутренний цикл на один раз меньше, чем количество элементов в массиве:
…
proc Sortirovka
mov ecx,MASSIZE-1
.cycl1:
xor ebx,ebx
.cycl2:
mov ah,[mas+ebx]
cmp ah,[mas+ebx+1]
jna .next
;если текущий элемент больше следующего
;меняем местами текущий и следующий
mov al,[mas+ebx+1]
mov word [mas+ebx],ax
.next:
inc ebx
cmp ebx,MASSIZE-1
jne .cycl2
loop .cycl1
ret
endp
…
Теперь наш массив будет верно отсортирован от начала до конца. Но наш способ еще далек от оптимального. Если после первого этапа сортировки крайний правый элемент заведомо находится на своем месте, а после второго — два крайних справа и т.д., то зачем нам каждый раз проверять весь массив полностью? Заменим команду cmp ebx,MASSIZE-1 на команду cmp ebx,ecx. Тогда получится, что в первый проход мы, как и раньше, остановимся на MASSIZE-1, затем команда loop уменьшит ECX, и на второй этап сортировки завершится при EBX=MASSIZE-2 и т.д. В последний раз будет проверена только одна пара (mas+0 и mas+1). Однако даже этот код все еще нуждается в оптимизации. Вдруг наш массив будет уже упорядочен или почти упорядочен? Например, если взять значения массива из прошлого занятия: 123,23,3,4,5. После первых двух проходов массив уже будет упорядочен, однако программа сделает после этого еще два прохода. Хорошо, когда массив небольшой, как в нашем примере, а если в нем будет тысяча элементов, и только два из них будут стоять не на своих местах — зачем нам делать лишних 997 циклических проходов? Надо что-то придумать, чтобы программа не совершала так много лишних действий. Мы можем с уверенностью сказать, что, если на одном из этапов не было сделано ни одной перестановки соседних элементов, то и на остальных этапах их не будет. Значит, если мы введем в ".cycl2" счетчик перестановок для каждого этапа, то после очередного прохода по нулевому значению этого счетчика мы сможем определить, что массив уже отсортирован.
…
proc Sortirovka
mov ecx,MASSIZE-1
.cycl1:
xor ebx,ebx
xor edx,edx
.cycl2:
mov ah,[mas+ebx]
cmp ah,[mas+ebx+1]
jna .next
mov al,[mas+ebx+1]
mov word [mas+ebx],ax
inc edx
.next:
inc ebx
cmp ebx,ecx
jne .cycl2
test edx,edx
loopnz .cycl1
ret
endp
…
Теперь наша процедура сортировки методом прямого обмена достаточно оптимизирована. Для выполнения сортировки по убыванию значений достаточно заменить jna .next на jnb .next. Как уже было сказано, кроме метода прямого обмена, существуют еще два базовых метода сортировки: метод прямого выбора и метод прямого включения. Суть метода сортировки прямым включением состоит в том, что на каждом этапе берется очередной элемент массива начиная со второго, и его местоположение ищется в левой части массива, которая считается уже отсортированной. Взятое значение включается в массив на свое законное место в отсортированной левой части. Если взятое значение и так находится на своем месте, то ничего никуда не сдвигаем, а берем следующее значение и т.д.
…
proc Sortirovka
mov esi,1
.cycl1:
push esi
.cycl2:
mov al,[mas+esi-1]
cmp al,[mas+esi]
jb .next
xchg al,[mas+esi]
dec esi ;двигаемся к началу массива
mov [mas+esi],al
jnz .cycl2
.next:
pop esi
inc esi ;двигаемся к концу массива
cmp esi,MASSIZE
jb .cycl1
ret
endp
…
По адресу [mas+esi] у нас будет числиться текущий "взятый" элемент, место включения которого мы ищем. Поэтому перед началом первого цикла мы поместим в ESI единицу, чтобы [mas+esi] изначально указывал на второй элемент массива. В первом цикле мы временно сохраняем очередную позицию текущего элемента — ESI, дабы не использовать под это дело два регистра, и сразу переходим к циклу номер два для включения элемента в отсортированную правую часть массива. Задвигаем в AL предыдущий элемент [mas+esi-1], сравниваем его с текущим. Если предыдущий оказался меньше текущего, значит, текущий элемент находится на своем месте, и можно переходить к поиску места следующего элемента. Иначе меняем местами текущий и предыдущий элементы, одновременно сдвигая указатель на текущий элемент на позицию влево (dec esi), чтобы продолжить поиск верного места для текущего элемента. На метке ".next:" мы восстанавливаем указатель на первый из несортированных элементов. Сдвигаем его вправо, так как после второго цикла он уже указывает на последний элемент отсортированной части. Проверяем, не весь ли массив мы уже отсортировали, и повторяем первый цикл, если сортировка еще не окончена. При сортировке методом прямого выбора на каждом этапе в правой несортированной части массива производится поиск минимального элемента, и его перемещение на место крайнего левого элемента несортированной части. То есть на первом этапе находим минимальный элемент во всем массиве и перемещаем его на первую позицию. На втором этапе ищем минимум в последовательности от второго элемента включительно до конца, найденное значение перемещаем на вторую позицию и т.д. В этот раз указатель на первый элемент несортированной части массива хранится в EDI, но это, как вы понимаете, не принципиально.
…
proc Sortirovka
mov edi,mas
mov ecx,MASSIZE
.cycl1:
lea ebx,[edi+ecx]
mov al,[edi]
.cycl2:
dec ebx
cmp al,[ebx]
jbe .next
xchg al,[ebx]
.next:
cmp ebx,edi
jnz .cycl2
mov [edi],al
inc edi
loop .cycl1
ret
endp
…
Перед циклом ".cycl2:" мы сохраняем в AL значение первого элемента текущей несортированной последовательности. В цикле мы сравниваем его со всеми элементами несортированной части начиная с последнего и, если находим элемент с еще меньшим значением, меняем местами AL и текущий элемент. После цикла мы сохраняем уже абсолютный минимум несортированной части, находящийся в AL, на место ее первого элемента (по адресу в EDI). Увеличиваем EDI, чтобы он указывал уже на следующий элемент, и повторяем ".cycl1:". Каждый из вышеупомянутых методов имеет свои плюсы и минусы, поэтому необходимо четко понять принцип действия каждого из них. В любом случае эти три метода являются лишь базовыми методами сортировки и не дают максимального быстродействия. Кроме базовых, существуют усовершенствованные методы сортировки. Но ввиду того, что наш курс и так может показаться достаточно сложным для чайников, я не стану здесь приводить эти методы. Однако я надеюсь, что, когда вы в достаточной мере освоите базу, вам не составит особого труда и самостоятельно разобраться с более навороченными методами, используя интернет или классические учебники по программированию.
Теперь давайте подготовимся к изучению динамических массивов, специфику которых мы рассмотрим подробнее в следующей части курса. Основное отличие динамического массива от статического в том, что в динамическом массиве число элементов может изменяться. Поэтому нам в первую очередь необходимо константу MASSIZE заменить переменной:
n dd MASSIZE
Теперь надо будет при обращении вместо константы MASSIZE к этой переменной не забывать брать ее в квадратные скобки, чтобы работать именно с ее значением, а не с адресом, по которому оно хранится. Учтите, что резервирование места под массив hmas следует оставить как есть. Мы не можем в качестве параметра директивы db или rd указать переменную. Также учтите, что, если мы, к примеру, будем переделывать процедуру сортировки "пузырек" для работы с динамическим массивом, то инициализацию счетчика ECX значением MASSIZE-1 придется заменить на:
mov ecx,[n]
dec ecx
Попробуйте теперь самостоятельно добавить в программу функцию удаления заданного элемента. Сделайте отдельное поле для ввода порядкового номера элемента. Только не забудьте убрать параметр ES_READONLY, иначе ввод будет запрещен. Создайте кнопку "удалить элемент", обработчик которой будет посылать этому полю сообщение WM_SETTEXT (первый параметр — количество символов, второй — буфер для текста), чтобы получить номер удаляемого элемента и преобразовывать символ из буфера в двоичное значение. И, конечно, напишите процедуру, которая будет удалять указанный элемент из массива со сдвигом остальных значений влево на позицию удаленного элемента. Попробуйте также удалить поле вывода удаляемого элемента и его дескриптор из массива hmas. Для удаления поля следует послать ему сообщение WM_CLOSE (параметры отсутствуют, так что пишем два нуля). Предусмотрите обработку ошибок, например, если введен неверный номер элемента или вообще не номер, а другой символ.
На этом я с вами прощаюсь. Удачи в разработке программы!
Все приводимые примеры были протестированы на правильность работы под Windows XP и, скорее всего, будут работать под другими версиями Windows, однако я не даю никаких гарантий их правильной работы на вашем компьютере. Исходные тексты программ вы можете найти на форуме: сайт
BarMentaLisk, SASecurity gr. q@sa-sec.org
Сортировка элементов массива — достаточно сложная тема даже если речь идет о высокоуровневом языке. А уж если говорить об ассемблере, то здесь новички боятся сортировки как огня. Но лишь в самом начале. Потом приходит понимание вопроса, и выясняется, что бояться, собственно, и нечего. Остается лишь вопрос: что же было сложного в изучении сортировки? Основная сложность понимания сортировки — это цикл в цикле. Существует несколько основных способов сортировки, но все они состоят из вложенных один в один циклов. И вот, когда в учебнике или в ВУЗе вам ни с того ни с сего представляют к изучению такой двойной цикл, у вас сначала очень быстро глаза разбегаются, а потом достаточно медленно, но верно пропадает желание что-либо понимать. Чтобы такого не произошло, мы наглядно разобьем сортировку на два этапа, и, лишь детально изучив их по отдельности, соединим воедино. А до этого давайте пока в качестве развлечения быстренько научимся производить поиск! Что искать-то будем? Просто искать заданное значение неинтересно — мы этим уже занимались в 10-й и 11-й частях. Ну и что, что мы искали пробел в текстовой строке? Пробел — это вполне конкретное значение (20h), как и любой другой символ, а строка состоит как раз из нескольких элементов одного типа, так что представляет собой не что иное, как одномерный массив. Так что увольте, но искать определенное значение надо было раньше. Сейчас мы будем искать максимальное и минимальное значения в массиве.
Стратегия поиска такова:
1. Определяем две ячейки размером с элемент массива: одну под минимальное значение, вторую — под максимальное.
2. Помещаем в обе этих ячейки значение первого элемента массива.
3. Сравниваем в цикле каждый элемент массива (начиная уже со второго) с нашими минимумом и максимумом, и, если элемент больше максимума, заменяем им значение максимума, а если элемент окажется меньше минимума, заменяем им значение минимума. Возьмем за шаблон программу вывода массива из прошлого занятия и немного ее доработаем:
…
;секция данных
_cstatic db 'STATIC',0
_tmin db 'MIN:',0
_tmax db 'MAX:',0
mas db 123,23,3,4,5,0,0
hmas rd MASSIZE
hmin rd 1
hmax rd 1
…
;секция кода
…
.wmcreate:
;создаем поле под каждый элемент массива mas
;и помещаем дескриптор каждого поля в массив hmas
mov esi,5
mov edi,5
xor ebx,ebx
.create_cycl:
invoke CreateWindowEx,0,_cedit,0,WS_VISIBLE+WS_CHILD+WS_BORDER+ ES_READONLY+ ES_RIGHT,esi,edi,40,20,[hwnd],ebx,[wc.hInstance],0
test eax,eax
jz error
mov [hmas+ebx*4],eax
add esi,50
inc ebx
cmp ebx,MASSIZE
jne .create_cycl
;создаем другие элементы
invoke CreateWindowEx,0,_cstatic,_tmin,WS_VISIBLE+WS_CHILD+ES_RIGHT, 5,30,40,20,[hwnd],ebx,[wc.hInstance],0
invoke CreateWindowEx,0,_cedit,0,WS_VISIBLE+WS_CHILD+WS_BORDER+ ES_READONLY+ES_RIGHT,55,30,40,20,[hwnd],ebx,[wc.hInstance],0
test eax,eax
jz error
mov [hmin],eax
invoke CreateWindowEx,0,_cstatic,_tmax,WS_VISIBLE+WS_CHILD+ES_RIGHT, 105,30,40,20,[hwnd],ebx,[wc.hInstance],0
invoke CreateWindowEx,0,_cedit,0,WS_VISIBLE+WS_CHILD+WS_BORDER+ ES_READONLY+ES_RIGHT,155,30,40,20,[hwnd],ebx,[wc.hInstance],0
test eax,eax
jz error
mov [hmax],eax
.find_minmax:
mov al,[mas]
mov ah,al
mov ebx,1
.find_cycl:
cmp [mas+ebx],ah
jna @f
mov ah,[mas+ebx]
@@:
cmp [mas+ebx],al
jnb @f
mov al,[mas+ebx]
@@:
inc ebx
cmp ebx,MASSIZE
jne .find_cycl
mov word [mas+MASSIZE],ax
.out_mas:
;заполняем поля значениями элементов массива
xor ebx,ebx
.masout_cycl:
mov ah,[mas+ebx]
lea edi,[buf+BUFSIZE]
.dec:
mov al,ah
aam
or al,30h ;можно заменить на add al,30h
dec edi
mov byte [edi],al
test ah,ah
jnz .dec
invoke SendMessage,[hmas+ebx*4],WM_SETTEXT,0,edi
inc ebx
cmp ebx,MASSIZE+2
jne .masout_cycl
jmp .finish
…
Как вы могли заметить, и в mas, и в hmas внесено два дополнительных элемента. Причем в mas они добавлены явно, а в hmas — неявно, а как отдельные переменные hmin и hmax. Тем не менее, они определены сразу следом за hmas и условно считаются продолжением массива. Такое решение является оптимальным для вывода в окно значений минимума и максимума. Нам не придется отдельно вызывать преобразование значений элементов min и max — оно будет выполнено сразу в цикле вывода элементов массива. Только для этого следует при проверке окончания вывода указать значение MASSIZE+2, чтобы были выведены не только значения массива, но и два дополнительных элемента. Естественно, следует предварительно еще при создании окна создать поля для этих элементов и поместить их дескрипторы в соответствующие ячейки hmas, имеющие для удобства чтения кода личные псевдонимы — hmin и hmas. Это проще сделать сразу после цикла создания полей под элементы массива. Минимальное значение будет у нас сохраняться в AL, а максимальное — в AH. Поэтому перед началом поиска мы копируем значение первого элемента в AL и в AH. EBX мы будем использовать в качестве счетчика, поэтому загружаем в него единицу: mas+1 укажет как раз на второй элемент, с которого мы начнем сравнение. В цикле сравниваем очередной элемент с AH, и, если он не больше текущего максимума, то переходим к сравнению с минимумом. Иначе, если значение оказалось больше, помещаем его в AH. Подобным же образом поступаем с минимумом, только минимум заменяем значением текущего элемента лишь в случае, если элемент окажется меньше. Увеличиваем EBX, сравниваем его с количеством элементов, повторяем цикл, если еще не все элементы были проверены. По окончании поиска минимума и максимума нам необходимо сохранить их значения в два дополнительных байта за массивом: AL — по адресу mas+MASSIZE, AH — по адресу mas+MASSIZE+1. А лучше это сделать за один раз, сохранив двухбайтовый AX по адресу mas+MASSIZE. В таком случае содержимое AL уляжется по младшему адресу, а AH — по старшему точно так, как требуется. Вот и все. Остается только вывести все значения, а это мы уже умеем. Только не забудьте про MASSIZE+2.
Сделайте передышку. Если чего-то не поняли — перечитайте разок-другой. Теперь приступим к покорению алгоритмов сортировки. Существует много способов сортировки. Не знаю, имеет ли смысл сейчас рассматривать их все, но три базовых мы уж точно осилим. Начнем с метода сортировки прямым обменом. В народе его еще называют методом пузырьковой сортировки, потому что на каждом этапе наибольшее из еще несортированных значений как бы "всплывает" над меньшими. Это, конечно, в том случае, если сортировка производится в порядке возрастания значений, с коей мы и начнем. На первом этапе самое большое число занимает свое крайнее правое место, на втором — второе по значимости занимает второе место справа, на третьем — третье и т.д. Причем на каждом этапе не только самое большое из несортированных чисел становится на свое место, но и могут "всплывать" некоторые "пузырьки" чуть меньшего размера. Начнем с реализации первого этапа, а остальные потом просто повторим в цикле. Не волнуйтесь: все разберем детально и разложим по полочкам! Для того, чтобы самое большое число массива заняло крайнее правое место, нам необходимо будет выполнить небольшой цикл операций:
1. Обнуляем счетчик элементов, чтобы адрес [mas+счетчик] указывал на первый элемент массива.
2. Сравниваем текущий элемент (по адресу mas+счетчик) со следующим за ним, и, если выясняется, что текущий элемент имеет большее значение, чем следующий, то меняем местами текущий и следующий элементы. Если же текущий элемент не больше следующего (меньше или равен), то сразу переходим к третьему пункту.
3. Увеличиваем счетчик, и, если он еще не указывает на последний элемент (за последним элементом уже не будет следующего, с которым можно сравнивать текущий), повторяем цикл со второго пункта.
Если мы возьмем за шаблон программу, написанную в предыдущей части статьи, то для реализации первого этапа сортировки нам будет достаточно добавить кнопку "сортировка по возрастанию" и преобразовать вышеуказанный алгоритм в ассемблерный код обработки нажатия этой кнопки: …
ID_SV =1001
…
_cbutton db 'BUTTON',0
_tsvbut db 'Сортировать по возрастанию',0
…
cmp [wmsg],WM_COMMAND
je .wmcommand
…
.wmcommand:
cmp [wparam],ID_SV
je .sv
jmp .finish
.sv:
call Sortirovka
jmp .out_mas
…
proc Sortirovka
xor ebx,ebx
.cycl:
mov ah,[mas+ebx]
cmp ah,[mas+ebx+1]
jna .next
;если текущий элемент больше следующего
;меняем местами текущий и следующий
mov al,[mas+ebx+1]
mov word [mas+ebx],ax
.next:
inc ebx
cmp ebx,MASSIZE-1
jne .cycl
ret
endp
…
Здесь я вынес этап сортировки в отдельную процедуру (функцию), чтобы заодно напомнить вам, что в ассемблере также можно использовать вызовы функций, как и в высокоуровневых языках. Вставьте тело функции Sortirovka сразу за окончанием (endp) процедуры обработки сообщений WindowProc. Теперь при каждом нажатии на кнопку сортировки наибольший из еще несортированных элементов будет становиться на свое место. Убедитесь в этом, запустив программу и нажав несколько раз на кнопку сортировки. Для того, чтобы окончательно автоматизировать процесс сортировки, нам необходимо заставить этот цикл исполниться столько раз, сколько у нас элементов в массиве. Даже на один раз меньше ввиду того, что, когда все элементы, кроме последнего, будут стоять на своих местах, последний оставшийся уж точно будет стоять на своем месте. Для этого мы организуем внешний цикл, который будет повторять внутренний цикл на один раз меньше, чем количество элементов в массиве:
…
proc Sortirovka
mov ecx,MASSIZE-1
.cycl1:
xor ebx,ebx
.cycl2:
mov ah,[mas+ebx]
cmp ah,[mas+ebx+1]
jna .next
;если текущий элемент больше следующего
;меняем местами текущий и следующий
mov al,[mas+ebx+1]
mov word [mas+ebx],ax
.next:
inc ebx
cmp ebx,MASSIZE-1
jne .cycl2
loop .cycl1
ret
endp
…
Теперь наш массив будет верно отсортирован от начала до конца. Но наш способ еще далек от оптимального. Если после первого этапа сортировки крайний правый элемент заведомо находится на своем месте, а после второго — два крайних справа и т.д., то зачем нам каждый раз проверять весь массив полностью? Заменим команду cmp ebx,MASSIZE-1 на команду cmp ebx,ecx. Тогда получится, что в первый проход мы, как и раньше, остановимся на MASSIZE-1, затем команда loop уменьшит ECX, и на второй этап сортировки завершится при EBX=MASSIZE-2 и т.д. В последний раз будет проверена только одна пара (mas+0 и mas+1). Однако даже этот код все еще нуждается в оптимизации. Вдруг наш массив будет уже упорядочен или почти упорядочен? Например, если взять значения массива из прошлого занятия: 123,23,3,4,5. После первых двух проходов массив уже будет упорядочен, однако программа сделает после этого еще два прохода. Хорошо, когда массив небольшой, как в нашем примере, а если в нем будет тысяча элементов, и только два из них будут стоять не на своих местах — зачем нам делать лишних 997 циклических проходов? Надо что-то придумать, чтобы программа не совершала так много лишних действий. Мы можем с уверенностью сказать, что, если на одном из этапов не было сделано ни одной перестановки соседних элементов, то и на остальных этапах их не будет. Значит, если мы введем в ".cycl2" счетчик перестановок для каждого этапа, то после очередного прохода по нулевому значению этого счетчика мы сможем определить, что массив уже отсортирован.
…
proc Sortirovka
mov ecx,MASSIZE-1
.cycl1:
xor ebx,ebx
xor edx,edx
.cycl2:
mov ah,[mas+ebx]
cmp ah,[mas+ebx+1]
jna .next
mov al,[mas+ebx+1]
mov word [mas+ebx],ax
inc edx
.next:
inc ebx
cmp ebx,ecx
jne .cycl2
test edx,edx
loopnz .cycl1
ret
endp
…
Теперь наша процедура сортировки методом прямого обмена достаточно оптимизирована. Для выполнения сортировки по убыванию значений достаточно заменить jna .next на jnb .next. Как уже было сказано, кроме метода прямого обмена, существуют еще два базовых метода сортировки: метод прямого выбора и метод прямого включения. Суть метода сортировки прямым включением состоит в том, что на каждом этапе берется очередной элемент массива начиная со второго, и его местоположение ищется в левой части массива, которая считается уже отсортированной. Взятое значение включается в массив на свое законное место в отсортированной левой части. Если взятое значение и так находится на своем месте, то ничего никуда не сдвигаем, а берем следующее значение и т.д.
…
proc Sortirovka
mov esi,1
.cycl1:
push esi
.cycl2:
mov al,[mas+esi-1]
cmp al,[mas+esi]
jb .next
xchg al,[mas+esi]
dec esi ;двигаемся к началу массива
mov [mas+esi],al
jnz .cycl2
.next:
pop esi
inc esi ;двигаемся к концу массива
cmp esi,MASSIZE
jb .cycl1
ret
endp
…
По адресу [mas+esi] у нас будет числиться текущий "взятый" элемент, место включения которого мы ищем. Поэтому перед началом первого цикла мы поместим в ESI единицу, чтобы [mas+esi] изначально указывал на второй элемент массива. В первом цикле мы временно сохраняем очередную позицию текущего элемента — ESI, дабы не использовать под это дело два регистра, и сразу переходим к циклу номер два для включения элемента в отсортированную правую часть массива. Задвигаем в AL предыдущий элемент [mas+esi-1], сравниваем его с текущим. Если предыдущий оказался меньше текущего, значит, текущий элемент находится на своем месте, и можно переходить к поиску места следующего элемента. Иначе меняем местами текущий и предыдущий элементы, одновременно сдвигая указатель на текущий элемент на позицию влево (dec esi), чтобы продолжить поиск верного места для текущего элемента. На метке ".next:" мы восстанавливаем указатель на первый из несортированных элементов. Сдвигаем его вправо, так как после второго цикла он уже указывает на последний элемент отсортированной части. Проверяем, не весь ли массив мы уже отсортировали, и повторяем первый цикл, если сортировка еще не окончена. При сортировке методом прямого выбора на каждом этапе в правой несортированной части массива производится поиск минимального элемента, и его перемещение на место крайнего левого элемента несортированной части. То есть на первом этапе находим минимальный элемент во всем массиве и перемещаем его на первую позицию. На втором этапе ищем минимум в последовательности от второго элемента включительно до конца, найденное значение перемещаем на вторую позицию и т.д. В этот раз указатель на первый элемент несортированной части массива хранится в EDI, но это, как вы понимаете, не принципиально.
…
proc Sortirovka
mov edi,mas
mov ecx,MASSIZE
.cycl1:
lea ebx,[edi+ecx]
mov al,[edi]
.cycl2:
dec ebx
cmp al,[ebx]
jbe .next
xchg al,[ebx]
.next:
cmp ebx,edi
jnz .cycl2
mov [edi],al
inc edi
loop .cycl1
ret
endp
…
Перед циклом ".cycl2:" мы сохраняем в AL значение первого элемента текущей несортированной последовательности. В цикле мы сравниваем его со всеми элементами несортированной части начиная с последнего и, если находим элемент с еще меньшим значением, меняем местами AL и текущий элемент. После цикла мы сохраняем уже абсолютный минимум несортированной части, находящийся в AL, на место ее первого элемента (по адресу в EDI). Увеличиваем EDI, чтобы он указывал уже на следующий элемент, и повторяем ".cycl1:". Каждый из вышеупомянутых методов имеет свои плюсы и минусы, поэтому необходимо четко понять принцип действия каждого из них. В любом случае эти три метода являются лишь базовыми методами сортировки и не дают максимального быстродействия. Кроме базовых, существуют усовершенствованные методы сортировки. Но ввиду того, что наш курс и так может показаться достаточно сложным для чайников, я не стану здесь приводить эти методы. Однако я надеюсь, что, когда вы в достаточной мере освоите базу, вам не составит особого труда и самостоятельно разобраться с более навороченными методами, используя интернет или классические учебники по программированию.
Теперь давайте подготовимся к изучению динамических массивов, специфику которых мы рассмотрим подробнее в следующей части курса. Основное отличие динамического массива от статического в том, что в динамическом массиве число элементов может изменяться. Поэтому нам в первую очередь необходимо константу MASSIZE заменить переменной:
n dd MASSIZE
Теперь надо будет при обращении вместо константы MASSIZE к этой переменной не забывать брать ее в квадратные скобки, чтобы работать именно с ее значением, а не с адресом, по которому оно хранится. Учтите, что резервирование места под массив hmas следует оставить как есть. Мы не можем в качестве параметра директивы db или rd указать переменную. Также учтите, что, если мы, к примеру, будем переделывать процедуру сортировки "пузырек" для работы с динамическим массивом, то инициализацию счетчика ECX значением MASSIZE-1 придется заменить на:
mov ecx,[n]
dec ecx
Попробуйте теперь самостоятельно добавить в программу функцию удаления заданного элемента. Сделайте отдельное поле для ввода порядкового номера элемента. Только не забудьте убрать параметр ES_READONLY, иначе ввод будет запрещен. Создайте кнопку "удалить элемент", обработчик которой будет посылать этому полю сообщение WM_SETTEXT (первый параметр — количество символов, второй — буфер для текста), чтобы получить номер удаляемого элемента и преобразовывать символ из буфера в двоичное значение. И, конечно, напишите процедуру, которая будет удалять указанный элемент из массива со сдвигом остальных значений влево на позицию удаленного элемента. Попробуйте также удалить поле вывода удаляемого элемента и его дескриптор из массива hmas. Для удаления поля следует послать ему сообщение WM_CLOSE (параметры отсутствуют, так что пишем два нуля). Предусмотрите обработку ошибок, например, если введен неверный номер элемента или вообще не номер, а другой символ.
На этом я с вами прощаюсь. Удачи в разработке программы!
Все приводимые примеры были протестированы на правильность работы под Windows XP и, скорее всего, будут работать под другими версиями Windows, однако я не даю никаких гарантий их правильной работы на вашем компьютере. Исходные тексты программ вы можете найти на форуме: сайт
BarMentaLisk, SASecurity gr. q@sa-sec.org
Компьютерная газета. Статья была опубликована в номере 35 за 2008 год в рубрике программирование
