Программирование. Курсовая работа.. Курсовая работа. Новосибирский государственный технический универстиет министерство образования и науки российской федерации новосибирский государственный технический универстиет
 Скачать 0.8 Mb.
|
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСТИЕТ МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСТИЕТ Пояснительная записка к курсовой работе по программированию «Шаблон иерархической структуры данных» Вариант 3.9 Факультет: АВТ Группа: АВТ-710 Студент: Покалюк Е.А. Преподаватель: Новицкая Ю.В. НОВОСИБИРСК 2018 ОглавлениеЗадание 3 1.1. Структура данных 5 1.2. Структурное описание разработки 5 1.3. Вставка объекта в список 6 1.4. Удаление объекта 6 2.Функциональное описание 7 2.1. List (Шаблонный класс) 7 2.2. Node (структура собственной разработки) 8 3.Описание пользовательского интерфейса 10 4.Описание работы программы 10 4.1. Примеры работы программы 10 4.2. Тестирование на время выполнения 12 Заключение 14 Список используемой литературы 14 Приложение 15 ЗаданиеДля заданной двухуровневой структуры данных, содержащей указатели на объекты (или сами объекты) - параметры шаблона, разработать полный набор операций (добавление, включение и извлечение по логическому номеру, сортировка, включение с сохранением порядка, загрузка и сохранение строк в бинарном файле, балансировка – выравнивание размерностей структур данных нижнего уровня). Предполагается, что операции сравнения хранимых объектов переопределены стандартным образом (в виде операций <,> и т.д.). Программа должна использовать шаблонный класс с объектами- строками и реализовывать указанные выше действия над текстом любого объема, загружаемого из файла. Программа должна реализовывать указанные выше действия. Протестировать структуру данных. Программа тестирования должна содержать меню, обеспечивающее выбор операций. Вариант № 3.9 Шаблон структуры данных – двусвязный список (нециклический), каждый элемент списка содержит указатель на объект. Для ускорения процедуры обхода структуры данные имеется динамический массив указателей на каждый 10-ый элемент списка (0,10,20 и т.д.). Структурное описание Структура данных Двусвязный список (нециклический) – это структура данных, состоящая из элементов одного типа, связанных между собой последовательно посредством указателей. Каждый элемент списка имеет указатель на следующий и предыдущий элементы. Элемент, на который нет указателя, является первым (головным) элементом списка. Последним элементом списка является элемент, у которого нет указателя на следующий элемент. Здесь ссылка в каждом узле указывает на следующий и предыдущий узел в списке.  Рис 1.1 Двусвязный список Структурное описание разработки
Созданный класс List включает в себя, согласно варианту задания, динамический массив указателей, который содержит указатели на каждый 10-й элемент списка (0,10,20 и т.д.). Основные алгоритмы: Вставка в конец Вставка по индексу Вставка в начало Извлечение по индексу Сортировка Сохранение в бинарный файл Загрузка из бинарного файла Загрузка строк из текстового файла Вставка объекта в список Реализовано три способа вставки объекта. Первый способ — помещать новые элементы в конец списка. Второй — помещать новые элементы по логическому номеру. Третий — вставлять элементы с сохранением порядка, при этом список должен быть отсортирован. Элементы связанного списка являются структурами, так как, помимо данных, они содержат ссылку на следующий и предыдущий элементы. Поэтому нужно было определить структуру, которая представлена ниже:    Рис 1.2 Вставка объекта в двусвязный список Удаление объекта Удаление элемента из двусвязного списка выполняется просто. Так же, как и при вставке, возможны три случая: удаление первого элемента, удаление элемента в середине, удаление последнего элемента.  Рис 1.3 Операция «удаление по номеру» Функциональное описание List (Шаблонный класс) Поля: данные доступные для класса Node *Head; - указатель на первый добавленный элемент Node *Tail; - указатель на последний добавленный элемент int length; - количество элементов в списке bool sorted; - отсортирован ли список Конструктор и деструктор: Конструктор List(); Инициализирует поля Head, Tail, mass – указывая на NULL. Конструктор с параметром List(T x); Инициализирует поля, при это добавляет в список объект Конструктор копирования List(const List Создает копию списка Деструктор List(); Очищает список Node (структура собственной разработки) Поля: T *data; - указатель на объект Node *next; - указатель на следующий элемент списка Node *prev; - указатель на предыдущий элемент списка Основные методы Метод проверяет пустой список или нет, путем проверки значения указателя на начало списка template bool List return Head == nullptr; } Метод выводит на экран список, начиная с указателя Head и передвигаясь дальше по списку. template string List check(); stringstream ss; // поток ввода-вывода со строкой в памяти for (Node * tmp = Head; tmp; tmp = tmp->next) { ss << " -> " << *tmp->data; } return ss.str(); } Метод добавляет элемент в конец, проверяет случай, когда список пуст, происходит «перебрасывание» указателей. После этого происходит проверка, нужно ли добавлять указатель в ДМУ, увеличивает значение размера списка. template void List if (index > length) { throw out_of_range("index too big!"); } if (0 == index) { push_s(data); } else { Node *inserted = new Node(data); Node *tmp = Head; for (; --index; ) { tmp = tmp->next; } inserted->next = tmp->next; inserted->prev = tmp; tmp->next = inserted; length++; } } template void List push(data, length); } template void List Node *inserted = new Node(data); inserted->next = Head; Head = inserted; length++; } Сортирует список при помощи сортировки пузырьком, при этом сравниваются узлы списка при помощи оператора присваивания. template void List { check(); T * data; for (Node * tmp1 = Head; tmp1 != nullptr; tmp1 = tmp1->next) { for (Node * tmp2 = Head; tmp2 != nullptr; tmp2 = tmp2->next) { if (*tmp1 > *tmp2) { data = tmp1->data; tmp1->data = tmp2->data; tmp2->data = data; } } } } Очищает список, если он не пуст, путем прохода по каждому элементу и удалению его. template void List check(); for (Node * tmp = Head->next; tmp != nullptr; tmp = tmp->next) { delete tmp->prev; } Head = (Tail = nullptr); length = 0; } Сохраняет список в бинарный файл. Для этого сначала записывается размер списка, затем в цикле от начала до конца списка- записывается размер объекта и сам объект. template void List Node *tmp = Head; fstream out("tmp.bin", ios::binary | ios::out); out.write((char*)&length, sizeof(length)); for (; tmp != nullptr; tmp = tmp->next) { int size = sizeof(*tmp->data); out.write((char*)&size, sizeof(size)); out.write((char*)&(*tmp->data), size * sizeof(char)); } out.close(); } Производит чтение из бинарного файла. Для этого сначала считывается размер списка, затем в цикле от начала до конца списка- считывается размер объекта и сам объект, после этого он добавляется в список. template void List int size; int len; fstream in("tmp.bin", ios::binary | ios::in); in.read((char*)&len, sizeof(len)); T* tmp = new T[len + 1]; for (int i = 0; i < len; i++) { in.read((char*)&size, sizeof(size)); in.read((char*)(&tmp[i]), size * sizeof(char)); push(&tmp[i]); } length = len; in.close(); } Описание пользовательского интерфейса Приложение создано в виде консоли, пользовательский интерфейс представлен в виде меню с основными операциями Выбор типа данных: Пользователь может выбрать тип данных из трех предложенных, а именно – целые числа, строки и Class. Вывод: Пользователь может вывести на экран объекты списка. Вставка в начало: При выборе этого пункта происходит вставка в начальную позицию в списке. Вставка в заданную позицию: При выборе этого пункта происходит вставка в заданную позицию в списке. Отсчет идет с 0-позиции. Вставка в конец: При выборе этого пункта происходит вставка в конечную позицию в списке. Сортировка: Происходит сортировка по возрастанию чисел, либо по первым буквам в типах данных char* и Class. Удаление по индексу: При выборе этого пункта происходит удаление по заданной позиции в списке. Отсчет идет с 0-позиции. Сортировка: При выборе этого пункта пользователь может сортировать список по убыванию. Описание работы программы Для удобного пользования программой было разработано меню, обеспечивающее демонстрацию всех основных функций.   Рис 4.1 Меню программы Тестирование на время выполнения Ниже приведены замеры времени работы операций добавления, удаления и балансировки при различном количестве элементов.
Табл 1 Время работы операций Добавление  Рис 4.1 График зависимости времени добавления от количества элементов Удаление  Рис 4.2 График зависимости времени удаления от количества элементов Сортировка  Рис 4.3 График зависимости времени сортировки от количества элементов Заключение В результате проведенной работы был разработан шаблонный класс, имеющий в качестве элементов списка указатели на объект. Реализованы методы создания файла, просмотра, добавления, удаления, обновления и сортировки объектов. Реализована специализация для оператора сравнения узлов списка. Реализован динамический массив указателей (ДМУ), который содержит указатели на каждый 10-ый элемент списка (0,10,20 и т.д.). При этом он используется в программе для того, чтобы ускорить извлечение и вставку по логическому номеру. Достоинством программы является наличие в качестве структуры данных верхнего уровня двусвязный список, который позволяет удобно управлять операциями над объектами. Список используемой литературы ГОСТ 2015 – 369. Язык программирования С++ – Изд-во: Бином. Бьерн Страуструп ГОСТ 2013 – 688. Освой самостоятельно C++ за 21 день. Седьмое издание – Изд-во: Вильямс Издательский дом. Сиддхартха Рао http://ermak.cs.nstu.ru/cprog - электронный учебник по дисциплине " Информатика". Романов E.Л. Приложение List.h #ifndef LIST_H #define LIST_H #include #include #include #include using namespace std; template { struct Node // структура представляющая единичный элемент списка { T *data; // указатель на объект Node *next; // указатель на следующий элемент списка Node *prev; // указатель на предыдущий элемент списка Node(T * data) : data(data) { } bool operator >(const Node& a) { return *data > *(a).data ? 1 : 0; } }; private: // данные доступные для класса Node *Head = nullptr; // указатель первый добавленный элемент Node *Tail = nullptr; // указатель на последний элемент public: // данные и методы доступные для пользователя класса size_t length = 0; // количество элементов в списке List(); // деструктор void push(T *data); void push(T *data, size_t index);//добавление по логическому номеру void push_s(T *data);//добавление в начало T pop(); T pop(size_t index); // извлечение по логическому номеру T pop_s(); void sort(); // сортировка void save(); // сохранить в бинарный файл void read(); // загрузить из бинарного файла void clear();// очистить список void check(size_t index = 0); string print(); bool isEmpty(); // проверка состояния списка (если список не пуст) }; template List clear(); // очистить список } template bool List return Head == nullptr; } template string List check(); stringstream ss; for (Node * tmp = Head; tmp; tmp = tmp->next) { ss << " -> " << *tmp->data; } return ss.str(); } template void List if (index > length) { throw out_of_range("index too big!"); } if (0 == index) { push_s(data); } else { Node *inserted = new Node(data); // создать новый указатель на элемент и выделяем память Node *tmp = Head; for (; --index; ) { tmp = tmp->next; } inserted->next = tmp->next; inserted->prev = tmp; tmp->next = inserted; length++; // увеличиваем количество элементов в списке } } template void List push(data, length); } template void List Node *inserted = new Node(data); // создать новый указатель на элемент и выделяем память inserted->next = Head; Head = inserted; length++; // увеличиваем количество элементов в списке } template void List { check(); T * data; for (Node * tmp1 = Head; tmp1 != nullptr; tmp1 = tmp1->next) { for (Node * tmp2 = Head; tmp2 != nullptr; tmp2 = tmp2->next) { if (*tmp1 > *tmp2) { data = tmp1->data; tmp1->data = tmp2->data; tmp2->data = data; } } } } template T List return pop(length - 1); } template T List check(index); if (index == 0) { return pop_s(); } T * data; Node * tmp = Head; for (; index--; tmp = tmp->next); tmp->prev->next = tmp->next; data = tmp->data; length--; return *data; // вернуть данные удаленного элемента } template T List check(); T * data; Node * tmp = Head; Head = Head->next; data = tmp->data; delete tmp; length--; return *data; // вернуть данные удаленного элемента } template void List check(); for (Node * tmp = Head->next; tmp != nullptr; tmp = tmp->next) { delete tmp->prev; } Head = (Tail = nullptr); length = 0; } template void List Node *tmp = Head; fstream out("tmp.bin", ios::binary | ios::out); out.write((char*)&length, sizeof(length)); for (; tmp != nullptr; tmp = tmp->next) { int size = sizeof(*tmp->data); out.write((char*)&size, sizeof(size)); out.write((char*)&(*tmp->data), size * sizeof(char)); } out.close(); } template void List int size; int len; fstream in("tmp.bin", ios::binary | ios::in); in.read((char*)&len, sizeof(len)); T* tmp = new T[len + 1]; for (int i = 0; i < len; i++) { in.read((char*)&size, sizeof(size)); in.read((char*)(&tmp[i]), size * sizeof(char)); push(&tmp[i]); } length = len; in.close(); } template void List { if (isEmpty()) { throw exception("Список пуст!"); } if (index >= length) { throw out_of_range("Индекс слишком велик!"); } } #endif main.cpp #include #include #include #include "list.h" int main() { List string s; int k, size = 0; setlocale(LC_ALL, "Rus"); while (true) try { cout << "Меню:" << endl << "1 - Вставка в конец" << endl << "2 - Вставка по индексу" << endl << "3 - Вставка в начало" << endl << "4 - Извлечение по индексу" << endl << "5 - Сортировка" << endl << "6 - Сохранить в бинарный" << endl << "7 - Загрузить из бинарного" << endl << "9 - Очистить список" << endl << "0 - Печать списка" << endl << endl; switch (_getch()) { // Вставка в конец case '1': { cout << "Введите строку: "; cin >> s; list.push(new string(s)); break; } // Вставка по индексу case '2': { cout << "Введите строку: "; cin >> s; cout << "Введите индекс: "; cin >> k; list.push(new string(s), k); break; } // Вставка в начало case '3': { cout << "Введите строку: "; cin >> s; list.push_s(new string(s)); break; } // Извлечение по индексу case '4': { cout << "Введите индекс: "; cin >> k; cout << "Удаленный объект " << list.pop(k) << endl; break; } // Сортировка case '5': { list.sort(); break; } // Сохранение в бинарный файл case '6': { list.save(); break; } // Запись из бинарного файла case '7': { list.read(); break; } // case '9': { list.clear(); cout << "Ок." << endl; break; } // Печать списка case '0': { cout << list.print() << endl; break; } default: { cout << "Нет такого пункта в мен.!" << endl; } } system("pause"); system("cls"); } catch(exception e) { cout << e.what() << endl; system("pause"); system("cls"); } return 0; } НОВОСИБИРСК 2018 |
