#include "iostream.h"
struct milt//一個鏈表的結構體，*注意：每個鏈表的頭都不存放數字，只是一個頭指針。
{
	float xi;
	int zhi;
	milt *next;
};
milt insert(milt a,milt b)//插入一個單元b，并在插入時實現指數從高到低的排列
{
	if(b.xi==0)
		return a;
	milt *p;
	milt *q;
	p=&a;
	q=new milt;
	q->xi=b.xi;
	q->zhi=b.zhi;
	q->next=NULL;
	if(a.next==NULL)
	{
		q->next=NULL;
		a.next=q;
	}
	else
	{
		p=a.next;
			while(p!=NULL)
			{
				if(p->zhi==q->zhi)//若輸入數的指數在原來的鏈表里存在時，只要把系數想加就可以了。
				{
					p->xi=p->xi+q->xi;
					break;
				}
				if(p->zhi<q->zhi)
				{
					q->next=p->next;
					p->next=q;
					milt k;
					k.xi=p->xi;
					k.zhi=p->zhi;
					p->xi=q->xi;
					p->zhi=q->zhi;
					q->xi=k.xi;
					q->zhi=k.zhi;
					break;					
				}
				if(p->next==NULL&&p->zhi>q->zhi)
				{
					q->next=NULL;
					p->next=q;
					break;
				}
				p=p->next;
				if(p==NULL)
				{
					q->next=NULL;
					
				}
			}
	}
	return a;
}
void view(milt a)//按規定的形式輸出多項式。
{
	milt *p;
	p=a.next;
	if(p!=NULL)
	{
		cout<<p->xi<<"X"<<p->zhi;
		p=p->next;
	}
	while(p!=NULL)
	{
		if(p->xi>0)
		{
			cout<<"+";
		}
		if(p->zhi==0)
		{
			cout<<p->xi;
		}
		else
		cout<<p->xi<<"X"<<p->zhi;
		p=p->next;
	}
	cout<<endl;
}
milt operator -(milt a,milt b)//定義了兩個多項式想加的算法。
{
	milt *t,*p;
	t=a.next;
	p=b.next;
	milt r,d;
	r.next=NULL;
	while(t!=NULL)//此處其實就是把兩個多項式連起來的算法，讓第二個多項式的各項系數取反即可。
	{
		while(p!=NULL)
		{
			if(t->zhi>p->zhi)
			{
				d=*t;
				d.next=NULL;
				r=insert(r,d);
				break;
			}
			if(t->zhi==p->zhi)
			{
				d.xi=t->xi-p->xi;
				d.zhi=p->zhi;
				d.next=NULL;
				p=p->next;
				r=insert(r,d);
				break;
			}
			if(t->zhi<p->zhi)
			{
				d=*p;
				d.xi=-(p->xi);
				d.next=NULL;
				r=insert(r,d);
				p=p->next;
			}
		}
		t=t->next;
		
	
	}
	while(p!=NULL)
	{
		d=*p;
		d.xi=-(p->xi);
		r=insert(r,d);
		p=p->next;
	}
	return r;
}
milt operator *(milt a,milt b)//定義一個多項式乘以一個milt單無的算法。即每個單元的系數相乘，指數相加。
{
	milt *t,k,m;
	t=a.next;
	k.next=NULL;
	while(t!=NULL)
	{
		m.xi=b.xi*t->xi;
		m.zhi=b.zhi+t->zhi;
		k=insert(k,m);
		t=t->next;
	}
	return k;
}
milt operator %(milt a,milt b)//取余的算法。要實現這個功能，要確保*，- 無誤。
{//只要把這個函數中的temp存貯并返回就是一個取商的算法。。
	milt *t,*p,temp,k;
	t=a.next;
	p=b.next;
	k.next=NULL;
	while((t->zhi)>=(p->zhi)&&t!=NULL&&p!=NULL)
	{
		temp.xi=(t->xi)/(p->xi);//消去最高式時要乘的系數
		temp.zhi=(t->zhi)-(p->zhi);//消去最高式時要乘的指數。
		temp.next=NULL;//可要可不要，但為了不出錯，，，最好給每個人指針都初始化一下。
		k=b*temp;
		a=a-k;
		t=a.next;
	}
	return a;
}
milt shouyi(milt a)//把一個多項式轉化成首一多項式。
{
	milt*p;
	p=a.next;
	milt m;
	m.xi=1/p->xi;//這跟上面的取余中消去最高項時的思想是一樣的。
	m.zhi=0;
	a=a*m;
	return a;
}
void main()
{
cout<<"**********************兩個多項式求最大公約多項式的程序**********"<<endl;
cout<<"												作者：陶發輝"<<endl;
int n1,n2;
milt a,b,c;
a.next=b.next=c.next=NULL;
cout<<"請輸入第一個多項式有幾項"<<endl;
cin>>n1;
cout<<"請輸入每一個多項項的系數和指數，格式為 :系數+空格+指數(若為整數，則看作是指數為一的多項式輸入)"<<endl;
for(int i=0;i<n1;i++)
{
	cin>>b.xi>>b.zhi;
	a=insert(a,b);
}
view(a);
cout<<"請輸入第二個多項式有幾項"<<endl;
cin>>n2;
cout<<"請輸入每一個多項項的系數和指數，格式為 :系數+空格+指數(若為整數，則看作是指數為一的多項式輸入)"<<endl;
for(i=0;i<n2;i++)
{
cin>>b.xi>>b.zhi;
c=insert(c,b);
}
view(c);
while(c.next->zhi>0)
{
	b=a%c;
	a=c;
	c=b;
}
a=shouyi(a);
cout<<"最大公約多項式為(為首一多項式)"<<endl;
view (a);


}