多项式的四则运算数据结构

1、数据结构07082018用链表实现多项式的四则运算数据结构第二次上机作业班级07082姓名丁敏学号07082018上机时间2011年3月31日报告时间：2011年4月5日实验目的：熟练使用指针，熟悉链表及其操作；利用链表解决实际问题要求：能够实现任意项有理多项式的加、减、乘、除、求模以及事运算多项式的除法注意除不尽的处理测试用例尽可能多，且说明用例的必要性用例必须包含一个自己系数为自己的学号摘要：多项式的四则运算问题是个很有趣的问题，它类似于有理数的四则运算，但又不仅仅于此.本篇课程论文重点研究了数据结构中多项式的四则运算问题。本论文的程序是通过MicrosoftVisualStudio201

2、0编译，来解决多项式的加、减、乘、除四则运算问题，从而达到了解数据结构的实用性及程序语言对于数学问题研究的重要性的目的。07082018数据结构正文：0需求分析:0.1问题描述编写程序来实现多项式的四则运算。0.2基本要求输入多项式的系数与指数，输入值为float型，输出值为float型;能够完成多项式之间的四种计算方式(+、-、*、/)。0.3函数说明typedefstructPolyNode:结构体变量，定义int型指数和float系数；PolyListCreatePolyList():创建多项式列表，返回头指针；DisplayPolyList(PolyListPoly):显示多项式；De

3、stroyPolyList(PolyListL):释放链表所用存储空间；MergePoly(PolyListPoly):将多项式合并同类项；SortPoly(PolyListPoly):将多项式按升序排列；PolyListPolyAdd(PolyListPolyA,PolyListPolyB):多项式相加，返回和多项式链表头指针；PolyListPolySub(PolyListpolyA,PolyListpolyB):多项式相减，返回差多项式链表头指针；PolyListPolyMutiply(PolyListPolyA,PolyListPolyB):多项式相乘，结果由Polyc返回；PolyL

4、istPolyDivide(PolyListPolyA,PolyListPolyB):多项式相除，商和余数用系数为0的结点分开。1程序执行结果及分析：1.1执行结果(1)* *多项式的创建*请输入多项式的第1项的系数和指数(用逗号分开)：3,2请输入多项式的第2项的系数和指数：2,0请输入多项式的第3项的系数和指数：0,0输入的多项式A：3.000000*xA2+2.000000*xA0请输入多项式的第1项的系数和指数(用逗号分开)：2,2请输入多项式的第2项的系数和指数：3,1请输入多项式的第3项的系数和指数：0,0输入的多项式B：2.000000*xA2+3.000000*xA1合并排序后

5、的多项式A:3.000000*xA2+2.000000*xA0合并排序后的多项式B:2.000000*xA2+3.000000*xA1* *多项式的四则运算*A+B:5.000000*xA2+3.000000*xA1+2.000000*xA0A-B:1.000000*xA2+-3.000000*xA1+2.000000*xA0A*B:6.000000*xA4+9.000000*xA3+4.000000*xA2+6.000000*xA1A/B:1.500000*xA0.-4.500000*xA1+2.000000*xA0请按任意键继续.* *多项式的创建*请输入多项式的第1项的系数和指数（用逗号

6、分开）：1,1请输入多项式的第2项的系数和指数：0,0输入的多项式A:1.000000*xA1请输入多项式的第1项的系数和指数（用逗号分开）：0,0输入的多项式B:0合并排序后的多项式A:1.000000*xA1合并排序后的多项式B:0* *多项式的四则运算*A+B:1.000000*xA1A-B:1.000000*xA1A*B:0Error:除项为空！A/B:请按任意键继续.* *多项式的创建*请输入多项式的第1项的系数和指数（用逗号分开）：2,3请输入多项式的第2项的系数和指数：2/3,1（出现乱码）1.2测试用例(1):，二二-二二C=A+B=30(x+y)C=AB=20(x+y)C=A

7、B=125(x2+2xy+y2)C=A-s-B=5x+Sy(2) A=xB=/C=A+B=x3+xzC=A-B=x3xzC=AB=xlcC=A-rB=x&(3) -.：二：=：-：，.C=A+B=x2+ya+2xy+x+yC=A-B=+ya+2xy-x-yC=AB=+3x2y+3xy2+y3C=A-rB=x+y(4)输入：A=3x+%B=x+6y输出：-C=A-B=2x-5yC=AB=3x2+19xy+6y21.3结果分析通过三次的运行，一二两次成功，但第三次乱码。从第三次的运行来看由于输入与所要求的不一样二出现乱码，故非程序的问题，所以本程序符合多项式的运算要求，是正确的。2程序的评

8、价:程序符合需求，能够有效地运行多项式之间的运算；程序结构合理，具有层次性，易读；程序运行界面友好，且不与别的程序相冲突由于程序会出乱码现象，所以还有一定的缺陷；3总结：本文的重点是对多项式的各种关系通过编程进行处理。笔者通过通过MicrosoftVisualStudio2010编译完成了所要求的内容。值得指出的是：本程序层次性较强，易读，且具有较高的精度，如进一步改善，将会有很强的适用性。笔者当然也碰到许多的问题，比如算法设计上仍有很大不足，流程图画的不是很熟练，全局变量不会定义，main函数的顺序位置等。这些问题都可以通过实践来解决，总之，一句话熟能生巧。附录#include<std

9、io.h>#include<stdlib.h>#include<math.h>结点定义typedefstructPolyNodeintexp;指数floatcoef;系数PolyNode*next;PolyNode,*PolyList;PolyListCreatePolyList();/创建多项式链表，返回头指针voidDisplayPolyList(PolyListPoly);/显示多项式voidDestroyPolyList(PolyListL);/释放链表所用存储空间voidMergePoly(PolyListPoly);/将多项式和并同类项voidSort

10、Poly(PolyListPoly);/将多项式按升序排列PolyListPolyAdd(PolyListPolyA,PolyListPolyB);/多项式相加，返回和多项式链表头指针PolyListPolySub(PolyListpolyA,PolyListpolyB);/多项式相减，返回差多项式链表头指针PolyListPolyMutiply(PolyListPolyA,PolyListPolyB);/多项式相乘，结果由PolyC返回PolyListPolyDivide(PolyListPolyA,PolyListPolyB);/多项式相除，结果存到PolyC中，商和余数用系数为0的结点分

11、开PolyListCreatePolyList()PolyNode*s,*rear,*head;inte;/指数floatc;/系数intn=1;计数器head=(PolyNode*)malloc(sizeof(PolyNode);rear=head;输入多项式的系数和指数，若输入系数为0退出printf("请输入多项式的第%d项的系数和指数(用逗号分开)："，n+);scanf("%f,%d",&c,&e);while(fabs(c)>1e-6)s=(PolyNode*)malloc(sizeof(PolyNode);s->

12、exp=e;s->coef=c;rear->next=s;rear=s;printf("请输入多项式的第%d项的系数和指数：",n+);scanf("%f,%d",&c,&e);)rear->next=NULL;returnhead;)计算两个多项式(可不按顺序排列)，结果存到链表PolyC中，并返回PolyListPolyAdd(PolyListPolyA,PolyListPolyB)PolyListPolyC;SortPoly(PolyA);SortPoly(PolyB);floatsum=0;/存储两项系数和Pol

13、yNode*pa,*pb,*rear,*s;PolyC=(PolyNode*)malloc(sizeof(PolyNode);pa=PolyA->next;pb=PolyB->next;rear=PolyC;rear->next=NULL;while(pa&&pb)if(pa->exp=pb->exp)sum=pa->coef+pb->coef;if(fabs(sum)>1e-6)如果两两系数不为0,则将两项和存入s中，并插入PolyC尾部s=(PolyNode*)malloc(sizeof(PolyNode);s->coe

14、f=sum;s->exp=pa->exp;rear->next=s;rear=s;)/pa,pb指针后移pa=pa->next;pb=pb->next;)elseif(pa->exp>pb->exp)右pa指数大于pb指数，将pa结点副本插入到PolyC尾部while(pa)s=(PolyNodes=(PolyNode*)malloc(sizeof(PolyNode);s->coef=pa->coef;s->exp=pa->exp;rear->next=s;rear=s;*)malloc(sizeof(PolyNod

15、e);s->coef=pa->coef;s->exp=pa->exp;rear->next=s;pa=pa->next;rear=s;pa=pa->next;else若pb指数大于pa指数将pb结点副本插入到PolyC尾部s=(PolyNode*)malloc(sizeof(PolyNode);s->coef=pb->coef;s->exp=pb->exp;rear->next=s;pb=pb->next;rear=s;while(pb)s=(PolyNode*)malloc(sizeof(PolyNode);s-&

16、gt;coef=pb->coef;s->exp=pb->exp;rear->next=s;pb=pb->next;rear=s;rear->next=NULL;returnPolyC;)voidDestroyPolyList(PolyListL)(PolyNode*p,*temp;p=L;while(p!=NULL)temp=p;p=p->next;free(temp);)将多项式和并同类项voidMergePoly(PolyListPoly)PolyNode*p,*q,*rear,*pre,*temp;rear=Poly;p=Poly->nex

17、t;while(rear->next!=NULL)q=p->next;pre=p;temp=p;while(q)if(p->exp=q->exp)p->coef+=q->coef;if(fabs(p->coef)>1e-6)pre->next=q->next;temp=q;q=temp->next;free(temp);else/两项系数和为0,释放结点p和qrear->next=p->next;temp=p;p=temp->next;free(temp);pre->next=q->next;tem

18、p=q;q=temp->next;free(temp);)elsepre=q;q=q->next;指数不等，指针q后移与p指数相同的节点合并完毕，或者没有找到，p后移rear=p;p=rear->next;rear->next=NULL;将多项式按升序排列voidSortPoly(PolyListPoly)PolyListrear,p,temp,prior;if(!Poly->next)return;若多项式为空，返回rear=Poly;intexp;/记录当前啊搜索项中的最小指while(rear->next!=NULL)exp=rear->next

19、->exp;p=rear->next;prior=rear;temp=prior->next;while(p!=NULL)if(p->exp>exp)exp=p->exp;temp=p;p=temp->next;elsep=p->next;MergePoly(Poly);if(rear->next->next=NULL)return;/p为最后一个元素且指数最小，提前返回)while(prior->next!=temp)prior=prior->next;prior->next=temp->next;temp-

20、>next=rear->next;rear->next=temp;rear=rear->next;)多项式相减，返回差多项式链表头指针PolyListPolySub(PolyListPolyA,PolyListPolyB)PolyListPolyC;SortPoly(PolyA);SortPoly(PolyB);floatsum=0;/存储两项系数差PolyNode*pa,*pb,*rear,*s;PolyC=(PolyNode*)malloc(sizeof(PolyNode);pa=PolyA->next;pb=PolyB->next;rear=PolyC

21、;rear->next=NULL;while(pa&&pb)if(pa->exp=pb->exp)sum=pa->coef-pb->coef;if(fabs(sum)>1e-6)如果两两系数不为0,则将两项和存入s中，并插入PolyC尾部s=(PolyNode*)malloc(sizeof(PolyNode);s->coef=sum;s->exp=pa->exp;rear->next=s;rear=s;)/pa,pb指针后移pa=pa->next;pb=pb->next;)elseif(pa->exp

22、>pb->exp)若pa指数大于pb指数，将pa结点副本插入到PolyC尾部(s=(PolyNode*)malloc(sizeof(PolyNode);s->coef=pa->coef;s->exp=pa->exp;rear->next=s;rear=s;pa=pa->next;)else若pb指数大于pa指数,将pb结点副本插入到PolyC尾部(s=(PolyNode*)malloc(sizeof(PolyNode);s->coef=-pb->coef;s->exp=pb->exp;rear->next=s;pb=

23、pb->next;rear=s;)while(pa)(s=(PolyNode*)malloc(sizeof(PolyNode);s->coef=pa->coef;s->exp=pa->exp;rear->next=s;pa=pa->next;rear=s;)while(pb)(s=(PolyNode*)malloc(sizeof(PolyNode);s->coef=-pb->coef;s->exp=pb->exp;rear->next=s;pb=pb->next;rear=s;)rear->next=NULL;

24、returnPolyC;)输出多项式voidDisplayPolyList(PolyListPoly)(if(Poly=NULL)printf("n");return;PolyNode*p=Poly->next;if(p=NULL)printf("0n");return;/如果链表为空提前退出while(p->next!=NULL)if(fabs(p->coef)>1e-6)if(fabs(p->next->coef)>1e-6)printf("%f*xA%d+",p->coef,p-&

25、gt;exp);elseprintf("%f*xA%d",p->coef,p->exp);elseprintf(".");/输出分割点p=p->next;if(fabs(p->coef)>1e-6)printf("%f*xA%d",p->coef,p->exp);printf("n");多项式相乘，结果由PolyC返回PolyListPolyMutiply(PolyListPolyA,PolyListPolyB)PolyListPolyC;PolyNode*pa,*pb,*

26、pc_pre,*pc,*s;if(PolyA=NULL|PolyB=NULL)returnNULL;若某一个多项式为空，返回PolyC=(PolyNode*)malloc(sizeof(PolyNode);pc=PolyC;pc->next=NULL;if(PolyA->next=NULL|PolyB->next=NULL)returnPolyC;SortPoly(PolyA);SortPoly(PolyB);pa=PolyA->next;pb=PolyB->next;s=(PolyNode*)malloc(sizeof(PolyNode);s->coef=

27、pa->coef*pb->coef;s->exp=pa->exp+pb->exp;if(pc->next=NULL)(pc->next=s;pc=s;pc->next=NULL;)直接插入第一个结点while(pa)(pb=PolyB->next;while(pb)(两项对应相乘，结果存入到s中pc=PolyC->next;if(pa=PolyA->next&&pb=PolyB->next)/避免重复插入第一个结点(pb=pb->next;if(pb=NULL)break;)s=(PolyNode*)

28、malloc(sizeof(PolyNode);s->coef=pa->coef*pb->coef;s->exp=pa->exp+pb->exp;/查找s合适的插入位置，使得插入后PolyC仍为升序排列while(pc&&pc->exp>s->exp)pc_pre=pc;pc=pc_pre->next;if(pc=NULL)pc_pre->next=s;s->next=NULL;pb=pb->next;elseif(pc->exp<s->exp)pc_pre->next=s;s

29、->next=pc;pb=pb->next;elseif(s->exp=pc->exp)pc->coef+=s->coef;free(s);if(fabs(pc->coef)<1e-6)pc_pre->next=pc->next;free(pc);pb=pb->next;pa=pa->next;returnPolyC;多项式相除，结果存到PolyC中，商和余数用系数为0的结点分开PolyListPolyDivide(PolyListPolyA,PolyListPolyB)if(!PolyA|!PolyB)returnNUL

30、L;if(PolyB->next=NULL)printf("Error:除项为空！n");returnNULL;PolyListPolyTI,PolyT2,pt,s,PolyC,p,s_pre;PolyC=(PolyList)malloc(sizeof(PolyNode);PolyC->next=NULL;if(PolyA->next=NULL)returnPolyC;p=PolyA->next;PolyTI=(PolyList)malloc(sizeof(PolyNode);pt=PolyTI;de);s_pre=(PolyList)malloc(

31、sizeof(PolyNowhile(p)将PollyA复制到PolyT中(s=(PolyList)malloc(sizeof(PolyNode);s->coef=p->coef;s->exp=p->exp;pt->next=s;pt=s;p=p->next;pt->next=NULL;将商存入到PolyC中p=PolyC;while(PolyT1->next&&PolyT1->next->exp>=PolyB->next->exp)(s=(PolyList)malloc(sizeof(PolyNode);s_pre->next=s;s->next=NULL;s->coef=PolyT1->next->coef/PolyB->next->coef;s->exp=PolyT1->next->exp-PolyB->next->exp;p->next=s;p=s;PolyT2=(PolyList)malloc(sizeof(PolyNode);PolyT2=PolySub(PolyT1,PolyMutiply(PolyB,s_pre);DestroyPolyList(PolyT1);PolyT1