Last active
January 25, 2018 10:42
-
-
Save whimo/10707eaa6d978d66c5f690e09ec095c3 to your computer and use it in GitHub Desktop.
Polynomial using linked list
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| #include <fstream> | |
| #include <string> | |
| #include <cmath> | |
| class Monomial | |
| { | |
| public: | |
| Monomial (int coef, unsigned int power): coef (coef), power (power), link (nullptr) {}; | |
| int coef; | |
| unsigned int power; | |
| Monomial* link; | |
| Monomial* insert_after(int coef, unsigned int power) | |
| { | |
| Monomial* new_element = new Monomial(coef, power); | |
| new_element -> link = link; | |
| link = new_element; | |
| return new_element; | |
| } | |
| Monomial* add_to_next(int coef) | |
| { | |
| link -> coef += coef; | |
| if (link -> coef == 0) | |
| { | |
| Monomial* next = link -> link; | |
| delete link; | |
| link = next; | |
| } | |
| } | |
| }; | |
| class Polynomial | |
| { | |
| public: | |
| Polynomial (): first (nullptr) {}; | |
| Polynomial (int* coeffs, size_t power) | |
| { | |
| first = new Monomial (coeffs [0], power); | |
| Monomial* current = first; | |
| for (size_t i = 0; i < power; i++) | |
| { | |
| if (coeffs [i + 1] != 0) | |
| { | |
| current->link = new Monomial (coeffs [i + 1], power - i - 1); | |
| current = current->link; | |
| } | |
| } | |
| } | |
| Monomial* first; | |
| void print () | |
| { | |
| Monomial* current = first; | |
| if (current == nullptr) std::cout << 0 << std::endl; | |
| else | |
| { | |
| for (; current->link != nullptr; current = current->link) | |
| std::cout << current->coef << (current->power != 1? ("*x^" + std::to_string(current->power)) : "*x") << " + "; | |
| std::cout << current->coef << (current->power != 0? ("*x^" + std::to_string(current->power)) : "") << std::endl; | |
| } | |
| } | |
| bool eqv (Polynomial p) | |
| { | |
| Monomial* self = first; | |
| Monomial* check = p.first; | |
| for (self = first, check = p.first; | |
| self != nullptr && check != nullptr; | |
| self = self->link, check = check->link) | |
| { | |
| if (self->coef != check->coef || self->power != check->power) | |
| return false; | |
| } | |
| if (self == nullptr && check == nullptr) | |
| return true; | |
| return false; | |
| } | |
| int res (int x) | |
| { | |
| int result = 0; | |
| for (Monomial* current = first; current != nullptr; current = current->link) | |
| result += (current->coef) * pow (x, current->power); | |
| return result; | |
| } | |
| Polynomial dif () | |
| { | |
| auto coeffs = new int [first->power]; | |
| for (Monomial* current = first; current != nullptr && current->power != 0; current = current->link) | |
| coeffs [current->power - 1] = (current->coef) * (current->power); | |
| return Polynomial (coeffs, first->power - 1); | |
| } | |
| void add (Polynomial p) | |
| { | |
| unsigned int new_power = first->power > p.first->power? first->power : p.first->power; | |
| auto coeffs = new int [new_power + 1]; | |
| Monomial* self = new Monomial(0, 0); | |
| Monomial* new_first = self; | |
| self -> link = first; | |
| Monomial* term = p.first; | |
| for (; term != nullptr; term = term->link) | |
| { | |
| while (self->link->power > term->power && self->link != nullptr) | |
| self = self->link; | |
| if (self->link->power < term->power || self->link == nullptr) | |
| self = self->insert_after(term->coef, term->power); | |
| else self->add_to_next(term->coef); | |
| } | |
| first = new_first -> link; | |
| delete new_first; | |
| } | |
| }; | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment