多项式基本运算的实现

  • 时间:
  • 来源:互联网
  • 文章标签:

多项式的基本运算(链表实现)

程序具体说明:
使用链表实现两个多项式的基本操作。
初级要求:实现加法、减法和微分操作。
高级要求:实现乘法和除法操作。(除法操作中,当不能除尽时还要求列出余式。)

节点要包括:系数,指数,下一节点的指针
链表中,各结点按指数升幂或降幂排列,生成的结果多项式仍使用原多项式所占用的存储空间:两个同类项相加或相减时,如果系数不为0,则修改该结点的系数值,而指数值不变,将该结点链入结果多项式中,而另一项则释放空间;如果系数为0,则这两项占用的空间均需释放。不同类项则直接放入结果多项式中。

输入数据格式:
使用文件保存初始的多项式数据,文件名为inputfile.txt,文件中应含有表示两个多项式的初始数据。文件中的数据格式为:
(a,n)…(a,n)(0,0)
(a,n)…(a,n)(0,0)
AND/SUB/DIFF/MUL/DIV(#,#)
其中,a是系数,n是指数,两数之间使用逗号分隔,并用括号括起来。其后以(0,0)作为一个多项式输入的结束。以字符串AND表示加法操作,以字符串SUB表示减法操作,以字符串DIFF表示微分操作,以字符串MUL表示乘法操作,以字符串DIV表示除法操作,以(#,#)作为全部数据输入的结束标志。

输出数据格式:
输出结果也保存在文件中,文件名为outputfile.txt,文件中应含有结果多项式的值,以多项式的形式输出结果,例如如下所示的多项式:
2x3 –5x2 + x1 +9
在输出文件中表示为:2x3 –5x2 + x1 +9

测试示例一:
(5,100)(9,31)(-7,2)(1,1)(10,0)(0,0)
(-60,81)(-9,31)(5,2)(1,1)(0,0)
AND(#,#)
测试示例二:
(5,100)(9,31)(-7,2)(1,1)(10,0)(0,0)
(-60,81)(-9,31)(5,2)(1,1)(0,0)
SUB(#,#)
测试示例三:
(5,100)(9,31)(-7,2)(1,1)(10,0)(0,0)
(-60,81)(-9,31)(5,2)(1,1)(0,0)
MUL(#,#)

代码:

#include<iostream>
#include<fstream>
#include<string>
using namespace std;
class Node {
public:
	int xishu,zhishu;
	Node*next;
	int tag = 0;
};
class List {
	Node*head;
	int count = 0;
	Node*cur;
	int now_index = 0;
public:
	List() { head = new Node; head->next = NULL; cur = head; }
	void insert( Node *);
	void remove(int i);
	void traverse();
	Node* gethead() { return head; }
};
void List::traverse()
{

	Node*cur1 = head;
	while (cur1->next)
	{
		cout << cur1->next->xishu << ' ' << cur1->next->zhishu<<' ';
		cur1 = cur1->next;
	}
	cout << endl;
}
void List::insert(Node *n)
{
	Node*tmp = new Node;//插入时,新生成一个节点存入插入节点所有信息,防止插入节点导致链表断裂
	tmp->tag = n->tag;
	tmp->xishu = n->xishu;
	tmp->zhishu = n->zhishu;
	cur = head;
	while(cur->next)
	{
		cur = cur->next;
	}
	tmp->next = cur->next;
	cur->next = tmp;
	cur = tmp;
	count++;
}
void List::remove(int i)
{
	cur = head;
	now_index = 0;
	while (now_index < i - 1)
	{
		now_index++;
		cur = cur->next;
		now_index++;

	}
	cur->next = cur->next->next;
	count--;
}


//---新函数
void swap(int&a, int&b)
{
	int tmp = a;
	a = b;
	b = tmp;
}
void Sort(List &l1)//针对加法,减法,微分进行处理
{
	Node*n1 = l1.gethead();
	Node*n2 = n1->next;
	while (n2)//将系数为0的部分删除
	{

		if (n2->xishu == 0)
		{
			n2 = n2->next;
			Node*tmp = n1->next;
			n1->next = n1->next->next;
			delete tmp;
		}
		else {
			n2 = n2->next;
			n1 = n1->next;
		}
	}
	n1 = l1.gethead();
	n2 = n1->next;
	while (n1&&n1->next)//按照指数进行排序
	{

		while (n2&&n2->next)
		{
			if (n1->next->zhishu < n2->next->zhishu)
			{
				swap(n1->next->xishu, n2->next->xishu);
				swap(n1->next->zhishu, n2->next->zhishu);
			}
			n2 = n2->next;
		}
		n1 = n1->next;
		n2 = n1->next;
	}
}
void Sort2(List&l1)//对乘除后的链表进行处理
{
	Node*n1 = l1.gethead();
	Node*n2 = n1->next;

	while (n1&&n1->next)//按照指数进行排序
	{

		while (n2&&n2->next)
		{
			if (n1->next->zhishu < n2->next->zhishu)
			{
				swap(n1->next->xishu, n2->next->xishu);
				swap(n1->next->zhishu, n2->next->zhishu);
			}
			if (n1->next->zhishu == n2->next->zhishu)//如果有指数相同的,则相加,并且将一项释放掉
			{
				n1->next->xishu += n2->next->xishu;
				Node*tmp = n2->next;
				n2->next = n2->next->next;
				delete tmp;
			}
			n2 = n2->next;
		}
		n1 = n1->next;
		n2 = n1->next;
	}

	n1 = l1.gethead();
	n2 = n1->next;
	while (n2)//将系数为0的部分删除
	{

		if (n2->xishu == 0)
		{
			n2 = n2->next;
			Node*tmp = n1->next;
			n1->next = n1->next->next;
			delete tmp;
		}
		else {
			n2 = n2->next;
			n1 = n1->next;
		}
	}


}
void div(List &l1, List &l2,List&l3)//l1 l2存放被除数和除数,l3存放商,l1也存放最后的余数
{
	Sort2(l1);//预先对l1 l2进行排序
	Sort2(l2);
	Node*n1 = l1.gethead();
	Node*n2 = l2.gethead();
	Node*n3;
	if (n1->next->zhishu < n2->next->zhishu)//如果被除数的指数小于除数,则商为0,l1自身为余数
	{
		n3 = new Node;
		n3->zhishu = 0;
		n3->xishu = 0;
		l3.insert(n3);
		return;
	}
	else//如果l1指数大于l2,则不断进行比较,直到小于
	{
		while (l1.gethead()->next&&l1.gethead()->next->zhishu >= l2.gethead()->next->zhishu)//当l1的指数大于l2,且l1中未被整除
		{
			n3 = new Node;
			int zhishu, xishu;
			zhishu = l1.gethead()->next->zhishu - l2.gethead()->next->zhishu;//求出商的指数和系数
			xishu = l1.gethead()->next->xishu / l2.gethead()->next->xishu;
			n3->zhishu = zhishu;
			n3->xishu = xishu;
			l3.insert(n3);
			delete n3;//释放内存

			n2 = l2.gethead();
			while (n2->next)//将l2中各项乘以当前算的商,放入l1中进行减法
			{
				Node*tmp = new Node;
				tmp->xishu = -n2->next->xishu * xishu;
				tmp->zhishu = n2->next->zhishu + zhishu;
				l1.insert(tmp);
				delete tmp;
				n2 = n2->next;

			}

			Sort2(l1);//对l1中进行去重排序
		}
	}
}
void add(List &l1, List &l2)//将结果全部存入l1中
{
	Node*n1 = l1.gethead();
	Node*n2 = l2.gethead();


	//将l2中的节点插入l1中
	while (n2&&n2->next)
	{
		l1.insert(n2->next);
		Node*tmp = n2->next;//释放内存
		n2->next = n2->next->next;
		delete tmp;
	}

	Sort2(l1);
}
void sub(List &l1, List &l2)
{
	Node*n1 = l1.gethead();
	Node*n2 = l2.gethead();


	//将l2中的节点插入l1中
	while (n2&&n2->next)
	{
		n2->next->xishu *=-1;//系数为负

		l1.insert(n2->next);
		Node*tmp = n2->next;
		n2->next = n2->next->next;
		delete tmp;
	}

	Sort2(l1);

}
void diff(List &l1)
{
	Node*n1 = l1.gethead();
	while (n1->next)
	{
		n1->next->xishu *= n1->next->zhishu;
		n1->next->zhishu--;
		n1 = n1->next;
	}
	Sort2(l1);
}
void mul(List &l1, List &l2)
{
	Node*n1 = l1.gethead();
	Node*n2 = l2.gethead();
	while (n1->next&&n1->next->tag==0)//将两个表达式相乘,生成的项放入l1的末尾,用tag来区分新生成的和旧的
	{

		while (n2->next)
		{
			Node*n3 = new Node;
			
			n3->tag = 1;
			n3->xishu = n1->next->xishu*n2->next->xishu;
			n3->zhishu = n1->next->zhishu + n2->next->zhishu;

			l1.insert(n3);
			delete n3;//释放内存
			n2 = n2->next;
		}
		n1 = n1->next;
		n2 = l2.gethead();
	}
	
	n2 = l2.gethead();
	while (n2->next)//所有结果全部保存l1中,则将l2中数据释放
	{

		Node*tmp=n2->next;
		n2->next = n2->next->next;
		delete tmp;

	}

	n1 = l1.gethead();
	while (n1->next&&n1->next->tag==0)//将l1前面自身的数据删掉,只留下结果
	{
			Node*tmp = n1->next;
			n1->next = n1->next->next;
			delete tmp;
	}

	Sort2(l1);

}
int main()
{
	List l1, l2,l3,l4;
	ifstream if1("inputfile.txt");
	ofstream of1("outputfile.txt");

	char*s1, *s2, *s3;
	s1 = new char[100];
	s2 = new char[100];
	s3 = new char[100];
	if1.getline(s1, 100);//将多项式以及命令读入三个数组中
	if1.getline(s2, 100);
	if1.getline(s3, 100);
	int i, j;
	for (i = 0; i < strlen(s1); i++)//将数组中的多项式放入链表中
	{
		int a1, a2;
		if (isdigit(s1[i])||s1[i]=='-')
		{
			string s_1;
			while (isdigit(s1[i])||s1[i]=='-')
			{
				s_1+=s1[i++];
			}
			 a1 = stoi(s_1);
		}
		if (s1[i] == ',')
		{
			i++;
			string s_2;
			while (isdigit(s1[i])||s1[i]=='-')
			{
				s_2 += s1[i++];
			}
			 a2 = stoi(s_2);
			 if (a1 == 0 && a2 == 0)
				 break;
			 Node*n1 = new Node;
			 n1->xishu = a1;
			 n1->zhishu = a2;
			 l1.insert(n1);

		}

	}
	for (i = 0; i < strlen(s2); i++)
	{
		int a1, a2;
		if (isdigit(s2[i]) || s2[i] == '-')
		{
			string s_1;
			while (isdigit(s2[i]) || s2[i] == '-')
			{
				s_1 += s2[i++];
			}
			a1 = stoi(s_1);
		}
		if (s2[i] == ',')
		{
			i++;
			string s_2;
			while (isdigit(s2[i]) || s2[i] == '-')
			{
				s_2 += s2[i++];
			}
			a2 = stoi(s_2);
			if (a1 == 0 && a2 == 0)
				break;
			Node*n1 = new Node;
			n1->xishu = a1;
			n1->zhishu = a2;
			l2.insert(n1);

		}

	}
	if (s3[0] == 'A')
	{
		 add(l1, l2);

	}
	if (s3[0] == 'S')
	{
		sub(l1, l2);

	}
	if (s3[0] == 'D'&&s3[1]=='I'&&s3[2]=='F')
	{
		 diff(l1);
		 diff(l2);

	}
	if(s3[0]=='M')
	{ 
		 mul(l1, l2);

	}
	if (s3[0] == 'D'&&s3[1] == 'I'&&s3[2] == 'V')
	{
		div(l1, l2, l3);

	}

	if (s3[0] == 'D'&&s3[1] == 'I'&&s3[2] == 'V')//如果进行除的运算
	{
		of1 << "商为:";
		Node*tmp = l3.gethead();
		while (tmp->next)
		{
			if (tmp->next->xishu > 0 && tmp != l3.gethead())
				of1 << '+';
			if (tmp->next->zhishu != 0)
				of1 << tmp->next->xishu << 'x' << tmp->next->zhishu;
			if (tmp->next->zhishu == 0)
				of1 << tmp->next->xishu;

			tmp = tmp->next;
		}
		of1 << endl << "余数为:";
		Node*n1 = new Node;
		n1 = l1.gethead();
		if (n1->next == NULL)//如果可以被整除
		{
			of1 << 0;
		}
		while (n1->next)
		{

			if (n1->next->xishu > 0 && n1 != l1.gethead())
				of1 << '+';
			if (n1->next->zhishu != 0)
				of1 << n1->next->xishu << 'x' << n1->next->zhishu;
			if (n1->next->zhishu == 0)
				of1 << n1->next->xishu;
			n1 = n1->next;
		}
		return 0;
	}
	Node*n1 = new Node;
	n1 = l1.gethead();
	if (s3[0] == 'D'&&s3[1] == 'I'&&s3[2] == 'F')
	{
		of1 << "第一个式子:";
	}
	while (n1->next)
	{

		if (n1->next->xishu > 0 && n1 != l1.gethead())
			of1 << '+';
		if(n1->next->zhishu!=0)
			of1 << n1->next->xishu << 'x' << n1->next->zhishu;
		if (n1->next->zhishu == 0)
			of1 << n1->next->xishu;
		n1 = n1->next;
	}
	if (s3[0] == 'D'&&s3[1] == 'I'&&s3[2] == 'F')//如果是微分的话,则将两个式子分别微分并存入文本
	{
		of1 << endl<<"第二个式子:";
		Node*n2 = new Node;
		n2 = l2.gethead();
		while (n2->next)
		{

			if (n2->next->xishu > 0 && n2 != l2.gethead())
				of1 << '+';
			if (n2->next->zhishu != 0)
				of1 << n2->next->xishu << 'x' << n2->next->zhishu;
			if (n2->next->zhishu == 0)
				of1 << n2->next->xishu;
			n2 = n2->next;
		}

	}
	
}

本文链接http://www.taodudu.cc/news/show-1781793.html