Статья
  • формат doc
  • размер 289,85 КБ
  • добавлен 13 ноября 2012 г.
Структуры данных и алгоритмы
2011. – 63 с.
(Автор и выходные данные не указаны.)
Содержание:
Методы сортировки. Общая постановка задачи.
Метод поиска с обменом (сортировка посредством выбора). Алгоритм «Пузырька».
Челночная сортировка (сортировка вставками). Метод подсчета.
Метод парных сравнений.
Быстрая сортировка (сортировка Хоара).
Понятие объекта. Наследование. Инкапсуляция.
Полиморфизм. Пример полиморфной процедуры.
Статические методы. Примеры.
Виртуальные методы. Примеры.
Выбор типов методов.
Реализация списка и очереди.
Реализация двух однотипных стеков.
Динамические объекты. Примеры.
Пример использования динамических объектов: реализация объектного типа «стек».
Абстрактный тип данных «Список». Реализация списков посредством массивов.
Абстрактный тип данных «Список». Реализация списков с помощью динамических переменных.
Абстрактный тип данных «Стек». Реализация посредством массивов.
Деревья. Основные понятия. Прямой, обратный и симметричный обходы дерева. Рекурсивные процедуры обхода деревьев.
Помеченные деревья и деревья выражений.
Абстрактный тип данных «Дерево». Рекурсивная и нерекурсивная процедуры обхода дерева.
Представление деревьев с помощью массивов. Оператор определение правого брата.
Представление деревьев с использованием списков сыновей. Функция нахождения самого левого сына. Представление деревьев посредством связанных списков.
Двоичные деревья. Построение дерева поиска.
Двоичные деревья как структура представления множеств. Реализация проверки на принадлежность элемента множеству, вставки нового элемента в ДДП, удаления элемента из ДДП.
Ориентированные графы. Основные определения. Представления ориентированных графов.
АТД для ориентированных графов. Основные операторы.
адача нахождения кратчайшего пути. Алгоритм Дейкстры.
Нахождение кратчайших путей между парами вершин. Алгоритм Флойда.
Поиск центра ориентированного графа.
Обход ориентированных графов. Поиск в глубину.
Алгоритм нахождения сильно связных компонент.
Представление неориентированных графов. Остовные деревья минимальной стоимости. Основные понятия.
Алгоритм Прима.
Алгоритм Крускала.
Поиск в ширину на неориентированном графе.
2-3 деревья. Основные понятия.
Вставка элемента в 2-3 дерево.
Удаление элемента из 2-3 дерева.
Структуры данных и алгоритмы для внешней памяти. Понятие В-дерева. Поиск записей.
Вставка и удаление записей из В-дерева.
Словари. Структуры данных, основанные на хеш-таблицах. Открытое хеширование.
Реализация словарей посредством открытой хеш-таблицы.
Похожие разделы