|
|
Отчет по лабораторной работе 7 Вариант 16 по дисциплине
Министерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное
учреждение высшего образования
ИРКУТСКИЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Институт - Информационных технологий и анализа данных
наименование
«АБСТРАКТHЫЕ СТРУКТУРЫ ДАHHЫХ»
Отчет по лабораторной работе № 7
Вариант 16
по дисциплине Программирование на языке высокого уровня
наименование учебной дисциплины
Выполнил
Студент, ИСТб-21-1
|
|
П.А.Наумов
|
01.04.2022
|
(подпись)
|
|
Принял Доцент
|
|
И. В. Игумнов
|
01.04.2022
|
(подпись)
|
|
|
|
|
Иркутск 2022
Задание
Задача №1 (Двунаправленный список). Элементы двунаправленного списка имеют структуру DSP: Шифр детали, наименование, расценка, вес, указатель предыдущего, указатель последующего. Необхоимо рассчитать сумму цен всех деталей списка и вывести наименования наибольшей и наименьшей соответственно.
Задача №2 (Бинарное дерево). В структуру, реализующую список, добавить поля для организации записей в форме бинарного дерева: Левый потомок, Правый потомок. А также создать функции для выполнения следующих операций: добавление элемента, поиск элемента по ключу, удаление элемента по ключу, обход дерева в ширину и печать элементов, обход дерева в глубину и печать элементов.
Таблица спецификаций
Задача №1 (Двунаправленный список).
Таблица внешних спецификаций
Имя
|
Назначение
|
Тип
|
codeValue
|
Шифр детали
|
Int
|
priceValue
|
Цена детали
|
Int
|
nameValue
|
Название детали
|
String
|
weightValue
|
Вес детали
|
Int
|
select
|
Переменная для выбора команды
|
Int
|
inselect
|
Переменная для выбора команды
|
Int
|
inselectOther
|
Переменная для выбора команды
|
Int
|
Таблица модулей спецификаций
struct DSP
Имя модуля
|
Назначение
|
Тип результата
|
Параметры
|
getSelfProperties
|
Вывод на экран всех свойств детали
|
void
|
|
struct list
Имя модуля
|
Назначение
|
Тип результата
|
Параметры
|
isEmpty
|
Функция проверки наличия деталей в списке
|
bool
|
|
insetTail
|
Функция__findByKey_Условие_1:_current__current->data_!=_keyУсловие_2:_current->data_>_keyФункция__insertByKey'>Функция добавления детали в хвост списка
|
void
|
int code, string name, int price,
int weight
|
printList
|
Функция вывода списка
|
void
|
|
removeByCode
|
Функция удаления детали по ее шифру
|
void
|
int code
|
mainTask
|
Функция основного задания
|
void
|
|
Задача №2 (Бинарное дерево)
Таблица внешних спецификаций
Имя
|
Назначение
|
Тип
|
marks
|
Переменная для вывода дерева
|
Int
|
select
|
Переменная для выбора команды
|
Int
|
selectTwo
|
Переменная для выбора команды
|
Int
|
selectThree
|
Переменная для выбора команды
|
Int
|
Таблица модулей спецификаций
Имя модуля
|
Назначение
|
Тип результата
|
Параметры
|
treeOutputInWidth
|
Функция вывода дерева в ширину
|
void
|
|
findByKey
|
Функция поиска элемента по ключу
|
void
|
int code
|
insertByKey
|
Функция добавления элемента по ключу
|
void
|
int code
|
eraseByKey
|
Функция удаления элемента по ключу
|
void
|
int code
|
directTreeOutput
|
Функция прямого вывода дерева
|
void
|
|
reverseTreeOutput
|
Функция обратного вывода дерева
|
void
|
|
Алгоритм программы
Задача №2 (Бинарное дерево)
Функция insertByKey
Условие 1: current && current->data != key
Условие 2: current->data > key && current-> leftDescendant == NULL
Условие 3: current->data < key && current-> leftDescendant == NULL
Условие 4: current->data > key
Функция findByKey
Условие 1: current && current->data != key
Условие 2: current->data > key
Функция insertByKey
Функция findByKey
Таблица тестов
Задача №1 (Двунаправленный список).
Номер теста
|
Назначение
|
Входные данные
|
Выходные данные
|
1
|
Распечатать список
|
select 3
|
None
|
2
|
Добавить деталь в конец списка
|
select = 1
inselsect = 1
codeValue = 1
nameValue = “NFC”
priceValue = 1455
weightValue = 15
|
1 – Inserted element in tail of list
|
3
|
Вывести на экран результат основной программы
|
select = 5
|
None
|
4
|
Удалить деталь из списка по шифру
|
select = 2
inselsect = 3
inselsectOther = 1
|
1 – Remove element from list by code
|
5
|
Выход из программы
|
select = 5
|
None
|
Задача №2 (Бинарное дерево)
Номер теста
|
Назначение
|
Входные данные
|
Выходные данные
|
1
|
Распечатать дерево
|
select = 4
selectTwo = 1
|
3.1 – Распечатать бинарное дерево
3.2 – Распечатать бинарное дерево в прямом порядке
3.3) Распечатать дерево в обратном порядке
|
2
|
Добавить элемент в бинарное дерево
|
select = 1
selectThree= 4
|
Введите значение:
|
3
|
Распечатать дерево
|
select = 4
selectTwo= 1
|
3.1 – Распечатать бинарное дерево
3.2 – Распечатать бинарное дерево в прямом порядке
3.3 – Распечатать дерево в обратном порядке
|
4
|
Найти элемент в дереве
|
select = 3
selectThree= 2
|
Введите значение:
Элемент (2) есть в бинарном дереве
|
5
|
Удалить элемент в дереве
|
select = 2
selectThree = 5
|
Введите значение:
|
Код программы
Задача №1 (Двунаправленный список)
#include
#include
using namespace std;
// Объявление главной структуры, хранящей в себе свойства типов int,string, price, weight.
// А также указатели на предыдущий элемемент спика и на следующий.
struct DSP {
int code;
string name;
int price;
int weight;
DSP *previous;
DSP *next;
DSP(int _code, string _name, int _price, int _weight) { // Конструктор структуры
code = _code; name = _name; price = _price; weight = _weight;
next = NULL;
previous = NULL;
}
// Функция getSelfProperties необходима для получения свойств текущего элемента структуры.
// Вывод реализован посредством простого консольного вывода свойств.
void getSelfProperties() {
cout << "code: " << code << endl;
cout << "name: " << name << endl;
cout << "price: " << price << endl;
cout << "weight: " << weight << endl;
cout << "next: " << next <<" " << "previous: " << previous<< endl << endl;
}
};
// Структура списка, включающая в себя указатели на первый и последний элемент списка.
struct list {
DSP* first;
DSP* last;
// Конструктор, присваивающий NULL первому и последнему элементу (так как список пуст).
list() {
first = NULL;
last = NULL;
}
// Функция isEmpty необходим для проверки списка на наличие элементов.
// Если указатель на первый элемент хранит NULL, то лист пуст.
bool isEmpty() {
return first == NULL;
}
// Функция insertTail необходима для добавления элемемента в конец списка.
// Если лист не пуст, то указатель последнего переходит на новый элемент, иначе добавленный элемент становится и первым и последним.
void insertTail(int _code, string _name, int _price, int _weight) {
DSP* pointer = new DSP(_code, _name, _price, _weight);
if (isEmpty()) {
first = pointer;
last = pointer;
return;
}
last->next = pointer;
pointer->previous = last;
last = pointer;
}
// Функция printList необходима для вывода списка в консоль.
// Если список пуст – выведется соотвествующее сообщение.
// Иначе адресс текущего элемента будет идти до конца списка, паралелльно выводя свойства каждого элемента.
void printList() {
if (isEmpty()) {
cout << "List is empty\n\n";
return;
}
DSP* pointer = first;
while (pointer != NULL) {
cout << pointer << endl;
pointer->getSelfProperties();
cout << "--------------------\n";
pointer = pointer->next;
}
cout << endl;
}
// Функция removeHead необходима для удаления первого элемента списка.
// Сперва список проверяется на пустоту. Если он пуст – выход из функции.
// Иначе проверка каждого элемента на NULL, и при успешной проверки – удаление.
void removeHead() {
if (isEmpty()) {
return;
}
DSP* pointer = first;
first = pointer->next; // Первой по списку детали присваем следующую деталь
if (first != NULL) { // Указателю на пред.деталь первой по списку детали сбрасываем значение
first->previous = NULL;
}
delete pointer;
}
// Функция removeTail необходима для удаления последнего элемента списка.
void removeTail() {
if (isEmpty()) {
return;
}
if (first == last) { // Если список состоит из одной детали
removeHead(); // Вызываем функцию удаления детали с начала списка
return;
}
DSP* pointer = last;
last = pointer->previous; // Последней по списку детали присваиваем предыдущую деталь
last->next = NULL; // Указателю на след.деталь последней по списку детали сбрасываем значение
delete pointer;
}
// Функция для добавления элемента в начало списка.
// После проверки на пустоту, в случае пустого листа новый элемент добавляется в начало списка с указателем first и last.
// В противном случае новый объект сдвинет предыдущий первый и займет его место в списке.
void insertHead(int _code, string _name, int _price, int _weight) {
DSP* pointer = new DSP(_code, _name, _price, _weight);
if (isEmpty()) {
first = pointer;
last = pointer;
return;
}
pointer->next = first;
first->previous = pointer;
first = pointer;
}
// Функция служит для удаления элемента по его шифру, который функция принимает, как аргумент, если лист пуст - программа экстренно выходит из функции, в противном случае перебирает список.
// После нахождения элемента с нужным шифром она его удаляет, смещая впереди стоящие элементы на 1 назад.
void removeByCode(int _code) {
if (isEmpty()) {
return;
}
if (first->code == _code) { // Если шифр детали совпадает с первой по списку детали
removeHead(); // Вызваем функцию удаления детали с начала списка
return;
} else if (last->code == _code) {
removeTail(); // Вызываем функцию удаления детали с конца списка
return;
}
DSP* slow = first; // Создаем указатель на первую деталь в списке
DSP* fast = first->next; // Создаем указатель на следующую деталь после первой в списке
while (fast && fast->code == _code) { // Пока первая деталь не пуста и шифр детали не равен искомой
fast = fast->next; // Переходим к следующей детали
slow = slow->next; // Переходим к следующей детали
}
if (!fast) {
cout << "Element does not exist\n";
return;
}
slow->next = fast->next; //Обновляем указатель пред.детали с перескоком на деталь
fast->next->previous = slow; //Обновляем указатель пред.детали с перескоком на деталь
delete fast;
}
// Функция основного задания является процедурной и не принимает никаких значений в качестве аргумента.
// Функция перебирает каждый элемент списка, прибвляя значение его цены к свойству totalPrice, а после выводит на эран сообщение с итоговой суммой.
// Паралелльно с этим программма отбирает значения цен наибольшего и наименьшего элементов списка, а после выводит их на экран.
void mainTask() {
DSP *current = first, *minPrice = first, *maxPrice = first;
int totalPrice = 0;
while (current != NULL) {
totalPrice = totalPrice + current->price;
if (current->price < minPrice->price) {
minPrice = current;
}
if (current->price > maxPrice->price) {
maxPrice = current;
}
current = current->next;
}
cout << "Min price -> " << minPrice->price << " " << minPrice->name<< endl;
cout << "Max price -> " << maxPrice->price << " " << maxPrice->name<< endl;
cout << "Total Sum price -> " << totalPrice << endl;
}
};
// Главная функция
int main() {
list somePhone; // Объявление листа с именем somePhone
int select, inselect, codeValue, priceValue, inselectOther;
string nameValue;
int weightValue;
// Реализация меню с помощью ветвления switch
while (true)
{
cout << "\n-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-\n\n1 Insert element in list tail" << endl <<
"2 Remove element in list by code" << endl <<
"3 Print List" << endl <<
"5 Print result of main task" << endl <<
"4 End of process\n\n-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-" << endl;
cout << "\nChoose command: "; cin >> select;// cout << endl;
switch (select)
{
case 1:
{
// Организация ввода элементов в список.
cout << "\n1 Insert element in list tail" << endl;
cout << "--------------------" << endl;
cout << "Code: "; cin >> codeValue;
cout << "Name: "; cin >> nameValue;
cout << "Price: "; cin >> priceValue;
cout << "Weight: "; cin >> weightValue;
cout << "--------------------\n" << endl;
// Функция для ввода элемента в хвост списка.
somePhone.insertTail(codeValue, nameValue, priceValue, weightValue);
break;
}
case 2: {
// Реализация пункта меню, удаляющего элемент списка по шифру.
cout << "1 Remove element by code" << endl;
cout << "Code: "; cin >> inselectOther;
somePhone.removeByCode(inselectOther);
break;
}
case 3: {
// Реализация пункта меню для вывода списка в консоль.
cout << endl; cout << "--------------------" << endl;
somePhone.printList();
break;
}
case 5: {
// Реализация пункта меню для вывода результата основного задания.
somePhone.mainTask();
break;
}
case 4: goto exit;
default: cout << "Wrong command!" << endl;
break;
}
}
exit:;
}
|
Задача №2 (Бинарное дерево)
#include
using namespace std;
int marks;
// Главная структура
struct treeElements {
int data;
treeElements* leftDescendant;
treeElements* rightDescendant;
treeElements(int value) {
leftDescendant = NULL;
rightDescendant = NULL;
data = value;
}
};
//Структура бинарного дерева
struct binaryTree {
treeElements* root;
// Инициализатор
binaryTree(int key) {
root = new treeElements(key);
}
// Деинициализатор
binaryTree() {
deleteTree(root);// По завершении вызываем функцию удаления
}
// Функция удаления дерева
void deleteTree(treeElements* current) {
if (current) {
deleteTree(current->leftDescendant);
deleteTree(current->rightDescendant);
delete current;
}
}
// Процедура вызова функции вывода дерева
void treeOutputInWidth() {
printTree(root);
cout << endl;
}
// Процедура вызова функции прямого вывода дерева
void directTreeOutput() {
forwardPassage(root);
cout << endl;
};
//Функция прямого вывода дерева
void forwardPassage(treeElements* current) {
if (current) {
cout << " " << current->data;
forwardPassage(current->leftDescendant);
forwardPassage(current->rightDescendant);
}
}
//Процедура вызова функции обратного вывода дерева
void reveseTreeOutput() {
reversePassage(root);
cout << endl;
}
//Функция обратного вывода дерева
void reversePassage(treeElements* current) {
if (current) {
reversePassage(current->leftDescendant);
reversePassage(current->rightDescendant);
cout << " " << current->data;
}
}
//Функция вывода дерева
void printTree(treeElements* current) {
if (current) {
marks += 5;
printTree(current->leftDescendant);
for (int i = 0; i < marks; i++) cout << " ";
cout << current->data << endl;
printTree(current->rightDescendant);
marks -= 5;
return;
}
}
// Функция поиска элемента по ключу
void findByKey(int key) {
treeElements* current = root;
while (current && current->data != key) {
if (current->data > key)
current = current->leftDescendant;
else
current = current->rightDescendant;
}
if (current != NULL) cout << "Element (" << key << ") is present in binaryTree" << endl;
else cout << "Element (" << key << ") is absent in binaryTreeе" << endl;
}
// Функция добавления элемента по ключу
void insertByKey(int key) {
treeElements* current = root;
while (current && current->data != key) {
if (current->data > key && current->leftDescendant == NULL) {
current->leftDescendant = new treeElements(key);
return;
}
if (current->data < key && current->rightDescendant == NULL) {
current->rightDescendant = new treeElements(key);
return;
}
if (current->data > key) current = current->leftDescendant;
else current = current->rightDescendant;
}
}
// Функиця удаления элемента по ключу
void eraseByKey(int key) {
treeElements* current = root;
treeElements* parent = NULL;
while (current && current->data != key) {
parent = current;
if (current->data > key) {
current = current->leftDescendant;
} else {
current = current->rightDescendant;
}
}
if (!current) {
return;
}
if (current->leftDescendant == NULL) {
// Вместо current подвешивается его правое поддерево
if (parent && parent->leftDescendant == current)
parent->leftDescendant = current->rightDescendant;
if (parent && parent->rightDescendant == current)
parent->rightDescendant = current->rightDescendant;
delete current;
return;
}
if (current->rightDescendant == NULL) {
// Вместо current подвешивается его левое поддерево
if (parent && parent->leftDescendant == current)
parent->leftDescendant = current->leftDescendant;
if (parent && parent->rightDescendant == current)
parent->rightDescendant = current->leftDescendant;
delete current;
return; }
// У элемента есть два потомка, тогда на место элемента поставим
// наименьший элемент из его правого поддерева
treeElements* replace = current->rightDescendant;
while (replace->leftDescendant)
replace = replace->leftDescendant;
int replace_valueue = replace->data;
eraseByKey(replace_valueue);
current->data = replace_valueue;
}
};
int main() {
int select, selectTwo, selectThree;
binaryTree someTree(0);
while (true) {
cout << endl << "Menu:" << endl <<
"1 – Insert element in binaryTree" << endl <<
"2 – Remove element from binaryTree" << endl <<
"3 – Find element in binaryTree" << endl <<
"4 – Output BinaryTree" << endl <<
"5 – End of process" << endl;
cout << "\nChoose command: "; cin >> select;
switch (select) {
case 1: {
cout << "Enter value: "; cin >> selectTwo;
someTree.insertByKey(selectTwo);
break; }
case 2: {
cout << "Enter value: "; cin >> selectTwo;
someTree.eraseByKey(selectTwo);
break; }
case 3: {
cout << "Enter value: "; cin >> selectTwo;
someTree.findByKey(selectTwo);
break; }
case 4: {
cout <<
"3.1 – Output binaryTree" << endl <<
"3.2 – Direct output binaryTree" << endl <<
"3.3 – Reverse output binaryTree" << endl;
cout << "\nChoose command: "; cin >> selectThree;
switch (selectThree) {
case 1: {
someTree.treeOutputInWidth();
break;
}
case 2: {
someTree.directTreeOutput();
break;
}
case 3: {
someTree.reveseTreeOutput();
break;
}
default:cout << "Wrong command!" << endl; break;
}
break;
case 5: {
goto exit;
}
}
default:cout << "Wrong command!" << endl;
break;
}
}
exit:;
}
|
Тесты
Задача №1 (Двунаправленный список)
Тест 1
Тест 2
Тест 3
Тест 4
Тест 5
Задача №2 (Бинарное дерево)
Тест 1
Тест 2
Тест 3
Тест 4
Тест 5
 |
|
|
Скачать 415.45 Kb.