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

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

Второй вариант неупорядоченного поиска

Программу первого варианта линейного поиска можно немного усовершенствовать вводом дополнительного элемента – барьера.

ПРОГРАММА prg27_430
//prg27_430 – программа на псевдоязыке линейного поиска в массиве (вариант 2).
//Вход: mas[n] – неупорядоченная последовательность двоичных значений длиной ri+1
; k – искомое значение
//Выход: i – позиция в mas[n] (0<i<n-l), соответствующая найденному символу.
ПЕРЕМЕННЫЕ
INT_BYTE n: //длина mas[n]
INT_BYTE mas[n+l]: //массив для поиска размерностью п+1 (О..п)
INT BYTE k: //искомый элемент
INT_WORD i=0 //индекс
НАЧ_ПРОГ
i: = 0: mas[n]: = k //установить барьер 52: ЕСЛИ (k==mas[i]) TO ПЕРЕЙТИ_НА _exit
1:-1+1: ПЕРЕЙТИ_НА s2 _exit: ЕСЛИ i>n TO ПЕРЕЙТИ_НА exit_error
//вывести значение i по месту требования exit_error:
//вывести сообщение об отсутствии элемента КОН_ПРОГ
:prg27_430 – программа на ассемблере линейного поиска в массиве (вариант 2).
.data
: задаем массив
mas db 50h. 08h. 52h. 06h. 90h. 17h. 89h. 27h. 65h. 42h. 15h. 51h. 61h.67h.76h.70h
n=$-mas
db Oh дополнительный элемент для барьера k db 15h
.code
xor si.si
mov al,k
mov mas[n].al:i: = 0: mas[n]: = k //установить барьер s2: cmpal.mas[si]
;ЕСЛИ k==mas[i] TO ПЕРЕЙТИ_НА _exit
je ok
inc si
jmps2;i:-1+l: ПЕРЕЙТИ_НА s2 ok: emp si,n:ЕСЛИ i>n TO ПЕРЕЙТИ_НА exit_error
je exit_error:вставить реакцию на удачный результат поиска
jmp exit exit_error:;реакция на неудачный результат поиска

Упорядоченный поиск

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

Двоичный поиск

Этот вид поиска (программа prg10_242.asm) предназначен для выполнения поиска в упорядоченном массиве (записей), содержащем N числовых ключей: kl < k2 < <-. <kN. Упорядоченный массив чисел 02h, 04h, 06h, 08h, 16h, 24h, 38h, 45h, 47h, 48h, 56h, 57h, 58h, 70h, 76h, 79h можно представить в виде двоичного дерева (Рис. 2.5).

Иллюстрированный самоучитель по задачам и примерам Assembler › Сложные структуры данных › Поиск в массивах
Рис. 2.5. Представление массива в виде двоичного дерева

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