Сборник по задачам и примерам Assembler

     

Односвязные списки



Односвязные списки

В простейшем случае односвязный список можно организовать в виде двух одномерных массивов, длины которых совпадают и определяются максимально возможной длиной списка. Поля первого массива содержат собственно данные, а соответствующие поля второго массива представляют собой указатели. Значением каждого из этих указателей является индекс элемента первого массива, который логически следует за данным элементом, образуя таким образом связанный список. В качестве примера рассмотрим программу, которая в некотором массиве связывает все ненулевые элементы, а затем в качестве полезной работы подсчитывает их количество. В последний единичный элемент в качестве признака конца списка заносим 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. Числовое значение ключа вычисляется по одной из следующих формул

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


Содержание раздела