Структуры данных в Python: начальный курс

Глава 1. Предисловие....9Глава 2. Основы языка программирования Python....102.1. Последовательность, выбор и итерация....102.2. Выражения и вычисление....112.3. Переменные, типы и состояние....112.4. Наборы данных....142.4.1. Строки (str)....142.4.2. Списки (list)....142.4.3. Кортежи (tuple)....152.4.4. Словари (dict)....162.4.5. Множества (set)....172.5. Некоторые общие правила работы с наборами данных....182.6. Итерации по наборам данных....182.7. Другие формы управления потоком выполнения....192.8. Модули и импортирование....21Глава 3. Объектно-ориентированное программирование....243.1. Простой пример....253.2. Инкапсуляция и открытый (общедоступный) интерфейс класса....283.3. Наследование и отношение «является» (is a)....293.4. Утиная типизация....313.5. Композиция и отношения «содержит» (has a)....32Глава 4. Тестирование....344.1. Написание тестов....344.2. Модульное тестирование с использованием unittest....354.3. Разработка через тестирование....364.4. Что необходимо тестировать....374.5. Тестирование и объектно-ориентированное проектирование....38Глава 5. Анализ во время выполнения....395.1. Измерение времени выполнения (тайминг) программ....405.2. Пример: сложение первых k чисел....445.3. Моделирование времени выполнения программы....465.3.1. Операции со списком....475.3.2. Операции со словарем....475.3.3. Операции с множеством....485.4. Асимптотический анализ и порядок роста....485.5. Сосредоточимся на самом худшем случае....495.6. O-большое....495.7. Самые важные свойства использования O-большого....505.8. Практическое использование O-большого и общие функции....505.9. Основания логарифмов....515.10. Практические примеры....51Глава 6. Стеки и очереди....536.1. Абстрактные типы данных....536.2. Абстрактный тип данных «стек»....546.3. Абстрактный тип данных «очередь»....556.4. Обработка ошибок....57Глава 7. Деки и связные списки....597.1. Абстрактный тип данных «дек»....597.2. Связные списки....607.3. Реализация очереди с помощью класса LinkedList....617.4. Хранение длины....637.5. Тестирование на основании АТД....647.6. Основные уроки....687.7. Шаблоны проектирования: шаблон «обертка»....68Глава 8. Двусвязные списки....708.1. Объединение двусвязных списков....72Глава 9. Рекурсия....749.1. Рекурсия и индукция....759.2. Некоторые основные правила....759.3. Стек вызовов функций....769.4. Последовательность Фибоначчи....779.5. Алгоритм Евклида....78Глава 10. Динамическое программирование....8010.1. Жадный алгоритм....8010.2. Рекурсивный алгоритм....8110.3. Версия с мемоизацией....8110.4. Алгоритм динамического программирования....8210.5. Еще один пример ....83Глава 11. Двоичный поиск....8511.1. Абстрактный тип данных «упорядоченный список»....87Глава 12. Сортировка....8912.1. Алгоритмы сортировки, выполняемые за квадратичное время....8912.2. Сортировка в Python....93Глава 13. Сортировка методом «разделяй и властвуй»....9513.1. Сортировка слиянием....9613.1.1. Анализ....9713.1.2. Итераторы слияния....9813.2. Быстрая сортировка....100Глава 14. Выбор....10414.1. Алгоритм quickselect....10514.2. Анализ....10614.3. В последний раз без рекурсии....10714.4. Резюме стратегии «разделяй и властвуй»....10714.5. Замечание о дерандомизации....108Глава 15. Отображения и хеш-таблицы....10915.1. Абстрактный тип данных «отображение»....10915.2. Минимальная реализация....11015.3. Расширенный абстрактный тип данных «отображение»....11115.4. Это слишком медленно....11315.4.1. Сколько контейнеров мы должны использовать?....11415.4.2. Двойное хеширование....11615.5. Вынос общих частей в суперкласс....116Глава 16. Деревья....12016.1. Еще несколько определений....12116.2. Деревья с точки зрения рекурсии....12116.3. Абстрактный тип данных дерево ....12316.4. Реализация....12416.5. Обход дерева....12616.6. Если хотите немного развлечься....12716.6.1. Есть одно «но»....12816.6.2. Уровень за уровнем....128Глава 17. Деревья двоичного поиска....13017.1. Абстрактный тип данных «упорядоченное отображение»....13017.2. Определение и свойства дерева двоичного поиска....13017.3. Минимальная реализация....13117.3.1. Метод floor....13417.3.2. Итерация....13517.4. Удаление....135Глава 18. Сбалансированные деревья двоичного поиска....13818.1. Реализация класса BSTMapping....13918.1.1. Совместимость снизу вверх шаблонов «фабрика»....14018.2. Взвешенные сбалансированные деревья....14018.3. Сбалансированные по высотедеревья (АВЛ-деревья)....14218.4. Косые деревья....144Глава 19. Очереди с приоритетами....14619.1. Абстрактный тип данных «очередь с приоритетами»....14619.2. Использование списка....14619.3. Кучи....14919.4. Хранение дерева в списке....15019.5. Создание кучи с нуля, _heapify....15119.6. Значимость и изменение приоритетов....15219.7. Итеративный проход по очереди с приоритетами ....15419.8. Пирамидальная сортировка....155Глава 20. Графы....15620.1. Абстрактный тип данных граф....15720.2. Реализация класса EdgeSetGraph....15720.3. Реализация класса AdjacencySetGraph....15820.4. Пути и связность....160Глава 21. Поиск в графах....16321.1. Поиск в глубину....16421.2. Исключение рекурсии....16521.3. Поиск в ширину....16621.4. Взвешенные графы и кратчайшие пути....16721.5. Алгоритм Прима для минимальных остовных деревьев....16921.6. Оптимизация поиска по первому наилучшему (приоритетному)совпадению....170Глава 22. (Непересекающиеся) множества....17222.1. Абстрактный тип данных «непересекающиеся множества» ....17222.2. Простая реализация....17322.3. Сжатие пути....17422.4. Слияние по высоте....17522.5. Слияние по весу....17622.6. Объединение эвристик....17622.7. Алгоритм Краскала....177Предметный указатель....179