Односвязные списки
Односвязные списки
В простейшем случае односвязный список можно организовать в виде двух одномерных массивов, длины которых совпадают и определяются максимально возможной длиной списка. Поля первого массива содержат собственно данные, а соответствующие поля второго массива представляют собой указатели. Значением каждого из этих указателей является индекс элемента первого массива, который логически следует за данным элементом, образуя таким образом связанный список. В качестве примера рассмотрим программу, которая в некотором массиве связывает все ненулевые элементы, а затем в качестве полезной работы подсчитывает их количество. В последний единичный элемент в качестве признака конца списка заносим Offh.
:prg3_10.asm - пример реализации односвязных списков с помощью двух массивов
:Вход: массивы с данными и указателями.
:Выход: нет. В динамике работа программы наблюдается под управлением отладчика.
.data
masdb 0.55.0.12.0.42.94.0.18.0.06.67.0.58.46 :задаем массив
n=$-mas
point db 0 указатель списка - индекс первого ненулевого элемента в mas
masjraint db n dup (0) определим массив указателей
.code
lea si.mas :b si адрес mas_point
xorbx.bx :b bx будут индексы - кандидаты на включение в массив указателей :ищем первый ненулевой элемент
movcx,n-l cycll: cmpbyte ptr [si][bx].O
jneml :если нулевые элементы
inc bx
loop cycll
jmpexit ;если нет ненулевых элементов ml: mov point.Ы :запоминаем индекс первого ненулевого в point
movdi.bx ;в di индекс предыдущего ненулевого ;просматриваем далее (сх тот же)
inc bx сус12: cmpbyte ptr [si][bx].O
je m2 ;нулевой => пропускаем :формируем индекс
movmas_point[di].bl ;индекс следующего ненулевого в элемент mas_point предыдущего
movdi.bx :запоминаем индекс ненулевого
т2: inc bx
loop cycl2
mov mas_point[di].Offh ;индекс следующего ненулевого в элемент mas_point ;выход :а теперь подсчитаем единичные, не просматривая все. - результат в ах
хог ах.ах
cmp point.0
je exit,
inc ax
mov bl .point cycl3: cmp mas_point[bx].Offh
je exit
inc ax
mov Ы ,mas_point[bx]
jmpcycl3 результат подсчета в ах. с ним нужно что- то делать, иначе он будет испорчен
Если количество нулевых элементов велико, то можно сократить объем хранения данного одномерного массива в памяти (см. ниже материал о разреженных массивах).
Кстати, в качестве еще одного реального примера использования односвязных списков вспомните, как реализован учет распределения дискового пространства в файловой системе MS DOS (FAT).
Далее рассмотрим другой, более естественный вариант организации связанного списка. Его элементы содержат как содержательную, так и связующую части.
Рассуждения относительно содержательной части пока опустим — они напрямую зависят от конкретной задачи. Уделим внимание связующей части. Понятно, что это адреса. Но какие? Можно считать, что существуют два типа адресов, которые могут находиться в связующей части: абсолютные и относительные. Абсолютный адрес в конкретном элементе списка — это, по сути, смещение данного элемента относительно начала сегмента данных или блока данных при динамическом выделении памяти и принципиально он лишь логически связан со списком. Относительный адрес формируется исходя из внутренней нумерации элементов в списке и имеет смысл лишь в контексте работы с ним. Пример относительной нумерации рассмотрен выше при организации списка с помощью двух массивов. Поэтому далее этот способ адресации мы рассматривать не будем, а сосредоточимся на абсолютной адресации.
Для начала разработаем код, реализующий применительно к односвязным спискам основные из обозначенных нами выше операций со связанными списками. Односвязные списки часто формируют с головы, то есть включение новых элементов производится в голову списка.
Первая проблема — выделение памяти для списка. Это можно делать либо статическим способом, зарезервировав место в сегменте данных, либо динамически, то есть так, как мы это делали выше при реализации операций со стеками и очередями. Недостатки первого способа очевидны, хотя в реализации он очень прост. Гораздо интереснее и предпочтительнее второй способ, который предполагает использование кучи для хранения связанного списка. Для придания боль-Шей реалистичности изложению рассмотрим простую задачу: ввести с клавиатуры
символьную строку, ограниченную символом "." (точка), и распечатать ее в обратном порядке.
:prgl5_102.asm - реализация программы инвертирования строки с односвязными списками
:Вход: символьная строка с клавиатуры.
:Выход: вывод на экран инвертированной обратной строки.
;.........
itemjist struc :элемент списка
next dd 0 :адрес следующего элемента
info db 0 содержательная часть (в нашем случае - символ)
ends
.data
mas db 80 dup С ') :в эту строку вводим
mas revdb 80 dup (' ') :из этой строки выводим
len mas rev=$-mas rev
mesl db 'Введите строку символов (до 80) для инвертирования (с точкой на конце):'
len_mesl=$-mesl
.code
списание макрокоманд работы со связанным списком;
createjist macro descr:REQ.head:REQ
: создание списка - формирование головы списка и первого элемента
;.........
endm
addjist macro descr:REQ.head:REQ.H_Head:REQ
добавление элемента в связанный список
endm
createjtem macro descr:REQ.H_Head:REQ
;создание элемента в куче для последующего добавления в связанный список
¦.........
endm
start proc near :точка входа в программу:
:вывод строки текста - приглашения на ввод строки для инвертирования !.........
:вводим строку в mas
:.........
;создаем связанный список createjist itemJist.HeadJist :первый элемент обрабатываем отдельно
leaesi.mas
moval.[esi]
cmp al."."
je rev_out
mov [ebx].info.al
:вводим остальные символы строки с клавиатуры до тех пор. пока не встретится "." cycl: incesi
mov al.[esi]
cmp al,"."
je rev_out
addj i st i temj i st. HeadJ i st. Hand_Head
mov [ebx].info.al
jmp cycl
:вывод строки в обратном порядке rev_out: mov esi.offset mas_rev
mov ebx,HeadJist cycl2: mov al .[ebx].info
mov [esil.al
inc esi
mov ebx.[ebx].next
cmpebx.Offffffffh
jne cycl2 ; выводим инвертированную строку на экран
Недостаток такого способа построения списка — в порядке включения элементов. Хорошо видно, что он обратный порядку поступления элементов. Для исправления данной ситуации можно, конечно, ввести еще один указатель на последний элемент списка. Есть и другой вариант — организация двусвязного списка. Уделим теперь внимание другим операциям с односвязным списком.
Включение в список
Для включения нового элемента в список необходимо предварительно локализовать элемент, до или после которого будет производиться это включение. Для того чтобы включить новый элемент после локализованного, необходимо выполнить действия, отраженные фрагментом кода:
itemjist struc элемент списка
next dd 0 ; адрес следующего элемента
info db 0 содержательная часть (в нашем случае - символ)
предполагаем, что адрес локализованного элемента находится в регистре ЕВХ.
:а адрес нового элемента - в ЕАХ
mov edx.[ebx].next
mov [eax].next.edx mov [ebx].next.eax
Для включения нового элемента после локализованного возникает проблема, I источник которой в однонаправленности односвязного списка, так как, по определению, проход к предшествующему элементу невозможен. Можно, конечно, включить новый элемент, как показано выше, а затем попросту обменять содержимое этих элементов. К примеру, это может выглядеть так:
itemjist 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_itern itemjist <.15> вставляемый элемент (поле info содержит значение -
:критерий вставки)
Headjist dd Offffffffh указатель на начало списка (Offffffffh - список пуст) Hand_Head dd 0 ;переменная, в которой хранится дескриптор кучи
.code
;здесь мы инициализировали и работали со списком
;список упорядочен по возрастанию
:ищем место вставки
;1 - выбираем первую ячейку
mov ebx.HeadJist .
хогеах.еах ; в еах будет указатель на предыдущий элемент ;2 последняя ячейка? ml: cmpebx.Offffffffh
je noJtern :список пустой :3 - новая ячейка до очередной выбранной? ovd1.CebxJ.info cmpdl.ins_item.info ja nextjtem cmpeax. jne into ;вставить первым
createjtem i temj i st. H_Head :макрос создания элемента в куче mov Headjist.edx :адрес нового в голову списка
mov [edx].next.ebx ;настройка указателей jmpexit :на выход
вставить внутрь списка
into: createjtem item_list.H_Head :макрос создания элемента в куче mov [еах].next.edx :адрес нового в поле next предыдущего mov [edx].next.ebx :в поле next нового адрес текущего jmp exit :на выход
: выбор очередного элемента nextjtem: moveax.ebx:aflpec текущего в еах mov ebx. [ebx].next jmp ml
:4 - список пуст или нет больше элементов no J tern: cmpeax.O
jne no_empty :список непустой :список пуст
mov Headjlist.edx :адрес нового в голову списка
mov [edx].next.Offffffffh:это будет пока единственный элемент в списке
jmpexit :на выход
no_empty: :список не пуст - новая ячейка в конец списка
mov [еах].next.edx
mov [edx].next.Offffffffh:это будет последний элемент в списке
exit: :общий выход
Исключение из списка
Алгоритм предполагает наличие двух указателей — на текущую и предыдущую ячейки. Для разнообразия этот алгоритм предполагает прямой порядок следования элементов в списке. В качестве упражнения читателю предлагается, если нужно, переписать приводимый ниже фрагмент для обратного порядка следования элементов.
:описание элемента списка
itemjist struc -.элемент списка
next dd 0 :адрес следующего элемента
info db 0 содержательная часть (в нашем случае - символ)
ends
.data
search_b db 0 критерий поиска (поле info экземпляра структуры itemjist)
Headjist dd Offffffffh указатель на начало списка (Offffffffh - список пуст)
.code
:здесь мы инициализировали и работали со списком
:ищеи ячейку, подлежащую удалению ;1 - выбираем первую ячейку
mov ebx.HeadJist
хогеах,еах; в еах будет указатель на предыдущую ячейку ;2 последняя ячейка?
cmpebx.Offffffffh
je no J tem cycl: cmp [ebx].info.search_b сравниваем с критерием поиска
jnechjiextjtem : нашли? ;да. нашли!
cmpeax.
jne no_fist:зто не первая ячейка :первая ячейка (?) »> изменяем указатель на начало списка и на выход
mov edx.[ebx].next
mov Headjist.edx
jmpexit no_fist: mov [eax].next.ebx перенастраиваем указатели -> элемент удален
jmpexit ;на выход
:выбор следующего элемента ch_nextjtem; mov eax.ebx : запомним адрес текущей ячейки в указателе на предыдущую
mov ebx.[ebx].next ;адрес следующего элемента в ebx
jmp cycl
:обработка ситуации отсутствия элемента nojtem:
Остальные обозначенные нами выше операции очевидны и не должны вызвать у читателя трудностей в реализации.
Другой интересный и полезный пример использования односвязных списков — работа с разреженными массивами. Разреженные массивы представляют собой массивы, у которых много нулевых элементов. Представить разреженный массив можно двумя способами: с использованием циклических списков с двумя полями связи и с использованием хэш-таблицы.
С разреженными массивами можно работать, используя методы хэширования. Для начала нужно определиться с максимальным размером хэш-таблицы М для хранения разреженного массива. Это значение будет зависеть от максимально возможного количества ненулевых элементов. Ключом для доступа к элементу хэш-таблицы выступает пара индексов (i,j), где i = l..p, j = l..q. Числовое значение ключа вычисляется по одной из следующих формул
Остальные действия зависят от избранного способа вычисления хэш-функции (см. выше соответствующий раздел о методах хэширования).
