Иллюстрированный самоучитель по задачам и примерам Assembler

Поиск в массивах

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

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

:prg10_242.asm – программа на ассемблере двоичного поиска
;Вход: mas[n] – упорядоченная последовательность двоичных значений длиной N
: к – искомое значение
:Выход: 1 – позиция в mas[n] (0<i<n-l), соответствующая найденному символу.
.data
; задаем массив
masdb 02h.04h.06h.08h.16h.24h.38h.45h.47h.48h.57h.56h.58h.70h.76h.79h
n-$-mas
k db 4;искомое значение
.code
в si и di индексы первого и последнего элементов последней просматриваемой части
последовательности:
movsi.O.
mov di,n-l
хог ах. ах
nraval.k;искомое значение в ах cont_search:;получим центральный индекс:
cmpsi.di;проверка на окончание (неуспешное):si>di
ja exit_bad
mov bx.si
addbx.di
shr bx.l;делим на 2
cmpmas[bx].al сравниваем с искомым значением
je exit_good – искомое значение найдено
ja @@ml;mas[bx]>k
movsi.bx:mas[bx]<k:
inc si
jmpcont_search @@ml: movdi.bx
decdi
jmp cont_search exit_bad: пор:вывод сообщения об ошибке
exit_good: пор;вывод сообщения об успехе

Двоичный поиск очень эффективен для поиска в предварительно отсортированном массиве. Другая возможность представления двоичного дерева – список. В списке каждый узел, кроме уникального ключа, содержит информационную часть и ссылки на последующий и, возможно, предыдущий элементы списка.

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

Если Вы заметили ошибку, выделите, пожалуйста, необходимый текст и нажмите CTRL + Enter, чтобы сообщить об этом редактору.