Список

Если у веревки есть один конец,
значит, у нее должен быть и другой.
Закон Микша (Прикладная Мерфология)

В общем случае под списком понимается линейно упорядоченная последовательность элементов данных, каждый из которых представляет собой совокупность одних и тех же полей. Упорядоченность элементов данных может быть двоякой:

• элементы списка располагаются последовательно как в структуре представления, так и в структуре хранения — список такого типа называется последовательным;
• порядок следования элементов определяется с помощью специальных указателей, которые расположены в самих элементах и определяют их соседей справа и/или слева — подобные списки называются связными.

Последовательные списки

Если количество элементов в списке постоянно, то в зависимости от их типа список вырождается в вектор, массив, структуру или таблицу. Отличие списка от этих структур данных — в длине. Для списков она является переменной. Поэтому программист, разбираясь с самими списками, должен уделить внимание тому, каким образом ему следует выделять память для хранения списка. Обычно языки высокого уровня имеют соответствующие средства в отличие от языка ассемблера. При написании программы на ассемблере программист должен уметь напрямую обратиться к операционной системе для решения проблемы динамического управления памятью. В примерах мы будем использовать соответствующие функции API Win32 как более современные, хотя для общего случая это не принципиально. В MS DOS имеются аналогичные функции (с точки зрения цели использования) — это функции 48h, 49h, 4ah прерывания 21h. Вопрос динамического управления памятью в силу своей важности в контексте настоящего рассмотрения требует особого внимания.
Отличие последовательных списков от связных состоит в том, что добавление и удаление элементов возможно только по концам структуры. В зависимости от алгоритма изменения различают такие виды последовательных списков, как стеки, очереди и деки. Эти виды списков обычно дополняются служебным дескриптором, который может содержать указатели на начало и конец области памяти, выделенной для списка, указатель на текущий элемент.
Зачем нужен, к примеру, стек? Необходимость использования своего стека в программе вполне вероятна, хотя бы исходя из того, что элементы, для хранения которых он создается, могут иметь размер, отличный от 2/4 байта.
Важно понимать, что внутренняя структура элемента практически не зависит от типа последовательного списка. Списки отличает набор операций, которые производятся над ними. Поэтому рассмотрим их отдельно для каждого типа последовательного списка.

Стек

Стек — последовательный список, в котором все включения и исключения элементов производятся на одном его конце — по принципу LIFO (Last In First Out — последним — пришел первым ушел). Для стека определены следующие операции:

• создание стека;
• включение элемента в стек;
• исключение элемента из стека;
• очистка стека;
• проверка объема стека (числа элементов в стеке);
• удаление стека.

Создание стека должно сопровождаться инициализацией специального дескриптора стека, который может содержать следующие поля: имя стека, адреса нижней и верхней границ стека, указатель на вершину стека.
Иллюстрацию организации и работы стека произведем на примере задачи, анализирующей правильность согласования скобок в некотором тексте. Причем условимся, что скобки могут быть нескольких видов: (), {}, [], <>. Программа реализована в виде приложения Win32 с использованием функций API Win32 для работы с кучей (из нее выделяется память для стека).

mov ecx,l_string
lea ebx.string
jmp cycl
e_xit: jmp exit cycl: jcxz e_xit
cmp byte ptr [ebx]."("
je m_push
cmp byte ptr [ebx],"["
je m_push
cmp byte ptr [ebx],"{"
je m_push
cmp byte ptr [ebx]."<"
je m_push
cmp byte ptr [ebx],")"
jneml извлекаем элемент из вершины стека и анализируем его
TestEmptyStk char_stk.mes_error
pop_stkchar_stk.<offset temp>
cmp temp." ("
jne mes_error
jmp r_next ml: cmp byte ptr [ebx],"]"
jnem2 извлекаем элемент из вершины стека и анализируем его
TestEmptyStk char_stk.mes_error
pop_stkchar_stk.<offset temp>
cmp temp," ["
jnemes_error
jmp r_next m2: cmp byte ptr [ebx],"}"
jnem3 ¦.извлекаем элемент из вершины стека и анализируем его
TestEmptyStk char_stk.mes_err6r
pop_stkchar_stk,<offset temp>
cmp temp."{"
jne mes_error
jmp r_next m3: cmp byte ptr [ebx],">"
jne rjiext извлекаем элемент из вершины стека и анализируем его
TestEmptyStk char_stk.mes_error
pop_stkchar_stk.<offset temp>
cmp temp,"<"
jne mes__error
jmp r_next m_push: включение скобки в стек
pushstk char_stk.ebx r_next:add ebx,char_stk.si ze_i tern
dec ecx
jmp cycl mes_error: :вывод на экран сообщения об ошибке mes_e
jmp exitexit
exit:
определяем стек на пустоту
pop_stkchar_stk,<offset temp> jncmes_error :стек не пуст :вывод на экран сообщения mes_ok
exit_exit: :выход из приложения
delete_stk char_stk :удаляем блок памяти со стеком

Код, выполняющий работу со стеком, оформлен в виде макрокоманд. При необходимости код можно сделать еще более гибким. Для этого нужно использовать функцию API Win32 HeapReAl 1 ос, которая изменяет размер выделенного блока в сторону его увеличения или уменьшения. В принципе, полезной может оказаться операция определения объема стека, то есть количества элементов в нем. Попробуйте реализовать ее самостоятельно.

Очередь

Очередь [2, 10, 15] — последовательный список, в котором включение элементов производится на одном конце, а исключение на другом, то есть по принципу FIFO (First In First Out — первым пришел — первым ушел). Сторона очереди, на которой производится включение элементов, называется хвостом. Соответственно, противоположная сторона — голова очереди. Очередь описывается дескриптором, который может содержать поля: имя очереди, адреса верхней и нижней границ области памяти, выделенной для очереди, указатели на голову и хвост. Набор операций для очереди:

• создание очереди (create_que);
• включение элемента в очередь (push_que);
• исключение элемента из очереди (popque);
• проверка пустоты очереди (TestEmptyQue);
• очистка очереди без освобождения памяти для нее (initque);
• удаление очереди (delete_que).

При помощи очереди удобно моделировать некоторые обслуживающие действия, например это может быть некоторая очередь запросов к критическому ресурсу или очереди заданий на обработку. К очереди так же, как и стеку, применимы такие параметры, как емкость очереди и размер элемента очереди.
На практике используются очереди двух типов — простые и кольцевые. Очередь обслуживается двумя указателями — головы (Р,) и хвоста очереди (Р2). Указатель головы Р идентифицирует самый старый элемент очереди, указатель хвоста — первый свободный слот после последнего включенного в очередь элемента. Сами элементы физически по очереди не двигаются. Меняется лишь значение указателей. При включении в очередь новый элемент заносится в ячейку очереди, на которую указывает Р2. Операция исключения подразумевает извлечение элемента из ячейки очереди, указываемой Р,. Кроме извлечения элемента операция исключения производит корректировку указателя Р, так, чтобы он указывал на очередной самый старый элемент очереди. Таким образом, Указатель хвоста простой очереди всегда указывает на свободную ячейку очере-Ди и рано или поздно он выйдет за границы блока, выделенного для очереди. И это случится несмотря на то, что в очереди могут быть свободные ячейки
(ячейки А. Чтобы исключить это явление, очередь организуется по принципу кольца. В обоих способах организации очереди важно правильно определить ее емкость. Недостаточный объем очереди может привести в определенный момент к ее переполнению, что чревато потерей новых элементов, претендующих на включение в очередь.
Для иллюстрации порядка организации и работы с очередью рассмотрим пример. Пусть имеется строка символов, которая следующим образом моделирует некоторую вычислительную ситуацию: символы букв означают запросы на некоторый ресурс и подлежат постановке в очередь (имеющую ограниченный размер). Если среди символов встречаются символы цифр в диапазоне 1-9, то это означает, что необходимо изъять из очереди соответствующее значению цифры количество элементов. Если очередь полна, а символов цифр все нет, то происходит потеря заявок (символов букв). В нашей программе будем считать, что очередь кольцевая и ее переполнение помимо потери новых элементов приводит к выводу соответствующего сообщения. Для кольцевой очереди возможны следующие соотношения значений указателей Р, и Р2: Pj < Р2, Pj = Р2 (пустая очередь), Р, > Р2. Память для очереди в нашей задаче выделяется динамически средствами API Win32.
Заметим, что исходя из потребностей конкретной задачи можно изменить дисциплину обслуживания очереди. Например, установить, что при переполнении очереди потере подлежат старые заявки (в голове очереди) и т. п.

jb ml cmpa1.39h
ja ml
xor есх.есх:удгляем из очереди элементы
mov cl,al
subcl,30h преобразуем символ цифры в двоичный эквивалент ш2: pop_quechar_que.<offset temp>
jc cycl ;если очередь пуста
1 oop m2
jmpcycl ml: добавляем элементы в очередь
mov temp,a 1
push_que char_que. <offset temp>
jnc cycl ;ycnex ;вывод на экран сообщения об ошибке - отсутствие места в очереди
jmp cycl
;выход из приложения exit: :удаляем блок памяти с очередью
delete_que char_que

Как и в случае со стеком, код, выполняющий работу с очередью, оформлен в виде макрокоманд. Программа выдает единственное Сообщение о переполнении очереди. Чтобы наблюдать работу программы в динамике, необходимо выполнить следующие действия.

1. 1. Загрузить исполняемый модуль программы в отладчик td32.exe.
2. 2. Отследить адрес начала блока памяти, который будет выделен системой по нашему запросу для размещения очереди. Для этого подвергните пошаговому выполнению в окне CPU содержимое макрокоманды createque.
3. 3. Выяснив адрес начала блока для размещения очереди, отобразите его в окне Dump и нажмите клавишу F7 или F8. Не отпуская этой клавиши, наблюдайте за тем, как изменяется состояние очереди.

Дека

Дека — очередь с двумя концами. Дека является последовательным списком, в котором включение и исключение элементов может осуществляться с любого из двух концов списка. Логическая и физическая структуры деки аналогичны обычной очереди, но относительно деки следует говорить не о хвосте и голове, а о правом и левом конце очереди. Реализацию операций включения и исключения в деку следует также дополнить признаками левого или правого конца. В литературе можно встретить понятие дека с ограниченным вводом. Это дека, в которой элементы могут вставляться в одном конце, а удаляться с обоих.

Связные списки

Связный список — набор элементов, каждый из которых структурно состоит из двух частей — содержательной и связующей. Содержательная часть представляет собой собственно данные или указатель на область памяти, где эти данные
содержатся. Связующая часть предназначена для связи элементов в списке и определяет очередность их следования. Благодаря связующей части в каждом из элементов становятся возможными «путешествия» по списку путем последовательных переходов от одного элемента к другому.
В отличие от последовательного списка связный список относится к динамическим структурам данных. Для них характерны непредсказуемость в числе элементов, которое может быть нулевым, а может и ограничиваться объемом доступной памяти. Другая характеристика связного списка — необязательная физическая смежность элементов в памяти.
Относительно связующей части различают следующие типы связных списков.

• Односвязный список — список, начало которого определяется указателем начала, а каждый элемент списка содержит указатель на следующий элемент. Последний элемент должен содержать признак конца списка или указатель на первый элемент списка. В последнем случае мы имеем одно-связный кольцевой список. Преимущество последнего состоит в том, что просмотр всех элементов списка можно начинать с любого элемента, а не только с головы. Более того, в случае кольцевого односвязного списка указателем его начала может быть любой элемент списка. Этот вид списка всегда линейный, так как однозначно задает порядок своего просмотра.
• Двусвязный список — список, связующая часть которого состоит из двух указателей — на предыдущий и последующий элементы. Начало и конец списка определяются отдельными указателями. Последние элементы дву-связного списка в каждом из направлений просмотра содержат признаки конца. Если замкнуть эти указатели друг на друга, то мы получим кольцевой двусвязный список. В этом случае потребность в указателе конца списка отпадает. Этот вид списка может быть как линейным (иметь одинаковый порядок просмотра в обоих направлениях), так и нелинейным (второй указатель каждого элемента списка задает порядок просмотра, который не является обратным порядку, устанавливаемому первым указателем).
• Многосвязный список — список, связующая часть элементов которого в общем случае содержит произвольное количество указателей. В этом виде списка каждый элемент входит в такое количество односвязных списков, сколько он имеет в себе полей связи.

В общем случае для связанных списков определены следующие операции:

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

Связные списки очень важны для представления различных сетевых структур, в частности деревьев, что и будет рассмотрено нами чуть ниже. Пока же рассмотрим работу с некоторыми из обозначенных нами типов связных списков на практических примерах.

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

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

Двусвязные списки

Двусвязный список представляет собой список, связующая часть которого состоит из двух полей. Одно поле указывает на левого соседа данного элемента списка, другое — на правого. Кроме этого, со списком связаны два указателя — на голову и хвост списка (рис. 2.13, сверху). Более удобным может быть представление списка, когда функции этих указателей выполняет один из элементов списка, одно из полей связи которого указывает на последний элемент списка (рис. 2.13, снизу).

Рис 2.13. Схемы организации двухсвязных списков

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

start proc near :точка входа в программу ,
:вывод строки текста - приглашение на ввод сроки для инвертирования :вводим строку текста для инвертирования
.-создаем связанный список, для чего инициализируем заголовок списка
create_doubly_li st Doubly_Head_l i st :вводим символы строки с клавиатуры до тех пор. пока не встретится "."
lea esi.mas cycl: mov al .[esi]
cmpal.V
je rev_out
add_li st i tem_l i st.Doubly_Head_li st.Hand_Head
mov [ebx].info.al
incesi
jmp cycl rev_out: ;вывод строки в обратном порядке
mov esi.offset mas_rev
mov ebx.DoublyJHeadJ i st. 1 ast cycl2: mova 1 .[ebx].info
mov [esi].al
incesi
mov ebx,[ebx].prev
cmp [ebx].info.Offh :дошли до последнего элемента списка"?
jnecycl2
:выводим инвертированную строку на экран :......

Включение в список

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

itemjist struc ; элемент списка
prev dd 0 :адрес предыдущего элемента
info db 0 содержательная часть (в нашем случае - символ)
next dd 0 :адрес следующего элемента
ends
;предполагаем, что адрес локализованного элемента находится в регистре ЕВХ.
:а адрес нового элемента - в ЕАХ
push [ebx].next
pop [eax].next :[ebx].next->[eax].next mcv [eax].prev.ebx;адрес предыд. эл-та->[еах].ргеу mov [ebx].next.eax:адрес след. эл-та->[еЬх].пех1
:будьте внимательны - меняем указатель предыд. эл-та в следующем за новым элементом mov ebx.[eax].next;адрес след. эл-та-KebxJ.next mov [ebx].prev.eax;адрес предыд. эл-та->[еЬх].ргеу

Включение элемента перед локализованным выполняется аналогично. Простота работы с двусвязными списками в отличие от односвязных достигается за счет отсутствия проблем с передвижением по списку в обе стороны.

Исключение из списка

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

itemjist struc ;элемент списка
prev dd 0 ;адрес предыдущего элемента
info db 0 содержательная часть (в нашем случае - символ)
next dd 0 -.адрес следующего элемента
ends
предполагаем, что адрес локализованного элемента находится в регистре ЕВХ
mov eax.[ebx].prev;адрес предыд. эл-та->еах
push [ebx].next
pop [eax].next
mov eax.[ebx].next ;адрес следующ. эл-та->еах
push [ebx].prev
pop [eax].prev

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

Рис. 2.14. Логическая структура нелинейного двусвязного списка