Файл: Разработка программы, реализующей алгоритмы сортировки и поиска.docx
Добавлен: 12.01.2024
Просмотров: 167
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Рисунок 24 – Функция интерполяционного поиска
3.4 Бинарный поиск в массиве
Алгоритм бинарного поиска реализуется в отсортированном массиве, принцип действия достаточно прост – массив делится на две примерно равные части, и поиск осуществляется в одной из этих частей, которая делится еще на две части, до тех пор, пока не будет найдено нужное значение. Для этого используется сравнение по значениям, заведомо большие значения сразу отбрасываются в виде частей. Именно поэтому, и нужен отсортированный массив, где значения упорядочены. В неотсортированном массиве поиск может застопориться, или даже не начаться толком. Реализация данного алгоритма поиска приведена на рисунке 25, производится операция сравнения значений с искомым, при нахождении искомого значения сразу же возвращает позицию элемента, который содержит нужное значение, иначе – продолжает поиск. В данном случае, поиск реализуется путем сравнения искомого значения с средним значением в одной из частей массива. При отсутствии искомого значения во всем массиве, выводится сообщение об этом факте[8].
Рисунок 25 – Функция бинарного поиска
Заключение
В данной курсовом проекте были выполнены все поставленные задачи:
-изучить и реализовать создание структур данных, то есть, массива и списка (односвязный типа очередь);
-изучены и реализованы алгоритмы для работы со списками типа очереди (генерация списка, добавление и удаление элементов, вывод списка);
-изучены и реализованы алгоритмы двух методов сортировки – поразрядная цифровая для массивов, и сортировка попарным слиянием для списка типа очереди.
-изучены и реализованы алгоритмы методов поиска – бинарного и интерполяционного для массивов, линейного для списка.
-изучены способы реализации и реализованы функций работы с файлами, а именно, чтения данных из списка в текстовый файл, и запись в него же.
Были проведены тестирование и отладка, программы справляются с со всеми требованиями курсового проекта, исключены различные ошибки в ходе реализации программ.
Список использованной литературы
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;
}