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

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

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

Оглавление
11

11.2.5. Удаление из трай-дерева . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 536
11.2.6. Оценка трай-деревьев . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537

11.3. Внешний поиск: B-деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
538

11.3.1. Время доступа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 538
11.3.2. Многовариантные деревья поиска . . . . . . . . . . . . . . . . . . . . . . 539
11.3.3. Сбалансированные многовариантные деревья . . . . . . . . . . . 539
11.3.4. Включение в B-дерево . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 540
11.3.5. Алгоритмы на языке Pascal: поиск и включение . . . . . . . . . 542
11.3.6. Удаление из B-дерева . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 548

11.4. Красно-черные деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
557

11.4.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 557
11.4.2. Определения и анализ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 558
11.4.3. Включение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 560
11.4.4. Включение на языке Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563

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

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

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

Глава 12.
Графы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
569

12.1. Математические основы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
569

12.1.1. Определения и примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 569
12.1.2. Неориентированные графы . . . . . . . . . . . . . . . . . . . . . . . . . . . . 570
12.1.3. Ориентированные графы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 571

12.2. Компьютерное представление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
572

12.3. Просмотр графа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
576

12.3.1. Методы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 576
12.3.2. Алгоритм просмотра в глубину . . . . . . . . . . . . . . . . . . . . . . . . 577
12.3.3. Алгоритм просмотра в ширину . . . . . . . . . . . . . . . . . . . . . . . . 578

12.4. Топологическая сортировка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
579

12.4.1. Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 579
12.4.2. Алгоритм упорядочения в глубину . . . . . . . . . . . . . . . . . . . . . 581
12.4.3. Алгоритм упорядочения в ширину . . . . . . . . . . . . . . . . . . . . . 582

12.5. Алгоритм экономного продвижения: кратчайшие маршруты . . . .
584

12.6. Графы как структуры данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
589

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

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

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

Глава 13.
Конкретный пример: польская нотация . . . . . . . . . . . . . . . . . . . . . . . . .
593

13.1. Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
593

13.1.1. Формула корней квадратного уравнения . . . . . . . . . . . . . . . . 593

13.2. Идея . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
595

13.2.1. Дерево выражения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 595
13.2.2. Польская нотация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 597
13.2.3. Метод для языка Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 599

13.3. Оценка выражений в польской нотации . . . . . . . . . . . . . . . . . . . . . . .
599

13.3.1. Оценка выражений в префиксной форме . . . . . . . . . . . . . . . . 599
13.3.2. Соглашения языка Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 600
13.3.3. Pascal-процедура для префиксной оценки . . . . . . . . . . . . . . . 601

Оглавление

13.3.4. Оценка постфиксных выражений . . . . . . . . . . . . . . . . . . . . . . 602
13.3.5. Доказательство правильности программы: подсчет элементов 
в стеке . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 603

13.3.6. Рекурсивная оценка постфиксных выражений . . . . . . . . . . . 607

13.4. Преобразование из инфиксной формы в польскую . . . . . . . . . . . . .
611

13.5. Интерактивная программа оценки выражений . . . . . . . . . . . . . . . . .
617

13.5.1. Общая структура . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 618
13.5.2. Представление данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 619
13.5.3. Инициализация и вспомогательные задачи . . . . . . . . . . . . . . 623
13.5.4. Преобразование выражения . . . . . . . . . . . . . . . . . . . . . . . . . . . 627
13.5.5. Оценка выражения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 637
13.5.6. Графическое отображение выражения . . . . . . . . . . . . . . . . . . 639

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

Приложение A. Математические методы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
643

A.1. Суммы степеней целых чисел . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
643

A.2. Логарифмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
645

A.2.1. Определение логарифмов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
646

A.2.2. Простые свойства . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
646

A.2.3. Выбор основания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
647

A.2.4. Натуральные логарифмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
648

A.2.5. Обозначения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
649

A.2.6. Изменение основания логарифмов . . . . . . . . . . . . . . . . . . . . . .
649

A.2.7. Логарифмические графики . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
650

A.2.8. Гармонические числа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
650

A.3. Перестановки, сочетания, факториалы . . . . . . . . . . . . . . . . . . . . . . . .
652

A.3.1. Перестановки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
652

A.3.2. Сочетания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
653

A.3.3. Факториалы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
653

A.4. Числа Фибоначчи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
655

A.5. Числа Каталана . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
656

A.5.1. Основной результат . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
656

A.5.2. Доказательство посредством однозначного соответствия . .
657

A.5.3. История вопроса . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
659

A.5.4. Численные результаты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
659

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

Приложение B. Случайные числа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
663

B.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
663

B.2. Метод . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
664

B.3. Разработка программы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
665

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

Приложение С. Модули, включаемые файлы и утилиты . . . . . . . . . . . . . . . . . . . . .
671

C.1. Модули Turbo Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
671

C.1.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
671

C.1.2. Синтаксис модулей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
672

C.2. Включаемые файлы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
674

C.2.1. Замена модулей включаемыми файлами . . . . . . . . . . . . . . . . .
674

C.2.2. Родовые средства . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
675

Оглавление
13

C.3. Модули, используемые в тексте . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
677

C.3.1. Структуры данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
677

C.3.2. Модуль утилит Utility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
678

C.3.3. Модуль анализа процессорного времени . . . . . . . . . . . . . . . . .
680

C.3.4. Модуль для обслуживания файлов . . . . . . . . . . . . . . . . . . . . . .
682

C.3.5. Модуль случайных чисел . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
685

C.4. Программы поиска и сортировки . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
685

C.4.1. Демонстрационная программа . . . . . . . . . . . . . . . . . . . . . . . . . .
685

C.4.2. Создание файлов данных для тестирования программ . . . . .
686

Приложение D. Свойства языка Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
694

D.1. Записи в языке Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
694

D.2. Процедуры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
700

D.2.1. Процедуры в качестве параметров . . . . . . . . . . . . . . . . . . . . . .
700

D.2.2. Упреждающие объявления . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
702

D.3. Указатели и связные списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
703

D.3.1. Введение и обзор . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
703

D.3.2. Указатели и динамическая память в языке Pascal . . . . . . . . .
707

D.3.3. Основы связных списков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
711

D.3.4. Связная реализация простых списков . . . . . . . . . . . . . . . . . . .
715

D.3.5. Советы для программистов . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
718

D.4. Синтаксические диаграммы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
721

D.5. Общие правила . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
730

D.5.1. Идентификаторы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
730

D.5.2. Правила использования пробелов . . . . . . . . . . . . . . . . . . . . . . .
731

D.5.3. Указания по формату программы . . . . . . . . . . . . . . . . . . . . . . .
732

D.5.4. Пунктуация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
733

D.5.5. Альтернативные знаки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
733

D.6. Стандартные объявления . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
733

D.6.1. Константы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
733

D.6.2. Типы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
735

D.6.3. Переменные . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
735

D.6.4. Процедуры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
736

D.6.5. Функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
736

D.7. Операторы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
737

Предметный указатель . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
738

Ученик плотника довольствуется лишь молотком и пилой, однако мастер
использует более замысловатые инструменты. Также и компьютерное программирование, 
чтобы удовлетворить все возрастающим требованиям современных 
прикладных задач, прибегает к разнообразным утонченным
средствам, и только практическая работа с ними позволяет программисту
приобрести необходимую сноровку в их эффективном использовании. В
этой книге в качестве фундаментальных средств разработки программ рассматриваются 
такие вопросы, как структурное решение задач, абстракция
данных, принципы программной инженерии и сравнительный анализ алгоритмов. 
Для того чтобы показать, как все эти средства совместно используются 
для построения законченных программ, в книге детально разбирается 
несколько примеров значительной сложности.
Многие изучаемые нами алгоритмы и структуры данных обладают
внутренней элегантностью, проявляющейся в том, что внешняя простота
скрывает богатый диапазон и мощь их применений. Очень быстро обу-
чающийся обнаруживает, что наивные методы, обычно предлагаемые во
вводных курсах, нуждаются в очень серьезных улучшениях. Однако эле-
гантность метода сочетается с неопределенностью. Вы вскоре сталкивае-
тесь с тем, что выбор наилучшего из нескольких возможных подходов к
решению конкретной задачи далеко не очевиден. Вот здесь-то и стано-
вится оправданным рассмотрение ряда непростых проблем, интересных
самих по себе и имеющих большое практическое значение, а также показ
применимости математических методов к верификации и анализу алго-
ритмов.
Студенты, приступая к изучению программирования, часто затрудня-
ются в практическом приложении абстрактных идей. Поэтому в настоя-
щей книге особое внимание уделяется вопросам преобразования идей в
алгоритмы, а также дальнейшего уточнения этих алгоритмов с целью по-
лучения конкретных программ, которые уже можно использовать для ре-
шения практических задач. Также на первое место перед выбором струк-
тур данных и их реализации выступает процесс спецификации и абстрак-
ции данных.
Лично я являюсь сторонником движения от конкретного к абстракт-
ному, последовательной разработки мотивирующих примеров, дающих
возможность представить идеи в более общей форме. Большинству сту-
дентов на ранних этапах их обучения требуется помощь в освоении не-
посредственного приложения идей, с которыми они знакомятся, и лучше

Предисловие

всего, если они будут писать и выполнять программы, иллюстрирующие
изучаемые ими концепции. С этой целью книга содержит большое коли-
чество программных примеров, как коротких процедур, так и закончен-
ных программ значительной длины. Более того, упражнения и программ-
ные проекты составляют неотъемлемую часть книги. Многие из этих уп-
ражнений иллюстрируют изучаемую в настоящий момент тему, и их
выполнение требует написания и отладки реальных программ с целью
анализа и сравнения используемых алгоритмов. Другие представляют со-
бой более объемные программные проекты, а некоторые предназначены
для использования небольшой группой работающих совместно студен-
тов.

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

Посредством рассмотрения первого большого проекта (игры «Жизнь»
Дж. Конвея) глава 1 вводит принципы нисходящей детализации, проектирования 
программы, критического обзора и тестирования; демонстрация 
этих принципов позволит студентам использовать их при изучении
последующих разделов. В то же время первый проект позволит студентам 
освежить свои знания языка Pascal, который выбран в качестве базового 
языка программирования для этой книги.
В главе 2 вводятся несколько базовых принципов программной инженерии, 
включая проблемы спецификации и анализа, прототипирова-
ния, абстракции данных, а также разработки, детализации, верификации
и анализа алгоритма. Эти принципы используются при разработке второго 
варианта игры «Жизнь», основанного на алгоритме, достаточно тонком 
для наглядной демонстрации необходимости в точной спецификации
и верификации, и, кроме того, позволяющем показать важность правильного 
выбора структур данных.
Глава 3 продолжает разъяснение концепций абстракции данных и
разработки алгоритмов посредством изучения стеков как абстрактного
типа данных и рекурсии как метода решения задач, а также внутренних
связей между стеками, рекурсией и определенными типами деревьев. В
главе 4 эти концепции иллюстрируются рассмотрением нескольких важ-
ных приложений рекурсии, включая алгоритмы с отходом, программы с
древовидной структурой и рекурсивно-нисходящий синтаксический ана-
лиз.
Центральной темой двух следующих глав являются очереди и спис-
ки. Здесь рассматриваются различные реализации каждого абстрактного
типа данных, строятся большие прикладные программы, демонстрирую-
щие относительные преимущества различных реализаций, и весьма не-
формальным образом вводятся идеи анализа алгоритмов. Основная цель
этих глав — подвести студента к пониманию важности абстракции дан-
ных и к приложению методов нисходящего проектирования как к дан-
ным, так и к алгоритмам.
В главах 7, 8 и 9 рассматриваются алгоритмы поиска, сортировки и
работы с таблицами (включая хеширование). Эти главы демонстрируют

Предисловие
15

Введение
в программную
инженерию

Принципы
программирования

Стеки и рекурсии

Примеры
рекурсий

Очереди

Списки

Поиск
и сортировка

взаимосвязь между алгоритмами и соответствующим им абстрактными
типами данных, структурами данных и реализациями. Здесь вводится по-
нятие «О большого» для элементарного анализа алгоритмов и подчерки-
вается критическая важность выбора, позволяющего наиболее эффектив-
ным образом использовать пространство памяти, время и программи-
стские усилия.
Этот выбор требует применения аналитических методов оценки алго-
ритмов, причем арсенал для проведения такого анализа должна нам
предоставить комбинаторная математика. На начальных стадиях обуче-
ния мы не можем требовать от студентов ни достаточно глубоких зна-
ний, ни математической зрелости, необходимых для оттачивания до со-
вершенства их навыков. Моя цель, таким образом, — помочь студентам
осознать важность приобретения этих навыков при изучении ими в даль-
нейшем соответствующих разделов математики.
Безусловно, к наиболее элегантным и полезным структурам данных
следует отнести двоичные деревья. Их изучение, которому посвящена
глава 10, связывает вместе концепции списков, поиска и сортировки.
Относясь к рекурсивно определяемым структурам данных, двоичные де-
ревья предоставляют студентам превосходную возможность изучить ре-
курсии применительно как к структурам данных, так и к алгоритмам.
Глава начинается с элементарных сведений и постепенно подводит чита-
теля к скошенным деревьям и амортизационному анализу алгоритмов.
В главе 11 продолжается изучение более сложных структур данных,
включая трай-структуры, B-деревья и красно-черные деревья. В следую-
щей главе вводятся графы, как наиболее общие структуры, используемые
при решении задач.
Конкретное исследование в главе 13 позволяет весьма детально рас-
смотреть польскую нотацию и исследовать взаимосвязь рекурсии, де-
ревьев и стеков в качестве средств решения задач и разработки алгорит-
мов. Некоторые аспекты этого исследования могут служить неформаль-
ным введением в проектирование компиляторов. Как и в других местах
книги, представленные алгоритмы разработаны до деталей и включены в
работоспособную Pascal-программу. Эта программа принимает входные
данные в виде обычного (инфиксного) выражения, преобразует это
выражение в постфиксную форму и оценивает его применительно к
заданным значениям переменных.
Приложения посвящены темам, строго говоря, не относящимся к
предмету книги, но часто отсутствующим в начальных курсах.
В приложении A дан обзор ряда вопросов дискретной математики.
Последние два раздела, посвященные числам Фибоначчи и Каталана, яв-
ляются более продвинутыми и необязательны для понимания основного
текста книги, однако они включены с целью развития интереса к комби-
наторике у студентов с математическим складом ума.
В приложении B обсуждаются псевдослучайные числа, программы
генерации таких чисел и их приложения. Этот предмет может заинтере-
совать многих студентов, хотя часто он выпадает из типичных программ
обучения.

16
Предисловие

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

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

Многовариантные
деревья

Графы

Конкретное
исследование:
польская нотация

Математические
методы

Случайные
числа

Приложение C детально описывает использование модулей системы
программирования Turbo Pascal и включаемых (include-) файлов при реа-
лизации абстрактных типов данных. В основном тексте книги в ряде
мест используются специально разработанные процедуры-утилиты и мо-
дули. В приложении C даны развернутые описания этих программных
средств.
Наконец, приложение D посвящено некоторым средствам программи-
рования на языке Pascal, обычно не входящим в начальные курсы обуче-
ния этому языку, именно, записям, процедурным параметрам и упреждаю-
щим объявлениям. Далее, в приложение D включены сведения о типах
указателей языка Pascal и элементарных операциях над указателями и
связными списками, поскольку эти средства являются неотъемлемой ча-
стью языка Pascal, а также с целью придания разделу книги, посвященно-
му связным спискам, большей общности. В завершающей части приложе-
ния D приведены стандартные диаграммы и таблицы, описывающие син-
таксис языка Pascal, а также дополнительная информация, которая может
помочь читателю в решении программистских проблем.

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

При подготовке книги к третьему изданию весь текст был тщательно
просмотрен в плане улучшения представления материала, а также с це-
лью отражения предложений многочисленных читателей, изучавших эту
книгу. Принципиальные изменения заключаются в следующем.
• Все программы были переработаны и улучшены с целью подчеркива-
ния абстракции данных, получения повторно используемого кода и
обеспечения однородности и элегантности стиля.
• Для облегчения этого процесса в книге широко используются модули
Turbo Pascal, хотя и в ненавязчивой форме, чтобы обеспечить беспре-
пятственное преобразование в стандартный Pascal или, при необходи-
мости, в другой диалект языка.
• Расширена документация к программам путем включения во все под-
программы неформальных спецификаций (пред- и постусловий).
• Рекурсия стала использоваться в книге значительно раньше, а ее повтор-
ное постоянное использование подчеркивает важность этого средства.
• В книге расширено представление современных продвинутых тем
включением разделов, посвященных скошенным и красно-черным де-
ревьям и амортизационному анализу алгоритмов.
• Включены новые примеры конкретных исследований, в частности,
синтаксический анализатор предложений языка Pascal и миниатюрный
текстовый редактор.
• Добавлено много новых упражнений и программных проектов, вклю-
чая последовательные варианты проектов, посвященных извлечению
информации, которые требуют от студента сравнительного анализа
производительности различных структур данных и алгоритмов.
• Материал по теории графов и алгоритмам реализации графов выделен
в отдельную главу.

Предисловие
17

Модули,
включаемые файлы
и процедурыутилиты

Средства языка
Pascal

• Рассмотрение списков стало более логичным, во-первых, за счет упро-
щения спецификаций списков, и, во-вторых, перенесением элементар-
ного обзора типов указателей языка Pascal в приложение, где этот ма-
териал изложен более подробно, чем раньше. Такое расположение
материала позволило в основном тексте книги сконцентрировать вни-
мание на основополагающих идеях, не отвлекаясь на детали реализа-
ции.
• Изъяты некоторые устаревшие темы, например, удаление рекурсии.
• Поставлявшийся ранее с книгой программный диск теперь можно при-
обрести у издателя; весь программный пакет также доступен в Интер-
нете. Пакет включает в себя исходные тексты всех программ и про-
граммных фрагментов, вошедших в книгу, вместе с выполнимыми
файлами (для компьютеров IBM PC и совместимых с ними), всех де-
монстрационных программ и почти всех программных проектов этой
книги.
• Для преподавателей имеется также отдельное (бесплатное) пособие,
включающее в себя полные решения всех упражнений и программных
проектов, диск с упомянутым выше программным пакетом, а также вто-
рой диск с полными исходными текстами всех программных проектов.

Структура курса

Для работы над этой книгой студент должен овладеть начальным курсом
программирования и иметь опыт использования элементарных средств
языка Pascal. В приложении D собраны некоторые продвинутые средства
языка Pascal, обычно не включаемые в вводные курсы. Для анализа поч-
ти всех алгоритмов достаточно хорошего знания школьной математики,
хотя знакомство с дискретной математикой (например, параллельно с
чтением книги) будет весьма полезным. В приложении A дан обзор всех
необходимых математических понятий.
Книга предназначена в качестве учебного пособия по таким курсам,
как ACM Course CS2 (Program Design and Implementation, Проектирова-
ние и реализация программ), ACM Course CS7 (Data Structures and
Algorithm Analysis, Структуры данных и анализ алгоритмов), а также кур-
сам, являющимся комбинацией упомянутых выше. В книге дано полное
освещение большинства модулей знаний ACM/IEEE1, касающихся струк-
тур данных и алгоритмов. Сюда входят модули:
AL1 Базовые структуры данных: массивы, таблицы, стеки, очереди, дере-
вья и графы;
AL2 Абстрактные типы данных;
AL3 Рекурсии и рекурсивные алгоритмы;
AL4 Анализ сложности с использованием нотации «О большого»;
AL6 Сортировка и поиск;
AL8 Практические стратегии решения задач с примерами серьезных кон-
кретных исследований.

18
Предисловие

требуемый
исходный
уровень
подготовки

содержание

1
См. Computing Curricula 1991: Report of the ACM/IEEE-CS Curriculum Task Force, ACM Press, New York, 1990.

Три наиболее продвинутых модуля знаний, AL5 (complexity classes
and NP-complete problems, классы сложности и НП-полные задачи), AL7
(computability and undecidability, вычислимость и неразрешимость) и AL9
(parallel and distributed algorithms, параллельные и распределенные алго-
ритмы) не освещаются в этой книге.
Большая часть глав этой книги построена таким образом, что сначала
представляются основные темы главы, сопровождаемые примерами, при-
ложениями и практическими исследованиями. Таким образом, при не-
хватке времени на серьезное изучение можно без потери связности быст-
ро переходить от главы к главе, знакомясь лишь с наиболее существен-
ными понятиями. В дальнейшем, когда время позволит, и студент, и
преподаватель смогут обращаться вразбивку к дополнительным темам и
комплексным примерам.
Двухсеместровый курс практически покрывает всю книгу, удачно интегрируя 
в себе многие темы таких разделов, как решение задач, структуры 
данных, разработка программ и анализ алгоритмов. Для понимания
общих методов студентам требуется время и практика. Комбинируя изучение 
абстракции данных, структур данных и алгоритмов с их реализациями 
в проектах реального размера, такой интегрированный курс будет
служить твердой базой, на которой в дальнейшем могут основываться
курсы, имеющие более теоретический характер.
Даже при не вполне исчерпывающем изучении, эта книга даст достаточно 
основательные знания, которые позволят интересующимся студентам 
по ходу своей дальнейшей работы использовать ее в качестве справочного 
пособия. В любом случае необходимо поручить студентам разработку 
основных программных проектов и предоставить им достаточное
время для доведения их до рабочего состояния.

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

Эта книга вместе с дополнительным материалом была написана с помощью 
собственного программного обеспечения автора под названием
PreTEX, объединяющего в себе препроцессор и макропакет для полиграфической 
системы TEX2. Пакет PreTEX, используя контекстную зависимость, 
автоматически обеспечивает значительную часть разметки текста,
требуемую программой TEX. PreTEX также предоставляет некоторые полезные 
для автора средства, в частности, мощную систему перекрестных
ссылок, существенное упрощение набора математических выражений и
листингов компьютерных программ, и автоматическую генерацию предметного 
указателя и содержания. В то же время PreTEX позволяет поэтапно 
обрабатывать текст книги, содержащийся в относительно небольших 
по размеру файлах. Решения, размещенные вместе с упражнениями
и проектами, автоматически убираются из текста и помещаются в отдельные 
документы. В сочетании с языком PostScript описания страниц,
PreTEX предоставляет удобные средства для цветоделения, обработки
растровых изображений и других специальных приемов.

Предисловие
19

двухсеместровый
курс

2
Система TEX была разработана Доналдом Кнутом (Donald E. Knuth), который внес весьма значительный вклад
в наше сегодняшнее понимание структур данных и алгоритмов. (См. ссылки на его имя в предметном
указателе).