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