polynomial.cpp

这个题目主要内容是单链接表的应用。通过单链接表的数据结构方式储存多项式

#include <iostream>
#include <cstdlib>	// for "system("pause")"
using namespace std;
// Singly-linked list node
class Link {									//节点结构体
public:
	int expo;								//指数项
	int coeff;								//系数项
	Link* next;								//连接下一节点的指针
	Link (const int indexval,const int coefficient,Link* nextval=NULL)
	{ expo=indexval; coeff=coefficient; next=nextval; }	//构造函数		
	Link (Link* nextval=NULL) { next=nextval; }      //构造函数
};

class Poly {						//单链接表多项式结构体
private:
	Link* head;					//单链表头指针
	Link* tail;					//单链表尾指针
	void removeall(){			//释放单链标储存空间
		Link* temp;
		while(head){
			temp=head;
			head=head->next;
			delete temp;
		}
	}
public:
	Poly () { head=tail=new Link;  }		//构造函数
	~Poly() { removeall(); }					//析构函数
	void print(); 				//以"系数X^指数"的形式打印链表内容
	void input(); 				//从屏幕内输入单链表,指数单调增
	const Poly& operator* (const Poly& P1) const;	//重载*运算符
	Poly& operator= (const Poly& p);				//重载=运算符
	void operator+=(const Poly& p) ;				//重载+=运算符
};


void Poly::input(){ // input for the polynomial, the exponent must be in
// assending order,
				  // exponent=-1 for end
	
	int c,p; // c,p:temporary store space for coeff and exponent
	int temp=-1; // an var to store the largest power to ensure assending 
// order
	while (1){
		cout << "exponent=";
		cin >> p;
		if (p<0) break;	// end for input(exponent=-1)
		if (p<=temp){	// not in assending order
			cout << "==============================\n";
			cout << "Exponent must be in assending order!\n";
			cout << "==============================\n";
			continue;
		}
		cout << "coefficient=";
		cin >> c;
		tail->next=new Link(p,c);	// enter an item in the list
		tail = tail->next;
		temp=p;
	}
}

void Poly::print(){	//Print the content of the list
	Link* ptr=head->next;
	while (ptr){	// ptr not points to end e.g ptr!=NULL
		cout << '(' << ptr->coeff <<  "X^" << ptr->expo << ")+";
		ptr = ptr->next;
	}
	cout << '\b' << ' ' << endl;
}

void Poly::operator +=(const Poly& p) 
{
	Link* ptr1=head; // ptr1=head to be able to insert a node before first one
	Link* ptr2=p.head->next;

	while (ptr2){	// insert ptr2 in a proper position in Poly1
		while(ptr1->next){ // searching for a proper position by help of ptr1
			if (ptr1->next->expo > ptr2->expo) {	// we need insert ptr2 before ptr1->next e.g after ptr1
				ptr1->next=new Link (ptr2->expo,ptr2->coeff,ptr1->next);
				ptr2=ptr2->next;
				break;
			}
			if (ptr1->next->expo==ptr2->expo){	// we find an item have same power
				ptr1->next->coeff += ptr2->coeff;
				ptr2=ptr2->next;
				break;
			}
			ptr1=ptr1->next;
		}
		if (ptr1->next==NULL){	// we have to insert ptr2 at the end
			ptr1->next=new Link(ptr2->expo,ptr2->coeff);
			ptr2=ptr2->next;
		}
		ptr1=ptr1->next; // because of assending order we dont need to set ptr1 to head
	}
	while (ptr1->next) ptr1=ptr1->next;	// find position for tail
	tail = ptr1;
}

Poly& Poly::operator =(const Poly& p)	
{
	if (head==p.head) return *this;	// copy itself
	removeall();
	head=tail=new Link;
	Link* ptr;	//  ptr used to copy the list
	ptr=p.head->next;
	while (ptr)
	{
		tail->next = new Link(ptr->expo,ptr->coeff);
		tail = tail->next;
		ptr=ptr->next;
	}
	return *this;
}

const Poly& Poly::operator* (const Poly& P1) const // overload the mutiplication operator
{
	Link* ptr1;	//
	Link* ptr2; // pointers to 2 Polys
	ptr1=head->next; ptr2=P1.head->next;
	Poly* result=new Poly; // result for recording the product
	Poly temp;
	temp.tail->next=new Link;
	temp.tail=temp.tail->next;
	while (ptr1){
		while(ptr2){	// calculate partial product and strore it to temp
			temp.tail->coeff = ptr1->coeff * ptr2->coeff;
			temp.tail->expo = ptr1->expo + ptr2->expo;
			*result+=temp;
			ptr2=ptr2->next;
		}
		ptr2=P1.head->next;
		ptr1=ptr1->next;
	}
	
	return *result;
}

int main()
{
	Poly test1,test2,result;
	
	cout << "Input for the FIRST polynomial:\n";
	cout << "Exponent must be in assending order.\n";
	cout << "Exponent=-1 for ending the input.\n" << flush;
	test1.input();
	cout << "You have entered:\n";
	test1.print();
	cout << "\n==============================\n";
	
	cout << "Input for the SECOND polynomial:\n";
	cout << "Exponent must be in assending order.\n";
	cout << "Exponent=-1 for ending the input.\n" << flush;
	test2.input();
	cout << "You have entered:\n";
	test2.print();
	cout << "\n==============================\n";

	result = test1 * test2;
	cout << "The result is:\n";
	result.print();
	system("pause");
	return 0;
}