Рис. 11.4 Список Г, использующий фиктивный элемент пг1[Г] (тёмно-серый прямоугольник). Вместо head[L\ используем nexi[nil[L\]. (а) Пустой список, (б) Список рис. 11.3а (элемент с ключом 9 - голова, 1 - хвост), (в) Тот же список после процедуры List-Insert(L, х), если fceg/fa;] = 25. (г) После удаления элемента с ключом 1. Новый хвост имеет ключ 4.

у хвоста списка занесём указатели на nil[L] (рис. 11.4). При этом next[ni\L]\ - указатель на голову списка, так что атрибут head[L] становится лишним. Пустой список L теперь будет кольцом, в котором nil[L] - единственный элемент.

В процедуре List-Search нужно лишь заменить nil на nil[L] и head[L] на next[nil[L]]:

List-Search(L, k)

1х <- next[nil[L]]

2while x ф nil[L] and key[x] ф k

3do x <- next[x]

4return x

Для удаления элемента годится процедура List-Delete, приведённая выше. Наконец, добавлять элемент к списку можно так:

List-Insert(L, х)

1next[x] <- next[nil[L]]

2prev[next[nil[L]]] <- х

3next[nil[L]] <- х

4prev[x] <- nil[L]

Пример работы процедур List-Insert и List-Delete показан на рис. 11.4.

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

Не следует применять фиктивные элементы без нужды. Если алгоритм использует много коротких списков, использование фик-

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

Упражнения

11.2-1 Можно ли добавить элемент в множество, представленное односторонне связанным списком, за время 0(1)? Тот же вопрос для удаления элемента.

11.2-2 Реализуйте стек на базе односторонне связанного списка. Операции Push и Pop должны выполняться за время 0(1).

11.2-3 Реализуйте очередь на базе односторонне связанного списка. Операции Enqueue и Dequeue должны выполняться за время 0(1).

11.2-4 Реализуйте словарные операции Insert, Delete и Search для свёрнутого в кольцо односторонне связанного списка. Каково время работы ваших процедур?

11.2-5 Операция Union (объединение) получает на входе два непересекающихся множества и возвращает их объединение (сами исходные множества при этом пропадают). Реализуйте эту операцию так, чтобы она работала за время 0(1), представляя множества списками подходящего типа.

11.2-6 Напишите процедуру, которая сливает два односторонне связанных упорядоченных списка в один (также упорядоченный), не используя фиктивных элементов. Затем сделайте это, используя фиктивный элемент с ключом оо (добавляемый в конец списков). Какая из двух программ проще?

11.2-7 Напишите нерекурсивную процедуру, которая за время О (га) переставляет элементы односторонне связанного списка в обратном порядке. Объём дополнительной (помимо необходимой для хранения исходного списка) памяти должен быть 0(1).

11.2-8* Есть способ сэкономить место при реализации двусторон-не связанного списка, сжав два указателя next и prev в одно значение гар[ж]. Будем считать, что все указатели суть /г-битные числа и указателю nil соответствует число нуль. Определим пр[х] по формуле пр[х] = next[x] XORprev[x], где XOR - побитовое сложение по модулю 2 (исключающее ИЛИ). Не забудьте указать, каким образом хранится информация о голове списка. Как реализовать операции Search, Insert и Delete? Объясните, как переставить такой список в обратном порядке за время 0(1).

Рис. 11.5 Список рис. 11.3а, представленный с помощью тройки массивов (key, next, prev). Каждому элементу списка соответствует светло-серый столбик. В верхней строчке выписаны порядковые номера, играющие роль указателей; действие указателей показано стрелками. Значение переменной Г - указатель на голову списка.

11.3. Реализация указателей и записей с несколькими полями

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

Представление с помощью нескольких массивов

Массив, составленный из записей, можно заменить несколькими массивами (по одному на каждое поле записи). Например, на рис. 11.5 показано, как представить в виде трёх массивов тот же список, что и на рис. 11.3а: в массиве key хранятся ключи, а в массивах next и prev - указатели. Каждому элементу списка соответствует тройка (key[x], next[x\, prev[x]) для некоторого индекса х. Роль указателя на этот элемент играет число х. В качестве NIL можно использовать число, не являющееся индексом никакого элемента массивов (например, 0 или -1). На рис. 11.3а запись с ключом 4 стоит в списке сразу после записи с ключом 16; и действительно, число 16 стоит в массиве key на месте с номером 5, число 4 - на месте номер 2, и имеем next[5] = 2, а также prev[2] = 5.

В наших программах обозначение типа кеу[х] может пониматься двояко: и как элемент массива key с индексом х, и как поле key записи с адресом х (в зависимости от возможностей языка программирования полезно то или другое понимание).

Представление с помощью одного массива

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