polynomial.cpp

数据结构经典算法的C语言实现 计算机专业数据结构课程实验

#include <iostream>

using namespace std;

struct polynode {
	float coef; //系数
	int exp;  //指数
	polynode *link; //指向下一项的指针
}; //结点型

typedef polynode* polypointer;

//建立一个新结点，其系数coef=c，指数exp=e，并将它链到d所指结点之后，然后返回这个新结点的指针
polypointer attach(float c, int e, polypointer d)
{
	polypointer x;
	x = new polynode;
	x -> coef = c;
	x -> exp = e;
	d -> link = x;
	return x;
}

//输入多项式
polypointer inpoly(void)
{
	polypointer x, d;
	char yn;
	int e, i;
	float a;

	x = new polynode;
	d = x;
	i = 1;
	yn = 'Y';  //初始化
	
	while ((yn == 'Y') || (yn == 'y')) {
		cout<<"请输入多项式第"<<i<<"项的系数：";
		cin>>a;
		cout<<"请输入多项式第"<<i<<"项的指数：";
		cin>>e;
		cout<<"此多项式还有其它项吗？(Y/N)";
		cin>>yn;
		d = attach(a, e, d);
		i++;
	}
	d->link = NULL;  //最后结点
	
	i = 1;  //将i复位
	d = x;
	x = x->link;
	delete d;

	return x;
}

//输出多项式
void outpoly(polypointer x)
{
	polypointer p;
	p = x;  //初始化

	if (p == NULL)
		cout<<"0\n";
	else {
		cout<<p->coef<<"X"<<p->exp;  //输出第一项
		p = p->link;
	}
	
	while (p != NULL) {
		if (p->coef > 0)
			cout<<" + "<<p->coef<<"X"<<p->exp;
		else if (p->coef < 0)
			cout<<" "<<p->coef<<"X"<<p->exp;
		p = p->link;
	}  //输出其它项
}

//比较某一项系数大小
char compare(float a, float b)
{
	if (a < b)
		return '<';
	else if (a > b)
		return '>';
	else
		return '=';
}

//多项式a和多项式b相加，返回结果多项式
polypointer polyadd(polypointer a, polypointer b)
{
	polypointer p, q, d, c;
	float x;  //也可以不用此变量
	p = a;
	q = b;
	c = new polynode;
	d = c;  //初始化

	while ((p != NULL) && (q != NULL))
		switch (compare(p->exp, q->exp)) {
			case '=':
				x = p->coef + q->coef;  //系数相加
				if (x != 0)
					d = attach(x, p->exp, d);  //将新结点链入
				p = p->link;
				q = q->link;  //前进一步
				break;
			case '>':
				d = attach(p->coef, p->exp, d);  //复制p所指结点并链入c中
				p = p->link;  //p前进
				break ;
			case '<':
				d = attach(q->coef, q->exp, d);  //复制q所指结点并链入c中
				q = q->link;  //q前进
				break;
		}  //switch and while

	while (p != NULL) {//复制a的剩余部分
		d = attach(p->coef, p->exp, d);
		p = p->link;
	}

	while (q != NULL) {//复制b的剩余部分
		d = attach(q->coef, q->exp, d);
		q = q->link;
	}

	d->link = NULL;  //最后结点
	p = c;
	c = c->link;
	delete p;  //删除临时用结点

	return c;
}

//多项式a和多项式b相减，返回结果多项式
polypointer polysub(polypointer a, polypointer b)
{
	polypointer p, q, d, c;
	float x;  //也可以不用此变量
	p = a;
	q = b;
	c = new polynode;
	d = c;  //初始化

	while ((p != NULL) && (q != NULL))
		switch (compare(p->exp, q->exp)) {
			case '=':
				x = p->coef - q->coef;  //系数相减
				if (x != 0)
					d = attach(x, p->exp, d);  //将新结点链入
				p = p->link;
				q = q->link;  //前进一步
				break;
			case '>':
				d = attach(p->coef, p->exp, d);  //复制p所指结点并链入c中
				p = p->link;  //p前进
				break ;
			case '<':
				d = attach(0 - q->coef, q->exp, d);  //复制q所指结点并链入c中
				q = q->link;  //q前进
				break;
		}  //switch and while

	while (p != NULL) {//复制a的剩余部分
		d = attach(p->coef, p->exp, d);
		p = p->link;
	}

	while (q != NULL) {//复制b的剩余部分与-1的积
		d = attach(0 - q->coef, q->exp, d);
		q = q->link;
	}

	d->link = NULL;  //最后结点
	p = c;
	c = c->link;
	delete p;  //删除临时用结点

	return c;
}

//多项式a和多项式b相乘，返回结果多项式
polypointer polymulti(polypointer a, polypointer b)
{
	polypointer p, q, d, c, temp;
	p = a;
	q = b;
	c = new polynode;
	d = c;
	temp = NULL;  //初始化

	while (q != NULL) {
		while (p != NULL) {
			d = attach((p->coef * q->coef), (p->exp + q->exp), d);
			p = p->link;  //p前进一步
		}
		d->link = NULL;  //最后结点

		temp = polyadd(temp, c->link);
		d = c;
		p = a;  //被乘数复位
		q = q->link;  //q前进一步
	}

	return temp;
}

//多项式a和多项式b相除，返回结果多项式
polypointer polydiv(polypointer &p, polypointer q)
{
	polypointer d, c;
	c = new polynode;
	c->link = NULL;	
	d = c;  //初始化
	
	while (p != NULL && p->exp >= q->exp) {
		d = attach((p->coef / q->coef), (p->exp - q->exp), d);
		d->link = NULL;
		p = polysub(p, polymulti(d, q));	//被除数与商和余数的积作差	
	}
	d->link  = NULL;
	
	d = c;
	c = c->link;
	delete d;

	return c;
}

void main()
{
	polypointer a, b, c, d, e, f;
	
	a = b = c = e = f = NULL;
	char yn = 'y';

	while ((yn == 'y') || (yn == 'Y')) {
		cout<<"欢迎使用本程序，请按降幂顺序输入多项式各项！\n";
		cout<<"请输入第一个多项式：\n";
		a = inpoly();
		cout<<"请输入第二个多项式：\n";
		b = inpoly();

		c = polyadd(a, b);
		d = polysub(a, b);
		e = polymulti(a, b);
	
		cout<<'\n'<<"第一个多项式为：\n";
		outpoly(a);
		cout<<'\n'<<"第二个多项式为：\n";
		outpoly(b);
	
		cout<<'\n'<<"两者之和为：\n";
		outpoly(c);
		cout<<'\n'<<"两者之差为：\n";
		outpoly(d);
		cout<<'\n'<<"两者之积为：\n";
		outpoly(e);
	
		if (b->coef == 0)
			cout<<"\n除数为零！";
		else {
			f = polydiv(a, b);  //执行除法时原多项式被破坏，因此先输出原多项式再做除法

			cout<<'\n'<<"两者之商为：\n";
			outpoly(f);
			cout<<'\n'<<"余数为：\n";  //a中保留的是余数
			outpoly(a);
			cout<<'\n';
		}

		cout<<"是否继续？(Y/N)";
		cin>>yn;
	}	
}