Односвязный список (asm x86)

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

Организация односвязного списка

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

;Пример реализации односвязных списков с помощью двух массивов 
;Вход: массивы с данными и указателями. 
;Выход: нет. В динамике работа программы наблюдается под управлением отладчика. 
.data 
mas db 0, 55, 0, 12, 0, 42, 94, 0, 18, 0, 6
    db 67, 0, 58, 46 ;задаем массив 
n = $ - mas 
point db 0 ;указатель списка - индекс первого ненулевого элемента в mas 
mas_point db n dup (0) ;определим массив указателей 
.code 
lea si, mas  si адрес mas_point 
xor bx, bx  bx будут индексы - кандидаты на включение в массив указателей 
;ищем первый ненулевой элемент 
mov cx, n-l 
cycll: cmp byte ptr [si][bx], O 
jne m1 ;если нулевые элементы 
inc bx 
loop cycll 
jmp exit ;если нет ненулевых элементов 
m1: mov point, bl ;запоминаем индекс первого ненулевого в point 
mov di, bx  di индекс предыдущего ненулевого ;просматриваем далее (сх тот же) 
inc bx 
сус12: cmp byte ptr [si][bx], O 
je m2 ;нулевой => пропускаем 
;формируем индекс 
mov mas_point[di],bl ;индекс следующего ненулевого в элемент mas_point предыдущего 
mov di, bx ;запоминаем индекс ненулевого 
m2: inc bx 
loop cycl2 
mov mas_point[di], Offh ;индекс следующего ненулевого в элемент mas_point  
;теперь подсчитаем единичные, не просматривая все. - результат в ах 
хоr ах, ах 
cmp point, 0 
je exit 
inc ax 
mov bl, point 
cycl3: cmp mas_point[bx], Offh 
je exit 
inc ax 
mov bl, mas_point[bx] 
jmp cycl3 
;результат подсчета в ах, с ним нужно что-то делать, иначе он будет испорчен

Если количество нулевых элементов велико, то можно сократить объем хранения данного одномерного массива в памяти.

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

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

Рассмотрим простую задачу: ввести с клавиатуры символьную строку, ограниченную символом "." (точка), и распечатать ее в обратном порядке.

;Реализация программы инвертирования строки с односвязными списками 
;Вход: символьная строка с клавиатуры. 
;Выход: вывод на экран инвертированной строки. 
;......... 
item_list struc ;элемент списка 
next dd 0 ;адрес следующего элемента 
info db 0 ;содержательная часть (в нашем случае - символ) 
ends 
.data 
mas db 80 dup (' ')  эту строку вводим 
mas_rev db 80 dup (' ') ;из этой строки выводим 
len_mas_rev = $ - mas_rev 
mesl db 'Введите строку символов (до 80) для инвертирования (с точкой на конце):' 
len_mesl = $ - mesl 
.code 
;oписание макрокоманд работы со связанным списком
create_list macro descr:REQ, head:REQ 
; создание списка - формирование головы списка и первого элемента 
;......... 
endm 
add_list macro descr:REQ, head:REQ, H_Head:REQ 
;добавление элемента в связанный список 
endm 
create_item macro descr:REQ, H_Head:REQ 
;создание элемента в куче для последующего добавления в связанный список 
;......... 
endm 
start proc near ;точка входа в программу 
;вывод строки текста - приглашения на ввод строки для инвертирования
;вводим строку в mas 
:......... 
;создаем связанный список 
create_list item_list, HeadJist ;первый элемент обрабатываем отдельно
lea esi, mas 
mov al, [esi] 
cmp al, "." 
je rev_out 
mov [ebx].info, al 
;вводим остальные символы строки с клавиатуры до тех пор. пока не встретится "." 
cycl: inc esi 
mov al, [esi] 
cmp al, "." 
je rev_out 
add_list item_list, Head_list, Hand_Head 
mov [ebx].info, al 
jmp cycl 
;вывод строки в обратном порядке 
rev_out: mov esi.offset mas_rev 
mov ebx, Head_list 
cycl2: mov al, [ebx].info 
mov [esi], al 
inc esi 
mov ebx, [ebx].next 
cmp ebx, Offffffffh 
jne cycl2 
;выводим инвертированную строку на экран

Недостаток такого способа построения списка заключается в порядке включения элементов. Он обрятен порядку поступления элементов. Для исправления данной ситуации можно ввести еще один указатель на последний элемент списка или организовать двусвязный список.

Операции с односвязными списками

В общем случае для связанных списков определены следующие операции:

  • создание связного списка;
  • включение элемента в связный список, в том числе и после (перед) определенным элементом;
  • доступ к определенному элементу связного списка (поиск в списке);
  • исключение элемента из связного списка;
  • упорядочение (перестройка) связного списка;
  • очистка связного списка;
  • проверка объема связного списка (числа элементов в связном списке);
  • объединение нескольких списков в один;
  • разбиение одного списка на несколько;
  • копирование списка;
  • удаление связного списка.

Рассмотрим примеры реализации некоторых из операций.

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

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

item_list struc ;элемент списка 
next dd 0 ; адрес следующего элемента 
info db 0 ;содержательная часть (в нашем случае - символ) 
;предполагаем, что адрес локализованного элемента находится в регистре ЕВХ, а адрес нового элемента - в ЕАХ 
mov edx, [ebx].next 
mov [eax].next, edx 
mov [ebx].next, eax

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

item_list struc ;элемент списка 
next dd 0 ;адрес следующего элемента 
info db 0 ;содержательная часть (в нашем случае - символ) 
ends
;предполагаем, что адрес локализованного элемента находится в регистре ЕВХ.
 адрес нового элемента - в ЕАХ 
mov edx, [ebx].next 
mov [eax].next, edx 
mov edx, [ebx].info 
mov [eax].info,  edx 
mov [ebx].next, eax 
;осталось заполнить поле info нового элемента

Если производится включение в упорядоченный список, то логичнее работать с двумя указателями — на текущий и предыдущий элементы списка. При этом предполагается, что новый элемент создается макрокомандой create_item.

item_list struc ;элемент списка 
next dd 0 ;адрес следующего элемента 
info db 0 ;содержательная часть (в нашем случае - символ) 
ends 
.data 
ins_item item_list <.15> ;вставляемый элемент (поле info содержит значение - критерий вставки) 
Head_list dd Offffffffh ;указатель на начало списка 
                       ;(Offffffffh - список пуст) 
Hand_Head dd 0 ;переменная, в которой хранится дескриптор кучи 
.code 
;здесь мы инициализировали и работали со списком 
;список упорядочен по возрастанию 
;ищем место вставки 
;1 - выбираем первую ячейку 
mov ebx, Head_list
хоr еах, еах  еах будет указатель на предыдущий элемент 
m1: cmp ebx, Offffffffh ;2 последняя ячейка? 
je no_item ;список пустой 
;3 - новая ячейка до очередной выбранной? 
mov dl, [ebx].info 
cmp dl, ins_item.info 
ja next_item 
test eax, eax
jnz , into 
;вставить первым 
create_item item_list. H_Head ;макрос создания элемента в куче 
mov Head_list, edx ;адрес нового в голову списка 
mov [edx].next, ebx ;настройка указателей 
jmp exit ;на выход 
;вставить внутрь списка 
into: create_item item_list.H_Head ;макрос создания элемента в куче 
mov [еах].next, edx ;адрес нового в поле next предыдущего 
mov [edx].next, ebx  поле next нового адрес текущего 
jmp exit ;на выход 
; выбор очередного элемента 
next_item: mov eax, ebx ;адрес текущего в еах 
mov ebx, [ebx].next 
jmp m1 
;4 - список пуст или нет больше элементов 
no_item: test eax, eax
jnz no_empty ;список непустой 
;список пуст 
mov Head_list, edx ;адрес нового в голову списка 
mov [edx].next, Offffffffh ;это будет пока единственный элемент в списке 
jmp exit ;на выход 
;список не пуст - новая ячейка в конец списка 
no_empty: mov [еах].next, edx 
mov [edx].next, Offffffffh ;это будет последний элемент в списке 
exit: ;общий выход

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

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

item_list struc ;элемент списка 
next dd 0 ;адрес следующего элемента 
info db 0 ; содержательная часть (в нашем случае - символ) 
ends 
.data 
search_b db 0 ; критерий поиска (поле info экземпляра структуры item_list) 
Head_list dd Offffffffh ;указатель на начало списка (Offffffffh - список пуст) 
.code 
;здесь мы инициализировали и работали со списком 
;ищеи ячейку, подлежащую удалению 
;1 - выбираем первую ячейку 
mov ebx, Head_list 
хоr еах, еах  еах будет указатель на предыдущую ячейку ;2 последняя ячейка? 
cmp ebx, Offffffffh 
je no_item
;сравниваем с критерием поиска 
cycl: mov dl, search_b
cmp [ebx].info, dl 
jne ch_next_item ; нашли? 
;да. нашли! 
test eax, eax
jnz no_first ;зто не первая ячейка 
;первая ячейка (?) => изменяем указатель на начало списка и на выход 
mov edx, [ebx].next 
mov Head_list, edx 
jmp exit 
no_fist: mov [eax].next, ebx ;перенастраиваем указатели => элемент удален 
jmp exit ;на выход 
;выбор следующего элемента 
ch_next_item; mov eax, ebx ;запомним адрес текущей ячейки в указателе на предыдущую 
mov ebx, [ebx].next ;адрес следующего элемента в ebx 
jmp cycl 
;обработка ситуации отсутствия элемента 
no_item:
;...

Примеры использования

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


    Остальные действия зависят от избранного способа вычисления хэш-функции.
  2. Учет распределения дискового пространства в файловой системе MS DOS (FAT).