Список
Преимущество использования двусвязных списков – в свободе передвижения по списку в обоих направлениях, в удобстве исключения элементов. Возникает вопрос о том, как определить начало списка. Для этого существуют по крайней мере две возможности: определить два указателя на оба конца списка или определить голову списка, указатели связей которой адресуют первый и последний элемент списка. В случае двусвязного списка добавление и удаление.
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).
Рис. 2.14. Логическая структура нелинейного двусвязного списка