курсовая с. КУРСОВАЯ с++ ПЕРВАЯ ПРАВКА. Разработка программы, реализующей алгоритмы сортировки и поиска
![]()
|
Заключение В данной курсовом проекте были выполнены все поставленные задачи: -изучить и реализовать создание структур данных, то есть, массива и списка (односвязный типа очередь); -изучены и реализованы алгоритмы для работы со списками типа очереди (генерация списка, добавление и удаление элементов, вывод списка); -изучены и реализованы алгоритмы двух методов сортировки – поразрядная цифровая для массивов, и сортировка попарным слиянием для списка типа очереди. -изучены и реализованы алгоритмы методов поиска – бинарного и интерполяционного для массивов, линейного для списка. -изучены способы реализации и реализованы функций работы с файлами, а именно, чтения данных из списка в текстовый файл, и запись в него же. Были проведены тестирование и отладка, программы справляются с со всеми требованиями курсового проекта, исключены различные ошибки в ходе реализации программ. Список использованной литературы 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; } |