Двусвязный список (asm x86)

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 19:50, 9 августа 2015.

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

Рис. 1. Схема организации двусвязных списков

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

; Программа: prg15_102.asm. Инвертирование строки (двусвязные списки).
; Вход: символьная строка с клавиатуры.
; Выход: вывод на экран инвертированной обратной строки.
item_list           struc                      ; элемент списка
prev                dd         0               ; адрес предыдущего элемента
info                db         0               ; содержательная часть у нас - символ )
next                dd         0               ; адрес следующего элемента
ends
Head_list           struct                     ; заголовок списка
first               dd         0               ; адрес первого элемента списка
info                db         0ffh            ; offh - признак заголовка списка
las                 dd         0               ; адрес последнего элемента списка
ends
.data
mas                 db         80 dup ( '  ' ) ; в эту строку вводим 
mas_rev             db         80 dup ( '  ' ) ; из этой строки выводим
                                len_mas_rev =$ - mas_rev
                                ; . . .
mes1                db         'Введите строку символов ( до 80) для инвертирования '
                    db         '( с точкой на конце): '
                    len_mes1=$ - mes1
.code
           ;----- описание макрокоманд работы со связанным списком
           ;----- создание двусвязного списка
create_doubly_list macro head:REQ
                         :...
endm
           :-----добавление элемента в двусвязный список
add_list         marco   descr:REQ.  head:REQ. H_Head:REQ
                 ;...
endm
start            proc      near                    ; точка входа в программу
                 ;...
          ;------вывод строки текста - приглашение
          ;      на ввод строки для инвертирования
                 ;...
          ;-----вводим строку текста для инвертирования
                 ;...
          ;-----создаем связанный список. для чего
          ;      инициализируем заголовок списка
                 create_doubly_list Doubly_Head_list
          ;-----вводим символы строки с клавиатуры до тех пор пока не встретится "."
                 lea        esi. mas
cycl:            mov        al. [esi]
                 cmp        al. "."
                 je         rev_out
                 add_list item_list. Doubly_Head_list. Hand_Head
                 mov        [ebx].info. al
                 inc        esi
                 jmp        cycl
         ;------ вывод строки в обратном порядке
rev_out:         lea        esi. mas_rev
                 mov        ebx. Doubly_Head_list.last
cyc12:           mov        al. [ebx].info
                 mov        [esi]. a1
                 inc         esi
                 mov         ebx. [ebx].prev
                 cmp         [ebx].info. 0ffh : дошли до последнего элемента списка?
                 jne         cyc12
;--------------  выводим интертированную строку на экран
                 ;...

Включение в список

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

item_list            struc                              ; элемент списка
prev                 dd       0                         ; адрес предыдущего элемента
info                 db       0                         ; содержательная часть у нас - символ )
next                 dd       0                         ; адрес следующего элемента
ends
             ;----------  предполагаем, что адрес локализованного элемента
             ;            находится в регистре EBX. а адрес нового элемента - в EAX
                          ;...
                          push   [ebx].next
                          pop    [eax].next            ; [ebx].next->[eax].next
                          mov    [eax].prev. ebx    ; адрес предыдущего элемента->[eax].prev
                          mov    [ebx].next. eax    ; адрес следующего элемента->[ebx].next
             ;----------  будте внимательны - меняем указатель предыдущего элемента
             ;            в следущем за новым элементом
                          mov     ebx. [eax].next   ; адрес следующего элемента->[ebx].next
                          mov     [ebx].prev. eax   ; адрес предыдущего элемента->[ebx].prev
                          ;...
Включение элемента перед локализованным элементом выполняется аналогично. Простота работы с двусвязными списками в отличие от односвязных достигается за счет отсутствия проблем с передвижением по списку в обе стороны.

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

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

item_list            struc                              ; элемент списка
prev                 dd       0                         ; адрес предыдущего элемента
info                 db       0                         ; содержательная часть у нас - символ )
next                 dd       0                         ; адрес следующего элемента
ends
             ;----------предполагаем, что адрес локализованного элемента
             ;            находится в регистре EBX. а адрес нового элемента - в EAX
                          ;...
                          mov    eax.[ebx].prev    ; адрес предыдущего элемента->eax
                          push   [ebx].next
                          pop    [eax].next 
                          mov    eax.[ebx].next    ; адрес следующего элемента->eax
                          push   [ebx].next
                          pop    [eax].next
                          ;...

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

Рис. 2. Логическая структура нелинейного двусвязного списка