稀疏一元多项式运算器实验报告附源程序

1、问题描述：完成一元稀疏多项式运算器，完成多项式创建，显示，复制，求和，求差，求值，稀疏一元多项式运算器0.退出1.创建多项式2.显示多项式3.复制多项式4.求和5.求差6.求值7.销毁多项式8.清空多项式9.修改多项式阶微分11.不定微分12.定微分销毁，清空，修改，n阶微分，不定积分，定积分操作。函数功能描述如下：退出创建并打印打印复制多项式a至空域b,非空报错输入abc位置，c=a+b输入abc位置,c=a-b输入位置,doublex,输出doubleresult销毁,使pi为NULL清空保留头指针,输出为0选择插入,删除,修改（删了再插）输入微分位置,阶数,结果存放于原位置输入积分位置，

2、不定积分，常数C取0输入积分位置,上下限值,输出定积分结果算法描述：通过主菜单调用函数完成各项功能,函数描述见程序结构描述部分。数据结构描述:多项式每一项结点定义如下：typedefstructlnodedoublecoef;intexp;structlnode*next;lnode,*linklist;包含指向下一结点指针linklistnext,存储系数的数据单元doublecoef,存储指数的数据单元intexp；结点名lnode,指向结点指针linklist。每一个多项式由头指针引出,头指针数组lnode*pN。每一个单元存储一多项式头指针。当多项式不存在,pi=NULL；多项式为空,

3、pi-next=NULL,即只存在头指针。操作函数见程序结构描述部分。程序结构描述：函数包括创建结点函数,有序插入函数,打印函数,创建多项式函数,多项式清空函数,多项式销毁函数,求值函数,求和函数,求差函数,复制函数,删除结点函数,修改函数,n阶微分函数,不定积分函数。对函数原型,功能,借口逐一描述如下：1. 创建结点函数函数原型：linklistmakenode（doublecoef,intexp）输入double型系数项,int型指数项,创建lnode结点,返回指向结点的linklist指针。功能：创建新结点,在复制函数以及输入系数指数插入结点时（修改多项式）调用。2. 有序插入函数函数原

4、型：voidinsert（linklistphead,linklisthead）输入插入结点指针phead以及多项式头指针head，无返回值功能：新结点phead有序插入头结点为head的多项式内（按指数项降序排列）,在创建,复制,修改函数中调用。3. 打印函数函数原型：voidprintlinklist(linklistphead)输入待打印多项式头指针phead，无返回值分别打印系数项和指数项，打印系数项是使用g输入取消无效0,通过特殊情况讨论(如exp=0,exp=1,首项的加号等情况)，使多项式输出符合书写习惯。功能：打印多项式4. 创建多项式函数原型：linklistcreatlis

5、t()返回创建多项式头指针,调用时先在主函数中输入该多项式头指针在头指针数组中位置。实现：先若该位置无多项式,申请头结点,之后新建数据结点,有序插入头结点对应多项式。5. 清空多项式函数原型：voidlinklistclear(linklisthead)输入待清空多项式头结点,无返回值,将pi仅保留头结点。实现：用前后两指针,遍历多项式并逐一删去结点,最后将头指针的next域置NULL。6. 销毁多项式函数原型：voidlinklistdestroy(linklist&head)输入待销毁多项式头结点,无返回值,将pi置NULL实现方法类似清空,删去包括head在内结点。7. 多项式求值函数原

6、型：doublelinklistvalue(linklisthead,doublex)输入待求多项式头结点，变量x值doublex，返回double型结果实现：通过exp求每一项权重,与系数coef相乘,最后累加所有结果。8. 多项式求和函数原型：voidlinklistadd(linklistahead,linklistbhead,linklist&chead)输入相加两多项式a,b头指针以及输出位置c，无返回值实现：通过pa,pb遍历a,b,新建c结点对比当前位置a,bexp大小,分别做对应赋值,之后将c结点插入c多项式中(*当c新结点系数为0时不进行插入)9. 多项式求差函数原型：voi

7、dlinklistsub(linklistahead,linklistbhead,linklist&chead)输入相减两多项式a,b头指针以及输出位置c，无返回值实现完全与求和相同10. 多项式复制函数原型：linklistlinklistcopy(linklista)输入待复制多项式头指针linklista，输出复制结果指针linklist。遍历多项式a，读取每一结点coef,exp值，调用makenode函数创建新结点，插入多项式b，返回b头指针head。11. 删除多项式中一节点函数原型：intlinklistdelete(linklisthead,intm)输入待删除多项式头指针li

8、nklisthead，待删除项指数值intm，成功返回1，反之-1删除head中一指数为m项，修改函数中调用实现：遍历多项式，若指数项系数为m，free(p)12. 修改多项式函数原型：voidlinklistmodify(linklisthead)输入待修改多项式头指针linklisthead，无返回值调用函数时输入1,2,3选择插入结点，删除结点，修改结点操作(删除后插入)，分别调用delete函数及insert函数实现。13. 微分函数原型：voidlinklistdiff(linklist&head)输入待微分多项式头指针linklisthead，按照求导规则逐项修改系数，指数，并对原

9、常数项结点进行删除操作。实现N阶微分是在主函数中n次调用即可。14. 不定积分函数原型：voiditeintegral(linklisthead)输入多项式头指针linklisthead，无返回值按多项式积分规则逐项修改系数，指数，对不定积分中C取0。实现定积分是同时调用不定积分函数与求值函数即可。算法时空分析：无复杂嵌套，均一次遍历即可，对多项式操作复杂度均为0(N)数量级。调试及结果分析：选择键面：创建多项式：创建并打印，指数为0结束显示多项式：判断第一项前不输出+，指数正负1,0修改输出格式复制多项式：求和：a，在未修改前因访说明：为测试一个多项式先加完的情况，选择b多项式指数项系数大于

10、问b-exp，而b=NULL报错。修改分情况讨论。求差：求值:销毁：清空：修改：n阶微分：验证删除常数项微分功能，选择该实验数据不定积分：定积分：遍历每个函数验证可行，一些特殊分支的测试函数不予以列出，调试时主要解决一些健壮性问题以及一些未考虑周全的方面。实验体会和收货：1. 实验中大部分函数思路较为简单，但存在大量细节问题。如打印多项式中，系数的无效0去除，打印结果与正常书写习惯的符合性；add函数中某多项式先插完的极端情况；加减函数中结果为0项的删除；主函数中输入位置i合法性检查等。完善其在各种极端情况下的健壮性很多时候更为耗时，但却是必须的。2. 在写较大函数时应进行分块。本实验完成时，

11、我采取了完成create,print函数后逐一写运算函数的方法，尽管在单个函数调试时并未有明显障碍，但给之后调用和阅读带来极大不便，以后需要避免。3. 处理这类问题时，最复杂的步骤往往是确定和建立数据结构，本次完成实验的很大一部分时间花在了基础函数(create,insert,print)的完成上，而非简单的运算函数。4. 测试数据选择需加以仔细思考一方面是有些数据可同时测试多路，提高效率，更重要的是很多极端情况只有特定函数才能完成测试。#include#include#includetypedefstructlnodedoublecoef;intexp;structlnode*next;ln

12、ode,*linklist;除结点n2.增加结点n3.修改结点#defineN20lnode*pN=NULL;n);scanf(%d,&flag);switch(flag)case1:printf(输入删除结点指数值:);scanf(%d,&exp);linklistdelete(head,exp);break;case2:printf(输入增加结点指数值系数:);scanf(%d%lf,&exp,&coef);insert(makenode(coef,exp),head);break;case3:printf(输入指数修改后系数:);scanf(%d%lf,&exp,&coef);linkl

13、istdelete(head,exp);insert(makenode(coef,exp),head);break;voidlinklistdiff(linklist&head)linklistp=head-next;while(p!=NULL)if(p-exp=0)linklistdelete(head,0);break;elsep-coef*=p-exp;p-exp-=1;p=p-next;voiditeintegral(linklisthead)linklistp=head-next;while(p!=NULL)p-exp+=1;p-coef=p-coef/p-exp;p=p-next;

14、intmain()intflag,i;printf(*n);printf(*稀疏一元多项式运算器退出*n);*n);建多项式printf(*0.*n);示多项式*n);制多项式*n);和*n);差*n);值*n);毁多项式*n);空多项式*n);改多项式*n);定微分*n);printf(*12.定微分*n);printf(*n);while(1)printf(键入数字选择操作：);scanf(%d,&flag);switch(flag)case0:printf(thanksforusingn);return0;case1:printf(inputlocation:);scanf(%d,&i)

15、;if(pi-1=NULL)pi-1=creatlist();elseprintf(空间已被占用n);break;case2:printf(输入显示位置：);scanf(%d,&i);if(pi-1!=NULL)printlinklist(pi-1);elseprintf(该位置无多项式n);break;case3:intj;printf(input原位置复制位置:);scanf(%d%d,&i,&j);if(pi-1!=NULL&pj-1=NULL)pj-1=linklistcopy(pi-1);elseprintf(输入位置空或输出位置满);break;case4:intj,k;print

16、f(输入a,b位置，以及输出c位置:);scanf(%d%d%d,&i,&j,&k);if(pi-1!=NULL&pj-1!=NULL&pk-1=NULL)linklistadd(pi-1,pj-1,pk-1);elseprintf(位置被占用或原多项式不存在n);break;case5:intj,k;printf(输入a,b位置，以及输出c位置:);scanf(%d%d%d,&i,&j,&k);if(pi-1!=NULL&pj-1!=NULL&pk-1=NULL)linklistsub(pi-1,pj-1,pk-1);elseprintf(位置被占用或原多项式不存在n);break;case

17、6:printf(输入多项式位置:);scanf(%d,&i);if(pi-1!=NULL)doubletempx;printf(输入x值:);scanf(%lf,&tempx);printf(结果为%gn,linklistvalue(pi-1,tempx);elseprintf(该位置无多项式n);break;case7:printf(输入删除位置:);scanf(%d,&i);if(pi-1!=NULL)linklistdestroy(pi-1);elseprintf(该位置无多项式n)break;case8:printf(输入清空位置：);scanf(%d,&i);if(pi-1!=NU

18、LL)linklistclear(pi-1);elsen);printf(该位置不存在多项式break;case9:printf(输入修改对象位置:);scanf(%d,&i);if(pi-1!=NULL)linklistmodify(pi-1);elseprintf(对应位置为空n);break;case10:printf(输入微分位置:);scanf(%d,&i);printf(输入求导阶数:);intn,j;scanf(%d,&n);if(pi-1!=NULL)for(j=0;jn;j+)linklistdiff(pi-1);elseprintf(该位置无多项式n)break;case11:printf(