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

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

本论文的程序是通过Microsoft Visual Studio 2010编译，来解决多项式的加、减、乘、除四则运算问题，从而达到了解数据结构的实用性及程序语言对于数学问题研究的重要性的目的。

正文：0需求分析：0.1问题描述编写程序来实现多项式的四则运算。

0.2基本要求⑴输入多项式的系数与指数，输入值为float型，输出值为float型；⑵能够完成多项式之间的四种计算方式（+、-、*、/）。

0.3函数说明typedef struct PolyNode：结构体变量，定义 int型指数和float 系数；PolyList CreatePolyList()：创建多项式列表，返回头指针；DisplayPolyList(PolyList Poly)：显示多项式；DestroyPolyList(PolyList L)：释放链表所用存储空间；MergePoly(PolyList Poly)：将多项式合并同类项；SortPoly(PolyList Poly)：将多项式按升序排列；PolyList PolyAdd(PolyList PolyA , PolyList PolyB)：多项式相加，返回和多项式链表头指针；PolyList PolySub(PolyList polyA , PolyList polyB)：多项式相减，返回差多项式链表头指针;PolyList PolyMutiply(PolyList PolyA , PolyList PolyB)：多项式相乘，结果由Poly c返回；PolyList PolyDivide(PolyList PolyA , PolyList PolyB)：多项式相除，商和余数用系数为0的结点分开。

1程序执行结果及分析：1.1执行结果⑴*******多项式的创建*******请输入多项式的第1项的系数和指数(用逗号分开)：3,2请输入多项式的第2项的系数和指数：2,0请输入多项式的第3项的系数和指数：0,0输入的多项式A: 3.000000*x^2 + 2.000000*x^0请输入多项式的第1项的系数和指数(用逗号分开)：2,2请输入多项式的第2项的系数和指数：3,1请输入多项式的第3项的系数和指数：0,0输入的多项式B: 2.000000*x^2 + 3.000000*x^1合并排序后的多项式A: 3.000000*x^2 + 2.000000*x^0合并排序后的多项式B: 2.000000*x^2 + 3.000000*x^1*******多项式的四则运算*******A+B: 5.000000*x^2 + 3.000000*x^1 + 2.000000*x^0A-B: 1.000000*x^2 + -3.000000*x^1 + 2.000000*x^0A*B: 6.000000*x^4 + 9.000000*x^3 + 4.000000*x^2 + 6.000000*x^1 A/B: 1.500000*x^0 ......-4.500000*x^1 + 2.000000*x^0请按任意键继续. . .⑵*******多项式的创建*******请输入多项式的第1项的系数和指数(用逗号分开)：1,1请输入多项式的第2项的系数和指数：0,0输入的多项式A: 1.000000*x^1请输入多项式的第1项的系数和指数(用逗号分开)：0,0输入的多项式B: 0合并排序后的多项式A: 1.000000*x^1合并排序后的多项式B: 0*******多项式的四则运算*******A+B: 1.000000*x^1A-B: 1.000000*x^1A*B: 0Error:除项为空!A/B:请按任意键继续. . .⑶*******多项式的创建*******请输入多项式的第1项的系数和指数(用逗号分开)：2,3请输入多项式的第2项的系数和指数：2/3,1（出现乱码）1.2测试用例(1)（2）(3)（4）输入：输出：1.3结果分析通过三次的运行，一二两次成功，但第三次乱码。

从第三次的运行来看由于输入与所要求的不一样二出现乱码，故非程序的问题，所以本程序符合多项式的运算要求，是正确的。

2程序的评价：⑴程序符合需求，能够有效地运行多项式之间的运算；⑵程序结构合理，具有层次性，易读；⑶程序运行界面友好，且不与别的程序相冲突⑷由于程序会出乱码现象，所以还有一定的缺陷；3总结：本文的重点是对多项式的各种关系通过编程进行处理。

笔者通过通过Microsoft Visual Studio 2010编译完成了所要求的内容。

值得指出的是：本程序层次性较强，易读，且具有较高的精度，如进一步改善，将会有很强的适用性。

笔者当然也碰到许多的问题，比如算法设计上仍有很大不足，流程图画的不是很熟练，全局变量不会定义，main函数的顺序位置等。

这些问题都可以通过实践来解决，总之，一句话熟能生巧。

附录#include<stdio.h>#include<stdlib.h>#include<math.h>//结点定义typedef struct PolyNode{int exp; //指数float coef; //系数PolyNode* next;}PolyNode , * PolyList;PolyList CreatePolyList(); //创建多项式链表，返回头指针void DisplayPolyList(PolyList Poly);//显示多项式void DestroyPolyList(PolyList L);//释放链表所用存储空间void MergePoly(PolyList Poly);//将多项式和并同类项void SortPoly(PolyList Poly);//将多项式按升序排列PolyList PolyAdd(PolyList PolyA , PolyList PolyB);//多项式相加，返回和多项式链表头指针PolyList PolySub(PolyList polyA , PolyList polyB);//多项式相减，返回差多项式链表头指针PolyList PolyMutiply(PolyList PolyA , PolyList PolyB);//多项式相乘，结果由PolyC返回PolyList PolyDivide(PolyList PolyA , PolyList PolyB);//多项式相除，结果存到PolyC中，商和余数用系数为0的结点分开PolyList CreatePolyList(){PolyNode *s,*rear,*head;int e; //指数float c; //系数int n=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->exp = e;s->coef = c;rear->next = s;rear = s;printf("请输入多项式的第%d项的系数和指数：" , n++);scanf("%f,%d" , &c , &e);}rear->next = NULL;return head;}//计算两个多项式（可不按顺序排列），结果存到链表PolyC中，并返回PolyList PolyAdd(PolyList PolyA , PolyList PolyB){PolyList PolyC ;SortPoly(PolyA);SortPoly(PolyB);float sum=0;//存储两项系数和PolyNode *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->coef = sum;s->exp = pa->exp;rear->next = s;rear = s;}//pa,pb指针后移pa = pa->next;pb = pb->next;}else if(pa->exp>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 = 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;return PolyC;}void DestroyPolyList(PolyList L){PolyNode * p , *temp;p = L;while(p!=NULL){temp = p ; p = p->next;free(temp); }}//将多项式和并同类项void MergePoly(PolyList Poly){PolyNode * p , *q , * rear ,*pre ,* temp;rear = Poly;p = Poly->next ;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和q{rear->next =p->next;temp = p;p = temp->next;free(temp);pre->next =q->next;temp = q;q = temp->next;free(temp);}}else{pre= q ; q = q->next;} //指数不等，指针q后移}//与p指数相同的节点合并完毕，或者没有找到，p后移rear = p;p = rear->next;}rear->next = NULL;}//将多项式按升序排列void SortPoly(PolyList Poly){PolyList rear , p ,temp , prior;if(!Poly->next) return; //若多项式为空，返回MergePoly(Poly);rear = Poly;int exp;//记录当前啊搜索项中的最小指数while(rear->next!=NULL){exp = rear->next->exp;p = rear->next ;prior = rear;temp = prior->next ;while(p!=NULL){if(p->exp > exp){exp = p->exp ;temp = p ;p = temp->next ;}else{p = p->next ;if(rear->next->next ==NULL) return; //p为最后一个元素且指数最小，提前返回}}while(prior->next != temp) prior = prior->next ;prior->next = temp->next;temp->next = rear->next ;rear->next = temp;rear = rear->next ;}}//多项式相减，返回差多项式链表头指针PolyList PolySub(PolyList PolyA , PolyList PolyB){PolyList PolyC ;SortPoly(PolyA);SortPoly(PolyB);float sum =0 ;//存储两项系数差PolyNode *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->coef = sum;s->exp = pa->exp;rear->next = s;rear = s;}//pa,pb指针后移pa = pa->next;pb = pb->next;}else if(pa->exp>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 = 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;return PolyC;}//输出多项式void DisplayPolyList(PolyList Poly) {if(Poly == NULL){printf("\n");return;}PolyNode *p=Poly->next ;if(p == NULL){printf("0\n"); return;} //如果链表为空提前退出while(p->next!=NULL){if(fabs(p->coef)>1e-6){if(fabs(p->next->coef)>1e-6)printf("%f*x^%d + " , p->coef , p->exp);else printf("%f*x^%d " , p->coef , p->exp);}else printf("......");//输出分割点p = p->next ;}if(fabs(p->coef)>1e-6)printf("%f* x^%d" , p->coef , p->exp);printf("\n");}//多项式相乘，结果由PolyC返回PolyList PolyMutiply(PolyList PolyA , PolyList PolyB){PolyList PolyC;PolyNode *pa , *pb , *pc_pre , *pc , *s;if(PolyA==NULL || PolyB==NULL) return NULL; //若某一个多项式为空，返回PolyC =(PolyNode*)malloc(sizeof(PolyNode));pc = PolyC ;pc->next = NULL;if(PolyA->next==NULL ||PolyB->next==NULL) return PolyC;SortPoly(PolyA);SortPoly(PolyB);pa = PolyA->next ;pb = PolyB->next;s =(PolyNode*)malloc(sizeof(PolyNode));s->coef = 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*)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;}else if( pc->exp <s->exp){pc_pre->next = s ; s->next = pc ; pb=pb->next; }else if(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;}return PolyC;}//多项式相除，结果存到PolyC中，商和余数用系数为0的结点分开PolyList PolyDivide(PolyList PolyA , PolyList PolyB){if(!PolyA || !PolyB) return NULL;if(PolyB->next ==NULL){printf("Error:除项为空!\n");return NULL;}PolyList PolyT1 , PolyT2 , pt , s , PolyC , p , s_pre;PolyC =(PolyList)malloc(sizeof(PolyNode));PolyC->next=NULL;if(PolyA->next==NULL) return PolyC;p = PolyA->next;PolyT1 =(PolyList)malloc(sizeof(PolyNode));pt = PolyT1;s_pre=(PolyList)malloc(sizeof(Pol yNode));while(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 = PolyT2; }//设置分隔结点 s=(PolyList)malloc(sizeof(PolyNode)); s->coef = 0; s->exp = 0; p->next = s; p = s;p->next = PolyT1->next; //将余项PolyT 复制到PolyC 中 free(PolyT1); return PolyC; }void main() {PolyList PolyA, PolyB , PolyC; //初始化PolyA ，PolyB ，以0结束 printf("*******多项式的创建*******\n");PolyA = CreatePolyList(); printf("输入的多项式A: "); DisplayPolyList(PolyA); printf("\n");PolyB = CreatePolyList();printf("输入的多项式B: "); DisplayPolyList(PolyB); printf("\n"); SortPoly(PolyA);printf("合并排序后的多项式A: "); DisplayPolyList(PolyA); SortPoly(PolyB);printf("合并排序后的多项式B: "); DisplayPolyList(PolyB);printf("*******多项式的四则运算*******\n");//PolyA + PolyBPolyC = PolyAdd(PolyA , PolyB); printf("A+B: ");DisplayPolyList(PolyC); DestroyPolyList(PolyC);//PolyA - PolyBPolyC = PolySub(PolyA , PolyB); printf("A-B: ");DisplayPolyList(PolyC); DestroyPolyList(PolyC);//PolyA*PolyBPolyC = PolyMutiply(PolyA , PolyB); printf("A*B: ");DisplayPolyList(PolyC); DestroyPolyList(PolyC); //PolyA/PolyBPolyC = PolyDivide(PolyA , PolyB); printf("A/B: ");DisplayPolyList(PolyC); DestroyPolyList(PolyC); }。