Иллюстрированный самоучитель по задачам и примерам Assembler

Список

Преимущество использования двусвязных списков – в свободе передвижения по списку в обоих направлениях, в удобстве исключения элементов. Возникает вопрос о том, как определить начало списка. Для этого существуют по крайней мере две возможности: определить два указателя на оба конца списка или определить голову списка, указатели связей которой адресуют первый и последний элемент списка. В случае двусвязного списка добавление и удаление.

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:адрес след. эл-та › [еbх].пех1
:будьте внимательны – меняем указатель предыд. эл-та в следующем за новым элементом
mov ebx.[eax].next;адрес след. эл-та-KebxJ.next mov [ebx].prev.eax;адрес предыд. эл-та › [еbх].ргеу

Включение элемента перед локализованным выполняется аналогично. Простота работы с двусвязными списками в отличие от односвязных достигается за счет отсутствия проблем с передвижением по списку в обе стороны.

Исключение из списка

Аналогично включению, исключение из двусвязного списка не вызывает проблем и достигается перенастройкой указателей. Фрагмент программы, демонстрирующей эту перенастройку, показан ниже.

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).

Иллюстрированный самоучитель по задачам и примерам Assembler › Сложные структуры данных › Список
Рис. 2.14. Логическая структура нелинейного двусвязного списка

Если Вы заметили ошибку, выделите, пожалуйста, необходимый текст и нажмите CTRL + Enter, чтобы сообщить об этом редактору.