Файл: Алгоритмы и структуры данныхНовая версия для Оберона cdмосква, 2010Никлаус ВиртПеревод с английского под редакцией.pdf

Динамические структуры данных
178
Очевидно, трюк состоит в том, чтобы вставить новую компоненту после p^
,
а потом произвести обмен значениями между новым элементом и p^
Теперь рассмотрим удаление из списка (list deletion). Нетрудно удалить эле%
мент, стоящий сразу за p^
. Эта операция показана здесь вместе с повторной встав%
кой удаленного элемента в начало другого списка (обозначенного переменной q
).
Ситуация показана на рис. 4.9, из которого видно, что имеет место циклический обмен значений трех указателей.
r := p.next; p.next := r.next; r.next := q; q := r
Рис. 4.9. Удаление и повторная вставка
Удаление самого элемента, на который указывает ссылка (а не следующего),
труднее, так как здесь возникает та же проблема, что и со вставкой: невозможно просто так перейти назад от элемента к предшествующему. Но удаление следую%
щего элемента после копирования его значения вперед – довольно очевидное и простое решение. Его можно применить, когда за p^
стоит некоторый элемент, то есть p^
не является последним элементом в списке. Однако необходимо гаранти%
ровать, что нет других переменных, ссылающихся на удаляемый элемент.
Обратимся теперь к фундаментальной операции прохода по списку. Предполо%
жим, что для каждого элемента списка, у которого первый элемент p^
, нужно вы%
полнить некоторую операцию
P(x)
. Эту задачу можно выполнить так:
WHILE
, p, DO
P;

END
Детали этой операции выглядят следующим образом:
WHILE p # NIL DO
P(p); p := p.next
END

179
Из определения оператора while и структуры связей следует, что
P
применяет%
ся ко всем элементам списка и ни к каким другим.
Очень часто используемая операция со списками – поиск в списке элемента с заданным ключом x
. В отличие от массивов, поиск здесь должен быть чисто по%
следовательным. Поиск прекращается, либо когда элемент найден, либо когда до%
стигнут конец списка. Это выражается логической конъюнкцией двух термов.
Снова предположим, что сначала p
указывает на голову списка.
WHILE (p # NIL) & (p.key # x) DO p := p.next END
Равенство p = NIL
означает, что записи p^
не существует, так что выражение p.key # x не определено. Поэтому порядок двух термов важен.
4.3.2. Упорядоченные списки
и перестройка списков
Представленный алгоритм поиска в линейном списке очень похож на поиск в мас%
сиве или последовательности. На самом деле последовательность – это в точности линейный список, для которого способ связи с последующим элементом скрыт.
Поскольку основные операции для последовательностей не допускают вставку новых элементов (разве что в конце) или удаления (кроме удаления всех элемен%
тов), выбор представления отдается полностью на откуп проектировщику, и он может выбрать последовательное размещение в памяти, располагая последо%
вательные компоненты в непрерывных областях памяти. Линейные списки с яв%
ными указателями дают больше гибкости, и поэтому их следует использовать,
когда в такой гибкости есть необходимость.
Чтобы показать различные приемы, рассмотрим в качестве примера задачу,
которая будет возникать на протяжении этой главы. Задача состоит в том, чтобы прочесть текст, определить все слова в нем и подсчитать частоту их появления в тексте. То есть построить алфавитный частотный словарь.
Очевидное решение – строить список слов, обнаруживаемых в тексте. Список просматривается для каждого слова. Если слово в нем найдено, соответствующий счетчик увеличивается; в противном случае слово добавляется в список. Для про%
стоты будем называть этот процесс просто поиском, хотя на самом деле здесь мо%
жет иметь место и вставка. Чтобы сосредоточиться на существенных для нас здесь аспектах работы со списками, предположим, что слова из обрабатываемого текста уже извлечены и закодированы целыми числами, из которых и состоит входная последовательность.
Ниже дана самая прямолинейная формулировка процедуры поиска (процеду%
ра search)
. Переменная root ссылается на голову списка, в который новые слова вставляются по мере необходимости. Полная программа представлена ниже; в нее включена процедура печати построенного списка в виде таблицы. Печать табли%
цы – пример операции, в которой некоторая операция выполняется ровно один раз для каждого элемента списка.
Линейные списки

Динамические структуры данных
180
TYPE Word = POINTER TO
(* ADruS432_List *)
RECORD key, count: INTEGER; next: Word END;
PROCEDURE search (x: INTEGER; VAR root: Word);
VAR w: Word;
BEGIN
w := root;
WHILE (w # NIL) & (w.key # x) DO w := w.next END;
(* (w = NIL) OR (w.key = x) *)
IF w = NIL THEN (* *)
w := root;
NEW(root); root.key := x; root.count := 1; root.next := w
ELSE
INC(w.count)
END
END search;
PROCEDURE PrintList (w: Word);
(* # ˆ W*)
BEGIN
WHILE w # NIL DO
Texts.WriteInt(W, w.key, 8); Texts.WriteInt(W, w.count, 8);
Texts.WriteLn(W);
w := w.next
END
END PrintList;
Алгоритм линейного поиска здесь похож на процедуру поиска для массива, так что можно вспомнить простой прием для упрощения условия завершения цикла –
использование барьера. Этот прием можно применить и при поиске по списку;
тогда барьер представляется вспомогательным элементом в конце списка. Новая процедура приведена ниже. Мы должны предположить, что добавлена глобаль%
ная переменная sentinel и что инициализация root := NIL
заменена операторами
NEW(sentinel); root := sentinel порождающими элемент, который будет использоваться в качестве барьера.
PROCEDURE search (x: INTEGER; VAR root: Word);
(* ADruS432_List2 *)
VAR w: Word;
BEGIN
w := root; sentinel.key := x;
WHILE w.key # x DO w := w.next END;
IF w = sentinel THEN (* *)
w := root;
NEW(root); root.key := x; root.count := 1; root.next := w
ELSE
INC(w.count)
END
END search

181
Очевидно, что мощь и гибкость связного списка в данном примере использу%
ются плохо и что последовательный просмотр всего списка приемлем, только если число элементов невелико. Однако легко сделать простое улучшение: поиск в упо
рядоченном списке. Если список упорядочен (скажем, по возрастанию ключей), то поиск может быть прекращен, как только встретился первый ключ, больший но%
вого. Упорядочение списка достигается вставкой новых элементов в надлежащем месте, а не в начале списка. При этом упорядоченность получается практически бесплатно. Это достигается благодаря легкости вставки элемента в связный спи%
сок, то есть благодаря полному использованию его гибкости. Такой возможности нет ни при работе с массивами, ни с последовательностями. (Однако заметим, что даже упорядоченные списки не дают возможности реализовать аналог двоичного поиска для массивов.)
Рис. 4.10. Вставка в упорядоченный список
Поиск в упорядоченном списке дает типичный пример ситуации, когда новый элемент нужно вставить перед заданным, в данном случае перед первым элемен%
том, чей ключ оказался слишком большим. Однако мы применим здесь новый прием, который отличается от показанного ранее. Вместо копирования значений вдоль списка проходят два указателя; w2
отстает на шаг от w1
и поэтому указыва%
ет на правильное место вставки, когда w1
обнаруживает слишком большой ключ.
Общий шаг вставки показан на рис. 4.10. Указатель на новый элемент (
w3
) дол%
жен быть присвоен полю w2.next
, за исключением того случая, когда список еще пуст. Из соображений простоты и эффективности нежелательно отслеживать этот особый случай с помощью условного оператора. Единственный способ избе%
жать этого – ввести фиктивный элемент в начале списка. Соответственно, опера%
тор инициализации root := NIL
заменяется на
NEW(root); root.next := NIL
Рассматривая рис. 4.10, можно записать условие перехода к следующему эле%
менту; оно состоит из двух термов, а именно
(w1 # NIL) & (w1.key < x)
Линейные списки

Динамические структуры данных
182
Получается такая процедура поиска:
PROCEDURE search (x: INTEGER; VAR root: Word);
(* ADruS432_List3 *)
VAR w1, w2, w3: Word;
BEGIN
(*w2 # NIL*)
w2 := root; w1 := w2.next;
WHILE (w1 # NIL) & (w1.key < x) DO
w2 := w1; w1 := w2.next
END;
(* (w1 = NIL) OR (w1.key >= x) *)
IF (w1 = NIL) OR (w1.key > x) THEN (* *)
NEW(w3); w2.next := w3;
w3.key := x; w3.count := 1; w3.next := w1
ELSE
INC(w1.count)
END
END search
Чтобы ускорить поиск, охрану оператора while опять можно упростить, ис%
пользуя барьер. Тогда с самого начала нужен как фиктивный элемент в начале списка, так и барьер в конце.
Теперь пора спросить, какой выигрыш нам даст поиск в упорядоченном спис%
ке. Помня о том, что дополнительные усложнения оказались малы, не стоит ожи%
дать чуда.
Предположим, что все слова в тексте встречаются с одинаковой частотой.
В этом случае выигрыш от лексикографического упорядочения – после того как все слова включены в список – тоже нулевой, так как положение слова не играет роли, если только полное число всех операций поиска велико и если все слова встречаются с одинаковой частотой. Однако выигрыш имеет место при вставке нового слова. Ведь тогда вместо прохода по всему списку в среднем просматри%
вается только половина списка. Поэтому вставка в упорядоченный список оправ%
дывает себя, только если в обрабатываемом тексте число различных слов велико по сравнению с частотами их появления. И поэтому предыдущие примеры про%
грамм хороши только как упражнения в программировании, но не для практиче%
ского использования.
Организацию данных в связный список можно рекомендовать, когда число элементов относительно мало (< 50), меняется и, более того, когда нет информа%
ции о частоте обращения к ним. Типичный пример – таблица имен в компилято%
рах языков программирования. Каждое объявление добавляет новое имя, которое удаляется из списка после выхода из его области видимости. Использование про%
стых связных списков уместно в приложениях с относительно короткими про%
граммами. Но даже в этом случае можно добиться значительного ускорения дос%
тупа к данным с помощью очень простого приема, который упоминается здесь прежде всего потому, что он представляет собой удачную иллюстрацию гибкости связных списков.

183
Типичное свойство программ состоит в том, что появления одного и того же идентификатора очень часто группируются таким образом, что за одним его появ%
лением то же слово часто появляется еще один или несколько раз. Это обстоя%
тельство наводит на мысль реорганизовывать список после каждой операции по%
иска перемещением найденного слова в голову списка, чтобы уменьшить длину пути поиска, когда это слово нужно будет снова найти. Такой способ доступа на%
зывают поиском с переупорядочением списка, или, несколько помпезно, поиском в самоорганизующемся списке. Представляя соответствующий алгоритм в виде процедуры, воспользуемся уже приобретенным опытом и с самого начала введем барьер. На самом деле наличие барьера не только ускоряет поиск, но в данном слу%
чае еще и упрощает программу. В исходном состоянии список не должен быть пуст,
но уже должен содержать элемент%барьер. Операторы инициализации таковы:
NEW(sentinel); root := sentinel
Заметим, что главное отличие нового алгоритма от простого поиска в списке –
это действия по переупорядочиванию при обнаружении элемента. В этом случае он удаляется со старой позиции и вставляется в голову списка. Такое удаление снова требует пары следующих друг за другом указателей, чтобы помнить поло%
жение предшественника w2
найденного элемента w1
. Это, в свою очередь, требует особой обработки первого элемента (то есть пустого списка). Чтобы стало понят%
ней, какие здесь нужны манипуляции с указателями, на рис. 4.11 показаны два указателя в тот момент, когда w1
был идентифицирован как искомый элемент.
Конфигурация после корректного переупорядочения показана на рис. 4.12
PROCEDURE search (x: INTEGER; VAR root: Word);
(* ADruS432_List4 *)
VAR w1, w2: Word;
BEGIN
w1 := root; sentinel.key := x;
IF w1 = sentinel THEN (* *)
NEW(root); root.key := x; root.count := 1; root.next := sentinel
ELSIF
w1.key = x THEN INC(w1.count)
ELSE (**)
REPEAT w2 := w1; w1 := w2.next
UNTIL w1.key = x;
IF w1 = sentinel THEN (* *)
w2 := root;
NEW(root); root.key := x; root.count := 1; root.next := w2
ELSE (* v, *)
INC(w1.count);
w2.next := w1.next; w1.next := root; root := w1
END
END
END search
Выигрыш в этом методе поиска сильно зависит от степени группировки слов во входных данных. При фиксированной степени группировки выигрыш будет
Линейные списки

Динамические структуры данных
184
тем больше, чем длинней список. Чтобы получить представление об ожидаемом выигрыше, были выполнены эмпирические измерения с использованием выше%
приведенной программы для одного короткого и одного относительно длинного текста, и затем сравнивались методы поиска в упорядоченном списке и поиск с переупорядочиванием. Данные измерений собраны в табл. 4.2. К сожалению,
наибольший выигрыш достигается в том случае, когда данные все равно нужно организовывать по%другому. Мы вернемся к этому примеру в разделе 4.4.
Таблица 4.2.
Таблица 4.2.
Таблица 4.2.
Таблица 4.2.
Таблица 4.2. Сравнение методов поиска в списке
Тест 1
Тест 1
Тест 1
Тест 1
Тест 1
Тест 2
Тест 2
Тест 2
Тест 2
Тест 2
Число разных ключей
53 582
Число появлений ключей
315 14341
Время поиска с упорядочением
6207 3200622
Время поиска с перегруппировкой
4529 681584
Фактор ускорения
1.37 4.70
Рис. 4.12. Список после переупорядочения
Рис. 4.11. Список до переупорядочения

185
4.3.3. Применение: топологическая сортировка
Хороший пример использования гибкой динамической структуры данных – то
пологическая сортировка. Это сортировка элементов, для которых определен
частичный порядок, то есть отношение порядка задано для некоторых, но не для всех пар элементов. Вот примеры частичного упорядочения:
1. В словаре одни слова могут быть определены через другие. Если слово v
используется в определении слова w
, то будем писать v
〈
w
. Топологическая сортировка слов означает такую их расстановку, чтобы каждое слово сто%
яло после всех тех слов, которые нужны для его определения.
2. Задача (например, инженерный проект) разбита на подзадачи. Обычно одни подзадачи должны быть выполнены до выполнения других. Если подзадача v
должна быть выполнена до подзадачи w
, то мы пишем v
〈
w
. Топологическая сортировка означает такую их расстановку, чтобы при начале выполнения каждой подзадачи все нужные подзадачи были бы уже выполнены.
3. В программе университетского обучения некоторые курсы предполагают владение материалом других курсов, которые поэтому должны изучаться раньше первых. Если курс v
должен быть прослушан до курса w
, то мы пи%
шем v
〈
w
. Топологическая сортировка означает расстановку курсов в таком порядке, чтобы все курсы, которые нужно прослушать до некоторого курса,
всегда стояли в списке до него.
4. В программе некоторые процедуры могут содержать вызовы других процедур.
Если процедура v
вызывается в процедуре w
, то пишем v
〈
w
. Топологическая сортировка подразумевает такую расстановку объявлений процедур, чтобы никакая процедура не вызывала еще не объявленные процедуры.
В общем случае частичный порядок на множестве
S
– это некоторое отношение между элементами
S
. Будем обозначать его символом
〈 (читается «предшест%
вует») и требовать выполнения следующих трех свойств (аксиом) для любых раз%
ных элементов x
, y
, z
из
S
:
1) если x
〈
y и y
〈
z
, то x
〈
z
(транзитивность);
2) если x
〈
y
, то неверно, что y
〈
x
(антисимметрия);
3) неверно, что z
〈
z
(нерефлексивность).
По очевидным причинам будем предполагать, что множества
S
, к которым бу%
дет применяться топологическая сортировка, конечны. Поэтому частичная сор%
тировка может быть проиллюстрирована диаграммой или графом, в котором вер%
шины обозначают элементы
S
, а направленные ребра представляют отношения упорядоченности. Пример показан на рис. 4.13.
Задача топологической сортировки – погрузить отношение частичного поряд%
ка в линейный порядок. Графически это подразумевает расположение вершин графа в линию так, чтобы все стрелки указывали вправо, как показано на рис. 4.14.
Свойства (1) и (2) частичного упорядочения гарантируют, что граф не содержит петель. Это в точности то условие, при котором погружение в линейный порядок возможно.
Линейные списки

Динамические структуры данных
186
Как приступить к поиску одного из возможных линейных упорядочений? Ре%
цепт довольно прост. Начнем с выбора любого элемента, у которого нет пред%
шественников (должен существовать хотя бы один такой элемент, иначе в графе будет петля). Этот элемент помещается в начало будущего списка и удаляется из множества
S
. Остаток множества по%прежнему частично упорядочен, и тот же ал%
горитм может применяться снова – до тех пор, пока множество не станет пустым.
Чтобы описать алгоритм более строго, нужно выбрать структуру данных и представление для
S
и для его частичного порядка. Выбор такого представления определяется операциями, которые нужно с ним производить, в частности речь идет об операции выбора элементов, не имеющих предшественников. Поэтому каждый элемент должен представляться тремя характеристиками: своим идентифи%
цирующим ключом, множеством элементов%«последователей» и числом элементов%
«предшественников». Так как число n
элементов в
S
не фиксировано заранее,
множество удобно организовать как связный список. Следовательно, дополни%
тельной компонентой описания каждого элемента будет указатель на следующий элемент списка. Будем считать, что ключи являются целыми (но не обязательно идущими подряд от
1
до n
). Аналогично, множество последователей каждого эле%
мента удобно представить связным списком. Каждый элемент списка последова%
телей описывается своим ключом и указателем на следующий элемент в этом списке. Если дескрипторы главного списка, в котором каждый элемент множества
S
встречается в точности один раз, назвать ведущими (
leader
), а дескрипторы эле%
Рис. 4.13. Частично упорядоченное множество
Рис. 4.14. Расположение в линию частично упорядоченного множества из рис. 4.13

187
ментов в списках последователей – ведомыми (
trailer
), то придем к следующим объявлениям типов данных:
TYPE Leader =
POINTER TO LeaderDesc;
Trailer =
POINTER TO TrailerDesc;
LeaderDesc = RECORD key, count: INTEGER;
trail: Trailer; next: Leader
END;
TrailerDesc = RECORD id: Leader; next: Trailer
END
Предположим, что множество
S
и отношения порядка между его элементами изначально представлены как последовательность пар ключей во входном файле.
Такие входные данные для примера на рис. 4.13 представлены ниже, где для ясно%
сти явно указаны символы б , обозначающие отношение частичного порядка:
1
〈 2 2
〈 4 4
〈 6 2
〈 10 4
〈 8 6
〈 3 1
〈 3 3
〈 5 5
〈 8 7
〈 5 7
〈 9 9
〈 4 9
〈 10
Первая часть программы топологической сортировки должна прочесть вход%
ные данные и преобразовать их в некую списковую структуру. Это делается последовательным чтением пар ключей x
и y
(
x
〈
y
). Обозначим указатели на их представления в связном списке ведущих как p
и q
. Эти записи нужно найти в списке, а если их там еще нет, вставить в этот список. Данная задача решается процедурой%функцией find
. Затем к списку ведомых для x
нужно добавить новый дескриптор, содержащий ссылку на q
; счетчик предшественников для y
увели%
чивается на 1. Этот алгоритм называется фазой ввода. Рисунок 4.15 показывает списочную структуру, порождаемую при обработке вышеприведенных входных данных. Функция find(w)
выдает указатель на элемент списка с ключом w
В следующем фрагменте программы мы используем средства сканирования
текстов системы Оберон. Здесь текст рассматривается как последовательность не литер, a лексем, которые могут быть идентификаторами, числами, цепочками литер, а также специальными литерами (такими как +, *, < и т. д.). Процедура
Texts.Scan(S)
просматривает текст, читая очередную лексему. Сканер
S
является разновидностью бегунка для текстов.
(*! *)
NEW(head); tail := head; Texts.Scan(S);
WHILE S.class = Texts.Int DO
x := S.i; Texts.Scan(S); y := S.i; p := find(x); q := find(y);
NEW(t); t.id := q; t.next := p.trail;
p.trail := t; INC(q.count); Texts.Scan(S)
END
После того как в фазе ввода построена структура данных, показанная на рис. 4.15, можно начинать выполнение собственно топологической сортировки,
описанной ранее. Но так как она состоит из повторяющегося выбора элемента с нулевым числом предшественников, разумно сначала собрать все такие элемен%
Линейные списки