Поиск в таблице - часть 6
Наглядный пример организации древовидной таблицы — расстановка слов в лексикографическом порядке. Эта операция выполняется с помощью лексикографических деревьев, понятие о которых приведено ниже — в разделе, посвященном деревьям. Там же приведен соответствующий пример.
Упорядоченные таблицы
Работа с таблицей оказывается более эффективной, если элементы в ней некоторым образом упорядочены. Наиболее часто таблица упорядочивается по значению ключевого поля. Но не исключено и использование другого принципа упорядочивания, к примеру по частоте обращения к элементам таблицы и т. п. Упорядочивание таблицы и последующий поиск в ней производится методами, рассмотренными выше. Порядок выполнения этих и других операций с упорядоченной по значению ключа таблицей рассмотрим на следующем примере.
Пусть необходимо запомнить элементы таблицы информацией о 10 словах, вводимых с клавиатуры. Длина слов — не более 20 символов. Структура элемента таблицы следующая: поле с количеством символов в слове; поле с самим словом. После ввода информации о словах необходимо упорядочить элементы таблицы по признаку длины слов. Затем вывести на экран элемент таблицы, содержащий первое из слов длиной 5 символов, удалить этот элемент из таблицы и вставить в нее новое слово, введенное с клавиатуры.
При такой постановке задачи нам придется решить весь комплекс проблем, возникающих при работе с упорядоченными таблицами.
:prg02_06.asm - программа на ассемблере демонстрации работы с упорядоченной таблицей
;Вход: 10 слов, вводимых с клавиатуры. Длина слов - не более 20 символов.
;Выход: вывод на экран элемента таблицы, содержащего первое из слов длиной 5 символов,
удаление этого элемента из таблицы и вставка в нее нового слова, введенного с
клавиатуры.
element tab struc
lendb 0 -.длина слова
simvjd db 20 dup (20h) :само слово
ends
0длина введенного слова (без учета 0dh) К db 21 dup (20h) -.буфер для ввода (с учетом 0dh)регистры
lea si.in_str -.откуда пересылать
Tea di out_str ;куда пересылать