qu.cpp

就是两个多项式的欧几里得算法

#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);


}