Иллюстрированный самоучитель по задачам и примерам 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.b1
:запоминаем индекс первого ненулевого в 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 b1,mas_point[bx]
jmpcycl3 результат подсчета в ах. с ним нужно что-то делать, иначе он будет испорчен

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

Кстати, в качестве еще одного реального примера использования односвязных списков вспомните, как реализован учет распределения дискового пространства в файловой системе MS DOS (FAT).

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

Рассуждения относительно содержательной части пока опустим – они напрямую зависят от конкретной задачи. Уделим внимание связующей части. Понятно, что это адреса. Но какие? Можно считать, что существуют два типа адресов, которые могут находиться в связующей части: абсолютные и относительные. Абсолютный адрес в конкретном элементе списка – это, по сути, смещение данного элемента относительно начала сегмента данных или блока данных при динамическом выделении памяти и принципиально он лишь логически связан со списком. Относительный адрес формируется исходя из внутренней нумерации элементов в списке и имеет смысл лишь в контексте работы с ним. Пример относительной нумерации рассмотрен выше при организации списка с помощью двух массивов. Поэтому далее этот способ адресации мы рассматривать не будем, а сосредоточимся на абсолютной адресации.

Если Вы заметили ошибку, выделите, пожалуйста, необходимый текст и нажмите CTRL + Enter, чтобы сообщить об этом редактору.