Типы и структуры данных - Курсовая работа

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ТОМСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТЦелью курсовой работы является закрепление материала, изучаемого в предыдущем семестре по дисциплине "Структуры и алгоритмы обработки данных": программирование реальных заданий с использованием наиболее распространенных в информационных технологиях структур данных и алгоритмов их обработки. Курсовая работа включает следующие разделы: 1.Реализовать процедуры перемещения элементов одно-связанного списка в стек и наоборот. Список реализуется с помощью указателей, стек - массивом. Абстрактный тип данных (АТД) - это тип данных, который предоставляет для работы с элементами этого типа определенный набор функций, а также возможность создавать элементы этого типа при помощи специальных функций. Основные операции: · Insert (x, e) - вставляет элемент е в позицию х · Retrieve (x) - возвращает элемент, находящийся в позиции xПример работы 1-ой части программыСоздать файл данных, описывающий данную предметную область. На основе файла создать словарь, состоящий из пар: КЛЮЧ-№ записи.Ассоциативный массив (словарь) - абстрактный тип данных (интерфейс к хранилищу данных), позволяющий хранить пары вида "(ключ, значение)" и поддерживающий операции добавления пары, а также поиска и удаления пары по ключу: · INSERT(ключ, значение) В паре значение называется значением, ассоциированным с ключом . Операция FIND(ключ) возвращает значение, ассоциированное с заданным ключом, или некоторый специальный объект UNDEF, означающий, что значения, ассоциированного с заданным ключом, нет. Ассоциативный массив с точки зрения интерфейса удобно рассматривать как обычный массив, в котором в качестве индексов можно использовать не только целые числа, но и значения других типов - например, строки. Для ускорения операции поиска можно упорядочить элементы этого массива по ключу и осуществлять нахождение методом бинарного поиска.Время поиска по ключу: 8 мс Время поиска по ключу: 26 мс Время поиска со словарем: 3 мс Время поиска со словарем: 18 мс · Чем больше текст, тем больше времени занимает поиск и с ключом, и со словарем. Но на протяжении всего эксперимента поиск по словарю происходит быстрее.· Провести экспериментальный сравнительный анализ различных методов сортировки. Для чистоты эксперимента сортировка должна проводиться на одинаковых наборах входных данных, которые генерируются случайным образом. Для более полного анализа методов сортировка должна проводиться для различных размерностей данных, например: 500, 1000, 3000, 5000, 8000, 10000, 30000, 60000.· В этой части работы происходит сортировка 500, 1000, 2000, 3000, 5000 элементов различными видами сортировки. Количество элементов Сортировка выбором Сортировки пузырьком Гномья сортировка Сортировка вставками Сортировка слиянием Блочная сортировка Сортировка Шелла Пирамидальная сортировка Быстрая сортировка STOOGESORTРеализовать процедуры создания красно-черных деревьев (динамическое представление), поиска, удаления и добавления узлов.Представлен пример выполнения программы.Хеш-таблица представляет базу данных предметной области, соответствующей варианту. Реализовать: · Выбор ключа для соответствующей базы данных. · Заполнение таблицы для каждой функции.Хеш-функции применяются для защиты паролей (хорошая перемешиваемость данных), быстрых операций со структурами данных, т.к. хеш-таблицы имеют в основном вычислительную сложность О(1).Пример работы 5-ой части программы Количество элементов Коллизии(хэш сложением) Коллизии(хэш умножением) Коллизии(хэш пирсона){static void Main(string[] args) Stack S = Program.List_Stack(L); Stack.Push(new STACKELEMENT(List.GETLISTELEMENT(i).Value)); {get {return this.value; } set {this.value = value; } {get {return next; } set {next = value; }String KEY="Интернет магазин"; //ключ, по которому будем искать в тексте KMP.KNUTHMORRISPRATT(file.READOBJECT(), KEY); //используя чтение из файла, находим по ключу KEY long t2=System.CURRENTTIMEMILLIS(); //окончание времени поиска по ключу long t3=System.CURRENTTIMEMILLIS(); //засекаем время начала поиска по ключу int key=4; //ищем подстроку Интернет магазин KMP.KNUTHMORRISPRATT(file.READOBJECT(), dict.get(key)); //используя чтение из файла, находим строки по ключам из словаря long t4=System.CURRENTTIMEMILLIS(); //окончание времени поиска по ключу {while (shift > 0 && (what.CHARAT(shift) != what.CHARAT(q))) //ищем совпадающее начало кусочка текста и подстроки shift = table[shift-1]; //меняем сдвиг if (what.CHARAT(shift)==what.CHARAT(q)) shift ; //считаем количество вхождений символов table[q]=shift; //записываем значения в таблицу - создаем префиксную функцию {while (shift>0 && what.CHARAT(shift)!=where.CHARAT(i)) //если первые символы не совпали, то shift=table[shift-1]; //двигаем текст на максимально возможное знаечение if (what.CHARAT(shift)==where.

Оглавление

1. Моделирование абстрактных типов данных (АТД) для различных реализаций

2. Поиск информации в файлах данных

2.1 Краткое теоретическое описание

2.2 Результаты работы программы

3. Исследование эффективности алгоритмов сортировок для различных структур и размерностей данных

4. Реализация структур данных типа дерево и типовые алгоритмы их обработки

4.1 Реализация функций расстановки (хеширование) и различных методов разрешения коллизий

4.2 Описание сферы практического применения используемого типа данных

Литература

Приложения