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

信息学院12级杨征元PB1221024713.10.25稀疏一元多项式运算器问题描述：完成一元稀疏多项式运算器，完成多项式创建，显示，复制，求和，求差，求值，销毁，清空，修改，n阶微分，不定积分，定积分操作。函数功能描述如下：稀疏一元多项式运算器0.退出退出1.创建多项式创建并打印2.显示多项式打印3.复制多项式复制多项式a至空域b，非空报错4.求和输入abc位置，c=a+b5.求差输入abc位置，c=a-b6.求值输入位置，doublex，输出doubleresult7.销毁多项式销毁，使p[i]为NULL8.清空多项式清空保留头指针，输出为09.修改多项式选择插入，删除，修改（删了再插）10.n阶微分输入微分位置，阶数，结果存放于原位置11.不定微分输入积分位置，不定积分，常数C取012.定微分输入积分位置，上下限值，输出定积分结果算法描述：通过主菜单调用函数完成各项功能，函数描述见程序结构描述部分。数据结构描述:多项式每一项结点定义如下：typedefstructlnode{doublecoef;intexp;structlnode*next;}lnode,*linklist;包含指向下一结点指针linklistnext，存储系数的数据单元doublecoef，存储指数的数据单元intexp；结点名lnode，指向结点指针linklist。每一个多项式由头指针引出，头指针数组lnode*p[N]。每一个单元存储一多项式头指针。当多项式不存在，p[i]=NULL；多项式为空，p[i]-next=NULL，即只存在头指针。操作函数见程序结构描述部分。程序结构描述：函数包括创建结点函数，有序插入函数，打印函数，创建多项式函数，多项式清空函数，多项式销毁函数，求值函数，求和函数，求差函数，复制函数，删除结点函数，修改函数，n阶微分函数，不定积分函数。对函数原型，功能，借口逐一描述如下：1.创建结点函数函数原型：linklistmakenode(doublecoef,intexp)输入double型系数项，int型指数项，创建lnode结点，返回指向结点的linklist指针。功能：创建新结点，在复制函数以及输入系数指数插入结点时（修改多项式）调用。2.有序插入函数函数原型：voidinsert(linklistphead,linklisthead)输入插入结点指针phead以及多项式头指针head，无返回值功能：新结点phead有序插入头结点为head的多项式内（按指数项降序排列），在创建，复制，修改函数中调用。3.打印函数函数原型：voidprintlinklist(linklistphead)输入待打印多项式头指针phead，无返回值分别打印系数项和指数项，打印系数项是使用%g输入取消无效0，通过特殊情况讨论（如exp=0,exp=1,首项的加号等情况），使多项式输出符合书写习惯。功能：打印多项式4.创建多项式函数原型：linklistcreatlist()返回创建多项式头指针，调用时先在主函数中输入该多项式头指针在头指针数组中位置。实现：先若该位置无多项式，申请头结点，之后新建数据结点，有序插入头结点对应多项式。5.清空多项式函数原型：voidlinklistclear(linklisthead)输入待清空多项式头结点，无返回值，将p[i]仅保留头结点。实现：用前后两指针，遍历多项式并逐一删去结点，最后将头指针的next域置NULL。6.销毁多项式函数原型：voidlinklistdestroy(linklist&head)输入待销毁多项式头结点，无返回值，将p[i]置NULL实现方法类似清空，删去包括head在内结点。7.多项式求值函数原型：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.多项式求差函数原型：voidlinklistsub(linklistahead,linklistbhead,linklist&chead)输入相减两多项式a,b头指针以及输出位置c，无返回值实现完全与求和相同10.多项式复制函数原型：linklistlinklistcopy(linklista)输入待复制多项式头指针linklista，输出复制结果指针linklist。遍历多项式a，读取每一结点coef,exp值，调用makenode函数创建新结点，插入多项式b，返回b头指针head。11.删除多项式中一节点函数原型：intlinklistdelete(linklisthead,intm)输入待删除多项式头指针linklisthead，待删除项指数值intm，成功返回1，反之-1删除head中一指数为m项，修改函数中调用实现：遍历多项式，若指数项系数为m，free(p)12.修改多项式函数原型：voidlinklistmodify(linklisthead)输入待修改多项式头指针linklisthead，无返回值调用函数时输入1,2,3选择插入结点，删除结点，修改结点操作（删除后插入），分别调用delete函数及insert函数实现。13.微分函数原型：voidlinklistdiff(linklist&head)输入待微分多项式头指针linklisthead，按照求导规则逐项修改系数，指数，并对原常数项结点进行删除操作。实现N阶微分是在主函数中n次调用即可。14.不定积分函数原型：voiditeintegral(linklisthead)输入多项式头指针linklisthead，无返回值按多项式积分规则逐项修改系数，指数，对不定积分中C取0。实现定积分是同时调用不定积分函数与求值函数即可。算法时空分析：无复杂嵌套，均一次遍历即可，对多项式操作复杂度均为O(N)数量级。调试及结果分析：选择键面：创建多项式：创建并打印，指数为0结束显示多项式：判断第一项前不输出+，指数正负1,0修改输出格式复制多项式：求和：说明：为测试一个多项式先加完的情况，选择b多项式指数项系数大于a，在未修改前因访问b-exp，而b=NULL报错。修改分情况讨论。求差：求值:销毁：清空：修改：n阶微分：验证删除常数项微分功能，选择该实验数据不定积分：定积分：遍历每个函数验证可行，一些特殊分支的测试函数不予以列出，调试时主要解决一些健壮性问题以及一些未考虑周全的方面。实验体会和收货：1.实验中大部分函数思路较为简单，但存在大量细节问题。如打印多项式中，系数的无效0去除，打印结果与正常书写习惯的符合性；add函数中某多项式先插完的极端情况；加减函数中结果为0项的删除；主函数中输入位置i合法性检查等。完善其在各种极端情况下的健壮性很多时候更为耗时，但却是必须的。2.在写较大函数时应进行分块。本实验完成时，我采取了完成create,print函数后逐一写运算函数的方法，尽管在单个函数调试时并未有明显障碍，但给之后调用和阅读带来极大不便，以后需要避免。3.处理这类问题时，最复杂的步骤往往是确定和建立数据结构，本次完成实验的很大一部分时间花在了基础函数(create,insert,print)的完成上，而非简单的运算函数。4.测试数据选择需加以仔细思考一方面是有些数据可同时测试多路，提高效率，更重要的是很多极端情况只有特定函数才能完成测试。#includestdio.h#includemalloc.h#includemath.htypedefstructlnode{doublecoef;intexp;structlnode*next;}lnode,*linklist;#defineN20lnode*p[N]={NULL};//p[]初始化linklistmakenode(doublecoef,intexp){//构造结点linklistp;p=(linklist)malloc(sizeof(structlnode));if(!p)returnfalse;//分配失败p-coef=coef;p-exp=exp;p-next=NULL;returnp;}voidinsert(linklistphead,linklisthead){//新结点phead有序插入头结点为head的多项式内if(phead-coef==0)free(phead);else{linklistp,q;p=head;q=head-next;while(q){if(phead-exp=q-exp)break;//p做后指针，寻找插入位置p=q;q=q-next;}if(q&&phead-exp==q-exp){//若存在exp相同，合并q-coef+=phead-coef;free(phead);if(!q-coef){//若合并系数为0，删除p-next=q-next;free(q);}}else{//若不存在则插入phead-next=q;p-next=phead;}}}voidprintlinklist(linklistphead){//打印，传入p[i]linklistq=phead-next;intflag=1;if(!q){printf(0\n);return;}while(q){if(q-coef0&&flag!=1)printf(+);//系数大于0且非第一项if(q-coef!=1&&q-coef!=-1){//coef为0项不会插入printf(%g,q-coef);//省去无意义0if(q-exp==1)putchar('X');elseif(q-exp==0);elseif(q-exp)printf(X^%d,q-exp);}else{if(q-coef==1){if(!q-exp)putchar('1');if(q-exp==1)putchar('X');elseif(q-exp==0);elseprintf(X^%d,q-exp);}if(q-coef==-1){if(!q-exp)putchar('-1');if(q-exp==1)putchar('-X');elseif(q-exp==0);elseprintf(-X^%d,q-exp);}}q=q-next;flag++;}printf(\n);}linklistcreatlist(){//创建，调用时p[i]=creatlistlinklistphead;linklisthead;//phead为增加节点指针，head为头指针phead=head=(linklist)malloc(sizeof(structlnode));//申请头结点head-next=NULL;while(fabs(phead-coef)1E-8){//若coef为0结束phead=(linklist)malloc(sizeof(structlnode));printf(inputcoefexp\n);scanf(%lf%d,&phead-coef,&phead-exp);if(phead-coef!=0)insert(phead,head);//有序插入}printlinklist(head);returnhead;}voidlinklistclear(linklisthead){linklistp,q;p=head-next;q=p-next;while(p!=NULL){free(p);p=q;if(q!=NULL)q