Моделирование абстрактных типов данных для различных реализаций. Поиск информации в файлах данных. Эффективность алгоритмов сортировок для различных структур и размерностей данных. Реализация структур данных типа дерево и типовые алгоритмы их обработки.
Аннотация к работе
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Институт - Институт кибернетики6. Реализация функций расстановки (хеширование) и различных методов разрешения коллизий6.3 Описание сферы практического применения используемого типа данныхЦелью курсовой работы является закрепление материала, изучаемого в предыдущем семестре по дисциплине «Структуры и алгоритмы обработки данных»: программирование реальных заданий с использованием наиболее распространенных в информационных технологиях структур данных и алгоритмов их обработки. Курсовая работа включает следующие разделы: 1. Моделирование абстрактных типов данных (АТД) для различных реализаций (табличное, списковое, комбинированное и т.д.).Реализовать процедуры перемещения элементов одно-связанного списка в стек и наоборот.Абстрактный тип данных (АТД) - это тип данных, который предоставляет для работы с элементами этого типа определенный набор функций, а также возможность создавать элементы этого типа при помощи специальных функций. Основные операции: · Insert (x, e) - вставляет элемент е в позицию х · Locate (e) - возвращает позицию элемента е в списке · Retrieve (x) - возвращает элемент, находящийся в позиции x · Delete (x) - удаляет элемент с позиции хПример работы 1-ой части программыСоздать файл данных, описывающий данную предметную область. На основе файла создать словарь, состоящий из пар: КЛЮЧ-№ записи.Ассоциативный массив (словарь) - абстрактный тип данных (интерфейс к хранилищу данных), позволяющий хранить пары вида «(ключ, значение)» и поддерживающий операции добавления пары, а также поиска и удаления пары по ключу: · INSERT(ключ, значение) В паре значение называется значением, ассоциированным с ключом . Операция FIND(ключ) возвращает значение, ассоциированное с заданным ключом, или некоторый специальный объект UNDEF, означающий, что значения, ассоциированного с заданным ключом, нет. Ассоциативный массив с точки зрения интерфейса удобно рассматривать как обычный массив, в котором в качестве индексов можно использовать не только целые числа, но и значения других типов - например, строки. Для ускорения операции поиска можно упорядочить элементы этого массива по ключу и осуществлять нахождение методом бинарного поиска.Время поиска по ключу: 8 МСВРЕМЯ поиска по ключу: 26 мс Время поиска со словарем: 3 МСВРЕМЯ поиска со словарем: 18 мс · Чем больше текст, тем больше времени занимает поиск и с ключом, и со словарем. Но на протяжении всего эксперимента поиск по словарю происходит быстрее.· Провести экспериментальный сравнительный анализ различных методов сортировки. Для чистоты эксперимента сортировка должна проводиться на одинаковых наборах входных данных, которые генерируются случайным образом. Для более полного анализа методов сортировка должна проводиться для различных размерностей данных, например: 500, 1000, 3000, 5000, 8000, 10000, 30000, 60000.Алгоритм сортировки выбором находит в исходном массиве максимальный или минимальный элементы, в зависимости от того как необходимо сортировать массив, по возрастанию или по убыванию. Если массив должен быть отсортирован по возрастанию, то из исходного массива необходимо выбирать минимальные элементы. Если же массив необходимо отсортировать по убыванию, то выбирать следует максимальные элементы. Допустим необходимо отсортировать массив по возрастанию.Метод сортировки обменами лежит в основе некоторых более совершенных алгоритмов, таких как шейкерная сортировка, пирамидальная сортировка и быстрая сортировка. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает - массив отсортирован.Алгоритм сортировки, похожий на сортировку вставками, но в отличие от последней перед вставкой на нужное место происходит серия обменов, как в сортировке пузырьком. Название происходит от предполагаемого поведения садовых гномов при сортировке линии садовых горшков, описанного на странице Дика Груна Гномья сортировка.Массив делится на 2 части: отсортированную и неотсортированную. На каждом шаге берется очередной элемент из неотсортированной части и включается в отсортированную.Сортировка слиянием - алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например - потоки) в определенном порядке.Bucket sort)-алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков (карманов, корзин) так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Преимущества: относится к классу быстрых алгоритмов с линейным временем исполнения O(N) (на удачных входных данных).Данный метод заключается в том, что сравниваются элементы, стоящие не только рядом, но и на расстоянии друг от друга.Выбираем в массиве некоторый элемент, который будем называть опорным элементом.
План
Оглавление
1. Задание на выполнение курсовой работы
2. Моделирование абстрактных типов данных (АТД) для различных реализаций
2.1 Постановка задачи
2.2 Краткое теоретические положения
2.3 Результат работы программы
3. Поиск информации в файлах данных
3.1 Постановка задачи
3.2 Краткое теоретическое описание
3.3 Результаты работы программы
3.2 Краткое теоретическое описание
3.3 Результаты работы программы
4. Исследование эффективности алгоритмов сортировок для различных структур и размерностей данных