Структуры данных и проектирование программ

СТРУКТУРЫ ДАННЫХ
И  ПРОЕКТИРОВАНИЕ
ПРОГРАММ

THIRD EDITION

St. Mary’s University
Halifax, Nova Scotia

PRENTICE HALL
Upper Saddle River, New Jersey 07458

DATA STRUCTURES
AND
PROGRAM DESIGN

Robert L. Kruse

Р. Круз
Р. Круз
Р. Круз
Р. Круз

СТРУКТУРЫ ДАННЫХ
И ПРОЕКТИРОВАНИЕ
ПРОГРАММ

Перевод 3-го английского издания
К. Г. Финогенова 

Москва
Лаборатория знаний
2021

4-е издание, электронное

УДК 004.7
ББК 32.973.202
К84
С е р и я о с н о в а н а в 2005 г.
Круз Р. Л.
К84
Структуры данных и проектирование программ / Р. Л. Круз ;
пер. с англ. — 4-е изд., электрон. — М. : Лаборатория знаний,
2021. — 768 с. — (Программисту). — Систем.
требования:
Adobe
Reader
XI
;
экран 10". — Загл. с титул. экрана. — Текст
:
электронный.
ISBN 978-5-93208-560-8
В качестве фундаментальных средств разработки программ рассматриваются такие вопросы, как структурное решение задач, абстракция данных,
принципы программной инженерии и сравнительный анализ алгоритмов.
Дано полное освещение большинства модулей знаний, касающихся структур
данных и алгоритмов.
Б´ольшая часть глав начинается основной темой и сопровождается
примерами, приложениями и практическими исследованиями.
Это учебное пособие дает основательные знания, которые позволяют
студентам по ходу своей дальнейшей работы использовать ее также
в качестве справочного пособия.
УДК 004.7
ББК 32.973.202

Деривативное издание на основе печатного аналога: Структуры данных и проектирование программ / Р. Л. Круз ; пер. с англ. — М. : БИНОМ.
Лаборатория знаний, 2008. — 765 с. : ил. — (Программисту).
ISBN 978-5-94774-879-6.

В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений, установленных
техническими
средствами
защиты
авторских
прав,
правообладатель
вправе
требовать
от
нарушителя возмещения убытков или выплаты компенсации

ISBN 978-5-93208-560-8

Authorized
Translation
from
the
English
language
edition,
entitled
DATA
STRUCTURES AND PROGRAM DESIGN, 3rd Edition; by ROBERT KRUSE; and
by BILL ZOBRIST; published by Pearson Education, Inc, publishing as Prentice
Hall. Copyright © 1994 by Prentice Hall, Inc. All rights reserved. No part
of this book may be reproduced or transmitted in any form or by any means,
electronic or mechanical, including photocopying, recording or by any information
storage retrieval system, without permission from Pearson Education, Inc. Electronic
RUSSIAN language edition published by BKL PUBLISHERS. Copyright © 2014.

Авторизованный перевод издания на английском языке, озаглавленного DATA
STRUCTURES AND PROGRAM DESIGN, авторы ROBERT KRUSE и BILL
ZOBRIST, опубликованного Pearson Education, Inc, осуществляющим издательскую деятельность под торговой маркой Prentice Hall. Copyright © 1994
by Prentice Hall, Inc. Все права защищены. Воспроизведение или распространение какой-либо части/частей данной книги в какой-либо форме, какими-либо
способами, электронными или механическими, включая фотокопирование,
запись и любые поисковые системы хранения информации, без разрешения
Pearson Education, Inc запрещены. Электронная русскоязычная версия издана
BKL Publishers. Copyright © 2014.
© Перевод, оформление. Лаборатория знаний, 2015

Оглавление

Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14

Краткий обзор . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15

Изменения в третьем издании . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17

Структура курса . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18

Разработка книги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19

Благодарности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20

Глава 1.
Принципы программирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21

1.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21

1.2. Игра «Жизнь» . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24

1.2.1. Правила игры «Жизнь» . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24

1.2.2. Примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25

1.2.3. Решение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26

1.2.4. Life: главная программа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27

1.3. Стиль программирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29

1.3.1. Имена . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29

1.3.2. Документация и форматы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32

1.3.3. Детализация программы и модульность . . . . . . . . . . . . . . . . . .
33

1.4. Кодирование, тестирование и дальнейшая детализация . . . . . . . . . .
39

1.4.1. Заглушки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39

1.4.2. Подсчет соседей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40

1.4.3. Ввод и вывод . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42

1.4.4. Драйверы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46

1.4.5. Трассировка программы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47

1.4.6. Принципы тестирования программы . . . . . . . . . . . . . . . . . . . . .
48

Подсказки и ловушки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52

Обзорные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
54

Литература для дальнейшего изучения . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
55

Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
55

Программистские принципы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
55

Игра «Жизнь» . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
56

Глава 2.
Введение в программную инженерию . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57

2.1. Поддержка программ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57

2.1.1. Обзор программы Life . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
58

2.1.2. Новый старт и новый метод для программы Life . . . . . . . . . .
60

2.2. Разработка алгоритма: второй вариант программы Life . . . . . . . . . .
63

2.2.1. Списки: спецификации для структуры данных . . . . . . . . . . . .
63

Оглавление

2.2.2. Программа Main . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
68

2.2.3. Сокрытие информации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
70

2.2.4. Детализация: разработка подпрограмм . . . . . . . . . . . . . . . . . . .
71

2.2.5. Верификация и алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
75

2.3. Кодирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
78

2.3.1. Пакет обработки списков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
79

2.3.2. Обработка ошибок . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
80

2.3.3. Демонстрация и тестирование . . . . . . . . . . . . . . . . . . . . . . . . . .
81

2.4. Кодирование процедур программы Life . . . . . . . . . . . . . . . . . . . . . . . .
85

2.5. Анализ и сравнение программ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
89

2.6. Заключение и предварительный просмотр . . . . . . . . . . . . . . . . . . . . . .
91

2.6.1. Игра «Жизнь» . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
92

2.6.2. Разработка программы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
93

2.6.3. Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
96

Подсказки и ловушки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
99

Обзорные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
99

Литература для дальнейшего изучения . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
99

Глава 3.
Стеки и рекурсия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
101

3.1. Стеки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
101

3.1.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
101

3.1.2. Первый пример: реверсирование строки . . . . . . . . . . . . . . . . .
102

3.1.3. Сокрытие информации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
104

3.1.4. Спецификации для стека . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
105

3.1.5. Реализация стеков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
107

3.1.6. Связные стеки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
109

3.2. Введение в рекурсию . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
116

3.2.1. Кадры стека для подпрограмм . . . . . . . . . . . . . . . . . . . . . . . . . .
116

3.2.2. Дерево вызовов подпрограмм . . . . . . . . . . . . . . . . . . . . . . . . . . .
117

3.2.3. Факториалы: рекурсивное определение . . . . . . . . . . . . . . . . . .
119

3.2.4. Метод разбиения: башни Ханоя . . . . . . . . . . . . . . . . . . . . . . . . .
121

3.3. Принципы рекурсии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
128

3.3.1. Разработка рекурсивных алгоритмов . . . . . . . . . . . . . . . . . . . . .
128

3.3.2. Как работает рекурсия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
129

3.3.3. Хвостовая рекурсия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
134

3.3.4. Когда не следует использовать рекурсию . . . . . . . . . . . . . . . . .
136

3.3.5. Рекомендации и заключения . . . . . . . . . . . . . . . . . . . . . . . . . . . .
140

Подсказки и ловушки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
142

Обзорные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
143

Литература для дальнейшего изучения . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
143

Глава 4.
Примеры рекурсии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
145

4.1. Алгоритмы с отходом: откладывание работы . . . . . . . . . . . . . . . . . . .
145

4.1.1. Решение задачи о восьми ферзях . . . . . . . . . . . . . . . . . . . . . . . .
146

4.1.2. Пример: четыре ферзя . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
146

4.1.3. Алгоритм с отходом . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
148

4.1.4. Детализация: выбор структур данных . . . . . . . . . . . . . . . . . . . .
148

4.1.5. Анализ алгоритма с отходом . . . . . . . . . . . . . . . . . . . . . . . . . . . .
152

Оглавление
7

4.2. Древовидные программы: прогнозирование в играх . . . . . . . . . . . . .
154

4.2.1. Деревья игр . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
154

4.2.2. Метод минимакса . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
156

4.2.3. Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
157

4.2.4. Детализация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
159

4.3. Компиляция методом рекурсивного спуска . . . . . . . . . . . . . . . . . . . . .
161

4.3.1. Главная программа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
162

4.3.2. Объявления типов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
163

4.3.3. Синтаксический анализ предложений . . . . . . . . . . . . . . . . . . . .
164

4.3.4. Синтаксический анализатор предложений языка Pascal . . . .
168

Подсказки и ловушки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
179

Обзорные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
180

Литература для дальнейшего изучения . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
180

Глава 5.
Очереди . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
182

5.1. Определения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
182

5.2. Реализация очередей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
185

5.3. Кольцевые очереди в языке Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
190

5.4. Приложения очередей: Моделирование . . . . . . . . . . . . . . . . . . . . . . . .
195

5.4.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
195

5.4.2. Моделирование работы аэропорта . . . . . . . . . . . . . . . . . . . . . . .
195

5.4.3. Случайные числа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
197

5.4.4. Главная программа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
198

5.4.5. Шаги моделирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
199

5.4.6. Пример результатов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
202

5.5. Связные очереди . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
205

5.6. Приложения: полиномиальная арифметика . . . . . . . . . . . . . . . . . . . . .
210

5.6.1. Цель проекта . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
210

5.6.2. Главная программа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
211

5.6.3. Структуры данных и их реализация . . . . . . . . . . . . . . . . . . . . .
214

5.6.4. Чтение и вывод полиномов . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
216

5.6.5. Сложение полиномов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
218

5.6.6. Завершение проекта . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
220

5.7. Абстрактные типы данных и их реализации . . . . . . . . . . . . . . . . . . . .
222

5.7.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
222

5.7.2. Общие определения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
224

5.7.3. Детализация спецификации данных . . . . . . . . . . . . . . . . . . . . .
227

Подсказки и ловушки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
228

Обзорные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
230

Литература для дальнейшего изучения . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
230

Глава 6.
Списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
231

6.1. Спецификации списков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
231

6.2. Реализация списков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
233

6.2.1. Непрерывная реализация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
234

6.2.2. Реализация простого связывания . . . . . . . . . . . . . . . . . . . . . . . .
235

6.2.3. Вариация: сохранение текущей позиции . . . . . . . . . . . . . . . . .
239

6.2.4. Дважды связные списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
240

6.2.5. Сравнение реализаций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
243

Оглавление

6.3. Цепочки символов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
246

6.3.1. Операции над цепочками символов . . . . . . . . . . . . . . . . . . . . . .
246

6.3.2. Реализация цепочек символов . . . . . . . . . . . . . . . . . . . . . . . . . . .
248

6.4. Приложение: текстовый редактор . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
253

6.4.1. Спецификации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
253

6.4.2. Реализация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
254

6.5. Связные списки в массивах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
261

6.6. Генерирование перестановок . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
271

Подсказки и ловушки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
276

Обзорные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
277

Литература для дальнейшего изучения . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
278

Глава 7.
Поиск . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
279

7.1. Введение и обозначения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
279

7.2. Последовательный поиск . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
281

7.3. Гардеробы: проект . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
287

7.3.1. Введение и спецификации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
287

7.3.2. Демонстрационная и тестирующая программы . . . . . . . . . . .
291

7.4. Двоичный поиск . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
295

7.4.1. Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
296

7.4.2. Вариант с забыванием . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
297

7.4.3. Распознавание равенства . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
299

7.5. Деревья сравнений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
302

7.5.1. Анализ для n=10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
303

7.5.2. Обобщение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
306

7.5.3. Методы сравнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
309

7.5.4. Общее отношение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
310

7.6. Нижние границы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
313

7.7. Асимптотика . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
318

7.7.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
318

7.7.2. О большое . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
319

7.7.3. Неточность определения O большого . . . . . . . . . . . . . . . . . . . .
322

7.7.4. Порядки распространенных функций . . . . . . . . . . . . . . . . . . . .
323

Подсказки и ловушки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
324

Обзорные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
325

Литература для дальнейшего изучения . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
326

Глава 8.
Сортировка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
327

8.1. Введение и обозначения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
327

8.2. Сортировка включением . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
329

8.2.1. Упорядоченные списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
329

8.2.2. Сортировка методом включения . . . . . . . . . . . . . . . . . . . . . . . . .
330

8.2.3. Связный вариант . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
332

8.2.4. Анализ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
334

8.3. Сортировка методом выбора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
339

8.3.1. Алгоритм . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
339

8.3.2. Непрерывная реализация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
340

8.3.3. Анализ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
342

8.3.4. Сравнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
342

Оглавление
9

8.4. Cортировка методом Шелла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   344
8.5. Нижние границы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
347

8.6. Сортировка методом разбиения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
350

8.6.1. Базовые идеи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
350

8.6.2. Пример . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
351

8.7. Сортировка слиянием для связных списков . . . . . . . . . . . . . . . . . . . . .
357

8.7.1. Процедуры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
357

8.7.2. Анализ метода сортировки слиянием . . . . . . . . . . . . . . . . . . . .
359

8.8. Метод быстрой сортировки для непрерывных списков . . . . . . . . . . .
365

8.8.1. Главная процедура . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
365

8.8.2. Разделение списка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
366

8.8.3. Анализ метода быстрой сортировки . . . . . . . . . . . . . . . . . . . . .
368

8.8.4. Анализ метода быстрой сортировки для среднего случая . .
371

8.8.5. Сравнение с методом слияния . . . . . . . . . . . . . . . . . . . . . . . . . .
373

8.9. Пирамиды и пирамидальная сортировка . . . . . . . . . . . . . . . . . . . . . . .
377

8.9.1. Двухвариантные деревья как списки . . . . . . . . . . . . . . . . . . . . .
377

8.9.2. Пирамидальная сортировка . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
379

8.9.3. Анализ пирамидальной сортировки . . . . . . . . . . . . . . . . . . . . . .
382

8.9.4. Очереди с приоритетами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
383

8.10. Обзор: сравнение методов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
386

Подсказки и ловушки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
390

Обзорные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
391

Литература для дальнейшего изучения . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
392

Глава 9.
Таблицы и извлечение информации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
394

9.1.  Введение: переход через барьер lg n . . . . . . . . . . . . . . . . . . . . . . . . . . . .    394
9.2. Прямоугольные массивы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
395

9.3. Таблицы различных форм . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
398

9.3.1. Треугольные таблицы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
398

9.3.2. Рваные таблицы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
400

9.3.3. Инвертированные таблицы . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
401

9.4.  Таблицы: новый абстрактный тип данных . . . . . . . . . . . . . . . . . . . . . . .   404
9.5. Приложение: поразрядная сортировка . . . . . . . . . . . . . . . . . . . . . . . . .
407

9.5.1. Идея метода . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
407

9.5.2. Реализация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
408

9.5.3. Анализ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
411

9.6. Хеширование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
412

9.6.1. Разреженные таблицы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
412

9.6.2. Выбор хеш-функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
414

9.6.3. Разрешение конфликтов с помощью открытой адресации . .
417

9.6.4. Разрешение столкновений посредством связных цепочек . .
422

9.7. Анализ хеширования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
428

9.8. Заключение: сравнение методов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
434

9.9. Приложение: снова игра «Жизнь» . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
435

9.9.1. Выбор алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
435

9.9.2. Спецификация структур данных . . . . . . . . . . . . . . . . . . . . . . . . .
435

9.9.3. Главная программа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
437

9.9.4. Процедуры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
438

Подсказки и ловушки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
442

Оглавление

Обзорные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
443

Литература для дальнейшего изучения . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
444

Глава 10.
Двоичные деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
445

10.1. Двоичные деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
445

10.1.1. Определения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445
10.1.2. Просмотр двоичных деревьев . . . . . . . . . . . . . . . . . . . . . . . . . 448
10.1.3. Связная реализация двоичных деревьев . . . . . . . . . . . . . . . . 453

10.2. Деревья двоичного поиска . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
457

10.2.1. Упорядоченные списки и реализации . . . . . . . . . . . . . . . . . . . 459
10.2.2. Поиск по дереву . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
10.2.3.  Включение в двоичное дерево поиска . . . . . . . . . . . . . . . . . . .   464
10.2.4. Древовидная сортировка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467
10.2.5.  Удаление из двоичного дерева поиска . . . . . . . . . . . . . . . . . . .   469

10.3.  Построение двоичного дерева поиска. . . . . . . . . . . . . . . . . . . . . . . . . . .  477

10.3.1. Начинаем . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478
10.3.2. Объявления и главная процедура . . . . . . . . . . . . . . . . . . . . . . 479
10.3.3. Включение узла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 480
10.3.4. Завершение задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481
10.3.5. Оценка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483
10.3.6. Случайные деревья поиска и оптимизация . . . . . . . . . . . . . . 483

10.4. Балансирование по высоте: AVL-деревья . . . . . . . . . . . . . . . . . . . . .
486

10.4.1. Определение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 487
10.4.2. Включение узла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 488
10.4.3. Удаление узла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494
10.4.4. Высота AVL-дерева . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 498

10.5. Скошенные деревья: самонастраивающиеся структуры данных .
501

10.5.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501
10.5.2. Шаги скашивания дерева . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502
10.5.3. Алгоритм скашивания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505
10.5.4. Амортизационный анализ алгоритмов: введение . . . . . . . . . 509
10.5.5. Амортизационный анализ скашивания . . . . . . . . . . . . . . . . . . 514

Подсказки и ловушки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
519

Обзорные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
520

Литература для дальнейшего изучения . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
522

Глава 11.
Многовариантные деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
524

11.1. Сады, деревья и двоичные деревья . . . . . . . . . . . . . . . . . . . . . . . . . . .
524

11.1.1. Классификация видов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 524
11.1.2. Упорядоченные деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 525
11.1.3. Леса и сады . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 528
11.1.4. Формальное соответствие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 529
11.1.5. Повороты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 530
11.1.6. Резюме . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 531

11.2. Деревья лексикографического поиска: трай-деревья . . . . . . . . . . . .
533

11.2.1. Трай-деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 533
11.2.2. Поиск ключа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 533
11.2.3. Алгоритм на языке Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 534
11.2.4. Включение в трай-дерево . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535