курсовая с. КУРСОВАЯ с++ ПЕРВАЯ ПРАВКА. Разработка программы, реализующей алгоритмы сортировки и поиска

• Название: Разработка программы, реализующей алгоритмы сортировки и поиска
• Анкор: курсовая с
• Дата: 07.04.2023
• Размер: 0.55 Mb.
• Имя файла: КУРСОВАЯ с++ ПЕРВАЯ ПРАВКА.docx
• Тип: Реферат; #1044592
• страница: 3 из 3

Заключение
В данной курсовом проекте были выполнены все поставленные задачи:
-изучить и реализовать создание структур данных, то есть, массива и списка (односвязный типа очередь);

-изучены и реализованы алгоритмы для работы со списками типа очереди (генерация списка, добавление и удаление элементов, вывод списка);

-изучены и реализованы алгоритмы двух методов сортировки – поразрядная цифровая для массивов, и сортировка попарным слиянием для списка типа очереди.

-изучены и реализованы алгоритмы методов поиска – бинарного и интерполяционного для массивов, линейного для списка.

-изучены способы реализации и реализованы функций работы с файлами, а именно, чтения данных из списка в текстовый файл, и запись в него же.

Были проведены тестирование и отладка, программы справляются с со всеми требованиями курсового проекта, исключены различные ошибки в ходе реализации программ.
Список использованной литературы
1. Массив (тип данных) [Электронный ресурс] URL: https://ru.wikipedia.org/wiki/Массив_(тип_данных) (Дата обращения: 08.10.2022).

2. Список (информатика) [Электронный ресурс] URL: https://ru.wikipedia.org/wiki/Список(информатика) (Дата обращения: 08.10.2022

3. Алгоритм сортировки [Электронный ресурс] URL: https://ru.wikipedia.org/wiki/Алгоритм_сортировки (Дата обращения: 23.10.2022

4. Линейный поиск [Электронный ресурс] URL: https://ru.wikipedia.org/wiki/Линейный_поиск (Дата обращения: 30.10.2022

5. Двоичный поиск [Электронный ресурс] URL: https://ru.wikipedia.org/wiki/Двоичный_поиск (Дата обращения: 31.10.2022

6. Интерполяционный поиск [Электронный ресурс] URL: https://ru.wikipedia.org/wiki/Интерполяционный_поиск (Дата обращения: 08.11.2022

7. Хайнеман, Джордж. Алгоритмы справочник. Второе издание. - М. : Диалектика. 2017.

8. Роберт, Седжвик Алгоритмы на C++. Анализ структуры данных. Сортировка. Поиск. Алгоритмы на графах. Руководство / Седжвик Роберт. - М.: Диалектика / Вильямс, 2016.

9. Прата, Стивен. Язык программирования С. Лекции и упражнения. – М. : Вильямс. 2013.
Приложение А. Блок-схема нахождения максимального значения

Приложение Б. Блок-схема алгоритма “Сортировка подсчетом”


Приложение В. Блок схема “Поразрядная сортировка”

Приложение Г. Код программы обработки списка
#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#pragma warning(disable:4996)

using namespace std;

struct node

{

int data;

node* next;

};

node* head = NULL;

node* tail = NULL;

node* temp;

node* sortedMerge(struct node* a, struct node* b)

{

// базовые случаи

if (a == NULL) {

return b;

}

else if (b == NULL) {

return a;

}

node* result = NULL;

// выбираем a или b и повторяем

if (a->data <= b->data)

{

result = a;

result->next = sortedMerge(a->next, b);

}

else {

result = b;

result->next = sortedMerge(a, b->next);

}

return result;

}

/*

Разделить узлы данного списка на переднюю и заднюю половины

и вернуть два списка, используя ссылочные параметры.

Если длина нечетная, дополнительный узел должен идти в переднем списке.

Он использует стратегию быстрого/медленного указателя

*/

void frontBackSplit(struct node* source, struct node** frontRef, struct node** backRef)

{

// если длина меньше 2, обрабатывать отдельно

if (source == NULL||source->next == NULL)

{

*frontRef = source;

*backRef = NULL;

return;

}

node* slow = source;

node* fast = source->next;

// продвигаем `fast` на два узла и продвигаем `slow` на один узел

while (fast != NULL)

{

fast = fast->next;

if (fast != NULL)

{

slow = slow->next;

fast = fast->next;

}

}

// `slow` находится перед средней точкой в списке, поэтому разделите его на две части

// в таком случае.

*frontRef = source;

*backRef = slow->next;

slow->next = NULL;

}

// Сортируем заданный связанный список, используя алгоритм сортировки слиянием

void mergesort(node** head)

{

// базовый вариант — длина 0 или 1

if (*head == NULL||(*head)->next == NULL) {

return;

}

node* a;

node* b;

// разделить head на подсписки a и b

frontBackSplit(*head, &a, &b);

// рекурсивно сортируем подсписки

mergesort(&a);

mergesort(&b);

// ответ = объединить два отсортированных списка

*head = sortedMerge(a, b);

}

void Insert(node*& head, int data) {

if (tail == NULL) {

tail = (struct node*)malloc(sizeof(struct node));

tail->next = NULL;

tail->data = data;

head = tail;

}

else {

temp = (struct node*)malloc(sizeof(struct node));

tail->next = temp;

temp->data = data;

temp->next = NULL;

tail = temp;

}

}

void print(node* head)

{

while (head)

{

cout << head->data << " ";

head = head->next;

}

cout << endl;

}

void del(node*& head, int data)

{

temp = head;

if (head == NULL) {

cout << "Нет элементов в списке" << endl;

return;

}

else

if (temp->next != NULL) {

temp = temp->next;

free(head);

head = temp;

}

else {

free(head);

head = NULL;

tail = NULL;

}

}

void search(node* head, int data)

{

int i = 0;

while (head)

{

if (head->data == data)

{

cout << "Элемент находится на позиции: " << i << endl;

return;

}

head = head->next;

i++;

}

cout << "Элемент не найден" << endl;

}

void save(node* head)

{

FILE* f = fopen("read.txt", "w");

while (head)

{

fprintf(f, "%d ", head->data);

head = head->next;

}

cout << endl;

fclose(f);

}

void read(node*& head)

{

FILE* f = fopen("read.txt", "r");

int data;

while (fscanf(f, "%d", &data) != EOF)

{

Insert(head, data);

}

fclose(f);

}

int main()

{

setlocale(LC_ALL, "Rus");

srand(time(NULL));

node* head = NULL;

int n;

int val;

cout << "Введите количество элементов в списке для случайного заполнения данными: ";

cin >> n;

for (int i = 0; i < n; i++)

{

Insert(head, rand() % 100);

}

cout << endl;

print(head);

cout << "Введите элемент, который вы хотите добавить: ";

cin >> val;

cout << endl;

Insert(head, val);

cout << "Введите элемент, который вы хотите удалить: ";

cin >> n;

cout << endl;

del(head, n);

print(head);

cout << endl;

mergesort(&head);

print(head);

cout << endl;

cout << "Введите элемент, который вы хотите найти: ";

cin >> n;

search(head, n);

cout << endl;

save(head);

cout << endl;

cout << endl;

print(head);

system("pause");

return 0;

}
Приложение Д. Код программы обработки массива
#include

#include

#include

#include

using namespace std;

void menu();

void random(int* arr, int size);

void print(int* arr, int size);

int binarySearch(int* arr, int size, int value);

int interpolationSearch(int* arr, int size, int value);

void radixsort(int array[], int size);

int main()

{

setlocale(LC_ALL, "Rus");

int size;

int value = 0;

int* arr = nullptr;

int choice = 0;

do

{

menu();

cin >> choice;

switch (choice)

{

case 1:

cout << "Введите размер массива: ";

cin >> size;

arr = new int[size];

random(arr, size);

break;

case 2:

print(arr, size);

break;

case 3:

radixsort(arr, size);

break;

case 4:

cout << "Введите значение: ";

cin >> value;

cout << "Индекс значения: " << binarySearch(arr, size, value) << endl;

break;

case 5:

cout << "Введите значение: ";

cin >> value;

cout << "Индекс значения: " << interpolationSearch(arr, size, value) << endl;

break;

case 6:

delete[] arr;

break;

}

} while (choice != 6);

system("pause");

return 0;

}

// функция возвращает наибольший элемент в массиве

int getMax(int array[], int n) {

int max = array[0];

for (int i = 1; i < n; i++)

if (array[i] > max)

max = array[i];

return max;

}

// Использование сортировки подсчетом для сортировки элементов по значимым местам

void countingSort(int array[], int size, int place) {

const int max = 10;

int* output = new int[size];

int count[max];

for (int i = 0; i < max; ++i)

count[i] = 0;

// Подсчет количества элементов

for (int i = 0; i < size; i++)

count[(array[i] / place) % 10]++;

// Расчет совокупности значений

for (int i = 1; i < max; i++)

count[i] += count[i - 1];

// Разместите элементы в отсортированном порядке

for (int i = size - 1; i >= 0; i--) {

output[count[(array[i] / place) % 10] - 1] = array[i];

count[(array[i] / place) % 10]--;

}

for (int i = 0; i < size; i++)

array[i] = output[i];

delete[] output;

}

// Основная функция для реализации поразрядной сортировки

void radixsort(int array[], int size) {

// Получение максимального значения в массиве

int max = getMax(array, size);

// Примение сортировки подсчетом для сортировки элементов по разрядам

for (int place = 1; max / place > 0; place *= 10)

countingSort(array, size, place);

}

void menu()

{

cout << "1. Рандом" << endl;

cout << "2. Вывод" << endl;

cout << "3. Сортировка" << endl;

cout << "4. Бинарный поиск" << endl;

cout << "5. Интерполяционный поиск" << endl;

cout << "6. Выход" << endl;

}

void random(int* arr, int size)

{

srand(time(0));

for (int i = 0; i < size; i++)

{

arr[i] = rand() % 100;

}

}

void print(int* arr, int size)

{

for (int i = 0; i < size; i++)

{

cout << arr[i] << " ";

}

cout << endl;

}

int binarySearch(int* arr, int size, int value)

{

int left = 0;

int right = size - 1;

while (left <= right)

{

int middle = (left + right) / 2;

if (arr[middle] == value)

{

return middle;

}

else if (arr[middle] < value)

{

left = middle + 1;

}

else

{

right = middle - 1;

}

}

cout << "Элемент не найден" << endl;

return -1;

}

int interpolationSearch(int* arr, int size, int value)

{

int left = 0;

int right = size - 1;

while (left <= right)

{

int middle = left + (value - arr[left]) * (right - left) / (arr[right] - arr[left]);

if (arr[middle] == value)

{

return middle;

}

else if (arr[middle] < value)

{

left = middle + 1;

}

else

{

right = middle - 1;

}

}

cout << "Элемент не найден" << endl;

return -1;

}