Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

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

Покупка
Артикул: 801909.02.99
В качестве фундаментальных средств разработки программ рассматриваются такие вопросы, как структурное решение задач, абстракция данных, принципы программной инженерии и сравнительный анализ алгоритмов. Дано полное освещение большинства модулей знаний, касающихся структур данных и алгоритмов. Большая часть глав начинается основной темой и сопровождается примерами, приложениями и практическими исследованиями. Это учебное пособие дает основательные знания, которые позволяют студентам по ходу своей дальнейшей работы использовать ее также в качестве справочного пособия.
327
394
445
524
593
Круз, Р. Л. Структуры данных и проектирование программ : учебное пособие / Р. Л. Круз. - 4-е изд. - Москва : Лаб. знаний, 2025. - 767 с. - (Программисту). - ISBN 978-5-93208-560-8. - Текст : электронный. - URL: https://znanium.ru/catalog/product/2221063 (дата обращения: 18.11.2026). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов
СТРУКТУРЫ ДАННЫХ
И  ПРОЕКТИРОВАНИЕ
ПРОГРАММ


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-го английского издания
К. Г. Финогенова 
Москва
Лаборатория знаний
2025
4-е издание, электронное


УДК 004.7
ББК 32.973.202
К84
С е р и я
о с н о в а н а
в
2005 г.
Круз Р. Л.
К84
Структуры данных и проектирование программ / Р. Л. Круз ;
пер. с англ. — 4-е изд., электрон. — М. : Лаборатория знаний,
2025. — 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