АиСД 1 лабораторная НГТУ. отчет. Алгоритмы и структуры данных
 Скачать 203.5 Kb.
|
МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ государственное БЮДЖЕТНОЕ образовательное учреждение высшего образования «НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ» _______________________________________________________________________ Факультет автоматики и вычислительной техники Кафедра автоматики  ОТЧЁТ по лабораторной работе №1 «Коллекция данных - список» по дисциплине: «Алгоритмы и структуры данных» Выполнил:Проверил: студент гр. АВТ-917 Цырендоржиев Влад Дыбко М.А. «___» _________ 2021 г.«___» _________ 2021г. _________________ (оценка, подпись) Новосибирск 2021 Цели работы Освоение технологии реализации позиционных, линейных коллекций на пример АТД «Список». Освоение методики тестирования трудоемкости реализации коллекций. 2. Задание Структура данных — односвязная на базе массива с индексными указателями. Спроектировать, реализовать и провести тестовые испытания АТД «Список» для коллекции, содержащей данные произвольного типа. Тип данных задается клиентской программой. АТД «Список» представляет собой позиционно-ориентированную, линейную последовательность с доступом к элементам по номеру позиции или по значению. Интерфейс АТД «Список» включает операции: Опрос размера списка Очистка списка Проверка на пустоту Опрос наличия заданного значения Чтение значения с заданным номером Изменение значения с заданным номером Получение позиции в списке с заданным значением Включение нового значения Включение нового значения в позицию с заданным номером Удаление заданного значения Удаления значения из позиции с заданным номером Итератор для доступа к элементам списка: Установка на первое значение Переход к следующему значению Проверка состояния итератора Доступ по чтению и записи к текущему элементу Для тестирования эффективности операций интерфейс АТД «Список» включает дополнительную операцию — опрос числа элементов списка, просмотренных операцией. 3. Описание АТД «Список» АТД «Список на базе массива с индексными указателями» List Список данных указанного типа T. Список имеет фиксированную максимальную размерность, задаваемую в конструкторе при создании объекта класса. После создания объекта размерность списка изменить нельзя. При попытке добавить значение в «полный» список возникает исключение. Исключения: Объект генерирует 3 исключения типа int, которые несут смысловую нагрузку: 1 - Выход за пределы допустимого диапазона элементов 2 - Обращение к несуществующему элементу (итератор обращается к удалённому объекту списка) 3 - Элемент не найден (при удалении элемента по значению) Данные: Параметры: Максимальный размер списка sizeOfList Текущее число элементов в списке Структура данных: Динамический массив с индексными указателями Операции: Конструктор Вход: максимальный размер списка sizeOfList (по умолчанию sizeOfList = 10), sizeOfList > 0 Предусловия: нет Процесс: создание динамических массивов объектов и индексов заданной размерности sizeOfList Выход: исключение типа 1 при отрицательном введённом размере списка Постусловия: создан пустой список ёмкости sizeOfList Конструктор копирования Вход: другой объект типа List Предусловия: нет Процесс: копирование полей входного объекта Выход: нет Постусловия: скопирован список Деструктор Вход: нет Предусловия: нет Процесс: удаление динамических массивов объектов и индексов Выход: нет Постусловия: объект удалён Получение размера списка Вход: нет Предусловия: нет Процесс: чтение параметра size Выход: текущий размер списка size: 0 <= size <= sizeOfList Постусловия: нет Очистка списка Вход: нет Предусловия: нет Процесс: удаление всех значений из списка Выход: нет Постусловия: список пуст Проверка списка на пустоту Вход: нет Предусловия: нет Процесс: проверка size > 0 Выход: 1, если список пуст, иначе 0 Постусловия: нет Проверка на наличие значения Вход: значение value типа T Предусловия: нет Процесс: поиск в списке значения равного value Выход: 1, если значение найдено, иначе 0 Постусловия: нет Получение значения по индексу Вход: индекс index запрашиваемого элемента Предусловия: 0 <= index < sizeOfList Процесс: чтение значения с заданной позиции Выход: возвращается значение типа T с заданным индексом или исключение типа 1 при неверно введённом индексе Постусловия: нет Изменение значение по индексу Вход: индекс изменяемого элемента index, значение типа T newValue Предусловия: 0 <= index < sizeOfList Процесс: изменение целевого элемента на значение newValue Выход: Исключение типа 1 при неверно введённом индексе Постусловия: значение с введённым индексом изменено на новое значение Получение индекса элемента по значению Вход: значение элемента для поиска типа T Предусловия: нет Процесс: проход значений списка от начала до тех пор, пока введённое значение не будет найдено, иначе до конца списка Выход: индекс первого элемента, имеющего введённое значение. Если значение не встречается в списке, возвращается -1 Постусловия: нет Вставка значения в конец списка Вход: вставляемое значение типа T Предусловия: size < sizeOfList Процесс: вставка в конец списка введённого значения Выход: исключение типа 1 при невыполненном предусловии Постусловия: в конец списка вставлен новый элемент Вставка значения по индексу Вход: индекс index для вставки и вставляемое значение типа T Предусловия: число элементов в списке < sizeOfList и индекс введён верно Процесс: вставка в указанную позицию Выход: исключение типа 1 в случае переполнения или неверного индекса Постусловия: в список вставлен новый элемент в позицию index Удаление элемента по значению Вход: значение value типа T для удаления Предусловия: в списке есть элемент со значением value Процесс: удаление первого элемента со значением value Выход: исключение типа 3, если значение value не встречается в списке Постусловия: из списка удалён элемент со значением value Удаление по индексу Вход: индекс index для удаления Предусловия: 0 <= index < sizeOfList Процесс: удаление элемента c номером index Выход: исключение типа 1 при неверно введённом индексе Постусловия: из списка удалён элемент с индексом index Итератор класса List: От начала к концу Может переходить в неопределенное состояние Данные: Параметры: Указатель на обрабатываемый объект класса List — list Текущая позиция итератора в списке Операции: Конструктор итератора Вход: ссылка на объект list типа List Предусловия: нет Процесс: установка итератора на первый элемент списка Выход: исключение типа 2, в случае ошибки обращения к памяти Постусловия: создан итератор для объекта list Сдвиг итератора в начало списка Предусловия: обрабатываемый объект существует Вход: нет Процесс: установка итератора на первый элемент списка Выход: исключение типа 2, если объект не существует Постусловия: итератор сдвинут на первый элемент обрабатываемого списка Сдвиг итератора вправо Вход: нет Предусловия: объект list не был изменён с момента создания итератора, иначе верная работа итератора не гарантируется. list существует. Итератор не вышел за пределы списка. Процесс: сдвиг итератора на один элемент вправо Выход: исключение типа 1, если итератор находится за пределами списка. Исключение типа 2, если list не существует Постусловия: итератор сдвинут на один элемент вправо Проверка на нахождение вне списка Вход: нет Предусловия: нет Процесс: проверка на нахождение вне диапазона элементов списка Выход: 1, если итератор за пределами списка, иначе 0 Постусловия: нет Доступ к значению по чтению и записи Вход: нет Предусловия: итератор находится внутри списка. Обрабатываемый итератором объект существует Процесс: нет Выход: адрес значения внутри списка, на элемент которого указывает итератор. Исключение типа 1, если итератор находится за пределами списка. Исключение типа 2, если list не существует Постусловия: возможность изменения значения элемента извне 4. Трудоёмкость операций над списком Для оценки эффективности работы созданного списка будем тестировать трудоёмкости операций вставки, удаления и поиска. Данным операциям соответствуют методы списка: «вставка по индексу», «удаление по индексу» и «проверка наличия значения». Для получения статистических данных проводится большое число итераций последовательного удаления из случайной позиции, вставки случайного значения в случайную позицию, поиска случайного значения в списке. Для тестирования пользователь задаёт размер создаваемого списка и диапазон значений для заполнения. Список целиком заполняется случайными числами в пределах указанного диапазона. Для получения статистических данных проведём число итераций, равное половине размера созданного списка. В каждой итерации будем подсчитывать количество пройденных элементов списка при удалении из случайной позиции, затем количество пройденных элементов при вставке случайного числа в случайную позицию, а затем подсчёт пройденных элементов при поиске случайного значения из диапазона. Порядок «удаление-вставка-поиск» позволяет избежать погрешности из-за изменения числа элементов: для удаления доступен весь диапазон элементов списка, после удаления одного из элементов, вставку также можно осуществить в любую позицию списка, в результате список вернулся к первоначальному размеру, и поиск значения проходит среди всех элементов списка. После проведения всех итераций мы получим среднее значение пройденных элементов при вставке, удалении, поиске путём деления значений счётчиков удаления, вставки и поиска на число итераций. Теоретически мы имеем дело с массивом, следовательно, операции вставки и удаления равновероятно могут производиться в любое место массива. Следовательно, теоретически, среднее значение проходов элементов массива при удалении и вставки при размере массива N должно приближаться к N/2. Поиск значения зависит лишь от диапазона генерируемых значений. Если числа генерируются в диапазоне от 0 до M, то в среднем операция поиска должна укладываться за M просмотров элементов списка. Табл. 4.1 — Трудоёмкости операций вставки, удаления и поиска
Как можно видеть, собранные статистические данные отклоняются от теоретических значений, что можно объяснить относительно небольшим числом итераций: для каждого случая лишь половина размера списка. Для повышения точности необходимо увеличить число итераций. Предсказанный характер поведения (теоретические данные) коллекции соответствует тому, что мы можем наблюдать на практике, собрав статистические данные.  Рис 4.1 — Сравнение практической и теоретической трудоёмкостей вставки и удаления для диапазона 1-100  Рис 4.2 — Сравнение практической и теоретической трудоёмкостей поиска элементов для диапазона 1-3000 По графикам и таблицам можно видеть, что операции вставки и удаления имеют линейную трудоемкость – O(n) (n – размер массива), что совпадает с теоретическими данными, а операция поиска уменьшает скорость своего роста из-за особенности методики тестирования. 4. Выводы Была разработана программная реализация АТД «Односвязанный список на базе массива с индексными указателями». Реализованы все стандартные функции. Проведенное тестирование операций не выявило ошибок. Также проведено тестирование трудоёмкости, которое показало линейный характер трудоёмкости операций вставки, удаления - O(n) и близость к нему операции поиска. Тестирование показало адекватность теоретических предположений о трудоёмкости: для вставки и удаления — N/2, для поиска — M/2, где N — размер списка, а M — диапазон генерируемых значений. Приложение А Исходный код программы-меню Модифицированный файл «classList.h» #ifndef CLASSLIST_H #define CLASSLIST_H ////////////////////////////////////////////////////////////////////////////// //Шаблонный класс односвязного списка на базе массива с индексными указателями //вариант 3 ////////////////////////////////////////////////////////////////////////////// //Расшифровка исключений: //1 - Выход за пределы диапазона //2 - Обращение к несуществующему элементу (итератор обращается к удалённому объекту списка) //3 - Элемент не найден (при удалении элемента по значению) ////////////////////////////////////////////////////////////////////////////// template protected: int head; //Индекс головы списка int empty; //Индекс первого пустого элемента int *nextArray; //Массив индексов следующих элементов T *objectArray; //Массив элементов списка int arraySize; //Размер массива int counter; //Счётчик элементов в списке int version; //"Версия" объекта public: List(int sizeOfList = 10); //Конструктор с параметром - длиной массива List(const List List(); //Деструктор //Интерфейс АТД: int getSizeOfList(); //Размер списка void clearList(); //Очистить список bool isEmpty(); //Проверка на пустоту bool haveValue(const T& value); //Проверка наличия значения T getValue(int index); //Чтение значения по номеру void changeValue(int index, const T& newValue);//Изменение значения по номеру int getIndexOf(const T& value); //Получить индекс по значению void insert(const T& value); //Вставка нового значения void insert1(int index, const T& value); //Вставка нового значения по индексу void deleteValue(const T& value); //Удалить значение void deleteAtIndex(int index); //Удалить по индексу //Класс итератора списка class Iterator { List *listPtr; //Указатель на список int cur; //Индекс текущего элемента int verison; //"Версия", должна совпадать с версией списка public: Iterator(List &list); //Конструктор void beg(); //В начало списка void next(); //К следующему элементу bool isOff(); //Истина, если вышли за пределы списка T& operator*(); //Оператор обращения к элементу списка }; friend class Iterator; }; ////////////////////////////////////////////////////////////////////////////// //Реализация полей класса списка ////////////////////////////////////////////////////////////////////////////// template //Проверка корректности индекса if(sizeOfList < 1) throw 1; //Создание массивов, задание значений индексов arraySize = sizeOfList; nextArray = new int[arraySize]; objectArray = new T[arraySize]; head = -1; empty = 0; counter = 0; version = 0; //Пустой массив превращаем в связанную цепочку пустых ячеек for(int i = 0; i < arraySize - 1; ++i) nextArray[i] = i + 1; nextArray[sizeOfList - 1] = -1; } template arraySize = anotherList.arraySize; nextArray = new int[arraySize]; objectArray = new T[arraySize]; head = anotherList.head; empty = anotherList.empty; version = anotherList.version; for(int i = 0; i < arraySize; ++i) { nextArray[i] = anotherList.nextArray[i]; objectArray[i] = anotherList.objectArray[i]; } } template delete []nextArray; delete []objectArray; } template return counter; } template head = -1; empty = 0; counter = 0; ++version; //Массив превращаем в связанную цепочку пустых ячеек for(int i = 0; i < arraySize - 1; ++i) nextArray[i] = i + 1; nextArray[arraySize - 1] = -1; } template if(counter) return 0; return 1; } template int i = head; while(i != -1) { if(objectArray[i] == value) return 1; i = nextArray[i]; } return 0; } template //Проверка индекса на верность if(index < 0 || index >= arraySize || index >= counter) throw 1; int i = head; for(int j = 0; j < index; ++j) i = nextArray[i]; return objectArray[i]; } template //Проверка индекса на верность if(index < 0 || index >= arraySize || index >= counter) throw 1; int i = head; for(int j = 0; j < index; ++j) i = nextArray[i]; objectArray[i] = newValue; //return 1; } template int i = head; int j = 0; while(i != -1) { if(objectArray[i] == value) return j; i = nextArray[i]; ++j; } return -1; } template if(counter == arraySize) throw 1; //return 0; if(counter == 0) { //Случай пустого списка head = empty; empty = nextArray[empty]; nextArray[head] = -1; objectArray[head] = value; } else { //Случай добавления в непустой список //Ищем последний элемент int lastIndex = head; for(int j = 0; j < counter - 1; ++j) lastIndex = nextArray[lastIndex]; //Вставляем элемент в конец nextArray[lastIndex] = empty; objectArray[empty] = value; empty = nextArray[empty]; nextArray[nextArray[lastIndex]] = -1; } ++version; ++counter; } template //Проверка индекса на верность if(index < 0 || index >= arraySize || counter == arraySize) throw 1; if(counter == 0) { //Случай пустого списка head = empty; empty = nextArray[empty]; nextArray[head] = -1; objectArray[head] = value; } else { //Случай непустого списка if(index == 0) { //Случай вставки в начало списка int newHead = empty; empty = nextArray[empty]; objectArray[newHead] = value; nextArray[newHead] = head; head = newHead; } if(index == counter) { //Случай вставки в конец списка //Ищем последний элемент int lastIndex = head; for(int j = 0; j < counter - 1; ++j) { lastIndex = nextArray[lastIndex]; } //Вставляем элемент в конец nextArray[lastIndex] = empty; objectArray[empty] = value; empty = nextArray[empty]; nextArray[nextArray[lastIndex]] = -1; } if(index > 0 && index < counter) { //Случай вставки в середину списка //Ищем элементы, между которыми произведём вставку int prevIndex(head); for(int j = 0; j < index - 1; ++j) { prevIndex = nextArray[prevIndex]; } //Вставка между найденными элементами int curIndex = empty; empty = nextArray[empty]; objectArray[curIndex] = value; nextArray[curIndex] = nextArray[prevIndex]; nextArray[prevIndex] = curIndex; } } ++version; ++counter; } template int i = head; int prev(-1); while(i != -1) { if(objectArray[i] == value) { if(prev == -1) { //Случай удаления первого элемента head = nextArray[i]; nextArray[i] = empty; empty = i; } else { //Элемент не первый nextArray[prev] = nextArray[i]; nextArray[i] = empty; empty = i; } --counter; ++version; return; } prev = i; i = nextArray[i]; } throw 3; } template //Проверка индекса на верность if(index < 0 || index >= arraySize || index >= counter) throw 1; //return 0; if(index == 0) { //Случай удаления первого элемента int cur = head; head = nextArray[cur]; nextArray[cur] = empty; empty = cur; } else { //Элемент не первый //Ищем удаляемый элемент int prev = head; for(int j = 0; j < index - 1; ++j) { prev = nextArray[prev]; } int cur = nextArray[prev]; //Удаляем nextArray[prev] = nextArray[cur]; nextArray[cur] = empty; empty = cur; } ++version; --counter; //return 1; } ////////////////////////////////////////////////////////////////////////////// //Реализация полей класса итератора ////////////////////////////////////////////////////////////////////////////// template beg(); } template try { cur = listPtr->head; } catch(...) { throw 2; } } template if(cur != -1) { try { cur = listPtr->nextArray[cur]; } catch(...) { throw 2; } } else throw 1; } template if(cur == -1) return 1; return 0; } template //Проверка на нахождение вне списка if(cur == -1) throw 1; try { return listPtr->objectArray[cur]; } catch(...) { throw 2; } } #endif // CLASSLIST_H Файл «main.cpp» #include "Header.h" #include #include using namespace std; int main(int argc, char* argv[]) { setlocale(LC_ALL, "rus"); //Строки const char programName[] = "######################################################\n Список на индексном массиве\n######################################################\n"; const char pressAnyKey[] = "Для продолжения нажмите любую клавишу...\n"; const char* exceptionText[4]; exceptionText[1] = strdup("Выход за границы диапазона\n"); exceptionText[2] = strdup("Обращение к несуществующему элементу\n"); exceptionText[3] = strdup("Элемент с данным значением не найден\n"); //Интерфейс программы List List int itPos(0); while (1) { //Ввод размера списка system("cls"); cout << programName; cout << "Ввведите размер списка:\n"; int tmp, tmp2; cin >> tmp; //Пробуем создать список указанного размера try { obj = new List } catch (int a) { //Размерность введена неверно cout << exceptionText[a] << pressAnyKey; getch(); continue; } //Меню bool iteratorExist(0); while (1) { system("cls"); cout << programName; //Отобразить список List cout << "########################Список########################\n"; if (i.isOff()) cout << "Список ещё пуст"; while (!i.isOff()) { cout << *i << ' '; i.next(); } //Отобразить итератор if (iteratorExist) { cout << "\n####################Итератор####################\n"; if (itPos < obj->getSizeOfList()) cout << "Позиция: " << itPos << "\tзначение: " << **iterator; else cout << "Позиция: -\tзначение: -"; } cout << "\n######################################################\n"; cout << "Действия:\n"; cout << "1. Вставка в конец списка\n"; cout << "2. Вставка в позицию\n"; cout << "3. Удалить по значению\n"; cout << "4. Удалить по индексу\n"; cout << "5. Получить размер списка\n"; cout << "6. Очистить список\n"; cout << "7. Проверить список на пустоту\n"; cout << "8. Проверка наличия значения в списке\n"; cout << "9. Получить значение из списка по индексу\n"; cout << "10. Изменить значение с заданным индексом\n"; cout << "11. Получить индекс значения\n"; //Меню для итератора if (iteratorExist) { cout << "12. Сдвинуть итератор вправо\n"; cout << "13. Сдвинуть итератор в начало\n"; cout << "14. Получить значение\n"; cout << "15. Изменить значение\n"; cout << "16. Итератор вышел за диапазон?\n"; cout << "17. Удалить итератор\n"; cout << "0. Выход\n"; cout << "######################################################\n"; } else { cout << "12. Создать итератор\n"; cout << "0. Выход\n"; cout << "######################################################\n"; } cin >> tmp; if (tmp < 0 || (!iteratorExist && tmp > 12) || (iteratorExist && tmp > 17)) continue; try { switch (tmp) { case 1: //Вставка в конец списка cout << "Введите значение для вставки: "; cin >> tmp; obj->insert(tmp); break; case 2: //Вставка в позицию cout << "Введите позицию и значение для вставки: "; cin >> tmp >> tmp2; obj->insert1(tmp, tmp2); break; case 3: //Удалить по значению cout << "Введите значение для удаления: "; cin >> tmp; obj->deleteValue(tmp); break; case 4: //Удалить по индексу cout << "Введите индекс элемента для удаления: "; cin >> tmp; obj->deleteAtIndex(tmp); break; case 5: //Получить размер списка cout << "Размер списка: " << obj->getSizeOfList() << '\n' << pressAnyKey; getch(); break; case 6: //Очистить список obj->clearList(); break; case 7: //Проверить список на пустоту if (obj->isEmpty()) cout << "Список пуст\n"; else cout << "Список не пуст\n"; cout << pressAnyKey; getch(); break; case 8: //Проверка наличия значения в списке cout << "Введите значение для проверки: "; cin >> tmp; if (obj->haveValue(tmp)) cout << "Значение в списке\n"; else cout << "Значения нет в списке\n"; cout << pressAnyKey; getch(); break; case 9: //Получить значение из списка по индексу cout << "Введите индекс: "; cin >> tmp; cout << "Значение с индексом " << tmp << " равно " << obj->getValue(tmp) << '\n' << pressAnyKey; getch(); break; case 10: //Изменить значение с заданным индексом cout << "Введите индекс и новое значение: "; cin >> tmp >> tmp2; obj->changeValue(tmp, tmp2); break; case 11: //Получить индекс значения cout << "Введите значение: "; cin >> tmp; cout << obj->getIndexOf(tmp) << '\n' << pressAnyKey; getch(); break; case 12: //Создать итератор/Сдвинуть итератор вправо if (iteratorExist) { iterator->next(); ++itPos; } else { iteratorExist = 1; itPos = 0; iterator = new List } break; case 13: //Итератор вначало if (iteratorExist) { iterator->beg(); itPos = 0; } break; case 14: //Получить значение if (iteratorExist) { cout << "Значение = " << **iterator << '\n'; cout << pressAnyKey; getch(); } break; case 15: //Изменить текущее значение if (iteratorExist) { cout << "Текущее значение = " << **iterator << '\n'; cout << "Изменить на: "; cin >> **iterator; } break; case 16: //Проверка выхода за диапазон if (iteratorExist) { if (iterator->isOff()) cout << "Итератор вне диапазона\n"; else cout << "Итератор внутри диапазона\n"; cout << pressAnyKey; getch(); } break; case 17: //Удалить итератор if (iteratorExist) { if (iterator) delete iterator; iteratorExist = 0; } break; case 0: //Выход return 0; } } //Обработчик исключений catch (int a) { cout << exceptionText[a] << pressAnyKey; getch(); continue; } } } } | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||