№1 Лабораторная работа Алгоритмы и структуры данных (2). Отчет по лабораторной работе 1 по Алгоритмам и структурам данных
 Скачать 23.85 Kb.
|
|
| Содержимое файла Matrix.h |
| #pragma once #include class Matrix { int ** A; int n, m; public : Matrix(int n, int m); Matrix(); void FillMatrix(); void PrintMatrix(); void SwapLines(int number_row_1, int number_row_2); }; |
| Содержимое файла Matrix.cpp |
| #include "Matrix.h" Matrix::Matrix(int n, int m) { this->n = n; this->m = m; A = new int*[n]; for (int i = 0; i < n; i++) { A[i] = new int[m]; } } Matrix::Matrix() { for (int i = 0; i < n; i++) { delete[] A[i]; } delete[] A; } void Matrix:: FillMatrix() { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { A[i][j] = rand() % 100; } } } void Matrix:: PrintMatrix() { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { std::cout << A[i][j] << " "; } std::cout << std::endl; } } void Matrix::SwapLines(int number_row_1, int number_row_2) { int *tmp = A[number_row_1]; A[number_row_1] = A[number_row_2]; A[number_row_2] = tmp; } |
| Содержимое файла Stack.h |
| #pragma once #include class Stack { int count, size; int* values; public: Stack(int size); int get_count(); int get_size(); bool isEmpty(); void push(int value); int pop(); void clear(); void print(); }; |
| Содержимое файла Stack.cpp |
| #include "Stack.h" Stack :: Stack (int size) { this->size = size; count = 0; values = new int[size]; } int Stack :: get_count() { return count; } int Stack:: get_size() { return size; } bool Stack:: isEmpty() { if (count == 0) return true; else return false; } void Stack::push(int value) { if (count == size) { throw std::exception("Stack overflow!"); } values[count] = value; count++; } int Stack::pop() { if (isEmpty()) { throw std::exception("Stack is empty!"); } count--; return values[count]; } void Stack::clear() { while (count != 0) { pop(); count--; } } void Stack::print() { for (int i = 0; i < count; i++) std::cout << values[i] << std::endl; } |
| Содержимое файла List.h |
| #pragma once #include struct Node { int val; Node* next; Node(int _val) : val(_val), next(nullptr) {} }; class List { Node* first; Node* last; bool is_empty() { return first == nullptr; } public: List() : first(nullptr), last(nullptr) {} void push_back(int _val) { Node* p = new Node(_val); if (is_empty()) { first = p; last = p; return; } last->next = p; last = p; } void print() { if (is_empty()) return; Node* p = first; while (p) { std :: cout << p->val << " "; p = p->next; } std :: cout << std :: endl; } void remove_last() { if (is_empty()) return; if (first == last) { remove_first(); return; } Node* p = first; while (p->next != last) p = p->next; p->next = nullptr; delete last; last = p; } void remove_first() { if (is_empty()) return; Node* p = first; first = p->next; delete p; } Node* operator[] (const int index) { if (is_empty()) return nullptr; Node* p = first; for (int i = 0; i < index; i++) { p = p->next; if (!p) return nullptr; } return p; } }; |
| Содержимое файла Queue.h |
| #pragma once #include #include using namespace std; template class Queue { private: T* p; // динамический массив int count; // количество элементов в очереди public: // конструктор по умолчанию Queue() { count = 0; // очередь пустая } // конструктор копирования Queue(const Queue& obj) { // скопировать obj в текущий объект count = obj.count; try { // попытка выделить память для p p = new T[count]; // заполнить значениями for (int i = 0; i < count; i++) p[i] = obj.p[i]; } catch (bad_alloc e) { // если память не выделена, то вывести текст ошибки cout << e.what() << endl; count = 0; // создать пустую очередь } } // добавить элемент в очередь void push(T item) { T* p2; // объявить дополнительный указатель p2 = p; // перенаправить дополнительный указатель на p try { // попытка выделить новый фрагмент памяти для p, но на 1 больше p = new T[count + 1]; // скопировать данные из участка на который указывает p2 (старые данные) // в участок, на который указывает p for (int i = 0; i < count; i++) p[i] = p2[i]; // скопировать последний элемент p[count] = item; // увеличить количество элементов на 1 count++; // освободить предварительно выделенную память if (count > 1) delete[] p2; } catch (bad_alloc e) { // если память не выделена cout << e.what() << endl; // вывести сообщение об ошибке // вернуть старый указатель на p p = p2; } } // вытянуть первый элемент из очереди T pop() { if (count == 0) return 0; // заполнить элемент, который вытягивается из очереди T item; item = p[0]; // сформировать новый участок памяти, который на 1 меньше try { T* p2; // попытка выделить пам'ять p2 = new T[count - 1]; count--; // уменьшить количество элементов в очереди // p=>p2 for (int i = 0; i < count; i++) p2[i] = p[i + 1]; // копируются все кроме первого элемента // освободить участок, на который указывает p if (count > 0) delete[] p; // перенаправить p на p2 p = p2; // вернуть item return item; } catch (bad_alloc e) { // если память не выделилась, то вернуть 0 cout << e.what() << endl; return 0; } } // операторная функция operator=(), // реализует присваивание объектов типа Queue Queue& operator=(const Queue& obj) { T* p2; // указатель на дополнительную память try { // попытка выделить новый участок памяти для p2 p2 = new T[obj.count]; // если память выделена успешно, // можно освобождать предварительно выделенную память для p if (count > 0) delete[] p; // скопировать obj в текущий объект p = p2; // перенаправить p на p2 count = obj.count; // заполнить значениями for (int i = 0; i < count; i++) p[i] = obj.p[i]; } catch (bad_alloc e) { // если память не выделилась, то вывести соответствующее сообщение cout << e.what() << endl; } return *this; // вернуть текущий объект } // деструктор Queue() { if (count > 0) delete[] p; } // взять первый элемент из очереди не вытягивая его T GetItem() { if (count > 0) return p[0]; else return 0; } // очистка очереди void clear() { if (count > 0) { delete[] p; count = 0; } } // проверка существования элементов в очереди bool IsEmpty() { return count == 0; } // количество элементов в очереди int GetN() { return count; } // метод, выводящий очередь void print(const char* objName) { cout << "Object: " << objName << endl; for (int i = 0; i < count; i++) cout << p[i] << "\t"; cout << endl; cout << "---------------------" << endl; } }; |
| Содержимое файла StackOnList.h |
| #pragma once #include #include "List.h" class StackOnList { List values; int count; public: StackOnList() { count = 0; } int get_count() { return count; } bool isEmpty() { return (count == 0); } void push(int value) { values.push_back(value); count++; } int pop() { if (isEmpty()) { throw std ::exception("Stack is empty!"); } values.remove_last(); count--; return values[count]->val; } void print() { for (int i = 0; i < count; i++) std::cout << values[i]->val << std::endl; } }; |
| main.cpp |
| #include #include "Stack.h" #include "Matrix.h" #include "List.h" #include "StackOnList.h" #include "Queue.h" void test_Stack() { try { Stack stack(4); stack.push(2); stack.push(7); stack.push(5); stack.push(4); stack.pop(); stack.print(); } catch (std::exception &ex) { std::cout << ex.what(); } } void test_Matrix() { Matrix matrix(3,3); matrix.FillMatrix(); matrix.PrintMatrix(); std::cout << std::endl; matrix.SwapLines(0, 2); matrix.PrintMatrix(); } void test_StackOnList() { try { StackOnList stackOnList; stackOnList.push(2); stackOnList.push(1); stackOnList.push(7); stackOnList.push(4); stackOnList.pop(); stackOnList.print(); } catch (std::exception &ex) { std::cout << ex.what(); } } void test_Queue() { Queue<int> Q1; Q1.print("Q1"); Q1.push(5); Q1.print("Q1"); Q1.push(8); Q1.push(11); Q1.push(17); // Q1 = {5,8,11,17} Q1.print("Q1"); int d; d = Q1.GetItem(); cout << "d = " << d << endl; Q1.print("Q1"); } void test_QueueOnList() { } int main() { test_Queue(); return 0; } |