Упражнения
5.1. Если объем информации, связанной с каждым ключом, относительно велик
(в сравнении с самим ключом), то ее не следует хранить в хэш%таблице. Объ%
ясните, почему, и предложите схему представления такого набора данных.
5.2. Рассмотрите решение проблемы скучивания, состоящее в построении деревьев вместо списков переполнения, то есть в организации ключей, претерпевших коллизию, в виде древесной структуры. Тогда каждый элемент хэш%таблицы может рассматриваться как корень (возможно, пустого) дерева. Сравните среднюю производительность такого метода хэширования с деревьями с про%
изводительностью метода открытой адресации.
5.3. Придумайте схему, в которой для разрешения коллизий при вставках и уда%
лениях из хэш%таблицы используются квадратичные приращения. Проведи%
те экспериментальное сравнение такой схемы с простым двоичным деревом,
используя случайную последовательность ключей для вставки и удаления.
5.4. Главный недостаток методов, использующих хэш%таблицы, – в том, что раз%
мер таблицы фиксируется, когда окончательное число элементов еще не из%
вестно. Предположим, что в вашей вычислительной системе есть механизм динамического распределения памяти, позволяющий получить память в лю%
бой момент. Тогда если хэш%таблица
H
заполнена (или почти заполнена), со%
здается большая таблица
H'
, и все ключи переносятся из
H
в
H'
, после чего область памяти из%под
H
возвращается системе управления памятью. Это так называемое повторное хэширование. Напишите программу, которая выпол%
няет повторное хэширование таблицы
H
размера
N
5.5. Очень часто ключи – не целые числа, а последовательности литер. Такие сло%
ва могут сильно варьироваться по длине, и поэтому хранить их в полях фик%
сированного размера неудобно и расточительно. Напишите программу, кото%
рая работает с хэш%таблицей и с ключами переменной длины.
Литература
[5.1] Maurer W. D. An Improved Hash Code for Scatter Storage. Comm. ACM, 11, No.
1 (1968), 35–38.
[5.2] Morris R. Scatter Storage Techniques. Comm. ACM, 11, No. 1 (1968), 38–43.
[5.3] Peterson W. W. Addressing for Random%access Storage. IBM J. Res. & Dev., 1
(1957), 130–146.
[5.4] Schay G. and Spruth W. Analysis of a File Addressing Method. Comm. ACM, 5,
No. 8 (1962) 459–462.
Упражнения
Приложение A
Множество символов ASCII
0 10 20 30 40 50 60 70 0
nul dle
0
@
P
'
p
1
soh dc1
!
1
A
Q
a q
2
stc dc2
"
2
B
R
b r
3
etx dc3
#
3
C
S
c s
4
eot dc4
$
4
D
T
d t
5
enq nak
%
5
E
U
e u
6
ack syn
&
6
F
V
f v
7
bel etb
'
7
G
W
g w
8
bs can
(
8
H
X
h x
9
ht em
)
9
I
Y
i y
A
lf sub
*
:
J
Z
j z
B
vt esc
+
;
K
[
k
{
C
ff fs
,
<
L
\
l
|
D
cr gs
-
=
M
]
m
}
E
so rs
>
N
^
n
F
si us
/
?
O
_
o del
Приложение B
Синтаксис Оберона
1. Синтаксис Оберона
ident = letter {letter | digit}.
number = integer | real.
integer = digit {digit} | digit {hexDigit} "H" .
real = digit {digit} "." {digit} [ScaleFactor].
ScaleFactor = ("E" | "D") ["+" | "-"] digit {digit}.
hexDigit = digit | "A" | "B" | "C" | "D" | "E" | "F".
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9".
CharConstant = """ character """ | digit {hexDigit} "X".
string = """ {character} """ .
qualident = [ident "."] ident.
identdef = ident ["*"].
TypeDeclaration = identdef "=" type.
type = qualident | ArrayType | RecordType | PointerType | ProcedureType.
ArrayType = ARRAY length {"," length} OF type.
length = ConstExpression.
RecordType = RECORD ["(" BaseType ")"] FieldListSequence END.
BaseType = qualident.
FieldListSequence = FieldList {";" FieldList}.
FieldList = [IdentList ":" type].
IdentList = identdef {"," identdef}.
PointerType = POINTER TO type.
ProcedureType = PROCEDURE [FormalParameters].
VariableDeclaration = IdentList ":" type.
designator = qualident {"." ident | "[" ExpList "]" | "(" qualident ")" | "^" }.
ExpList = expression {"," expression}.
expression = SimpleExpression [relation SimpleExpression].
relation = "=" | "#" | "<" | "<=" | ">" | ">=" | IN | IS.
SimpleExpression = ["+"|"-"] term {AddOperator term}.
AddOperator = "+" | "-" | OR .
term = factor {MulOperator factor}.
MulOperator = "*" | "/" | DIV | MOD | "&" .
factor = number | CharConstant | string | NIL | set |
designator [ActualParameters] | "(" expression ")" | "" factor.
set = "{" [element {"," element}] "}".
element = expression [".." expression].
ActualParameters = "(" [ExpList] ")" .
Приложение В
266
statement = [assignment | ProcedureCall |
IfStatement | CaseStatement | WhileStatement | RepeatStatement |
LoopStatement | WithStatement | EXIT | RETURN [expression] ].
assignment = designator ":=" expression.
ProcedureCall = designator [ActualParameters].
IfStatement = IF expression THEN StatementSequence
{ELSIF expression THEN StatementSequence}
[ELSE StatementSequence]
END.
CaseStatement = CASE expression OF case {"|" case} [ELSE StatementSequence] END.
Case = [CaseLabelList ":" StatementSequence].
CaseLabelList = CaseLabels {"," CaseLabels}.
CaseLabels = ConstExpression [".." ConstExpression].
WhileStatement = WHILE expression DO StatementSequence END.
LoopStatement = LOOP StatementSequence END.
WithStatement = WITH qualident ":" qualident DO StatementSequence END .
ProcedureDeclaration = ProcedureHeading ";" ProcedureBody ident.
ProcedureHeading = PROCEDURE identdef [FormalParameters].
ProcedureBody = DeclarationSequence [BEGIN StatementSequence] END.
ForwardDeclaration = PROCEDURE "^" identdef [FormalParameters].
FormalParameters = "(" [FPSection {";" FPSection}] ")" [":" qualident].
FPSection = [VAR] ident {"," ident} ":" FormalType.
FormalType = {ARRAY OF} qualident.
DeclarationSequence = {CONST {ConstantDeclaration ";"} |
TYPE {TypeDeclaration ";"} | VAR {VariableDeclaration ";"}}
{ProcedureDeclaration ";" | ForwardDeclaration ";"}.
Module = MODULE ident ";" [ImportList] DeclarationSequence
[BEGIN StatementSequence] END ident "." .
ImportList = IMPORT import {"," import} ";" .
Import = ident [":=" ident].
2. Символы и ключевые слова
+
:=
ARRAY
IS
TO
-
^
BEGIN
LOOP
TYPE
*
=
CASE
MOD
UNTIL
/
#
CONST
MODULE
VAR
<
DIV
NIL
WHILE
&
>
DO
OF
WITH
<=
ELSE
OR
,
>=
ELSIF
POINTER
;
END
PROCEDURE
|
:
EXIT
RECORD
(
)
IF
REPEAT
[
]
IMPORT
RETURN
{
}
IN
THEN
267 Синтаксис Оберона 3. Стандартные типы данныхCHAR, BOOLEAN, SHORTINT (8 бит) INTEGER (16 or 32 bits) LONGINT, REAL, SET (32 bits) LONGREAL (64 bits) 4. Стандартные функции и процедурыИмя Тип аргумента Тип результата ABS(x) числовой тип x абсолютное значение ODD(x) целый тип BOOLEAN x MOD 2 = 1 CAP(x) CHAR CHAR соответствующая заглавная буква ASH(x, n) целые типы LONGINT x × 2 n (арифметический сдвиг) LEN(v, n) v: массивовый тип LONGINT длина v в n %м измерении LEN(v) v: массивовый тип LONGINT длина v в 0 %м измерении ORD(x) CHAR INTEGER числовой код литеры x CHR(x) INTEGER CHAR литера с числовым кодом x SHORT(x) LONGINT INTEGER тождество (возможна потеря цифр!) INTEGER SHORTINT LONGREAL REAL LONG(x) SHORTINT INTEGER тождество INTEGER LONGINT REAL LONGREAL ENTIER(x) вещественный тип LONGINT наибольшее целое, не превывающее x INC(v, n) целые типы v := v + n INC(v) целые типы v := v + 1 DEC(v, n) целые типы v := v – n DEC(v) целые типы v := v –1 INCL(v, n) v: SET; n: целый тип v := v + {n} EXCL(v, n) v: SET; n: целый тип v := v – {n} COPY(x, v) x : массив литер, цепочка литер v := x NEW(v) указательный тип разместить v^ HALT(x) целая константа остановить вычисление Приложение CЦикл ДейкстрыДейкстра [C.1] (см. также [C.2]) ввел многоветочный вариант цикла WHILE , обо% сновав его в своей теории систематического вывода императивных программ. Этот цикл оказывается удобным для выражения и, главное, верификации алго% ритмов, обычно записываемых через вложенные циклы, позволяя резко снизить усилия по отладке. В версии языка Оберон, известной как Оберон%07 и представленной в [C.3], синтаксис этого цикла определяется следующим правилом: WhileStatement = WHILE # DO {ELSIF # DO } END. Если вычисление любого из логических выражений (охран) дает TRUE , то выполняется соответствующая последовательность операторов. Вычисление охран и выполнение соответствующих последовательностей повторяются до тех пор, пока все охраны не будут давать FALSE . Таким образом, постусловием для этого цикла является конъюнкция отрицаний всех охран. Пример: WHILE m > n DO m := m – n ELSIF n > m DO n := n – m END Постусловие: (m > n) & (n > m) , что эквивалентно n = m Инвариант цикла должен выполняться в начале и в конце каждой ветви. Грубо говоря, обычно n %веточный цикл Дейкстры соответствует конструк% циям из n обычных циклов, каким%то образом вложенных друг в друга. Удобство цикла Дейкстры обусловлено тем, что вся логика сколь угодно слож% ного цикла выводится на один уровень и радикально проясняется, причем алго% ритмы с разными случаями запутанных циклов трактуются совершенно едино% образно. Эффективный способ построения такого цикла состоит в том, чтобы перечислять все возможные ситуации, которые могут возникнуть, описывая их соответствующи% ми охранами, и для каждой из них независимо от остальных строить операции, обес% печивающие продвижение по данным, вместе с операциями, обеспечивающими восстановление инварианта. Перечисление ситуаций заканчивается, когда дизъ% 269 Цикл Дейкстры юнкция (или) всех охран покроет предполагаемое предусловие цикла. При этом задача корректного построения цикла облегчается, если отложить беспокойство о порядке вычисления охран и выполнения ветвей, экономии операций при вычис% лении охран и т. п. до тех пор, пока цикл не будет корректно построен. Такие мел% кие оптимизации редко по%настоящему важны, а их реализация сильно облегчает% ся, когда корректность сложного цикла уже обеспечена. Хотя в теории Дейкстры последовательность выбора ветвей цикла и вычисле% ния соответствующих охран не определена, в этой книжке принято, что охраны вычисляются в текстуальном порядке. Во многих языках программирования цикл Дейкстры приходится моделиро% вать. В старых версиях Оберона, включая Компонентный Паскаль, достаточно использовать цикл LOOP , тело которого состоит из многоветочного условного опе% ратора с оператором выхода в ветке ELSE : LOOP IF # THEN {ELSIF # THEN } ELSE EXIT END END. В других языках конструкция может быть более громоздкой, но это с лихвой окупается упрощением построения и отладки сложных циклов. Литература[C.1] Dijkstra E. W. A Discipline of Programming. Prentice%Hall, 1976 (имеется пе% ревод: Дейкстра Э. Дисциплина программирования. – М.: Мир, 1978). [C.2] Gries D. The Science of Programming. Springer%Verlag, 1981 (имеется пере% вод: Грис Д. Наука программирования. – М.: Мир, 1984). [C.3] Wirth N. The Programming Language Oberon. Revision 1.9.2007. EBNF, 48 In situ, 72 n%ка (n%tuple), 29 N%путевое слияние, 109 NIL (особое значение указателей), 173 p%набор, 100 Абстракция, 18 АВЛ%дерево, 210 Адрес, 32 Активный источник, 111 Алгоритм Бойера и Мура, 63 Алгоритм Кнута, Морриса и Пратта, 58 Алгоритм с возвратом, 143 Алфавитный частотный словарь, 179 Аргумент поиска (искомое значение), 49 Б%дерево, 229 Базовый тип, 21 Базовый тип дерева, 191 Базовый тип массива, 26 Базовый тип последовательности, 35 Байт, 32 Балансировка, 210 Балансировка страниц (дерева), 234 Барьер, 50 Бегунок (объект доступа), 37 Бинарное (двоичное) дерево, 194 БМ%алгоритм, 63 Буфер, 36 Буферизация, 36 Быстрая сортировка, 88 Вес дерева, 222 Взаимное исключение, 45 Взвешенная длина путей (дерева), 220 Внешняя сортировка, 70 Внутренний узел, 193 Внутренняя сортировка, 70 Возврат, 148 Восстановление баланса (дерева), 210 Вставка в сбалансированное дерево, 211 Вставка в список, 177 Выравнивание, 32 Вырожденное дерево, 221 Высота дерева, 191 Гильбертова кривая, 137 Глубина дерева, 191 Горизонтальное распределение, 118 ДБ%дерево, 239 Двоичное (бинарное) дерево, 194 Двоичное Б%дерево, 239 Двунаправленный список, 251 Двухфазная сортировка, 98 Двухфазная сортировка, 98 Декартово дерево, 247 Дерево, 191 Дерево Фибоначчи, 211 Дерево поиска, 199 Динамическая структура данных, 168 Динамическое распределение памяти, 171 Длина внешний путей, 193 Длина внутренних путей, 193 Длина массива, 27 Длина последовательности, 35 Длина путей (дерева), 193 Длина пути (узла в дереве), 193 Естественные слияния, 102 Задача о восьми ферзях, 149 Задача о путешествии шахматного коня, 143 Задача о стабильных браках, 154 Задача оптимального выбора, 160 Записевый тип, 30 Запись, 30 Идеально сбалансированное дерево, 196 Идентификатор поля (записи), 30 Инвариант (цикла), 50 Индекс (компоненты массива), 27 Индексированная переменная, 27 Источник, 99 Каскадное слияние, 129 Ключ элемента, 72 КМП%алгоритм, 62 Коллизия, 256 Кольцевой буфер, 43 Компонента массива, 26 Концевая литера, 53 Концевая рекурсия, 134 Концевой (терминальный) узел, 193 Корень дерева, 191 Косвенно рекурсивная (процедура), 133 Коэффициент заполнения, 262 Красно%черное дерево, 246 Кривая Серпиньского, 139 Куча (приоритетное дерево), 247 Лексема, 187 Лексикографическое дерево, 203 Линейный поиск, 50 Линейный список, 175 Лист (дерева), 193 Максимальная серия, 103 Массив, 26 Массивовый тип, 27 Предметный указатель
Предметный указатель
271
Матрица, 28
Медиана, 93
Метод квадратичных проб, 259
Метод линейных проб, 258
Метод структурирования (данных), 22
Механизм доступа, 37
Многопутевое слияние, 109
Многофазная сортировка, 113
Множество, 26
Модуль, 40
Монитор, 45
Мощность типа, 21
Область переполнения, 258
Обход дерева, 197
Общие переменные, 45
Объект доступа (бегунок), 37
Объявление, 20
Однофазная сортировка, 98
Определение, 39
Оптимальное решение, 160
Открытая адресация, 258
Отпимальное дерево поиска, 221
Охрана, 43
Переполнение, 23
Пирамида, 84
Повторное хэширование, 263
Поддеревья, 191
Поиск, 49
Поиск в списке, 179
Поиск в таблице, 53
Поиск в упорядоченном списке, 181
Поиск делением пополам, 51
Поиск образца в тексте, 54
Поиск по дереву со вставкой, 200
Поиск с переупорядочением списка, 183
Поле (записи), 30
Порядок Б%дерева, 229
Последовательность (sequence), 35
Последовательный доступ, 36
Последовательный файл, 36
Постусловие, 50
Потомок (узла в дереве), 191
Потребитель, 42
Правило стабильных браков, 154
Предок (узла в дереве), 191
Предусловие, 41
Преобразование ключей, 256
Приемник, 99
Примитивный тип, 22
Приоритетное дерево поиска, 247
Присваивание, 22
Проба, 256
Производитель, 42
Произвольный (прямой) доступ, 27
Просеивание, 85
Простая сортировка вставками, 73
Простая сортировка выбором, 76
Простая сортировка обменами (пузырьковая), 78
Простая сортировка слияниями, 97
Простой (линейный) список, 175
Простой поиск образца в тексте, 55
Простые методы сортировки, 72
Проход, 98
Проход по списку, 178
Прямое связывание, 257
Прямой (произвольный) доступ, 36
Пузырьковая сортировка, 78
Пустое дерево, 191
Разрешение коллизий, 256
Распределение начальных серий, 123
Расширенная нормальная нотация Бэкуса
(EBNF), 48
Рекурсивный объект, 132
Рекурсивный тип, 168
Ротация (узлов дерева), 214
Сбалансированное дерево, 210
Сбалансированные слияния, 98
Сборка мусора, 207
Связный список, 176
СДБ%дерево, 242
Селектор (компоненты массива), 27
Селектор (поля записи), 30
Серия, 102
Сигнал, 44
Сильно ветвящееся дерево, 194;, 229
Симметричное двоичное Б%дерево, 242
Сканер (scanner), 48
Сканирование текстов, 187
Слипание серий, 119
Слияние, 97
Слово (единица пересылки данных), 32
Слово (цепочка литер), 53
Смещение, 34
Создание списка, 176
Сопрограмма, 126
Сортировка, 70
Сортировка Шелла, 82
Сортировка двоичными вставками, 74
Сортировка последовательностей, 97
Сортировка слияниями, 97
Составляющие типы, 21, 29
Составной или структурированный тип, 21, 29
Список, 175
Сравнение, 22
Статическая структура данных, 168
Степень узла дерева, 193
Страница (поддерево), 229
Строка (серия), 102
Структура данных, 11
Терминальный (концевой) узел, 193
Предметный указатель 272 Никлаус Вирт Алгоритмы и структуры данныхНовая версия для Оберона + CDГлавный редактор Мовчан Д. А.dm@dmkpress.ru Перевод Ткачев Ф. В.Корректор Синяева Г. И.Верстка Чаннова А. А.Дизайн обложки Харевская И. В.Подписано в печать 05.10.2009. Формат 70 ×100 1 / 16 Гарнитура «Петербург». Печать офсетная. Усл. печ. л. 36. Тираж 1000 экз. № Web%сайт издательства: www.dmk%press.ru Internet%магазин: www.alians%kniga.ru Тип (данных), 20 Топологическая сортировка, 185 Трехленточное слияние, 98 Турнирная сортировка, 83 Удаление из дерева, 206 Удаление из сбалансированного дерева, 216 Удаление из списка, 178 Указатель, 170 Упаковка, 33 Упорядоченное двоичное дерево, 194 Упорядоченное дерево, 191 Упорядоченный список, 179 Упорядоченный тип, 22 Упрятывание информации, 39 Уровень строки, 117 Уровень узла, 191 Устойчивый метод сортировки, 72 Фаза (сортировки), 98 Фаза ввода, 187 Файл, 36 Файловая переменная, 37 Фиктивные серии, 117 Фундаментальный тип, 168 Хэш%таблица, 259 Хэш%функция, 257 Хэширование, 257 Цена (дерева поиска), 221 Центроид, 227 Цепочка литер, 53 Цикл Дейкстры, 55;, 268 Циклический список, 251 Частичный порядок, 185 Числа Леонардо, 211 Числа Фибоначчи порядка p, 116 Шейкер%сортировка, 79 Эффективные сортировки, 81 Явно рекурсивная (процедура), 133 |
Скачать 2.67 Mb.