#include "fun.h"
#include <stack>
#include <QString>
polynome::polynome():first(NULL),size(0){};
polynome::~polynome() {
for(Node *p; p = first; delete p)//˼·������ͷָ�벻�ǿգ��Ͱ�ͷָ������
first = first -> next;
}
void polynome::insert(double r,int e,int pos) {
if(pos > size|| pos < 0)return;
if(pos == 0){
Node* n = new Node(r,e,first);
first = n;
++size;
return ;
}
Node *current = first;
Node *prev = NULL;
int p = 0;
for (int i = 0; i < pos;++i){
prev = current;
current = current->next;
}//�����ƶ���ʹ�ý��½ڵ��ŵ�prev��current֮��
Node *n = new Node(r,e,current);
prev->next = n;
++size;
}
void polynome::remove(int pos) {
if (pos < 0|| pos >= size)return;
if (pos == 0){
Node *p = first;
first = first->next;
--size;
delete p;
return;
}
Node* current = first;
Node* prev = NULL;
for (int i=0;i < pos;++i){
prev = current;
current = current->next;
}//�����ƶ���ʹ��Ҫɾ���ĵ�����current
prev -> next = current ->next;
delete current;
--size;
}
int polynome::length()const {
return size;
}
void polynome::clear() {
for(Node *p; p = this->first; delete p)
this->first = this->first -> next;
size = 0;
}
polynome::polynome(const polynome & pl) {
//copy constructor
if(pl.length() <= 0){
first = 0;
size = 0;
return;
}
*this = pl;
}
polynome& polynome::operator = (const polynome & pl) {
if (this == &pl)//���������ڵ�ַ�ϵȼ�
return *this;
if(pl.length() <= 0){
clear();
return *this;
}
first = new Node(pl.first -> ratio, pl.first -> exponent);
Node *current = first;
Node *current_pl = pl.first -> next;
while (current_pl != NULL){
current -> next = new Node(current_pl -> ratio,current_pl -> exponent);
current = current -> next;
current_pl = current_pl -> next;
}
size = pl.size;
return *this;
}
/*
istream& operator >> (istream & cin, polynome & p) {
int n,e;
double r;
p.clear();
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> r>>e;
p.insert(r,e,0);
}
p.sort();
return cin;
}
ostream& operator << (ostream & cout, const polynome & p) {
if (p.length() <= 0)return cout;
Node *current = p.first;
bool first_time = true;
for (int i = 0; i < p.length() ; ++i) {
if (current -> ratio == 0) {
if (current -> exponent == 0 && p.length() == 1) {
cout << current -> ratio;
first_time = false;
} else {
cout << "the exponent = "<<current->exponent<<endl;
cout << "the ratio = "<<current->ratio<<endl;
}
current = current -> next;
continue;
}
if (current -> exponent == 0) {
if (first_time || current -> ratio < 0) {
cout <<current -> ratio;
first_time = false;
} else{
cout <<"+"<< current -> ratio;
}
} else if (current -> exponent == 1) {
if (first_time || current -> ratio < 0) {
if (current -> ratio != 1)
cout << current -> ratio << "x";
else
cout << "x";
first_time = false;
} else {
cout << "+";
if (current -> ratio != 1)
cout << current -> ratio << "x";
else
cout << "x";
}
} else {
if (first_time || current -> ratio < 0){
if (current -> ratio != 1)
cout << current -> ratio << "x^"<<current->exponent;
else
cout << "x^"<<current->exponent;
first_time = false;
}else{
cout << "+";
if (current -> ratio != 1)
cout << current -> ratio << "x^"<<current->exponent;
else
cout << "x^"<<current->exponent;
}
}
current = current -> next;
}
return cout;
}
*/
void polynome::sort() {
for (Node *p = first; p ; p = p -> next){
for (Node* q = p -> next; q; q = q->next) {
if (*p > *q) {
int temp_exponent = p->exponent;
p->exponent = q->exponent;
q->exponent = temp_exponent;
double temp_ratio = p->ratio;
p->ratio = q->ratio;
q->ratio = temp_ratio;
}
}
}
stack<int>stack_exponent;
Node *s,*prev;
for (Node *p = first; p ; ) {
if (stack_exponent.empty() || stack_exponent.top() != p->exponent){
stack_exponent.push(p->exponent);
prev = p;
p = p -> next;
}else {
prev->ratio += p->ratio;
s = p;
prev->next = p->next;
p = p->next;
delete s;
size --;
}
}
//����ȥ��
//����ȥ��������0
prev = first;
if (first != NULL){
for (Node *p = first -> next; p ; ) {
if ( abs(p -> ratio) < EPS ) {
prev -> next = p -> next;
s = p;
p = p -> next;
delete s;
--size;
}else {
prev = p;
p = p -> next;
}
}
if (size > 1 && abs(first -> ratio) < EPS ) {
s = first;
first = first -> next;
delete s;
--size;
}
}
//ȥ��������ʽ0ת������ֵ0
if(size == 1 && first -> ratio == 0) {
first->exponent = 0;
} else if (size == 0) {
first = new Node(0,0,0);
size ++;
}
}
polynome polynome::operator + ( polynome & p ) {
polynome new_polynome;
sort();
p.sort();
//����p��this,�������ϲ��ظ������о��� ȥ������ȥ����0��
Node *it_p = first, *it_q = p.first;
while (it_p != NULL && it_q != NULL) {
if ( it_p -> exponent == it_q -> exponent ) {
new_polynome.insert(it_p ->ratio + it_q->ratio, it_p->exponent,0);
it_p = it_p -> next;
it_q = it_q -> next;
} else if (it_p ->exponent < it_q -> exponent ){
new_polynome.insert(it_p -> ratio, it_p -> exponent,0);
it_p = it_p -> next;
} else if (it_p -> exponent > it_q -> exponent) {
new_polynome.insert(it_q -> ratio, it_q -> exponent,0);
it_q = it_q -> next;
}
}
while (it_p != NULL) {
new_polynome.insert(it_p -> ratio, it_p -> exponent,0);
it_p = it_p -> next;
}
while (it_q != NULL) {
new_polynome.insert(it_q -> ratio, it_q -> exponent,0);
it_q = it_q -> next;
}
new_polynome.sort();
return new_polynome;
}
polynome polynome::operator - ( polynome & p ) {
polynome new_polynome;
sort();
p.sort();
//����p��this,�������ϲ��ظ������о��� ȥ������ȥ����0��
Node *it_p = first, *it_q = p.first;
while (it_p != NULL && it_q != NULL) {
if ( it_p -> exponent == it_q -> exponent ) {
new_polynome.insert(it_p ->ratio - it
