Поиск в массивах
Поиск информации является одной из самых распространенных проблем, с которыми сталкивается программист в процессе написания программы. Правильное решение задачи поиска для каждого конкретного случая позволяет значительно повысить эффективность исполнения программы. Для общего случая обычно предполагается, что поиск ведется среди массива записей определенной структуры. В каждой записи есть уникальное ключевое поле. Абстрагируясь, можно сказать, что массив записей – это массив ключевых полей. В этом случае задачу поиска в массиве записей можно свести к задаче поиска в массиве ключевых слов. В этом разделе мы обсудим проблему поиска в массивах и пути ее решения.
В отличие от методов сортировки классификация методов поиска не отличается особым разнообразием. Уверенно можно сказать, что методы поиска будут различными для упорядоченных и неупорядоченных массивов. Неупорядоченными массивами здесь считаются массивы, о порядке следования элементов которых нельзя сделать никаких предположений. Для таких массивов особых способов поиска нет, кроме как последовательно просматривать все их элементы. В теории такой поиск называется линейным. Если элементы массивов каким-то образом отсортированы, то речь идет об упорядоченных массивах и для поиска в них существует определенный набор методов. В следующих разделах мы рассмотрим ассемблерную реализацию наиболее интересных методов поиска, применяемых в тех случаях, когда ключевое поле – некоторое число.
Большой интерес представляют методы поиска в строке, которые рассматриваются в главе 4. И наконец, существует третий класс методов поиска, основанный на арифметическом преобразовании исходных ключей – "хэшировании". Эти методы мы рассмотрим в разделе "Поиск в таблице".
Неупорядоченный поиск
Для выполнения неупорядоченного (линейного) поиска нет определенных методов. Чтобы эффективно реализовать эту операцию, необходимо умело использовать средства языка программирования. Если поиск ведется в массиве чисел (а не записей с числовым ключевым полем), то наибольшей эффективности для реализации линейного поиска в программе на языке ассемблера можно достичь, если использовать цепочечные команды. Поэтому мы рассмотрим варианты реализации линейного поиска, предполагая, что массив, в котором ведется поиск, на самом деле является массивом записей и использование цепочечных команд не представляется возможным. Для вставки приведенных ниже фрагментов в свои реальные программы вы должны скорректировать соответствующие смещения.
Первый вариант неупорядоченного поиска
Этот вариант программы реализации линейного поиска предполагает обычный перебор до тех пор, пока не будет найден нужный элемент или не будут перебраны все элементы.
ПРОГРАММА prg27_429 //prg27_429 – программа на псевдоязыке линейного поиска в массиве (вариант 1). //Вход: mas[n] – неупорядоченная последовательность двоичных значений длиной n: k – искомое значение //Выход: 1 – позиция в mas[n] (0<i<n-l), соответствующая найденному символу. ПЕРЕМЕННЫЕ INT_BYTE n: //длина mas[n] INTJSYTE mas[n]: //массив для поиска размерностью п (О..п-l) INTJYTE к; //искомый элемент INT_W0RD 1-0 //индекс НАЧ_ПРОГ s2: ЕСЛИ (k==mas[i]) TO ПЕРЕЙТИ_НА _exit ЕСЛИ (i=<n) TO ПЕРЕЙТИ_НА s2 _exit: //вывести значение 1 по месту требования КОН_ПРОГ :prg27_429.asm – программа на ассемблере линейного поиска в массиве (вариант 1). .data : задаем массив mas db 50h.08h.52h.06h.90h.17h,89h.27h.65h.42h.15h.51h.61h.67h.76h.70h n=$-mas k db 15h .code xorsi.si;1-(s1): = 0 mov al,k s2: cmpal.mas[si];ЕСЛИ k==mas[i] TO ПЕРЕЙТИ_НА _exit je ok inc si:i: = i+l cmpsi,n-l:ЕСЛИ i=<n TO ПЕРЕЙТИ_НА s2 jbes2:реакция на неудачный результат поиска jmp exit ok::реакция на удачный результат поиска jmpexit