ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.03.2024
Просмотров: 16
Скачиваний: 0
МИНОБРНАУКИ РОССИИ
Санкт-Петербургский государственный
электротехнический университет
«ЛЭТИ» им. В.И. Ульянова (Ленина)
Кафедра Информационных Систем
курсовая работа
по дисциплине «Алгоритмы и Структуры Данных»
Тема: Сортировка и поиск данных
Студент гр. 1323 |
|
Мансуров Я.В. |
Преподаватель |
|
Молдовян Д.Н. |
Санкт-Петербург
2023
ОГЛАВЛЕНИЕ
-
Введение. Постановка задачи и исходные данные…………………………...3
-
Спецификация……………………………………………………………….….4
-
Входные данные………………………………………………………………...4
-
Выходные данные……………………………………………………………....5
-
Описание алгоритмов…………………………………………………………..6
-
Код программы………………………………………………………………….7
-
Заключение……………………………………………………………………...13
-
Список использованной литературы………………………………………….14
1. Введение. Постановка задачи и исходные данные
Вариант 9. Сортировка и поиск данных.
Содержательная постановка задачи:
-
Реализовать алгоритм поиска данных
-
Для разрабатываемого алгоритма реализовать следующие функции: а) использование алгоритмов сортировок вставками, выбором, обменом
б) поиск по ключу с использованием бинарных деревьев поиска с рандомизацией
3. Программа должна быть написана в соответствии со стандартом
Формальная постановка задачи:
-
созданном файле имеются cведения о газетах (название газеты, индекс издания, фамилию, ФИО редактора, цену экземпляра газеты).
Требуется произвести сортировку данных по ключу и реализовать поиск данных по заданному значению ключа.
Исходные данные:
Сведения о газетах (название газеты, индекс издания, фамилию, ФИО редактора, цену экземпляра газеты).
Ограничения на исходные данные:
Нет
2. Спецификация
№ |
Входные данные (формальное |
Результат (Выходные |
спецификации |
описание) |
данные) |
1. |
Запуск без отладки |
Меню выбора действий |
2. |
Функции работы с базой данных |
|
2.1 |
Открыть файл |
Данные считываются с файла |
2.2 |
Вывод данных |
Доступ к выходным данным |
3. |
Функции из задания курсовой работы |
|
3.1 |
Сортировка данных (по названию газеты) |
Сортировка данных |
3.1.0 |
Без ввода данных вручную или открытия файла |
Данные отсутствуют |
3. Входные данные
Paper D
24680
Alex
9
Paper B
67890
Petta
12
Paper A
12345
Ivan
10
Paper C
54321
Elena
8
Paper G
13579
Olga
11
Ограничения на входные данные:
Нет
4. Выходные данные
Отсортированные данные по названию газеты:
5. Описание алгоритмов
Пузырьковая сортировка или Bubble Sort
-
один из самых известных алгоритмов сортировки. Здесь нужно последовательно сравнивать значения соседних элементов и менять числа местами, если предыдущее оказывается больше последующего. Таким образом элементы с большими значениями оказываются в конце списка, а с меньшими остаются в начале.
Сортировка вставками или Insertion Sort
-
При сортировке вставками массив постепенно перебирается слева направо. При этом каждый последующий элемент размещается так, чтобы он оказался между ближайшими элементами с минимальным и максимальным значением.
Сортировка выбором или Selection Sort
-
Сначала нужно рассмотреть подмножество массива и найти в нём максимум (или минимум). Затем выбранное значение меняют местами со значением первого неотсортированного элемента. Этот шаг нужно повторять до тех пор, пока в массиве не закончатся неотсортированные подмассивы.
|
Выбором |
Вставками |
Пузырьковая |
Худшее время |
O(n^2) |
O(n^2) |
O(n^2) |
Лучшее время |
O(n^2) |
O(n) |
O(n) |
Среднее время |
O(n^2) |
O(n^2) |
O(n^2) |
Затраты памяти |
O(n) |
O(n) |
O(1) |
Бинарное рандомизированное дерево
-
это алгоритм, в котором каждый узел двоичного дерева поиска будет содержать ключ key, который, по сути, управляет всеми процессами, и пару указателей left и right на левое и правое поддеревья. Если какой-либо указатель нулевой, то соответствующее этому указателю дерево является пустым. Помимо этого, нам для реализации рандомизированного дерева потребуется еще одно поле size, в котором будет храниться размер дерева с корнем в данном узле.
Основное свойство дерева поиска — любой ключ в левом поддереве меньше корневого ключа, а в правом поддереве — больше корневого ключа, то есть ключи дерева отсортированы . Это свойство позволяет нам очень просто организовать поиск заданного ключа, перемещаясь от корня вправо или влево в зависимости от значения корневого ключа.
Идея рандомизации заключается в том, что, если ключи как следует перемешать, то получится создать неплохо сбалансированное дерево – его высота будет порядка 2log2n против log2n для идеально сбалансированного дерева
6. Текст программы
Kursovaya_4s.cpp (основная программа) #include <fstream>
#include <vector>
#include <clocale>
#include "RBST.h"
using namespace std;
void bubblesort(std::vector<Newspaper>& arr) {
size_t n = arr.size();
for (size_t i = 0; i < n - 1; ++i) {
for (size_t j = 0; j < n - i - 1; ++j) {
if (arr[j] > arr[j + 1]) {
std::swap(arr[j], arr[j + 1]);
}
}
}
}
void selectionsort(std::vector<Newspaper>& arr) {
size_t n = arr.size();
for (size_t i = 0; i < n - 1; ++i) {
size_t minIndex = i;
for (size_t j = i + 1; j < n; ++j) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
std::swap(arr[i], arr[minIndex]);
}
}
void insertsort(std::vector<Newspaper>& np)
{
for (size_t i = 1; i < np.size(); i++)
for (size_t j = i; j > 0 && np[j - 1] > np[j]; j--)
std::swap(np[j - 1], np[j]);
}
//-----------------------------------------------------------------------------------------------------------------------------------------//
int main() {
setlocale(LC_ALL, "Russian"); // на всякий
std::vector<Newspaper> newspapers;
// Чтение данных из текстового файла
std::ifstream inputFile("newspapers.txt");
if (!inputFile) {
std::cout << "Ошибка открытия файла." << std::endl;
return 1;
}
for (int i = 0; i < 5; i++) { //input to temp file
Newspaper temp;
inputFile >> temp;
newspapers.push_back(temp);
}
RBS_Tree *tree = nullptr;
for (Newspaper np : newspapers)
tree = RBST::insert(tree, np);
if (RBST::find(tree, newspapers[0]))
std::cout << "Found!\n";
else
std::cout << "That sucks :(\n";
cout << "choose 1, 2 or 3. 1 is Bubble Sort, 2 is Selection Sort, 3 is Insertion Sort. Your choice: ";
int x;
cin >> x;
switch (x)
{
case 1:
bubblesort(newspapers);
break;
case 2:
selectionsort(newspapers);
break;
case 3:
insertsort(newspapers);
break;
default:
cout << "choose 1, 2 or 3";
break;
}
for (Newspaper np : newspapers) { // console output
std::cout << np << "\n";
}
return 0;
}
RBST.cpp #include "RBST.h"
namespace RBST
{
int getsize(RBS_Tree* p)
{
if (!p) return 0;
return p->size;
}
void fixsize(RBS_Tree* p)
{
p->size = getsize(p->left) + getsize(p->right) + 1;
}
RBS_Tree* find(RBS_Tree* p, Newspaper& k)
{
if (!p) return 0;
if (k == p->key)
return p;
if (k < p->key)
return find(p->left, k);
else
return find(p->right, k);
}
RBS_Tree* insert(RBS_Tree* p, Newspaper& k)
{
if (!p) return new RBS_Tree(k);
if (rand() % (p->size + 1) == 0)
return insertroot(p, k);
if (p->key > k)
p->left = insert(p->left, k);
else
p->right = insert(p->right, k);
fixsize(p);
return p;
}
RBS_Tree* rotateright(RBS_Tree* p)
{
RBS_Tree* q = p->left;
if (!q) return p;