Файл: отчёт_курсовая.docx

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 19.03.2024

Просмотров: 20

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

СОДЕРЖАНИЕ

1. Введение. Постановка задачи и исходные данные

2. Спецификация

3. Входные данные

4. Выходные данные

5. Описание алгоритмов

6. Текст программы

7. Заключение

8. Список использованной литературы

МИНОБРНАУКИ РОССИИ

Санкт-Петербургский государственный

электротехнический университет

«ЛЭТИ» им. В.И. Ульянова (Ленина)

Кафедра Информационных Систем

курсовая работа

по дисциплине «Алгоритмы и Структуры Данных»

Тема: Сортировка и поиск данных

Студент гр. 1323

Мансуров Я.В.

Преподаватель

Молдовян Д.Н.

Санкт-Петербург

2023

ОГЛАВЛЕНИЕ

  1. Введение. Постановка задачи и исходные данные…………………………...3

  2. Спецификация……………………………………………………………….….4

  3. Входные данные………………………………………………………………...4

  4. Выходные данные……………………………………………………………....5

  5. Описание алгоритмов…………………………………………………………..6

  6. Код программы………………………………………………………………….7

  7. Заключение……………………………………………………………………...13

  8. Список использованной литературы………………………………………….14

1. Введение. Постановка задачи и исходные данные

Вариант 9. Сортировка и поиск данных.

Содержательная постановка задачи:

  1. Реализовать алгоритм поиска данных

  2. Для разрабатываемого алгоритма реализовать следующие функции: а) использование алгоритмов сортировок вставками, выбором, обменом

б) поиск по ключу с использованием бинарных деревьев поиска с рандомизацией

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;

Смотрите также файлы