《稀疏一元多项式运算器实验报告材料附源程序.doc》由会员分享,可在线阅读,更多相关《稀疏一元多项式运算器实验报告材料附源程序.doc(17页珍藏版)》请在课桌文档上搜索。
1、word稀疏一元多项式运算器问题描述:完成一元稀疏多项式运算器,完成多项式创建,显示,复制,求和,求差,求值,销毁,清空,修改,n阶微分,不定积分,定积分操作。函数功能描述如下:稀疏一元多项式运算器0.退出 退出1.创建多项式 创建并打印2.显示多项式 打印3.复制多项式 复制多项式a至空域b,非空报错4.求和 输入abc位置,c=a+b5.求差 输入abc位置,c=a-b6.求值 输入位置,double x,输出double result7.销毁多项式 销毁,使pi为NULL8.清空多项式 清空保存头指针,输出为09.修改多项式 选择插入,删除,修改删了再插10.n阶微分 输入微分位置,阶数
2、,结果存放于原位置11.不定微分 输入积分位置,不定积分,常数C取012.定微分 输入积分位置,上下限值,输出定积分结果算法描述:通过主菜单调用函数完成各项功能,函数描述见程序结构描述局部。数据结构描述:多项式每一项结点定义如下:typedef struct lnodedouble coef;int exp;struct lnode* next;lnode,*linklist;包含指向下一结点指针linklist next,存储系数的数据单元double coef,存储指数的数据单元int exp;结点名lnode,指向结点指针linklist。每一个多项式由头指针引出,头指针数组lnode*
3、 pN。每一个单元存储一多项式头指针。当多项式不存在,pi=NULL;多项式为空,pi-next=NULL,即只存在头指针。操作函数见程序结构描述局部。程序结构描述:函数包括创建结点函数,有序插入函数,打印函数,创建多项式函数,多项式清空函数,多项式销毁函数,求值函数,求和函数,求差函数,复制函数,删除结点函数,修改函数,n阶微分函数,不定积分函数。对函数原型,功能,借口逐一描述如下:1. 创建结点函数函数原型:linklist makenode(double coef, int exp)输入double型系数项,int型指数项,创建lnode结点,返回指向结点的linklist指针。功能:创
4、建新结点,在复制函数以与输入系数指数插入结点时修改多项式调用。2. 有序插入函数函数原型:void insert(linklist phead,linklist head)输入插入结点指针phead以与多项式头指针head,无返回值功能:新结点phead有序插入头结点为head的多项式按指数项降序排列,在创建,复制,修改函数中调用。3. 打印函数函数原型:void printlinklist(linklist phead)输入待打印多项式头指针phead,无返回值分别打印系数项和指数项,打印系数项是使用%g输入取消无效0,通过特殊情况讨论如exp=0,exp=1,首项的加号等情况,使多项式输出
5、符合书写习惯。功能:打印多项式4. 创建多项式函数原型:linklist creatlist()返回创建多项式头指针,调用时先在主函数中输入该多项式头指针在头指针数组中位置。实现:先假如该位置无多项式,申请头结点,之后新建数据结点,有序插入头结点对应多项式。5. 清空多项式函数原型:void linklistclear(linklist head)输入待清空多项式头结点,无返回值,将pi仅保存头结点。实现:用前后两指针,遍历多项式并逐一删去结点,最后将头指针的next域置NULL。6. 销毁多项式函数原型:void linklistdestroy(linklist &head)输入待销毁多项式
6、头结点,无返回值,将pi置NULL实现方法类似清空,删去包括head在结点。7. 多项式求值函数原型:double linklistvalue(linklist head,double x)输入待求多项式头结点,变量x值 double x,返回double型结果实现:通过exp求每一项权重,与系数coef相乘,最后累加所有结果。8. 多项式求和函数原型:void linklistadd(linklist ahead,linklist bhead,linklist &chead)输入相加两多项式a,b头指针以与输出位置c,无返回值实现:通过pa,pb遍历a,b,新建c结点比照当前位置a,b ex
7、p大小,分别做对应赋值,之后将c结点插入c多项式中*当c新结点系数为0时不进展插入9. 多项式求差函数原型:void linklistsub(linklist ahead,linklist bhead,linklist &chead)输入相减两多项式a,b头指针以与输出位置c,无返回值实现完全与求和一样10. 多项式复制函数原型:linklist linklistcopy(linklist a)输入待复制多项式头指针 linklist a,输出复制结果指针 linklist。遍历多项式a,读取每一结点coef,exp值,调用makenode函数创建新结点,插入多项式b,返回b头指针head。1
8、1. 删除多项式中一节点函数原型:int linklistdelete(linklist head, int m)输入待删除多项式头指针 linklist head,待删除项指数值int m,成功返回1,反之-1删除head中一指数为m项,修改函数中调用实现:遍历多项式,假如指数项系数为m,free(p)12. 修改多项式函数原型:void linklistmodify(linklist head)输入待修改多项式头指针 linklist head,无返回值调用函数时输入1,2,3选择插入结点,删除结点,修改结点操作删除后插入,分别调用delete函数与insert函数实现。13. 微分函数原
9、型:void linklistdiff(linklist &head)输入待微分多项式头指针linklist head,按照求导规如此逐项修改系数,指数,并对原常数项结点进展删除操作。实现N阶微分是在主函数中n次调用即可。14. 不定积分函数原型:void iteintegral(linklist head)输入多项式头指针 linklist head,无返回值按多项式积分规如此逐项修改系数,指数,对不定积分中C取0。实现定积分是同时调用不定积分函数与求值函数即可。算法时空分析:无复杂嵌套,均一次遍历即可,对多项式操作复杂度均为O(N)数量级。调试与结果分析:选择键面:创建多项式:创建并打印,
10、指数为0完毕显示多项式:判断第一项前不输出+,指数正负1,0修改输出格式复制多项式:求和:说明:为测试一个多项式先加完的情况,选择b多项式指数项系数大于a,在未修改前因访问b-exp,而b=NULL报错。修改分情况讨论。求差:求值:销毁:清空:修改:n阶微分:验证删除常数项微分功能,选择该实验数据不定积分:定积分:遍历每个函数验证可行,一些特殊分支的测试函数不予以列出,调试时主要解决一些健壮性问题以与一些未考虑周全的方面。实验体会和收货:1. 实验局部函数思路较为简单,但存在大量细节问题。如打印多项式中,系数的无效0去除,打印结果与正常书写习惯的符合性;add函数中某多项式先插完的极端情况;加
11、减函数中结果为0项的删除;主函数中输入位置i合法性检查等。完善其在各种极端情况下的健壮性很多时候更为耗时,但却是必须的。2. 在写较大函数时应进展分块。本实验完成时,我采取了完成create,print函数后逐一写运算函数的方法,尽管在单个函数调试时并未有明显障碍,但给之后调用和阅读带来极大不便,以后需要防止。3. 处理这类问题时,最复杂的步骤往往是确定和建立数据结构,本次完成实验的很大一局部时间花在了根底函数(create,insert,print)的完成上,而非简单的运算函数。4. 测试数据选择需加以仔细思考一方面是有些数据可同时测试多路,提高效率,更重要的是很多极端情况只有特定函数才能完
12、成测试。#include#include#includetypedef struct lnodedouble coef;int exp;struct lnode* next;lnode,*linklist;#define N 20lnode* pN=NULL; /p初始化 linklist makenode(double coef, int exp) /构造结点 linklist p; p=(linklist)malloc(sizeof(struct lnode); if(!p) return false;/分配失败 p-coef=coef;p-exp=exp;p-next=NULL; ret
13、urn p;void insert(linklist phead,linklist head) /新结点phead有序插入头结点为head的多项式if(phead-coef=0)free(phead);elselinklist p,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-ne
14、xt;free(q);else /假如不存在如此插入phead-next=q;p-next=phead; void printlinklist(linklist phead) /打印,传入pilinklist q=phead-next;int flag=1;if(!q)printf(0n);return;while(q)if(q-coef0&flag!=1)printf(+); /系数大于0且非第一项if(q-coef!=1&q-coef!=-1) /coef为0项不会插入printf(%g,q-coef); /省去无意义0 if(q-exp=1)putchar(X); else if(q-e
15、xp=0);else if(q-exp)printf(X%d,q-exp);elseif(q-coef=1)if(!q-exp) putchar(1);if(q-exp=1) putchar(X);else if(q-exp=0);else printf(X%d,q-exp);if(q-coef=-1)if(!q-exp) putchar(-1);if(q-exp=1) putchar(-X);else if(q-exp=0);else printf(-X%d,q-exp);q=q-next;flag+;printf(n);linklist creatlist() /创建,调用时pi=crea
16、tlistlinklist phead;linklist head; /phead为增加节点指针,head为头指针 phead=head=(linklist)malloc(sizeof(struct lnode); /申请头结点head-next=NULL;while(fabs(phead-coef)1E-8) /假如coef为0完毕phead=(linklist)malloc(sizeof(struct lnode); printf(input coef expn); scanf(%lf %d,&phead-coef,&phead-exp); if(phead-coef!=0) insert
17、(phead,head); /有序插入printlinklist(head);return head;void linklistclear(linklist head)linklist p,q;p=head-next;q=p-next;while(p!=NULL)free(p);p=q;if(q!=NULL)q=q-next;head-next=NULL;void linklistdestroy(linklist &head)linklist p,q;p=head;q=p-next;while(p!=NULL)free(p);p=q;if(q!=NULL)q=q-next;head=NULL;
18、double linklistvalue(linklist head,double x)double sum=0,t; /t:项数权重int i;linklist p;for(p=head-next;p;p=p-next)t=1;for(i=p-exp;i!=0;)if(icoef*t;return sum;void linklistadd(linklist ahead,linklist bhead,linklist &chead)linklist qa,qb,qc,hc;qa=ahead-next;qb=bhead-next;hc=(linklist)malloc(sizeof(struct
19、 lnode);hc-next=NULL; /hc为尾结点chead=hc;while(qa|qb) /qa,qb不全为NULLqc=(linklist)malloc(sizeof(struct lnode); /qc为新增结点if(qb=NULL)qc-coef=qa-coef;qc-exp=qa-exp;qa=qa-next;else if(qa=NULL) /假如a或b为null,qa-exp无意义即一条链已插完,先排除这种情况qc-coef=qb-coef;qc-exp=qb-exp;qb=qb-next;else if(qa-expqb-exp)qc-coef=qa-coef;qc-
20、exp=qa-exp;qa=qa-next;else if(qa-exp=qb-exp)qc-coef=qa-coef+qb-coef;qc-exp=qa-exp;qa=qa-next;qb=qb-next;else if(qa-expexp)qc-coef=qb-coef;qc-exp=qb-exp;qb=qb-next;if(fabs(qc-coef)1E-8) /coef非0,接入多项式qc-next=hc-next;hc-next=qc;hc=qc;elsefree(qc);void linklistsub(linklist ahead,linklist bhead,linklist
21、&chead) /减法linklist qa,qb,qc,hc;qa=ahead-next;qb=bhead-next;hc=(linklist)malloc(sizeof(struct lnode);hc-next=NULL; /hc为尾结点chead=hc;while(qa|qb) /qa,qb不全为NULLqc=(linklist)malloc(sizeof(struct lnode); /qc为新增结点if(qb=NULL)qc-coef=qa-coef;qc-exp=qa-exp;qa=qa-next;else if(qa=NULL) /假如a或b为null,qa-exp无意义即一条
22、链已插完,先排除这种情况qc-coef=-qb-coef;qc-exp=qb-exp;qb=qb-next;else if(qa-expqb-exp)qc-coef=qa-coef;qc-exp=qa-exp;qa=qa-next;else if(qa-exp=qb-exp)qc-coef=qa-coef-qb-coef;qc-exp=qa-exp;qa=qa-next;qb=qb-next;else if(qa-expexp)qc-coef=-qb-coef;qc-exp=qb-exp;qb=qb-next;if(fabs(qc-coef)1E-8) /coef非0,接入多项式qc-next
23、=hc-next;hc-next=qc;hc=qc;elsefree(qc);linklist linklistcopy(linklist a)linklist qa,bhead;qa=a-next;bhead=(lnode*)malloc(sizeof(struct lnode);bhead-next=NULL;while(qa)insert(makenode(qa-coef,qa-exp),bhead);qa=qa-next;return bhead;int linklistdelete(linklist head, int m)/删除head中的一个结点,指数为mlinklist p,q
24、;if(!head|!head-next) return -1;p=head;q=p-next;while(q&m!=q-exp)p=p-next;q=q-next;if(!q) return -1;else p-next=q-next; free(q);return 1;void linklistmodify(linklist head)int flag,exp;double coef;printf(操作选择:n1.删除结点n2.增加结点n3.修改结点n);scanf(%d,&flag);switch(flag)case 1:printf(输入删除结点指数值: );scanf(%d,&exp
25、);linklistdelete(head,exp);break;case 2:printf(输入增加结点指数值 系数: );scanf(%d %lf,&exp,&coef);insert(makenode(coef,exp),head);break;case 3:printf(输入指数 修改后系数: );scanf(%d %lf,&exp,&coef);linklistdelete(head,exp);insert(makenode(coef,exp),head);break;void linklistdiff(linklist &head) linklist p=head-next; wh
26、ile(p!=NULL) if(p-exp=0) linklistdelete(head,0); break; else p-coef*=p-exp; p-exp-=1; p=p-next;void iteintegral(linklist head)linklist p=head-next;while(p!=NULL)p-exp+=1;p-coef=p-coef/p-exp;p=p-next;int main()int flag,i;printf(*n);printf(* 稀疏一元多项式运算器 *n);printf(* 0.退出 *n);/退出printf(* 1.创建多项式 *n);/创建
27、并打印printf(* 2.显示多项式 *n);/打印printf(* 3.复制多项式 *n);/复制多项式a至空域b,非空报错printf(* 4.求和 *n);/输入abc位置,c=a+bprintf(* 5.求差 *n);/输入abc位置,c=a-bprintf(* 6.求值 *n);/输入位置,double x,输出double resultprintf(* 7.销毁多项式 *n);/销毁,使pi为NULLprintf(* 8.清空多项式 *n);/清空保存头指针,输出为0printf(* 9.修改多项式 *n);/选择插入,删除,修改删了再插printf(* 10.n阶微分 *n);
28、printf(* 11.不定微分 *n); printf(* 12.定微分 *n);printf(*n);while(1)printf(键入数字选择操作:);scanf(%d,&flag);switch(flag)case 0:printf(thanks for usingn);return 0;case 1:printf(input location:);scanf(%d,&i);if(pi-1=NULL) pi-1=creatlist();elseprintf(空间已被占用n);break;case 2:printf(输入显示位置:);scanf(%d,&i);if(pi-1!=NULL)
29、 printlinklist(pi-1);elseprintf(该位置无多项式n);break;case 3:int j;printf(input 原位置 复制位置: );scanf(%d %d,&i,&j);if(pi-1!=NULL&pj-1=NULL)pj-1=linklistcopy(pi-1);elseprintf(输入位置空或输出位置满);break;case 4:int j,k;printf(输入a,b位置,以与输出c位置: );scanf(%d %d %d,&i,&j,&k);if(pi-1!=NULL&pj-1!=NULL&pk-1=NULL)linklistadd(pi-1
30、,pj-1,pk-1);else printf(位置被占用或原多项式不存在n);break;case 5:int j,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);else printf(位置被占用或原多项式不存在n);break;case 6:printf(输入多项式位置: );scanf(%d,&i);if(pi-1!=NULL)double tempx;printf(输入x值: );scanf(%lf,&
31、tempx);printf(结果为%gn,linklistvalue(pi-1,tempx);elseprintf(该位置无多项式n);break;case 7:printf(输入删除位置: );scanf(%d,&i);if(pi-1!=NULL)linklistdestroy(pi-1);elseprintf(该位置无多项式n);break;case 8:printf(输入清空位置:);scanf(%d,&i);if(pi-1!=NULL)linklistclear(pi-1);elseprintf(该位置不存在多项式n);break;case 9:printf(输入修改对象位置: );s
32、canf(%d,&i);if(pi-1!=NULL)linklistmodify(pi-1);elseprintf(对应位置为空n);break; case 10:printf(输入微分位置: );scanf(%d,&i);printf(输入求导阶数: );int n,j;scanf(%d,&n);if(pi-1!=NULL)for(j=0;jn;j+)linklistdiff(pi-1);elseprintf(该位置无多项式n);break;case 11:printf(输入不定积分位置: );scanf(%d,&i);if(pi-1!=NULL)iteintegral(pi-1);elseprintf(该位置无多项式n);break;case 12:printf(输入定积分位置: );scanf(%d,&i);double j1,j2;printf(输入上下限: );scanf(%lf %lf,&j1,&j2);if(pi-1!=NULL)iteintegral(pi-1);printf( %g n,linklistvalue(pi-1,j1)-linklistvalue(pi-1,j2);elseprintf(该位置无多项式n);break;17 / 17