• Язык
 

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

ISBN: 978-5-00101-451-5

Москва: Лаборатория знаний, 2017

Объем (стр):768

Дополнительная информация:3-е изд. (эл.)

 

Постраничный просмотр для данной книги Вам недоступен.

Аннотация

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

Содержание

Предисловие 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
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
8.4. Упорядочение методом Шелла 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. Введение: переход через барьер lgn 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.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
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

Рекомендации материалов по теме: нет