Міністерство освіти і науки, молоді та спорту України Національний університет „Львівська політехніка” Кафедра ЕОМ Звіт про виконання лабораторної роботи № 3 з дисципліни: “Обчислювальний практикум” на тему: “ Застосування АТД "Список" до розв’язання прикладних задач” Львів 2013 Мета: Ознайомитись з АТД «Список» Теоретичні відомості: Зв'язаний список в програмуванні — одна з найважливіших структур даних, в якій елементи лінійно впорядковані, але порядок визначається не номерами елементів, а вказівниками, які входять в склад елементів списку та вказують на наступний за даним елемент (в однозв'язаних або однобічно зв'язаних списках) або на наступний та попередній елементи (в двозв'язаних або двобічно зв'язаних списках). Список має «голову» — перший елемент та «хвіст» — останній елемент. Зв'язані списки мають серію переваг порівняно з масивами. Зокрема, в них набагато ефективніше (за час О(1), тобто незалежно від кількості елементів) виконуються процедури додавання та вилучення елементів. Натомість, масиви набагато кращі в операціях, які потребують безпосереднього доступу до кожного елементу, що у випадку зі зв'язаними списками неможливо та потребує послідовного перебору усіх елементів, які передують даному. Однобічно зв'язані списки / Однобічно зв'язаний список з трьох елементів В однобічно зв'язаному списку, який є найпростішим різновидом зв'язаних списків, кожний елемент складається з двох полів: data або даних, та вказівника next на наступний елемент. Якщо вказівник не вказує на інший елемент (інакше: next = NULL), то вважається, що даний елемент — останній в списку. Двобічно зв'язаний список / Двобічно зв'язаний список В двобічно зв'язаному списку елемент складається з трьох полів — вказівника на попередній елемент prev, поля даних data та вказівника next на наступний елемент. Якщо prev=NULL, то в елемента немає попередника (тобто він є «головою» списку), якщо next=NULL, то в нього немає наступника («хвіст» списка). Кільцевий список В кільцевому списку перший та останній елемент зв'язані. Тобто, поле prev голови списка вказує на хвіст списка, а поле next хвоста списка вказує на голову списка. Застосування списків Списки інтенсивно застосовуються в програмуванні як самостійні структури. Також на їх основі можуть будуватись складніші структури даних, такі як дерева. На базі списків також можуть бути реалізовані стеки та черги. Завдання: Многочлен виду
,де
представити у вигляді зв’язаного списку в якому кожний вузол має три поля: одне – для коефіцієнта Сi , друге – для показника степеня ni , третє – для вказівника на наступний вузол списку. Для описаного представлення многочленів програмно реалізувати таку операцію: Множення многочлена на одночлен. Текст програми: Polinomial.h #ifndef _POLYNOMIAL_H_ #define _POLYNOMIAL_H_ #include <list> #include <iostream> using std::list; using std::istream; using std::ostream; using std::ios_base; struct monomial { double coff; int index; }; class polynomial { private: list<monomial> lst; public: polynomial(); ~polynomial(); friend ostream & operator<<(ostream &os, const polynomial &pol); friend istream & operator>>(istream & is, polynomial &pol); polynomial operator*(monomial mon); friend polynomial operator*(monomial mon, const polynomial &pol); }; #endif /* _POLYNOMIAL_H_ */ Main.cpp #include "polynomial.h" using std::cout; using std::endl; using std::cin; int main() { setlocale(0, "Ukr"); polynomial pol; cout << "Введiть многочлен типу (коеф. степiнь). Для завершення введiть 0 для коеф." << endl; cin >> pol; cout << pol << endl; cout << "Введiть одночлен типу (коеф. степiнь): "; monomial mon; cin >> mon.coff; cin >> mon.index; cout << "Результат виразу mon*pol: " << mon*pol << endl; cout << "Результат виразу pol*mon: " << pol*mon << endl; system("pause"); return 0; } Polinomial.cpp #include "polynomial.h" polynomial::polynomial() { } polynomial::~polynomial() { } ostream & operator<<(ostream &os, const polynomial &pol) { list<monomial>::const_iterator c_itr; for (c_itr = pol.lst.cbegin(); c_itr != pol.lst.cend(); c_itr++) { os.setf(ios_base::showpos); os <<(*c_itr).coff << "*X^" << (*c_itr).index << " "; } return os; } istream & operator>>(istream & is, polynomial &pol) { monomial mon; double tmp; while (is >> tmp && tmp != 0.0) { mon.coff = tmp; is >> mon.index; pol.lst.push_back( mon); } return is; } polynomial polynomial::operator*(monomial mon) { polynomial res; res.lst = this->lst; list<monomial>::iterator itr; for (itr = res.lst.begin(); itr != res.lst.end(); itr++) { (*itr).coff *= mon.coff; (*itr).index += mon.index; } return res; } polynomial operator*(monomial mon, const polynomial &pol) { polynomial res; res.lst = pol.lst; list<monomial>::iterator itr; for (itr = res.lst.begin(); itr != res.lst.end(); itr++) { (*itr).coff *= mon.coff; (*itr).index += mon.index; } return res; } Результат виконання програми: Висновок: на цій лабораторній роботі я ознайомився із АТД «СПИСОК» і навчився застосовуати його у практичних задачах.