//函數結果狀態代碼
#include <stdlib.h>
#include <stdio.h>
#include <iostream.h>
#define TRUE 1
#define FALSE 0
#define OK 1 
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;

typedef struct PNode
{
	int coef;    //系數                       
	int exp;     //指數                    
	struct PNode *next;               
}PNode,*LinkPN;

void AddPolyn(LinkPN pa,LinkPN pb,LinkPN &pc)      //實現兩個多項式相加
{
	PNode *qa,*qb,*qc,*q;
	qa=pa->next;
	qb=pb->next;
	qc=pc;
	while(qa&&qb)
	{
			if(qa->exp>qb->exp)
		{
			q=(LinkPN)malloc(sizeof(PNode));
            q->coef=qb->coef;
			q->exp=qb->exp;
			qb=qb->next;
			qc->next=q;
			q->next=NULL;
			qc=qc->next;
		}
		else if(qa->exp==qb->exp)
		{
            q=(LinkPN)malloc(sizeof(PNode));
			q->coef=qa->coef+qb->coef;
			q->exp=qa->exp;
			qa=qa->next;
			qb=qb->next;
			qc->next=q;
			q->next=NULL;
            qc=qc->next;
		}
		else
		{ 
			q=(LinkPN)malloc(sizeof(PNode));
            q->coef=qa->coef;
			q->exp=qa->exp;
			qa=qa->next;
			qc->next=q;
			q->next=NULL;
			qc=qc->next;
		}
	}
    while(qa)
	{
		q=(LinkPN)malloc(sizeof(PNode));
		q->coef=qa->coef;
		q->exp=qa->exp;
		qc->next=q;
		q->next=NULL;
		qc=qc->next;
		qa=qa->next;
	}

	while(qb)
	{
		q=(LinkPN)malloc(sizeof(PNode));
		q->coef=qb->coef;
		q->exp=qb->exp;
		qc->next=q;
		q->next=NULL;
		qc=qc->next;
		qb=qb->next;
	}

}
	
void SubtractPolyn(LinkPN &pa,LinkPN &pb,LinkPN &pc)        //實現兩個多項式相減
{
	PNode *qa,*qb,*qc,*q;
	qa=pa->next;
	qb=pb->next;
	qc=pc;
	while(qa&&qb)
	{
		if(qa->exp>qb->exp)
		{
			q=(LinkPN)malloc(sizeof(PNode));
            q->coef=0-qb->coef;
			q->exp=qb->exp;
			qb=qb->next;
			qc->next=q;
			q->next=NULL;
			qc=qc->next;
		}
		else if(qa->exp==qb->exp)
		{
            q=(LinkPN)malloc(sizeof(PNode));
			q->coef=qa->coef-qb->coef;
			q->exp=qa->exp;
			qa=qa->next;
			qb=qb->next;
			qc->next=q;
			q->next=NULL;
            qc=qc->next;
		}
		else
		{
			q=(LinkPN)malloc(sizeof(PNode));
            q->coef=qa->coef;
			q->exp=qa->exp;
			qa=qa->next;
			qc->next=q;
			q->next=NULL;
			qc=qc->next;
		}
	}
    while(qa)
	{
		q=(LinkPN)malloc(sizeof(PNode));
		q->coef=qa->coef;
		q->exp=qa->exp;
		qc->next=q;
		q->next=NULL;
		qc=qc->next;
		qa=qa->next;
	}

	while(qb)
	{
		q=(LinkPN)malloc(sizeof(PNode));
		q->coef=0-qb->coef;
		q->exp=qb->exp;
		qc->next=q;
		q->next=NULL;
		qc=qc->next;
		qb=qb->next;
	}

}

void main()
{
	LinkPN pa,pb,pc1,pc2;                   //pa用來存儲第一個多項式，pb存儲第二個多項式，pc1、pc2存儲兩式之和和差
	PNode *qa1,*qb1,*qa2,*qb2,*qc;          //qa1、qa2分別指向pa、pb中的元素，qb1、qb2存儲輸入元素，qc用于和和差的輸出
	int i,j;
	pa=(LinkPN)malloc(sizeof(PNode));
	pb=(LinkPN)malloc(sizeof(PNode));
	pc1=(LinkPN)malloc(sizeof(PNode));
	pc2=(LinkPN)malloc(sizeof(PNode));
	if(!pa||!pb||!pc1||!pc2)
		exit(OVERFLOW);
	qa1=pa;
	qb1=pb;
	pa->next=NULL;
	pb->next=NULL;
	cout<<"請輸入第一個多項式的項數：";
	cin>>i;
	cout<<endl;
	cout<<"請按提示輸入第一個多項式的系數項和指數項："<<endl;
	for(j=0;j<i;j++)
	{
		qa2=(LinkPN)malloc(sizeof(PNode));
		cout<<"第"<<j+1<<"項的系數：";
		cin>>qa2->coef;
		cout<<endl;
		cout<<"第"<<j+1<<"項的指數：";
		cin>>qa2->exp;
		cout<<endl;
		qa1=pa;
		if(pa->next==NULL)
		{
		  pa->next=qa2;
		  qa2->next=NULL;
		  qa1=qa1->next;
		}
         int flag=1;		
		while(qa1->next!=NULL&&flag)
		{
          if(qa1->next->exp>qa2->exp)
		  {
			  qa2->next=qa1->next;
			  qa1->next=qa2;
			  flag=0;
		  }
		  else 
			  if (qa1->next->exp==qa2->exp)
			  {
                 qa1->next->coef+=qa2->coef;
				 flag=0;
			  }
		  else
		      qa1=qa1->next;
		}
		if(flag)
		{
		  qa1->next=qa2;
		  qa2->next=NULL;
		}

	}

	cout<<"請輸入第二個多項式的項數：";
	cin>>i;
	cout<<endl;
	cout<<"請按提示輸入第二個多項式的系數項和指數項："<<endl;
	for(j=0;j<i;j++)
	{
		qb2=(LinkPN)malloc(sizeof(PNode));
		cout<<"第"<<j+1<<"項的系數：";
		cin>>qb2->coef;
		cout<<endl;
		cout<<"第"<<j+1<<"項的指數：";
		cin>>qb2->exp;
		cout<<endl;
        qb1=pb;
		if(pb->next==NULL)
		{
		  pb->next=qb2;
		  qb2->next=NULL;
		  qb1=qb1->next;
		}
	    int flag=1;
		while(qb1->next!=NULL&&flag)
		{
          if(qb1->next->exp>qb2->exp)
		  {
			  qb2->next=qb1->next;
			  qb1->next=qb2;
			  flag=0;
		  }
		  else 
			  if (qb1->next->exp==qb2->exp)
			  {
                 qb1->next->coef+=qb2->coef;
				 flag=0;
			  }
		  else
		      qb1=qb1->next;
		}
		if(flag)
		{
		  qb1->next=qb2;
		  qb2->next=NULL;
		}
	}

	cout<<"下面將輸出兩個多項式的和："<<endl;
	AddPolyn(pa,pb,pc1);
	qc=pc1->next;
	j=1;
	while(qc)
	{
		cout<<"第"<<j<<"項的系數："<<qc->coef<<endl;
		cout<<"第"<<j<<"項的指數："<<qc->exp<<endl<<endl;
		j++;
		qc=qc->next;
	}

	cout<<"下面將輸出兩個多項式的差："<<endl;
	SubtractPolyn(pa,pb,pc2);
	qc=pc2->next;
	j=1;
	while(qc)
	{
		cout<<"第"<<j<<"項的系數："<<qc->coef<<endl;
		cout<<"第"<<j<<"項的指數："<<qc->exp<<endl<<endl;
		j++;
		qc=qc->next;
	}
}

/*程序結果
請輸入第一個多項式的項數：4

請按提示輸入第一個多項式的系數項和指數項：
第1項的系數：3

第1項的指數：2

第2項的系數：2

第2項的指數：0

第3項的系數：4

第3項的指數：3

第4項的系數：1

第4項的指數：1

請輸入第二個多項式的項數：5

請按提示輸入第二個多項式的系數項和指數項：
第1項的系數：-5

第1項的指數：2

第2項的系數：-2

第2項的指數：4

第3項的系數：3

第3項的指數：0

第4項的系數：6

第4項的指數：3

第5項的系數：2

第5項的指數：1

下面將輸出兩個多項式的和：
第1項的系數：5
第1項的指數：0

第2項的系數：3
第2項的指數：1

第3項的系數：-2
第3項的指數：2

第4項的系數：10
第4項的指數：3

第5項的系數：-2
第5項的指數：4

下面將輸出兩個多項式的差：
第1項的系數：-1
第1項的指數：0

第2項的系數：-1
第2項的指數：1

第3項的系數：8
第3項的指數：2

第4項的系數：-2
第4項的指數：3

第5項的系數：2
第5項的指數：4

Press any key to continue*/