//链表结构的实现
#include<iostream>
#include<stdlib.h>
#include<iomanip>
#include<string>
using namespace std;

typedef struct{
	int exp;
	int coef;
}ElemType;//按实际情况修改

void Exception(bool Condition, string ErrorMsg){
	if(Condition){cerr << ErrorMsg << endl; abort();}
}

template <class T> class Chain;

template <class T>
class ChainNode{
   friend class Chain<T>;
   private:
//	public:
      T data;
      ChainNode<T> *link;
};

template<class T>
class Chain {
   public:
      Chain();
      ~Chain();
	  void Clear();      //清空链表
      bool IsEmpty() {return first->link == 0;}
      int Length(); 
	  T Get(int k) ;  //返回第i个结点的值
	  int Find( T e) ; //返回值等于e的结点的序号，无则返回0
      //int Search(const T& x) const; 
      bool Delete(int k, T &x); 
      bool Insert(int k,  T x);
      void Output(ostream& out) ;
	  void inputPolynomial(void);
	  void Add(Chain<T> &A, Chain<T> &B);
	  void Sub(Chain<T> &A, Chain<T> &B);
	  void Multi(Chain<T> &A, Chain<T> &B);
   private:
      ChainNode<T> *first;  // pointer to first node
};

template<class T>
Chain<T>::Chain(){    //构造函数
	first = new ChainNode<T>;  //申请连续空间，返回空间首地址
	Exception(!first, "there is no space in memory"); //若申请空间失败，则程序中断
	first->link = 0;
}

template<class T>
Chain<T>::~Chain()
{// Chain destructor. Delete all nodes in chain.
   ChainNode<T> *link;  // next node
   while (first) {
      link = first->link;
      delete first;
      first = link;
      }
}

template<class T>
void Chain<T>::Clear()      //清空链表
{
   ChainNode<T> *next1, *next2;  // next node
   next1 = first->link;
   while (next1) {
      next2 = next1->link;
      delete next1;
      next1 = next2;
      }
   first->link = 0;
}


template<class T>
int Chain<T>::Length() 
{// Return the number of elements in the chain.
   ChainNode<T> *current = first->link;
   int len = 0;
   while (current) {
     len++;
     current = current->link;
     }
   return len;
}

template<class T>
T Chain<T>::Get(int k) 
{// Set x to the k'th element in the chain.
 // Return false if no k'th; return true otherwise.
   Exception(k<1, "Out of bounds access."); //越界、非法
   ChainNode<T> *current = first->link;
   int index = 1;  // index of current
   while (index < k && current) {
      current = current->link;
      index++;
      }
   Exception(!current, "Out of bounds access."); //越界、非法
   return current->data;
}

template<class T>
int Chain<T>::Find( T x) 
{// Locate x.  Return position of x if found.
 // Return 0 if x not in the chain.
   ChainNode<T> *current = first->link;
   int index = 1;  // index of current
   while (current && current->data != x) {
      current = current->link;
      index++;
      }
   if (current) return index;
   return 0;
}

template<class T>
bool Chain<T>::Delete(int k, T &x)
{// Set x to the k'th element and delete it.
 // Throw OutOfBounds exception if no k'th element.
   Exception((k < 1 || !first->link), "Out of bounds access.");
   
   // move q to k-1'th 
      ChainNode<T> *q = first;
      for (int index = 0; index < k - 1 && q->link; index++)
         q = q->link;
 
     Exception(!(q->link), "Out of bounds access."); // no k'th
	    // p will eventually point to k'th node
      ChainNode<T> *p = q->link; // k'th
      q->link = p->link; // remove from chain

   // save k'th element and free node p
   x = p->data;
   delete p;
   return true;
}

template<class T>
bool Chain<T>::Insert(int k,  T x)
{// Insert x at the k'th element.
 // Throw OutOfBounds exception if no k'th element.
 // Pass NoMem exception if inadequate space.
   Exception((k <= 0), "Out of bounds access.");

   // p will eventually point to k-1'th node
   ChainNode<T> *p = first;
   for (int index = 0; (index < k-1) && p; index++)  // move p to k'th
      p = p->link;
   Exception((!p), "Out of bounds access."); // no k'th

   // insert
   ChainNode<T> *y = new ChainNode<T>;
   y->data = x;
           y->link = p->link;
           p->link = y;
   return true;
}

template<class T>
void Chain<T>::Output(ostream& out) 
{// Insert the chain elements into the stream out.
	if( !first->link){
		cout << 0 << endl;
		return;
	}
    ChainNode<T> *current;
    for (current = first->link; current;
	current = current->link){
		if(current->data.coef > 0)
			out << '+';
		out << current->data.coef << "x^" << current->data.exp;
	}
	out << endl;
}

// overload <<
template <class T>
ostream& operator<<(ostream& out,  Chain<T>& x)
   {x.Output(out); return out;}


template<class T>
void Chain<T>::inputPolynomial(void)//按降幂排列输入多项式
{
	int m, n = 0;
	int n1 = 10000;
	ElemType e;
	cout << "请按降幂排列输入多项式: " << endl;
	while(n >= 0){
		cout << "输入次数:(-1 退出) ";
		cin >> n;
		if(n < n1){
			if(n >= 0){
				cout << "请输入系数 a(" << n << "):";
		        cin >> m;
		        e.exp = n;
		        e.coef = m;
		        Insert(1, e);
				n1 = n;
			}
		}
		else
			if(n >= 0)
				cout << "请输入<" << n1 << "的次数:" << endl;
	}
}

template<class T>
void Chain<T>::Add(Chain<T> &A, Chain<T> &B)//两个多项式相加（系数相加）C=A+B
{
	
	ChainNode<T> *p;
	ChainNode<T> *q;
	p = A.first->link;
	q = B.first->link;
	ElemType e;
	int i = 1;
	while(p && q){
		if(p->data.exp < q->data.exp){
			Insert(i, p->data);
			p = p->link;
			i++;
		}else if(p->data.exp > q->data.exp){
			Insert(i, q->data);
			q = q->link;
			i++;
		}else{
			if(p->data.coef + q->data.coef != 0){
				e.coef = p->data.coef + q->data.coef;
				e.exp = p->data.exp;
				Insert(i, e);
				i++;
			}
			p = p->link;
			q = q->link;
		}
	}
	while(p){
		Insert(i, p->data);
		p = p->link;
		i++;
	}
	while(q){
		Insert(i, q->data);
		q = q->link;
		i++;
	}	
}

template<class T>
void Chain<T>::Sub(Chain<T> &A, Chain<T> &B)//两个多项式相减（系数相减）C=A-B
{
	
	ChainNode<T> *p;
	ChainNode<T> *q;
	p = A.first->link;
	q = B.first->link;
	ElemType e;
	int i = 1;
	while(p && q){
		if(p->data.exp < q->data.exp){
			Insert(i, p->data);
			p = p->link;
			i++;
		}else if(p->data.exp > q->data.exp){
			e.coef = -q->data.coef;
			e.exp = q->data.exp;
			Insert(i, e);
			q = q->link;
			i++;
		}else{
			if(p->data.coef - q->data.coef != 0){
				e.coef = p->data.coef - q->data.coef;
				e.exp = p->data.exp;
				Insert(i, e);
				i++;
			}
			p = p->link;
			q = q->link;
		}
	}
	while(p){
		Insert(i, p->data);
		p = p->link;
		i++;
	}
	while(q){
		e.coef = -q->data.coef;
		e.exp = q->data.exp;
		Insert(i, e);
		q = q->link;
		i++;
	}	
}

template<class T>
void Chain<T>::Multi(Chain<T> &A, Chain<T> &B)//两个多项式相乘 C=A*B
{
	ChainNode<T> *p;
	ChainNode<T> *q;
	ChainNode<T> *r;
	ElemType e;
	int n = 0;
	p = A.first->link;
	while(p){
		r = p;
		p = p->link;
	}
	n = r->data.exp;
	q = B.first->link;
	while(q){
		r = q;
		q = q->link;
	}
	n += r->data.exp;
	int a, j = 1;
	for(int i = 0; i <= n; i++){
		a = 0;
		p = A.first->link;
		while(p){
			q = B.first->link;
			while(q  && (p->data.exp + q->data.exp <= i)){
				if(p->data.exp + q->data.exp == i)
					a += p->data.coef * q->data.coef;
				q = q->link;
			}
			p = p->link;
		}
		if(a != 0){
			e.coef = a;
			e.exp = i;
			Insert(j, e);
			j++;
		}
	}
}

int main()
{
	Chain<ElemType> A, B, C1, C2, C3;
	A.inputPolynomial();
	cout << "第一个多项式是：" << endl << A;
	B.inputPolynomial();
	cout << "第二个多项式是：" << endl << B;
	C1.Add(A, B);
	cout << "两个多项式的和是：" << endl << C1;
	C2.Sub(A, B);
	cout << "两个多项式的差是：" << endl << C2;
    C3.Multi(A, B);
	cout << "两个多项式的乘积是：" << endl << C3;

 //按实际情况给出
}