Двусвязные списки
Двусвязные списки
Двусвязный список представляет собой список, связующая часть которого состоит из двух полей. Одно поле указывает на левого соседа данного элемента списка, другое — на правого. Кроме этого, со списком связаны два указателя — на голову и хвост списка (Рисунок 2.13, сверху). Более удобным может быть представление списка, когда функции этих указателей выполняет один из элементов списка, одно из полей связи которого указывает на последний элемент списка (Рисунок 2.13, снизу).
Рис 2.13. Схемы организации двухсвязных списков
Преимущество использования двусвязных списков — в свободе передвижения по списку в обоих направлениях, в удобстве исключения элементов. Возникает вопрос о том, как определить начало списка. Для этого существуют по крайней мере две возможности: определить два указателя на оба конца списка или определить голову списка, указатели связей которой адресуют первый и последний элемент списка. В случае двусвязного списка добавление и удаление
start proc near :точка входа в программу ,
:вывод строки текста - приглашение на ввод сроки для инвертирования :вводим строку текста для инвертирования
.-создаем связанный список, для чего инициализируем заголовок списка
create_doubly_li st Doubly_Head_l i st :вводим символы строки с клавиатуры до тех пор. пока не встретится "."
lea esi.mas cycl: mov al .[esi]
cmpal.V
je rev_out
add_li st i tem_l i st.Doubly_Head_li st.Hand_Head
mov [ebx].info.al
incesi
jmp cycl rev_out: ;вывод строки в обратном порядке
mov esi.offset mas_rev
mov ebx.DoublyJHeadJ i st. 1 ast cycl2: mova 1 .[ebx].info
mov [esi].al
incesi
mov ebx,[ebx].prev
cmp [ebx].info.Offh :дошли до последнего элемента списка"?
jnecycl2
:выводим инвертированную строку на экран :......
Включение в список
Для включения нового элемента в список необходимо предварительно локализовать элемент, до или после которого будет производиться это включение. Для того чтобы включить новый элемент после локализованного, то есть справа, необходимо выполнить действия, отраженные фрагментом кода:
itemjist struc ; элемент списка
prev dd 0 :адрес предыдущего элемента
info db 0 содержательная часть (в нашем случае - символ)
next dd 0 :адрес следующего элемента
ends
;предполагаем, что адрес локализованного элемента находится в регистре ЕВХ.
:а адрес нового элемента - в ЕАХ
push [ebx].next
pop [eax].next :[ebx].next->[eax].next mcv [eax].prev.ebx;адрес предыд. эл-та->[еах].ргеу mov [ebx].next.eax:адрес след. эл-та->[еЬх].пех1
:будьте внимательны - меняем указатель предыд. эл-та в следующем за новым элементом mov ebx.[eax].next;адрес след. эл-та-KebxJ.next mov [ebx].prev.eax;адрес предыд. эл-та->[еЬх].ргеу
Включение элемента перед локализованным выполняется аналогично. Простота работы с двусвязными списками в отличие от односвязных достигается за счет отсутствия проблем с передвижением по списку в обе стороны.
Исключение из списка
Аналогично включению, исключение из двусвязного списка не вызывает проблем и достигается перенастройкой указателей. Фрагмент программы, демонстрирующей эту перенастройку, показан ниже.
itemjist struc ;элемент списка
prev dd 0 ;адрес предыдущего элемента
info db 0 содержательная часть (в нашем случае - символ)
next dd 0 -.адрес следующего элемента
ends
предполагаем, что адрес локализованного элемента находится в регистре ЕВХ
mov eax.[ebx].prev;адрес предыд. эл-та->еах
push [ebx].next
pop [eax].next
mov eax.[ebx].next ;адрес следующ. эл-та->еах
push [ebx].prev
pop [eax].prev
В общем случае одно- и двусвязные списки представляют собой линейные связанные структуры. Но в определенных случаях второй указатель двусвязного списка может задавать порядок следования элементов, не являющийся обратным по отношению к первому указателю (Рисунок 2.14).
Рисунок 2.14. Логическая структура нелинейного двусвязного списка
