Список
В общем случае для связанных списков определены следующие операции:
- создание связного списка;
- включение элемента в связный список, в том числе и после (перед) определенным элементом;
- доступ к определенному элементу связного списка (поиск в списке);
- исключение элемента из связного списка;
- упорядочение (перестройка) связного списка;
- очистка связного списка;
- проверка объема связного списка (числа элементов в связном списке);
- объединение нескольких списков в один;
- разбиение одного списка на несколько;
- копирование списка;
- удаление связного списка.
Связные списки очень важны для представления различных сетевых структур, в частности деревьев, что и будет рассмотрено нами чуть ниже. Пока же рассмотрим работу с некоторыми из обозначенных нами типов связных списков на практических примерах.
Односвязные списки
В простейшем случае односвязный список можно организовать в виде двух одномерных массивов, длины которых совпадают и определяются максимально возможной длиной списка. Поля первого массива содержат собственно данные, а соответствующие поля второго массива представляют собой указатели. Значением каждого из этих указателей является индекс элемента первого массива, который логически следует за данным элементом, образуя таким образом связанный список. В качестве примера рассмотрим программу, которая в некотором массиве связывает все ненулевые элементы, а затем в качестве полезной работы подсчитывает их количество. В последний единичный элемент в качестве признака конца списка заносим 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).
Далее рассмотрим другой, более естественный вариант организации связанного списка. Его элементы содержат как содержательную, так и связующую части.
Рассуждения относительно содержательной части пока опустим – они напрямую зависят от конкретной задачи. Уделим внимание связующей части. Понятно, что это адреса. Но какие? Можно считать, что существуют два типа адресов, которые могут находиться в связующей части: абсолютные и относительные. Абсолютный адрес в конкретном элементе списка – это, по сути, смещение данного элемента относительно начала сегмента данных или блока данных при динамическом выделении памяти и принципиально он лишь логически связан со списком. Относительный адрес формируется исходя из внутренней нумерации элементов в списке и имеет смысл лишь в контексте работы с ним. Пример относительной нумерации рассмотрен выше при организации списка с помощью двух массивов. Поэтому далее этот способ адресации мы рассматривать не будем, а сосредоточимся на абсолютной адресации.