#include<iostream.h>
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
                      //結點結構
typedef struct LNode
{
	double coef;                                      //系數
	int exp;                                         //指數
	struct LNode *next;
}LNode,*link;

typedef struct
{
	link head,tail;
	int len;
}linklist;
                    //聲明函數原型
linklist *InitL();
linklist *INITL(linklist *L1,linklist *L2);
linklist *fun(linklist *T);
linklist *xyz(linklist *T);
linklist *mul(linklist *L1,linklist *L2);
void outplay(linklist *PL);
                    //主函數
void main()
{
	linklist *La,*Lb,*pa,*pb;
	char ch;
	                     //輸入第一個多項式
loop: cout<<"請輸入第一個多項式（輸入格式如：若要輸入\"3X^2-5X^3\"就請輸入\"3 2 -5 3 0\"）。"<<endl
		  <<"注意：不能把項系數輸為0，因為0表示輸入結束！"<<endl;
	La=InitL();
	                        //輸入第二個多項式
	cout<<"請輸入第二個多項式（輸入格式如：若要輸入\"3X^2-5X^3\"就請輸入\"3 2 -5 3 0\"）。"<<endl
		<<"注意：不能把項系數輸為0，因為0表示輸入結束！"<<endl;
	Lb=InitL();
	                      //開始進行加減運算
	cout<<"請輸入運算符，\"+\"\"-\"或\"*\""<<endl;
	cin>>ch;
	switch(ch)
	{
	case '+':                  //加法
		{
			pa=INITL(La,Lb);
			pb=fun(pa);
			outplay(pb);
			break;
		}
	case '-':                 //減法
		{
			Lb=xyz(Lb);
		    pa=INITL(La,Lb);
		    pb=fun(pa);
		    outplay(pb);
		    break;
		}
	case '*':                //乘法
		{
			pa=mul(La,Lb);
			pb=fun(pa);
			outplay(pb);
			break;
		}
	default :cout<<"無此運算符！";break;
	}
	                                         //若還要繼續進行兩個一元多項式的運算，繼續
	cout<<endl<<endl;
	cout<<"如果還要繼續兩個任意一元多項式的加、減或乘運算，請按enter鍵，否則請按其他鍵。"<<endl;
	if(ch=getchar()=='\n')
	    goto loop;
	system("pause");
}

linklist *InitL()                                //建立一個一元多項式的鏈表
{
	int i=0;
	link p1=0,p2=0;
	linklist *p;

	if(!(p=new linklist)) return 0;
	p->len=0;p->head=p->tail=0;

	if(!(p1=new LNode)) return 0;                 //建立表頭節點
	p1->coef=p1->exp=0;
	p1->next=0;

	p->head=p1;
	for (;;i++)                                  //輸入一元多項式
	{
		if(i%2==0)
		{
		    if(!(p2=new LNode)) return 0;
			cin>>p2->coef;
		    p2->next=0;
			if(p2->coef==0)
				break;
		}
		else
		{
			cin>>p2->exp;
		    p1->next=p2;
			p1=p2;
		}
	}
	p->tail=p1;
	p->len=i/2;
	return p;
}

linklist *INITL(linklist *L1,linklist *L2)            //把兩個一元多項式合并成一個
{
	L1->tail->next=L2->head->next;
	delete L2->head;
	L1->tail=L2->tail;
	L1->len+=L2->len;
	delete L2;
	return L1;
}
linklist *fun(linklist *T)              //對鏈表進行排序且進行相加運算
{
	int i,j;
	bool exchange;
	link p1,p2,p3;
	                                     //對一元多項式進行排序
	for(i=0;i<T->len-1;i++)
	{
		exchange=false;
		p1=T->head->next;p2=p1->next;p3=T->head;
		for(j=1;j<=T->len-i-1;j++)
		{
			if(p1->exp>p2->exp)
			{
				p3->next=p2;
				p3=p2;
				p1->next=p2->next;
				p2->next=p1;
				p2=p1->next;
				exchange=true;
			}
			else
			{
			    p3=p1;p1=p2;p2=p2->next;
			}
		}
		if(!exchange)
			break;
	}
	                                             //把排序后的一元多項式中批數相同的項進行合并
	p1=T->head->next;p2=p1->next;j=T->len;
	for(i=0;i<j-1;i++)
	{
		if(p1->exp==p2->exp)
		{
			p1->coef+=p2->coef;
			p1->next=p2->next;
			p3=p2;
			p2=p2->next;
			T->len--;
			delete p3;
		}
		else
		    p1=p1->next;p2=p1->next;
	}
	return T;
}

linklist *xyz(linklist *T)                                  //把第二個一元多項式的各項系數求反
{
	int i;
	link p=T->head->next;
	for(i=0;i<T->len;i++)
	{
		p->coef*=-1;
		p=p->next;
	}
	return T;
}

linklist *mul(linklist *L1,linklist *L2)                 //求出計算兩個一元多項式的乘積所構成的鏈表
{
	int i,j;
	linklist *LP;

	LP=new linklist;
	LP->len=L1->len*L2->len;LP->head=LP->tail=0;
	                                              //建立表頭結點
	LP->head=new LNode;
	LP->head->coef=LP->head->exp=0;LP->head->next=0;

	link pa=L1->head->next,pb,pc=LP->head,pd=0,p=0;
	delete L1->head;
	                                           //此循環進行多項式的乘法運算
	for (i=0;i<L1->len;i++)
	{
		pb=L2->head->next;
		for(j=0;j<L2->len;j++)
		{
			pd=new LNode;
			pd->coef=pd->exp=0;
			pd->coef=pa->coef*pb->coef;
			pd->exp=pa->exp+pb->exp;
			pd->next=0;
			pc->next=pd;
			pc=pd;
			pb=pb->next;
		}
		p=pa;
		pa=pa->next;
		delete p;
	}
	LP->tail=pc;
	p=L2->head;
	delete L1;
	                          //此循環對不用的鏈表所占的內存空間進行釋放
	for(i=0;i<=L2->len;i++)
	{
		pc=p;
		p=p->next;
		delete pc;
	}
	delete L2;
	return LP;
}

void outplay(linklist *PL)                            //輸出計算后的一元多項式
{
	cout<<"輸出計算后的一元多項式："<<endl;
	int i;
	link p=PL->head->next;
	for(i=0;i<PL->len;i++)
	{
		if(p->exp==0)
		    cout<<"+"<<p->coef;
		else if(p->coef==0)
		{
			p=p->next;
			continue;
		}
		else if(p->exp==1)
		{
			if(p->coef<0)
				cout<<p->coef<<"X";
			else
			    cout<<"+"<<p->coef<<"X";
		}
		else if(p->coef<0)
			cout<<p->coef<<"X^"<<"("<<p->exp<<")";
		else
			cout<<"+"<<p->coef<<"X^"<<"("<<p->exp<<")";
		p=p->next;
	}
}