Сборник по задачам и примерам Assembler


Поиск в таблице - часть 8


inc si

jmpcont_search @@m3: pop bx :1

mov di .bx

dec di

jmp cont_search @@m4: movax.type element_tab

mul si

mov si.ax

: конец поиска - в si адрес элемента таблицы со словом длиной 5 байт :выводим его на экран :преобразуем длину в символьный вид:

mov al, [si]. Ten

хог ex.ex

movcl.al ;длина для movsb

aam

or ах. ;в ах длина в символьном виде

mov buf. 1 en_buf.ah

mov buf .lerMn.al push si :сохраним указатель на эту запись

add si .simvjd

lea di .buf.buf_in rep movsb

mov byte ptr [di].'$' :конец строки для вывода 09h (int 21h) :теперь выводим:

lea dx.buf

mov ah.09h

int 21h

:удаляем запись pop si :-i- восстановим указатель на удаляемую запись

mov di .si

add si .type element_tab

mov cx.len_tab

sub ex.si ;в сх сколько пересылать rep movsb :обнуляем последнюю запись

xor al .al

mov ex.type element_tab rep stosb

:вводим слово с клавиатуры: insert: ;вводим слово с клавиатуры lea dx.buf mov ah.0ah int21h :c помощью линейного поиска ищем место вставки, в котором выполняется условие buf.1еn_

in=<[si].Ten

lea si.tab

mov al .buf.len_in @@m5: emp al,[si].Ten

jbe @@m6

add si .type element_tab

jmp @@m5

@@m6: push si сохраняем место вставки :раздвигаем таблицу, последний элемент теряется

add si.type element_tab

mov cx.len_tab

sub ex.si ;сколько пересылать std

lea si .tab

add si , lentab

mov di.si

sub si.type element_tab rep movsb eld

;формируем и вставляем новый элемент pop di восстанавливаем место вставки :обнуляем место вставки push di

хог al .al

mov ex.type element_tab rep stosb popdi

lea si ,buf .bufjn

mov cl .buf .lenjn

mov [di].len,cl

add di ,simv_id rep movsb

Таблицы с вычисляемыми входами

Ранее мы отмечали, что скорость доступа к элементам таблицы зависит от двух факторов — способа организации поиска нужного элемента и размера таблицы. Для маленьких таблиц любой метод доступа будет работать быстро. С ростом размера таблицы выбор способа организации доступа приходится производить прежде всего исходя из критерия скорости локализации нужного элемента таблицы. Элементы таблицы отличаются друг от друга уникальным значением ключевого поля. При этом ключевыми могут являться не только одно, но и несколько полей элемента таблицы. Ключ, в том числе и символьный, в памяти представляется последовательностью двоичных байт. Исходя из того что ключ уникален, соответствующая двоичная последовательность также будет уникальной. А нельзя ли использовать это уникальное значение ключа для вычисления адреса местоположения элемента в таблице? Оказывается, можно, а в ряде приложений это оказывается очень эффективно, так как в идеальном случае доступ к нужному элементу таблицы осуществляется всего за одно обращение к памяти. С другой стороны, на практике часто возникает необходимость размещения элементов таблицы с достаточно большим диапазоном возможных значений ключевого поля, в то время как программа реально использует лишь небольшое подмножество значений этих ключей. Например, значение ключевого поля может быть в диапазоне 0..3999, но задача постоянно использует не более 50 значений. В этом случае крайне неэффективным было бы резервировать память для таблицы размером в 4000 элементов, а реально использовать чуть больше 1 % отведенной для нее памяти. Гораздо лучше иметь возможность воспользоваться некоторой процедурой, отображающей задействованное пространство ключей на таблицу размером, близким к значению 50. Большинство подобных задач решается с использованием методики, называемой хэшированием. Ее основу составляют различные алгоритмы отображения значения ключа в значение адреса размещения элемента в таблице. Непосредственное преобразование ключа в адрес производится с помощью функций расстановки, или хэш-функций. Адреса, получаемые из ключевых слов с помощью хэш-функций, называются хэш-адресами. Таблицы, для работы с которыми используются методы хеширования, называются таблицами с вычисляемыми входами, хэш-таблицами, или таблицами с прямым доступом.




Начало  Назад  Вперед



Книжный магазин