Содержание книги "Структуры данных в Python
:
начальный курс"
Глава 1. Предисловие
Глава 2. Основы языка программирования Python
2.1. Последовательность, выбор и итерация
2.2. Выражения и вычисление
2.3. Переменные, типы и состояние
2.4. Наборы данных
2.5. Некоторые общие правила работы с наборами данных
2.6. Итерации по наборам данных
2.7. Другие формы управления потоком выполнения
2.8. Модули и импортирование
Глава 3. Объектно-ориентированное программирование
3.1. Простой пример
3.2. Инкапсуляция и открытый (общедоступный) интерфейс класса
3.3. Наследование и отношение «является» (is a)
3.4. Утиная типизация
3.5. Композиция и отношения «содержит» (has a)
Глава 4. Тестирование
4.1. Написание тестов
4.2. Модульное тестирование с использованием unittest
4.3. Разработка через тестирование
4.4. Что необходимо тестировать
4.5. Тестирование и объектно-ориентированное проектирование
Глава 5. Анализ во время выполнения
5.1. Измерение времени выполнения (тайминг) программ
5.2. Пример: сложение первых k чисел
5.3. Моделирование времени выполнения программы
5.4. Асимптотический анализ и порядок роста
5.5. Сосредоточимся на самом худшем случае
5.6. O-большое
5.7. Самые важные свойства использования O-большого
5.8. Практическое использование O-большого и общие функции
5.9. Основания логарифмов
5.10. Практические примеры
Глава 6. Стеки и очереди
6.1. Абстрактные типы данных
6.2. Абстрактный тип данных «стек»
6.3. Абстрактный тип данных «очередь»
6.4. Обработка ошибок
Глава 7. Деки и связные списки
7.1. Абстрактный тип данных «дек»
7.2. Связные списки
7.3. Реализация очереди с помощью класса LinkedList
7.4. Хранение длины
7.5. Тестирование на основании АТД
7.6. Основные уроки
7.7. Шаблоны проектирования: шаблон «обертка»
Глава 8. Двусвязные списки
8.1. Объединение двусвязных списков
Глава 9. Рекурсия
9.1. Рекурсия и индукция
9.2. Некоторые основные правила
9.3. Стек вызовов функций
9.4. Последовательность Фибоначчи
9.5. Алгоритм Евклида
Глава 10. Динамическое программирование
10.1. Жадный алгоритм
10.2. Рекурсивный алгоритм
10.3. Версия с мемоизацией
10.4. Алгоритм динамического программирования
10.5. Еще один пример
Глава 11. Двоичный поиск
11.1. Абстрактный тип данных «упорядоченный список»
Глава 12. Сортировка
12.1. Алгоритмы сортировки, выполняемые за квадратичное время
12.2. Сортировка в Python
Глава 13. Сортировка методом «разделяй и властвуй»
13.1. Сортировка слиянием
13.2. Быстрая сортировка
Глава 14. Выбор
14.1. Алгоритм quickselect
14.2. Анализ
14.3. В последний раз без рекурсии
14.4. Резюме стратегии «разделяй и властвуй»
14.5. Замечание о дерандомизации
Глава 15. Отображения и хеш-таблицы
15.1. Абстрактный тип данных «отображение»
15.2. Минимальная реализация
15.3. Расширенный абстрактный тип данных «отображение»
15.4. Это слишком медленно
15.5. Вынос общих частей в суперкласс
Глава 16. Деревья
16.1. Еще несколько определений
16.2. Деревья с точки зрения рекурсии
16.3. Абстрактный тип данных дерево
16.4. Реализация
16.5. Обход дерева
16.6. Если хотите немного развлечься
Глава 17. Деревья двоичного поиска
17.1. Абстрактный тип данных «упорядоченное отображение»
17.2. Определение и свойства дерева двоичного поиска
17.3. Минимальная реализация
17.4. Удаление
Глава 18. Сбалансированные деревья двоичного поиска
18.1. Реализация класса BSTMapping
18.2. Взвешенные сбалансированные деревья
18.3. Сбалансированные по высоте деревья (АВЛ-деревья)
18.4. Косые деревья
Глава 19. Очереди с приоритетами
19.1. Абстрактный тип данных «очередь с приоритетами»
19.2. Использование списка
19.3. Кучи
19.4. Хранение дерева в списке
19.5. Создание кучи с нуля, _heapify
19.6. Значимость и изменение приоритетов
19.7. Итеративный проход по очереди с приоритетами
19.8. Пирамидальная сортировка
Глава 20. Графы
20.1. Абстрактный тип данных граф
20.2. Реализация класса EdgeSetGraph
20.3. Реализация класса AdjacencySetGraph
20.4. Пути и связность
Глава 21. Поиск в графах
21.1. Поиск в глубину
21.2. Исключение рекурсии
21.3. Поиск в ширину
21.4. Взвешенные графы и кратчайшие пути
21.5. Алгоритм Прима для минимальных остовных деревьев
21.6. Оптимизация поиска по первому наилучшему (приоритетному) совпадению
Глава 22. (Непересекающиеся) множества
22.1. Абстрактный тип данных «непересекающиеся множества»
22.2. Простая реализация
22.3. Сжатие пути
22.4. Слияние по высоте
22.5. Слияние по весу
22.6. Объединение эвристик
22.7. Алгоритм Краскала
Предметный указатель
