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

用链表实现多项式的四则运算——数据结构第二次上机作业班级07082姓名丁敏学号07082022上机时间年月日2022331报告时间年月日202245实验目的熟练使用指针，熟悉链表及其操作；利用链表解决实际问题要求能够实现任意项有理多项式的加、减、乘、除、求模以及幕运算多项式的除法注意除不尽的处理测试用例尽可能多，且说明用例的必要性用例必须包含一个自己系数为自己的学号摘要多项式的四则运算问题是个很有趣的问题，它类似于有理数的四则运算，但又不仅仅于此.本篇课程论文重点研究了数据结构中多项式的四则运算问题本论文的程序是通过编译，来解决多项式的加、减、乘、除Microsoft VisualStudio2022四则运算问题，从而达到了解数据结构的实用性及程序语言对于数学问题研究的重要性的目的正文需求分析:0pc-next=s;〃多项式相除，结果存到中，商和余数PolyCpc=s;用系数为的结点分开pc-next=NULL;PolyList PolyDividePolyList PolyA,PolyList}〃直接插入第一个结点whilepaPolyB if!PolyA||!PolyB returnNULL;ifPopb=PolyB-next;lyB-next=whilepb除项为空〃两项对应相乘，结果存入到s PolyList PolyTl,PolyT2,pt,s,PolyC,中p,s_pre;二二PolyCpc PolyC-next;PolyListmallocsizeofPolyNode;二ifpa==PolyA-nextpb PolyC-next=NULL;二PolyB-next//避免重复插入第一个结点ifPolyA-next==NULL return PolyC;p=PolyA-next;pb=pb-next;二PolyTlifpb==NULL break;}s—PolyListmallocsizeofPolyNode;PolyNode*mallocsizeofPolyNode;s-二pt PolyTl;coef=pa-coef*pb-coef;s-exp=pa-exp+pb-exp;s_pre=PolyListmallocsizeofPolyNode;〃查找合适的插入位置，使得s〃将复制到中whilep PollyAPolyT插入后仍为升序罗列PolyCwhile pcpc-exps-二sexp{pc_pre=pc;pc=pc_pre-next;}PolyListmallocsizeofPolyNode;ifpc s-coef=p-coef;s-exp=p-exp;==NULL{pc_pre-next=s;s-next=NULL;pb=pb-next;}pt-next=s;else ifpc-exps-exp pt=s;{pc_pre-next=s;s-next=pc;pb=pb-next;}p=p-next;else ifs-exp==pc-exp二{pc-coef+s-coef;pt-next=NULL;frees;〃将商存入到PolyC中p=PolyC;二iffabspc-coef1e-6{pc_pre-nextwhilePolyT1-next pc-next;freepc;}PolyT1-next-exp=PolyB-next-exp{pb=pb-next;二spa=pa-next;PolyListmallocsizeofPolyNode;return PolyC;s_pre-next=s;s-next=NULL;s-coef=SortPolyPolyA;PolyT1-next-coef/PolyB-next-coef;合并排序后的多项式s-exp=PolyTl-next-exp-Display PolyListPolyA;PolyB-next-exp;SortPoly PolyB;p-next=s;合并排序后的多项式p=s;DisplayPolyListPolyB;二//PolyT2多项式的四则运算PolyListmallocsizeofPolyNode;PolyT2=PolySubPolyTl,PolyMutiplyPolyB,s_pre;//PolyA+PolyBDestroy Poly ListPolyTl;PolyC=PolyAddPolyA,PolyB;PolyTl=PolyT2;DisplayPolyListPolyC;〃设置分隔结点DestroyPolyListPolyC;s=Poly Listmalloc sizeofPolyN ode;s-coef=0;//PolyA-PolyBs-exp=0;PolyC=PolySubPolyA,PolyB;p-next=s;p=s;DisplayPolyListPolyC;//将余项p-next=PolyTl-next;DestroyPolyList PolyC;复制到中PolyT PolyCfreePolyTl;〃PolyA*PolyBreturn PolyC;PolyC=PolyMutiplyPolyA,PolyB;void mainDisplayPolyListPolyC;PolyList PolyA,PolyB,PolyC;DestroyPolyList PolyC;//PolyA/PolyB〃初始化以结束PolyA,PolyB,多项式的创建PolyC=PolyDividePolyA,PolyB;二PolyA CreatePolyList;DisplayPolyListPolyC;输入的多项式DestroyPolyListPolyC;DisplayPolyListPolyA;输入的多项式Disp layPolyListPolyB;PolyB=CreatePolyList;问题描述

0.1编写程序来实现多项式的四则运算基本要求

0.2⑴输入多项式的系数与指数，输入值为float型，输出值为float型；⑵能够完成多项式之间的四种计算方式+、-、*、/o函数说明

0.3typedef structPolyNode结构体变量，定义int型指数和float系数；PolyList CreatePolyList创建多项式列表，返回头指针；DisplayPolyList PolyList Poly显示多项式；DestroyPolyList PolyListL释放链表所用存储空间；MergePoly PolyListPoly将多项式合并同类项；SortPolyPolyList Poly将多项式按升序罗列;PolyList PolyAdd PolyList PolyA,PolyList PolyB多项式相加,返回和多项式链表头指针；PolyList PolySubPolyList polyA,PolyList polyB多项式相减,返回差多项式链表头指针；PolyList PolyMutiplyPolyList PolyA,PolyList PolyB多项式相乘，结果由Poly c返回；PolyList PolyDividePolyList PolyA,PolyList PolyB多项式相除，商和余数用系数为0的结点分开程序执行结果及分析1执行结果L1*******多项式的创建*******请输入多项式的第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.000000x^0A*B:

6.000000^x^4+

9.000000^x^3+

4.000000^x^2+

6.000000^x^1A/B:

1.500000^x^

4.500000*xT+

2.000000^x^0请按任意键继续

（2）・・・*******多项式的仓建*******U请输入多项式的第1项的系数和指数（用逗号分开）1,1请输入多项式的第2项的系数和指数0,0输入的多项式A:L000000*x」请输入多项式的第1项的系数和指数（用逗号分开）0,0输入的多项式B:0合并排序后的多项式A:L000000*x」合并排序后的多项式B:0*******多项式的四则运算*******A+B:

1.000000^x^1A-B:

1.000000^x^1A*B:0Error:除项为空！A/B:请按任意键继续・・・*******多项式的仓建*******请输入多项式的第1项的系数和指数（用逗号分开）2,3请输入多项式的第2项的系数和指数2/3,1（浮现乱码）测试用例L2C=A+B=5x+5y1A=x、B—x2C=A+B=x8+/C=A—B=x8—x2C=AB=x10C=A+B=xC=A+B=x2+y2+2xy+x+yC=A—B=xz+y2+2xy—x—yC=AB=x3+3F+3XY2+y3XC=A+B=x+y⑷输入A=3x+y,B=x+6y输出C=A+B=^+7yC=A—B=2x—5yC=AB=32+19xy+6y2X结果分析

1.3通过三次的运行，一二两次成功，但第三次乱码从第三次的运行来看由于输入与所要求的不一样二浮现乱码，故非程序的问题，所以本程序符合多项式的运算要求，是正确的程序的评价2⑴程序符合需求，能够有效地运行多项式之间的运算；⑵程序结构合理，具有层次性，易读；⑶程序运行界面友好，且不与别的程序相冲突⑷由于程序会出乱码现象，所以还有一定的缺陷；总结3本文的重点是对多项式的各种关系通过编程进行处理笔者通过通过Microsoft VisualStudio20编10译完成为了所要求的内容值得指出的是本程序层次性较强，易读，且具有较高的精度，如进一步改善，将会有很强的合用性笔者固然也碰到许多的问题，比如算法设计上仍有很大不足，流程图画的不是很熟练，全局变量不会定义，main函数的顺序位置等这些问题都可以通过实践来解决，总之，一句话熟能生巧附录#includestdio.h〃将多项式按升void SortPolyPolyListPoly;#includestdlib.h序罗列〃结点定义#includemath.h typedefstructPolyList PolyAddPoly List PolyA,PolyListPolyNode〃多项式相力口，返回和多项式链表PolyB;头指针〃指数//系数int exp;float coef;PolyList PolySubPolyListpolyA,PolyListPolyNode*next;〃多项式相减，返回差多项式链表头polyB;}PolyNode,*PolyList;指针；//创建多项式链表,PolyList CreatePolyListPolyList PolyMutiplyPolyList PolyA,PolyList返回头指针〃多项式相乘，结果由返回PolyB;PolyC显示多项void DisplayPolyListPolyListPoly;//PolyList PolyDividePolyListPolyA,PolyList式〃多项式相除，结果存到中，商PolyB;PolyC〃释放链表所void DestroyPolyListPolyListL;和余数用系数为的结点分开0PolyList用存储空间CreatePolyList〃将多项式和void MergePolyPolyListPoly;PolyNode*s,*rear,*head;并同类项int e;〃指数float c;〃系数int n=l;〃计数器*malloc sizeofPoly Node;s-coef=sum;s-head=PolyNode*exp=pa-exp;mallocsizeofPolyNode;rear-next=s;rearrear=head;二；s//输入多项式的系数和指数，若输入系指针后移//pa,pb数为退出pa=pa-next;请输入多项式的第％项的系d二pb pb-next;数和指数用逗号分开//若指else ifpa-exppb-exp pawhilefabscle-6数大于指数，将结点副本插入到pb paPolyC{s=PolyNode尾部*mallocsizeofPolyNode;s-exp=e;s-coef=c;rear-next=s;rear=s;二s PolyNode请输入多项式的第％项€1*mallocsizeofPolyNode;的系数和指数二s-coef pa-coef;s-exp=pa-exp;rear-next=NULL;return head;rear-next=s;rear=s;〃计算两个多项式可不按顺序罗列，结果pa=pa-next;存到链表中，并返回PolyC PolyListPolyAdd Poly ListPolyA,〃若指数大于指数，将else pb pa pbPolyListPolyB结点副本插入到尾部PolyCPolyList PolyC;SortPolyPolyA;二s PolyNodeSortPolyPolyB;〃存储两项系数和*mallocsizeofPolyNode;float sum=0;PolyNode*pa,*pb,*rear,*s;s-coef=pb-coef;s-exp=pb-exp;PolyC=PolyNode*mallocsizeofPolyNode;pa=PolyA-next;pb=PolyB-next;rear=PolyC;rear-next=NULL;whilepapbifpa-exp==pb-exp{sum=pa-coef+pb-coef;〃如果两两iffabssum1e-6系数不为则将两项和存入中，并插入0,s尾部PolyC二s PolyNoderear-next=s;whilerear-next!=NULLpb=pb-next;rear=s;q=p-next;pre-p;二temp p;whileqwhilepa{s=PolyNode ifp-exp二二q-exp*mallocsizeofPolyNode;{p-coef+=q-coef;s-coef=pa-coef;iffabsp-coef1e-6s-exp=pa-exp;rear-next=s;二pre-next q-next;pa=pa-next;rear=s;temp=q;q=temp-next;freetemp;whilepb{s二PolyNode else〃两项系数和为释放结点和0,p q*mallocsizeofPolyNode;s-coef=pb-coef;s-exp=pb-exp;rear-next=p-next;rear-next=s;二temp p;pb=pb-next;p=temp-next;rear=s;freetemp;pre-next=rear-next=NULL;q-next;temp=q;return PolyC;q=temp-next;freetemp;void DestroyPolyListPolyListL}PolyNode*p,*temp;P=L;〃指else{pre=q;q=q-next;}whilep!=NULL数不等，指针后移q{temp=p;p=p-next;freetemp;}〃与指数相同的节点合并完毕，或p}者没有找到，后移p〃将多项式和并同类项二rear p;void MergePolyPolyListPoly二p rear-next;产PolyNode*p,*q,*rear,*pre temp;rear-next=NULL;rear=Poly;p=Poly-next;〃将多项式按升序罗列SortPolyPolyB;void SortPolyPolyListPoly{float sum=0;〃存储两项系数差PolyList rear,p,temp,prior;PolyNode*pa,*pb,*rear,*s;PolyC=PolyNode//若多项式为空,if!Poly-next return;*malloc sizeofPoly Node;返回pa=PolyA-next;MergePolyPoly;pb=PolyB-next;rear=Poly;rear=PolyC;记录当前啊搜索项中的最小指rear-next=NULL;int exp;//whilepapb数whilerear-next!=NULL二=ifpa-exp pb-exp{exp=rear-next-exp;sum=pa-coef-pb-coef;p=rear-next;〃如果两两iffabssum1e-6prior=rear;系数不为则将两项和存入中，并插入0,stemp=prior-next;尾部PolyCwhilep!=NULL ifp-expexp二s PolyNodeexp=p-exp;*mallocsizeofPo!yNode;temp=p;s-coef=sum;s-p=temp-next;exp=pa-exp;else rear-next=s;rearp=p-next;=s;ifrear-next-next为最后一个元素且指数最==NULL return;//p指针后移//pa,pb小，提前返回pa=pa-next;pb=pb-next;//若指else ifpa-exppb-exp pawhileprior-next!=temp prior=数大于指数，将结点副本插入到prior-next;pbpaPolyC尾部prior-next=temp-next;temp-next=rear-next;rear-next=temp;rear={rear-next;s=PolyNode*mallocsizeofPolyNode;s-coef=pa-coef;}s-exp=pa-exp;〃多项式相减，返回差多项式链表头指针rear-next=s;rear=s;PolyList PolySubPolyListPolyA,PolyListpa=pa-next;PolyBPolyList PolyC;SortPolyPolyA;PolyNode*p=Poly-next;〃若指数大于指数,将else pbpa pbiffabsp-coef1e-6结点副本插入到尾部PolyCs=PolyNodeif fobsp-next-coefle-6*mallocsizeofPolyNode;+,p-coef,p-exp;s-coef=-pb-coef;s-exp=pb-exp;p-coef,p-exp;rear-next=s;pb=pb-next;rear-s;else输出分割点}p=p-next;}whilepa二s PolyNode*mallocsizeofPolyNode;s-coef=pa-coef;s-exp=pa-exp;rear-next=s;//多项式相乘，结果由返回PolyCpa=pa-next;PolyListPolyMutiplyPolyListPolyA,PolyListrear=s;PolyB}PolyList PolyC;whilepbPolyNode*pa,*pb,*pc_pre,*pc,*s;ifPolyA==NULL||PolyB==NULLs二PolyNode returnNULL;〃若某一个多项式为空，返回PolyC=*malloc sizeofPolyNode;s-coef=-pb-coef;PolyNode*mallocsizeofPolyNode;pc=PolyC;s-exp=pb-exp;rear-next=s;pc-next=NULL;pb=pb-next;ifPolyA-next==NULL||rear=s;PolyB-next==NULL returnPolyC;SortPolyPolyA;rear-next=NULL;SortPoly PolyB;pa=PolyA-next;returnPolyC;pb=PolyB-next;二s〃输出多项式PolyNode*mallocsizeofPolyNode;s-coefvoid DisplayPolyListPolyListPoly{二pa-coef*pb-coef;s-exp=pa-exp+if Pol=NULLypb-exp;ifpc-next==NULL〃如果链表为空提前退出return;}whilep-next!=NULL。