Сборник по задачам и примерам Assembler
Односвязные списки - часть 6
:ищеи ячейку, подлежащую удалению ;1 - выбираем первую ячейку
mov ebx.HeadJist
хогеах,еах;в еах будет указатель на предыдущую ячейку ;2 последняя ячейка?
cmpebx.Offffffffh
je no J tem cycl: cmp [ebx].info.search_b сравниваем с критерием поиска
jnechjiextjtem : нашли? ;да. нашли!
cmpeax.
jne no_fist:зто не первая ячейка :первая ячейка (?) »> изменяем указатель на начало списка и на выход
mov edx.[ebx].next
mov Headjist.edx
jmpexit no_fist: mov [eax].next.ebx перенастраиваем указатели -> элемент удален
jmpexit ;на выход
:выбор следующего элемента ch_nextjtem; mov eax.ebx : запомним адрес текущей ячейки в указателе на предыдущую
mov ebx.[ebx].next ;адрес следующего элемента в ebx
jmp cycl
:обработка ситуации отсутствия элемента nojtem:
Остальные обозначенные нами выше операции очевидны и не должны вызвать у читателя трудностей в реализации.
Другой интересный и полезный пример использования односвязных списков — работа с разреженными массивами. Разреженные массивы представляют собой массивы, у которых много нулевых элементов. Представить разреженный массив можно двумя способами: с использованием циклических списков с двумя полями связи и с использованием хэш-таблицы.
С разреженными массивами можно работать, используя методы хэширования. Для начала нужно определиться с максимальным размером хэш-таблицы М для хранения разреженного массива. Это значение будет зависеть от максимально возможного количества ненулевых элементов. Ключом для доступа к элементу хэш-таблицы выступает пара индексов (i,j), где i = l..p, j = l..q. Числовое значение ключа вычисляется по одной из следующих формул
Остальные действия зависят от избранного способа вычисления хэш-функции (см. выше соответствующий раздел о методах хэширования).
