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

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阶微分 输入微分位置，阶数，结果存放于原位置11.不定微分 输入积分位置，不定积分，常数C取012.定微分 输入积分位置，上下限值，输出定积分结果算法描述：通过主菜单调用函数完成各项功能，函数描述见程序结构描述局部。数据结构描述:多项式每一项结点定义如下：typedef struct lnodedouble coef;int exp;struct lnode* next;lnode,*linklist;包含指向下一结点指针linklist next，存储系数的数据单元double coef，存储指数的数据单元int exp；结点名lnode，指向结点指针linklist。每一个多项式由头指针引出，头指针数组lnode* pN。每一个单元存储一多项式头指针。当多项式不存在，pi=NULL；多项式为空，pi->next=NULL，即只存在头指针。操作函数见程序结构描述局部。程序结构描述：函数包括创建结点函数，有序插入函数，打印函数，创建多项式函数，多项式清空函数，多项式销毁函数，求值函数，求和函数，求差函数，复制函数，删除结点函数，修改函数，n阶微分函数，不定积分函数。对函数原型，功能，借口逐一描述如下：1. 创建结点函数函数原型：linklist makenode(double coef, int exp)输入double型系数项，int型指数项，创建lnode结点，返回指向结点的linklist指针。功能：创建新结点，在复制函数以与输入系数指数插入结点时修改多项式调用。2. 有序插入函数函数原型：void insert(linklist phead,linklist head)输入插入结点指针phead以与多项式头指针head，无返回值功能：新结点phead有序插入头结点为head的多项式按指数项降序排列，在创建，复制，修改函数中调用。3. 打印函数函数原型：void printlinklist(linklist phead)输入待打印多项式头指针phead，无返回值分别打印系数项和指数项，打印系数项是使用%g输入取消无效0，通过特殊情况讨论如exp=0,exp=1,首项的加号等情况，使多项式输出符合书写习惯。功能：打印多项式4. 创建多项式函数原型：linklist creatlist()返回创建多项式头指针，调用时先在主函数中输入该多项式头指针在头指针数组中位置。实现：先假如该位置无多项式，申请头结点，之后新建数据结点，有序插入头结点对应多项式。5. 清空多项式函数原型：void linklistclear(linklist head)输入待清空多项式头结点，无返回值，将pi仅保存头结点。实现：用前后两指针，遍历多项式并逐一删去结点，最后将头指针的next域置NULL。6. 销毁多项式函数原型：void linklistdestroy(linklist &head)输入待销毁多项式头结点，无返回值，将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 exp大小，分别做对应赋值，之后将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。11. 删除多项式中一节点函数原型：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. 微分函数原型：void linklistdiff(linklist &head)输入待微分多项式头指针linklist head，按照求导规如此逐项修改系数，指数，并对原常数项结点进展删除操作。实现N阶微分是在主函数中n次调用即可。14. 不定积分函数原型：void iteintegral(linklist head)输入多项式头指针 linklist head，无返回值按多项式积分规如此逐项修改系数，指数，对不定积分中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. 测试数据选择需加以仔细思考一方面是有些数据可同时测试多路，提高效率，更重要的是很多极端情况只有特定函数才能完成测试。#include<stdio.h>#include<malloc.h>#include<math.h>typedef 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; return 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->next;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->coef>0&&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->exp=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=creatlistlinklist 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(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;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(i<0)t=t/x;i+;elset=t*x;i-;sum+=p->coef*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 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->exp>qb->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->exp<qb->exp)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 &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无意义即一条链已插完，先排除这种情况qc->coef=-qb->coef;qc->exp=qb->exp;qb=qb->next;else if(qa->exp>qb->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->exp<qb->exp)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);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;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);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; while(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");/创建并打印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");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) 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,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",&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("输入修改对象位置: ");scanf("%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;j<n;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