Массивы структур – таблицы
Упорядоченные таблицы
Работа с таблицей оказывается более эффективной, если элементы в ней некоторым образом упорядочены. Наиболее часто таблица упорядочивается по значению ключевого поля. Но не исключено и использование другого принципа упорядочивания, к примеру по частоте обращения к элементам таблицы и т. п. Упорядочивание таблицы и последующий поиск в ней производится методами, рассмотренными выше. Порядок выполнения этих и других операций с упорядоченной по значению ключа таблицей рассмотрим на следующем примере.
Пусть необходимо запомнить элементы таблицы информацией о 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;куда пересылать movcx.lenjnovs – . сколько пересылать repmevsb; пересылаем строку восстанавливаем регистры tabelement._tab 10 dup (<>) len_tab=$-tab buf buf_0ah<> key db 5 nrev element tab <>;предыдущий элемент Г element tab" <> временная переменная для сортировки .code leadi.tab lea si.buf.bufjn mov ex. 10 lea dx .buf movah.Oah push ds mh;вводим слова с клавиатуры в буфер buf -.сохраняем регистры……… intZlh move1, buf .lenjn mov [di].len.cl;длина слова › tab.length adddi,simv id repmovsb – . пересылка слова в элемент таблицы:восстанавливаем регистры……… adddi.type element_tab ;Упорядочиваем таблицу методом пузырьковой сортировки п-10 mov cx.n-1 mov si.1 @@сус11::внешний цикл – по 1 push ex subcx'.S! количество повторений внутреннего цикла push si временно сохраним 1 – теперь о=п mov si.n-1 @@cyc!2: push si movax.type element_tab mul si mov si.ax mov di.si sub di.type element_tab:в di адрес предыдущей записи mov al.[di].len cmp [si].len.al сравниваем последующий с предыдущим ja @@ml;обмениваем s_movsbx.[di].<type element_tab>:x=mas[j-l] s_movsb[di].[si].<type element_tab>;mas[j-l]"mas[j];mas[j]=x push ex mov ex.type element_tab:сколько пересылать mov di,si lea si.x юткуда пересылать repmovsb: пересылаем строку pop ex @@ml: pop si dec si:цикл по j с декрементом n-i раз loop @@cycl2 pop si inc si pop ex dec ex jcxz in2 jmp @@cycl 1 m2:;ищем элемент путем двоичного поиска :в si и di индексы первого и последнего элементов последней ; просматриваемой части последовательности; mov si.0 mov di.n-1 ;получим центральный индекс: cont_search: cmp si.di:проверка на окончание (неуспешное):si>di ja exit