Односвязные списки - часть 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. Числовое значение ключа вычисляется по одной из следующих формул

Остальные действия зависят от избранного способа вычисления хэш-функции (см. выше соответствующий раздел о методах хэширования).