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

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

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

3、olyList(PolyList Poly) :显示多项式； DestroyPolyList(PolyList L):释放链表所用存储空间；MergePoly(PolyList Poly):将多项式合并同类项；SortPoly(PolyList Poly):将多项式按升序排列；PolyList PolyAdd(PolyListPolyA , PolyList PolyB):多项式相加，返回和多项式链表头指针；PolyList PolySub(PolyListpolyA , PolyList polyB):多项式相减，返回差多项式链表头指针；PolyList PolyMutiply(PolyLi

4、st PolyA , PolyList PolyB):多项式相乘，结果由Poly c返回；PolyList PolyDivide(PolyList PolyA , PolyList PolyB):多项式相除，商和余数用系数为0的结点分开。1程序执行结果及分析：1.1执行结果*多项式的创建请输入多项式的第1项的系数和指数(用逗号分开)：3,2 请输入多项式的第请输入多项式的第2项的系数和指数：2,03项的系数和指数：0,0输入的多项式 A： 3.000000*xA2 + 2.000000*xA0 请输入多项式的第1项的系数和指数(用逗号分开)：2,2 请输入多项式的第2项的系数和指数：3,1请输

5、入多项式的第3项的系数和指数：0,0输入的多项式 B： 2.000000*xA2 + 3.000000*xA1合并排序后的多项式 A: 3.000000*xA2 + 2.000000*xP合并排序后的多项式 B: 2.000000*xA2 + 3.000000*xA1*多项式的四则运算*A+B: 5.000000*xA2 + 3.000000*乂八1 + 2.000000*乂八0A-B: 1.000000*xA2 + -3.000000*xA1 + 2.000000*乂八0A*B: 6.000000*xA4 + 9.000000*乂八3 + 4.000000*乂八2 + 6.000000*乂八

6、1A/B: 1.500000*xA0 -4.500000*xA1 + 2.000000*乂八0请按任意键继续 *多项式的创建*请输入多项式的第1项的系数和指数（用逗号分开）：1,1请输入多项式的第2项的系数和指数：0,0输入的多项式A: 1.000000*xA1请输入多项式的第1项的系数和指数（用逗号分开）：0,0 输入的多项式B: 0 合并排序后的多项式A: 1.000000*xA1合并排序后的多项式B: 0* 多项式的四贝y运算*A+B: 1.000000*xA1A-B: 1.000000*xA1A*B: 0Error:除项为空!A/B: 请按任意键继续*多项式的创建*请输入多项式的第1项

7、的系数和指数（用逗号分开）：2,3 请输入多项式的第2项的系数和指数：2/3,1（出现乱码）1.2测试用例(1):= 二-二 ：C = A+B = 30(x + y)C = A-B=20(x + y)多项式的四则运算C = AB = 125(x2 + 2xy +ya)C = A-s-B = 5x + Sy(2) .< - ' Z -二C = A+B = x3+xzC = A-B = x3x2C = AB = xlcC = A-r B = x& x2 + y2 + 2XY.B = x + yC = A + B = x2 +ya + 2xy + x + yC = A - B

8、= x: +ya + 2xy- x- yC = AB = x3 +3x + 3xy2 + y3C = A-r B = x+y(4)输入:'-金'弋飞一餐输出：-了C = A - B = 2x - 5yC = AB = 3x2 + 19xy + 6y2C = A-s-B = x+6y1.3结果分析通过三次的运行，一二两次成功，但第三次乱码。从第三次的运行来 看由于输入与所要求的不一样二出现乱码，故非程序的问题，所以本程序符 合多项式的运算要求，是正确的。2程序的评价：程序符合需求，能够有效地运行多项式之间的运算； 程序结构合理，具有层次性，易读； 程序运行界面友好，且不与别的程序

9、相冲突 由于程序会出乱码现象，所以还有一定的缺陷；3总结：本文的重点是对多 项式的各种关 系通过编程进 行处理。笔者 通过通过 Microsoft Visual Studio 2010编译完成了所要求的内容。值得指出的是：本程序层次性较强，易读，且具有较高的精度，如进一步改善，将会有很强的适用 性。笔者当然也碰到许多的问题，比如算法设计上仍有很大不足，流程图画的 不是很熟练，全局变量不会定义， main函数的顺序位置等。这些问题都可以通 过实践来解决，总之，一句话熟能生巧。11附录#in clude<stdio.h>#in clude<stdlib.h>#i nclud

10、e<math.h> 结点定义typedef struct PolyNodeint exp;/ 指数float coef;/ 系数PolyNode* next;PolyNode , * PolyList;PolyList CreatePolyList(); / 创建多项式链表，返回头指针void DisplayPolyList(PolyList Poly);/ 显示 多项式void DestroyPolyList(PolyList L); 释放链表所用存储空间void MergePoly(PolyList Poly);/ 将多项式 和并同类项void SortPoly(PolyLis

11、t Poly);/将多项式按升序排列PolyList PolyAdd(PolyList PolyA , PolyListPolyB);/多项式相加，返回和多项式链表头 指针PolyList PolySub(PolyList polyA , PolyListpolyB);/多项式相减，返回差多项式链表头 指针PolyList PolyMutiply(PolyList PolyA ,PolyList PolyB);/多项式相乘，结果由PolyC返回PolyList PolyDivide(PolyList PolyA ,PolyList PolyB);/多项式相除，结果存到PolyList Crea

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

13、de);s->exp = e;s->coef = c;rear->next = s;rear = s;PolyC中，商和余数用系数为 0的结点分开printf(”请输入多项式的第 %d项的系数和指数：” ,n+);scanf("%f,%d" , &c , &e);rear->next = NULL;retur n head;计算两个多项式(可不按顺序排列)，结 果存到链表PolyC中，并返回PolyList PolyAdd(PolyList PolyA , PolyListPolyB)PolyList PolyC ;SortPoly(

14、PolyA);SortPoly(PolyB);float sum=0;存储两项系数和PolyNode *pa , *pb , *rear , *s ;PolyC = (PolyNode*)malloc(sizeof(PolyNode);pa = PolyA->n ext;pb = PolyB->n ext;rear->next = NULL;while(pa && pb)if(pa->exp = pb->exp)sum = pa->coef+pb->coef;if(fabs(sum)>1e-6)/ 如果两两系数不为0 ,则将两项和

15、存入s中，并插入PolyC尾部s = (PolyNode*)malloc(sizeof(PolyNode);s->coef = sum;s->exp = pa->exp;rear->next = s; rear = s;pa,pb指针后移pa = pa->n ext;pb = pb->n ext;rear = PolyC;多项式的四则运算else if(pa->exp>pb->exp)/若pa指数大于pb指数，将pa结点副本插入到PolyC尾部while(pa)s = (PolyNodes = (PolyNode*)malloc(sizeo

16、f(PolyNode);*)malloc(sizeof(PolyNode);s->coef = pa->coef;s->coef = pa->coef:s->exp = pa->exp;s->exp = pa->exp;rear->n ext = s ;rear->next = s;rear = s ;pa = pa->n ext;pa = pa->n ext;rear = s ;else右 pb指数大于 pa指数，while(pb)将pb结点副本插入到PolyC尾部s = (PolyNodes = (PolyNode*)

17、malloc(sizeof(PolyNode);*)malloc(sizeof(PolyNode);s->coef = pb->coef;s->coef = pb->coef;s->exp = pb->exp;s->exp = pb->exp;rear->next = s;rear->n ext = s;pb = pb->n ext;pb = pb->n ext;rear = s ;rear = s ;多项式的四则运算26while(q)q->n ext;rear->n ext = NULL;return Po

18、lyC;void DestroyPolyList(PolyList L)PolyNode * p , *temp;p = L;while(p!=NULL)temp = p ; p = p_>n ext; free(temp); 将多项式和并同类项void MergePoly(PolyList Poly)PolyNode * p , *q , * rear ,*pre ,* temp;rear = Poly;p = Poly _>next ;while(rear-> next!=NULL)q = p_>n ext;pre = p;temp = p;if(p->exp

19、 = q->exp)p_>coef+=q_>coef;if(fabs(p->coef)>1e-6)pre_>next =q_>n ext;temp = q;q = temp->n ext;free(temp);elseII两项系数和为0，释放结点p和qrear->n ext =p_>n ext;temp = p;p = temp->n ext;free(temp);pre_>next =temp = q;q = temp->n ext;free(temp);elsepre= q ; q = q_>n ext;/

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

21、xt ;prior = rear;temp = prior- >next ; while(p!=NULL)if(p->exp > exp)exp = p->exp ; temp = p ;p = temp->next ;elseMergePoly(Poly);p = p->n ext ;if(rear- >n ext-> next=NULL) return;p为最后一个元素且指数最小，提前返回while(prior- >n ext != temp) prior =prior- >n ext ;prior- >next = tem

22、p->n ext;temp->next = rear->next ;rear->n ext = temp;rear = rear->n ext ;/多项式相减，返回差多项式链表头指针PolyList PolySub(PolyList PolyA , PolyList PolyB)PolyList PolyC ;SortPoly(PolyA);SortPoly(PolyB);PolyNode *pa , *pb , *rear , *s ;PolyC = (PolyNode*)malloc(sizeof(PolyNode);pa = PolyA->n ext;

23、pb = PolyB->n ext;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;float

24、sum =0 ;/存储两项系数差s->coef = -pb->coef;pa,pb指针后移s->exp = pb->exp;pa = pa->n ext;rear->n ext = s;pb = pb->n ext;pb = pb->n ext;rear = s ;else if(pa->exp>pb->exp)/ 若pa指数大于pb指数，将pa结点副本插入到PolyC尾部while(pa)s = (PolyNodes = (PolyNode*)malloc(sizeof(PolyNode);*)malloc(sizeof(Po

25、lyNode);s->coef = pa->coef;s->coef = pa->coef;s->exp = pa->exp;s->exp = pa->exp;rear->n ext = s ;rear->next = s;rear = s ;pa = pa->n ext;pa = pa->n ext;rear = s ;else右pb指数大于 pa指数，while(pb)将pb结点副本插入到PolyC尾部s = (PolyNodes = (PolyNode*)malloc(sizeof(PolyNode);s->c

26、oef = -pb->coef;*)malloc(sizeof(PolyNode);else prin tf("%f*xA%d",p->coef , p->exp);else printf(”");/输出分割点 p = p_>n ext ;if(fabs(p->coef)>1e-6)pri ntf("%f*xA%d",p->coef , p->exp);prin tf("n");/多项式相乘，结果由PolyC返回PolyList PolyMutiply(PolyList Pol

27、yA ,/ PolyList PolyB)PolyList PolyC;PolyNode *pa , *pb , *pc_pre , *pc*s;s->exp = pb_>exp;rear->n ext = s;pb = pb->n ext; rear = s ;rear->n ext = NULL;return PolyC;/输出多项式void DisplayPolyList(PolyList Poly)if(Poly = NULL) pri ntf("n");return;PolyNode *p=Poly-> next ;if(p =

28、 NULL)printf("0n”); return;如果链表为空提前退出while(p-> next!=NULL)if(fabs(p->coef)>1e-6)if(fabs(p->n ext->coef)>1e-6)prin tf("%f*xA%d + " , p->coef , p->exp);if(PolyA=NULL | PolyB=NULL)return NULL;/若某一个多项式为空，返PolyC =(PolyNode*)malloc(sizeof(PolyNode); pc = PolyC ;pc- &

29、gt;n ext = NULL;if(PolyA-> next=NULL |PolyB-> next=NULL) return PolyC;SortPoly(PolyA); SortPoly(PolyB); pa = PolyA->n ext ; pb = PolyB->n ext;s =(PolyNode*)malloc(sizeof(PolyNode); s->coef = pa->coef * pb->coef ; s->exp = pa->exp + pb->exp ; if(pc-> next = NULL)pc-&g

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

31、coef;s->exp = pa->exp +pb->exp ;/查找s合适的插入位置，使得插入后PolyC仍为升序排列while( pc && pc->exp >s->exp) pc_pre = pc ; pc=pc_pre _>n ext ;if(pc=NULL)pc_pre-> next=s ; s->n ext=NULL;pb=pb-> next;else if( pc->exp <s->exp)pc_pre _>n ext = s ; s_>next = pc ;pb=pb-&g

32、t;n ext; else if(s->exp = pc->exp )pc->coef += s->coef ;free(s);if(fabs(pc->coef)<1e-6 )pc_pre->n ext=pc->n ext ; free(pc);pb = pb->n ext;pa = pa->n ext;return PolyC;/多项式相除，结果存到PolyC中，商和余数用系数为0的结点分开PolyList PolyDivide(PolyList PolyA ,PolyList PolyB)if(!PolyA | !PolyB) r

33、eturn NULL;if(PolyB-> next = NULL)pri ntf("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- >n ext;PolyT1 =(PolyList)malloc(sizeof(PolyNode);pt = Po

34、lyT1;s_pre=(PolyList)malloc(sizeof(PolyNode);while(p)将 PollyA 复制到 PolyT 中s =(PolyList)malloc(sizeof(PolyNode);s->coef = p->coef ;s->exp = p->exp ;pt- >n ext = s;pt = s;p = p_>next ;pt-> next=NULL;将商存入到PolyC中p = PolyC;while(PolyT1-> next &&PolyT1- >n ext->exp >

35、;= PolyB->n ext->exp)s =(PolyList)malloc(sizeof(PolyNode);s_pre->n ext = s;s-> next=NULL;s->coef=PolyT1- >n ext->coef/PolyB->n ext->coef;s->exp = PolyT1- >n ext->exp -PolyB->n ext->exp;p_>n ext = s;p = s;PolyT2 =(PolyList)malloc(sizeof(PolyNode);PolyT2 = PolySub(Poly