Главная страница
Навигация по странице:

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

  • Приложение А. Блок-схема нахождения максимального значения

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

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

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


    Скачать 0.55 Mb.
    НазваниеРазработка программы, реализующей алгоритмы сортировки и поиска
    Анкоркурсовая с
    Дата07.04.2023
    Размер0.55 Mb.
    Формат файлаdocx
    Имя файлаКУРСОВАЯ с++ ПЕРВАЯ ПРАВКА.docx
    ТипРеферат
    #1044592
    страница3 из 3
    1   2   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;

    }
    1   2   3


    написать администратору сайта