Список
Исключение из списка
Алгоритм предполагает наличие двух указателей – на текущую и предыдущую ячейки. Для разнообразия этот алгоритм предполагает прямой порядок следования элементов в списке. В качестве упражнения читателю предлагается, если нужно, переписать приводимый ниже фрагмент для обратного порядка следования элементов.
:описание элемента списка itemjist struc – . элемент списка next dd 0:адрес следующего элемента info db 0 содержательная часть (в нашем случае – символ) ends .data search_b db 0 критерий поиска (поле info экземпляра структуры itemjist) Headjist dd Offffffffh указатель на начало списка (Offffffffh – список пуст) .code :здесь мы инициализировали и работали со списком :ищеи ячейку, подлежащую удалению;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. Числовое значение ключа вычисляется с помощью соответствующих формул.
Остальные действия зависят от избранного способа вычисления хэш-функции (см. выше соответствующий раздел о методах хэширования).
Двусвязные списки
Двусвязный список представляет собой список, связующая часть которого состоит из двух полей. Одно поле указывает на левого соседа данного элемента списка, другое – на правого. Кроме этого, со списком связаны два указателя – на голову и хвост списка (рис. 2.13, сверху). Более удобным может быть представление списка, когда функции этих указателей выполняет один из элементов списка, одно из полей связи которого указывает на последний элемент списка (рис. 2.13, снизу).
Рис. 2.13. Схемы организации двухсвязных списков