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

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

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