#include<iostream>
#include<stdlib.h>
#include<iomanip>
#include<string>
using namespace std;

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

template<class ElemType>
class SeqList{
	private:
		ElemType *elem;   //顺序表存储数组，存放实际的数据结点
		int length;     //顺序表中的结点个数，亦称表的长度
		int MaxSize;   //顺序表的最大可能长度
	public:
		SeqList(int InitSize); //构造函数
		SeqList(SeqList &A); //复制构造函数
		~SeqList();        //析构函数
		void Clear();      //清空顺序表
		bool IsEmpty()  {return(length==0);}//表为空返回TRUE，否则返回FALSE
		bool IsFull()  {return(length==MaxSize);}//表为满返回TRUE，否则返回FALSE
		int Length() ;  //表的长度
		ElemType Get(int i) ;  //返回第i个结点的值
		int Next(int i) ; //若第i个结点的直接后继结点存在，返回其下标，否则返回0
		int Prior(int i) ;//若第i个结点的直接前驱结点存在，返回其下标，否则返回0
		int Find(ElemType e); //返回值等于e的结点的序号，无则返回0
		bool Insert(int i, ElemType e);//在第i个位置上插入新的结点(值为e)，
		             //并使原来的第i个结点至最后一个结点的序号依次加1。插入成功返回1，否则为false
		bool Delete(int i, ElemType &e); //若第i个结点存在，删除并将其值放人e，
		             //若i非法，则删除失败，返回false。
		void inputPolynomial(void);
		void Output(ostream& out) ;
};

template<class ElemType>
SeqList<ElemType>::SeqList(int InitSize){    //构造函数
	if(InitSize >0){
		elem = new ElemType[InitSize];  //申请连续空间，返回空间首地址
		Exception(!elem, "there is no space in memory"); //若申请空间失败，则程序中断
		length = 0;
		MaxSize = InitSize - 1;
	}
}

template<class ElemType>
SeqList<ElemType>::SeqList(SeqList &A){    //复制构造函数
	delete []elem;
	elem = new ElemType[A.MaxSize + 1];  //申请连续空间，返回空间首地址
	Exception(!elem, "there is no space in memory"); //若申请空间失败，则程序中断
	for(int i = 1; i <= A.length; i++)
		elem[i] = A.elem[i];
	length = A.length;
	MaxSize = A.MaxSize;
	
}

template<class ElemType>
SeqList<ElemType>::~SeqList(){    //析构函数
	delete []elem;   //释放占用的连续空间
}

template<class ElemType>
void SeqList<ElemType>::Clear(){   //清空顺序表
	length = 0;  //声明顺序表List中结点个数为零
}

template<class ElemType>
int SeqList<ElemType>::Length()  {  //返回表的长度
	return length;
}

template<class ElemType>
ElemType SeqList<ElemType>::Get(int i)  {  //读出第i个结点的值并返回
	Exception((i<1)||(i>length), "Out of bounds access."); //越界、非法
	return elem[i];
}

template<class ElemType>
int SeqList<ElemType>::Next(int i)  {  //若第i个结点的直接后继结点存在，返回其下标
	Exception((i<1)||(i>length-1), "Out of bounds access."); 
	return i+1;   //返回直接后继结点的下标
}

template<class ElemType>
int SeqList<ElemType>::Prior(int i)  {  //若第i个结点的直接前驱结点存在，返回其下标
	Exception((i<=1)||(i>length), "Out of bounds access."); //无直接前驱结点，错
	return i-1;   //返回直接前驱结点的下标
}

template<class ElemType>
int SeqList<ElemType>::Find(ElemType e){
	   //按照下标从大到小顺序查找值为e的数组结点的下标并将其返回。
	elem[0] = e;   //elem[0]做哨兵用，保证即使查找失败，也可以在哨兵位上能找到值e。
	int i = length;  //初始位置为尾结点所在下标
	while(elem[i] != e) i--; //不等时继续向前比较，找到返回结点下标，否则返回0
	return i;
}

template<class ElemType>
bool SeqList<ElemType>::Insert(int i,  ElemType e){
	     //在位置i上插入一个值为e的结点，原来的第i个结点变为第i+1个结点，
	     //其余后继结点序号同样加1，插入成功返回true。
	Exception((i<1)||(i>length+1), "i is not correct.");  //插入位置i不合法
	Exception(MaxSize == length, "no space for new item.");  //存储空间已经满了，无法插入
	     //从尾结点起到第i个结点逐个向后移动一个位置
	for(int j = length; j >= i; j--) 
		elem[j+1] = elem[j];
	elem[i] = e;   //将要插入的结点值放人第i个结点的位置
	length++;      //顺序表结点个数加1
	return true;      //插入成功返回true
}

template<class ElemType>
bool SeqList<ElemType>::Delete(int i, ElemType &e){
	     //若第i个结点存在，删除并将其值放人e，若i非法，删除失败
	Exception((i<1)||(i>length), "i is not correct."); 
	e = elem[i];   //将第i个结点值首先读出，用于返回
	for(int j = i; j < length; j++) elem[j] = elem[j + 1]; //第i+1个结点到尾结点逐个前移
	length--;      //顺序表长度减1
	return true;      //删除成功返回true
}

template<class ElemType>
void SeqList<ElemType>::Output(ostream& out) 
{
	if(length <= 0){
		out << "The polynomial is empty. " << endl;
		return;
	}
	else
		for(int i =1; i <= length ; i++){
			if( elem[i] != 0){
				if( i == 1)
					out << elem[i];
				else if ( i == 2){
				    if(elem[i] > 0)
						out << '+';
					out << elem[i] << 'x';
				}
			    else {
				    if(elem[i] > 0)
						out << '+';
				    cout << elem[i] << "x^" << i - 1;
				}
			}
		}
		out << endl;
    return;
}

template<class ElemType>
void SeqList<ElemType>::inputPolynomial(void)
{
	int n;
	ElemType m;
	cout << "Enter the degree of the Polynomial: ";
	cin >> n;
	for(int i = 1; i <= n + 1; i++){
		cout << "Enter the coef. of a(" << i - 1 << "):";
		cin >> m;
		Insert(i, m);
	}
}

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

template<class T>  
void Add(SeqList<T> &C, SeqList<T> &A, SeqList<T> &B) 
{
	int  i=1,k=1;
    while((i<=A.Length()) && (i<=B.Length()))
		C.Insert(k++,A.Get(i) + B.Get(i++));  
	while(i<= A.Length())
		C.Insert(k++,A.Get(i++));
    while(i<= B.Length())
        C.Insert(k++,B.Get(i++));
}

template<class T>  
void Sub(SeqList<T> &C, SeqList<T> &A, SeqList<T> &B) 
{
	int  i=1,k=1;
    while((i<=A.Length()) && (i<=B.Length()))
		C.Insert(k++,A.Get(i) - B.Get(i++));  
	while(i<= A.Length())
		C.Insert(k++,A.Get(i++));
    while(i<= B.Length())
        C.Insert(k++,-B.Get(i++));
}

template<class T>  
void Multi(SeqList<T> &C, SeqList<T> &A, SeqList<T> &B)//两个多项式相乘C=A*B
{
	int a;
	for(int i = 0; i <= A.Length() + B.Length() - 2; i++){
		a = 0;
		for(int j = 0; j <= i; j++)
			if(j < A.Length() && i-j < B.Length() )
			a += A.Get(j + 1) * B.Get(i - j + 1); 
		C.Insert(i + 1, a);
	}

}

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

 //按实际情况给出
}