Міністерство освіти і науки України Національний університет „Львівська політехніка” Кафедра ЕОМ / Звіт про виконання лабораторної роботи №6 на тему: «Структура даних Список» Варіант № 2 Мета: вивчення фундаментальної абстрактної структури даних списку. Набуття практичних навичок побудови списку, дослідження динаміки його вмісту та використання списків для розв'язання прикладних задач. Вибір варіанту: мій номер у журналі 2, перша літера прізвища-“Б” отже варіант 2; Постановка задачі: Побудувати динамічну структуру даних список, реалізований за допомогою зв’язаних вузлів. Варіант 2: написати програму, яка будує лінійний зв’язаний список, що містить N великих літер латинського алфавіту, які вводяться з клавіатури, і перевіряє, чи будуть вузли списку впорядковані за алфавітом. (Примітка: великі літери латинського алфавіту в таблиці ASCII мають номери від 65 до 90 ). Результат виконання програми: / Рис.1 Резельтат виконання програми Спеціфікація програми #include <iostream> using namespace std; class LinkedList { private: int _size; struct Node { char data; Node* next; } *head; bool compare(Node* head, Node* headToCompare) { if(head == nullptr && headToCompare == nullptr) { return true; } else { if(head == nullptr || headToCompare == nullptr) return false; else if(head->data != headToCompare->data) return false; else return compare(head->next, headToCompare->next); } } public: LinkedList() { _size = 0; head = nullptr; }; ~LinkedList() { struct Node *tmpNode; while(head) { tmpNode = head; head = tmpNode->next; delete tmpNode; } }; void add(char n) { auto *newNode = new Node; newNode->data = n; newNode->next = nullptr; _size++; if (head == nullptr) { head = newNode; return; } Node *cur = head; while(cur) { if(cur->next == nullptr) { cur->next = newNode; return; } cur = cur->next; } } void insertFront(char n) { auto *newNode = new Node; newNode->data = n; newNode->next = head; head = newNode; _size++; } Node* search(char n) { Node *cur = head; while(cur) { if(cur->data == n) { return cur; } cur = cur->next; } cout << "No Node " << n << " in list.\n"; return nullptr; } bool remove(char n) { Node* cur = head; if(n == head->data) { head = cur->next; delete cur; return true; } while(cur) { if(cur->next->data == n) { Node* del = cur->next; cur->next = cur->next->next; delete del; return true; } cur = cur->next; } _size--; return false; } LinkedList* reverse() { Node *parent = head; Node *me = parent->next; Node *child = me->next; parent->next = nullptr; while(child) { me->next = parent; parent = me; me = child; child = child->next; } me->next = parent; auto * out = new LinkedList(); out->head = me; out->_size = this->_size; return out; } bool compare(LinkedList* list) { if(head == nullptr && list->head == nullptr) { return true; } else { if(head == nullptr || list->head == nullptr) return false; else if(head->data != list->head->data) return false; else return compare(head->next, list->head->next); } } void display() { Node *list = head; while(list) { cout << list->data << " "; list = list->next; } cout << endl; } LinkedList* copy() { auto *newLL = new LinkedList(); Node *cur = head; while (cur) { newLL->add(cur->data); cur = cur->next; } return newLL; } int size() { return _size; } bool check() { bool flag = true; Node *node = head; char cur; char next; while (node->next) { cur = node->data; next = node->next->data; if(cur > next) { flag = false; break; } node = node->next; } return flag; } }; int main() { auto *list = new LinkedList(); cout<<"Введіть великі літери латинського алфавіту (0 - завершити):"<<endl; while (true) { char ch; cin>>ch; if (ch == '0') { break; } else if (ch < 65 || ch > 90) { cout<<"Некоректний символ!"<<endl; } else { list->add(ch); } } if (list->check()) { cout << "Символи впорядковані за алфавітом." << endl; } else { cout << "Символи не впорядковані за алфавітом." << endl; } } Висновок: під час лабораторної роботи було вивчено фундаментальну абстрактну структуру даних - список. Набув практичних навичок побудови списку, дослідження динаміки його вмісту та використання списків для розв'язання прикладних задач.