一元稀疏多项式的加法运算数据结构实习.doc

-实习一线性表、栈和队列及其应用 一元稀疏多项式的加法运算【问题描述】设计一个实现一元稀疏多项式相加运算的演示程序。【根本要求】1输入并建立两个多项式；2多项式a与b相加，建立和多项式c；3输出多项式a,b,c。输出格式：比方多项式a为：A(*)=c1*e1+ c2*e2+ cm*em，其中，ci和ei分别为第i项的系数和指数，且各项按指数的升幂排列，即0e1e2em。多项式b,c类似输出。【测试数据】1(1+*+*2+*3+*4+*5)+(-*3-*4)=(1+*+*2+*5)2(*+*100)+(*100+*200)=(*+2*100+*200)3(2*+5*8-3*11)+(7-5*8+11*9)=(7+2*+11*9-3*11)一需求分析1.输入的形式和输入值的围：输入是从键盘输入的，输入的容为多项式的系数和指数，其中多项式的每一项分别以一个系数和指数的形式输入，不带未知数*，系数为任意的实数，指数为任意的整数。要完毕该多项式的输入时，输入的指数和系数都为0.2. 输出的形式从屏幕输出，显示用户输入的多项式，并显示多项式加减以后的多项式的值，并且多项式中将未知数*表示了出来. 形式为：+c1*e1+c2*e2+ci*ei+(ci和ei分别是第i项的系数和指数，序列按指数升序排列。)当多项式的*一项的系数为+1或者-1时侧该项多项式的输出形式为*ei或-*ei；当该项的系数为正时输出+ci*ei,当为负数时则输出ci*ei3. 程序所能到达的功能输入并建立多项式，实现一元稀疏多项式的相加并输出。4. 注意：所有多项式都必须以指数升密形式输入。5. 测试数据为1(1+*+*2+*3+*4+*5)+(-*3-*4)=(1+*+*2+*5)2(*+*100)+(*100+*200)=(*+2*100+*200)3(2*+5*8-3*11)+(7-5*8+11*9)=(7+2*+11*9-3*11)二设计1.设计思路1.储存构造：链式存储2. 主要算法根本思路首先定义一个多项式的构造体，存放多项式每一项的系数和指数以及ne*t指针；然后定义两个指针，第一个指针指向第一个多项式，第二个指针指向第二个多项式。然后比较两个多项式第一项的指数的大小，如果两个多项式的指数一样，则将他们的系数相加，指数不变；如果不同则比较他们指数的大小，并将指数小的放在第一项。然后指向指数小的那一项的指针后移，它的指数去和刚刚必然的那一项的指向相比较直至两个多项式相加完。其中如果*二项的系数相加后为0，则该项不输出。相加时的程序如下：pnode * add(pnode *heada,pnode *headb) /多项式相加/pnode *headc,*p,*q,*s,*r;float *;p=heada; /p指针指向第一个多项式的第一项/q=headb; /q指针指向第二个多项式的第一项/ headc=(pnode *)malloc(sizeof(pnode); /为两式相加的结果c申请存/ r=headc; /r指向结果/ while(p!=NULL&&q!=NULL) /判断两个式子都合法/if(p->e=q->e ) /指数一样时系数相加/*=p->c+q->c;if(*!=0)s=(pnode *)malloc(sizeof(pnode); s->c=*;s->e=p->e;r->ne*t=s;r=s;q=q->ne*t;p=p->ne*t; /指向多项式的下一项/else if(p->e>q->e) /多项式按升幂排序/s=(pnode *)malloc(sizeof(pnode);s->c=q->c;s->e=q->e;r->ne*t=s;r=s;q=q->ne*t;elses=(pnode *)malloc(sizeof(pnode);s->c=p->c;s->e=p->e;r->ne*t=s;r=s;p=p->ne*t;while(p!=NULL) /第一个式子不为0时的相加法则/s=(pnode *)malloc(sizeof(pnode);s->c=p->c;s->e=p->e;r->ne*t=s;r=s;p=p->ne*t;while(q!=NULL) /第二个式子不为0的相加法则/s=(pnode *)malloc(sizeof(pnode);s->c=q->c;s->e=q->e;r->ne*t=s;r=s;q=q->ne*t;r->ne*t=NULL;headc=headc->ne*t; /c的指向依次指向下一项/return headc; /返回两式相加的结果/2.设计表示1函数调用关系图main->create()->create()->add()->display()->display()->display()2函数规格接口说明 pnode * creat() /*此函数时用来创立多项式的*/ void display(pnode *head) /*head为每个多项式的头指针*/ pnode * add(pnode *heada,pnode *headb) /* heada headb为两个多项式的头指针*/3.实现注释1根据提示输入多项式每一项的指数和系数，完毕该多项式的输入时系数和指数都应该输入0。2可以输入任何指数型式的多项式。4.详细设计主要算法的细化输出函数如下： void display(pnode *head) /多项式输出/pnode *p;int one_time=1; p=head; while(p!=NULL) /判断头结点非空/if(one_time=1)if(p->e=0) /当指数为0即*o时只需要输出系数c/printf("%f",p->c); else if(p->c=1) /系数为1时输出*ei/printf("*%d",p->e);else if(p->c=-1 ) /系数为-1时输出-*ei/printf("-*%d",p->e);else if(p->c>0) /系数大于0时系数前面带"+/printf("+%f*%d",p->c,p->e);else if(p->c<0) /系数为副时原样输出/printf("%f*%d",p->c,p->e);one_time=0;elseif(p->e=0)if(p->c!=0)printf("+%f",p->c);else if(p->c=1) /系数为1时输出*ei/printf("+*%d",p->e);else if(p->c=-1 ) /系数为-1时输出-*ei/printf("-*%d",p->e);else if(p->c>0) /系数大于0时系数前面带"+printf("+%f*%d",p->c,p->e); else if(p->c<0) /系数为副时原样输出/;printf("%f*%d",p->c,p->e) p=p->ne*t;printf("n");主函数如下： void main()pnode * a,*b,*c; /定义三个多项式/ printf("input the first:n"); /输入第一个多项式/ a=creat(); /调用创立函数，创立第一个多项式/ printf("input the second:n"); /输入第二个多项式/b=creat(); /调用创立函数，创立第二个多项式/ c=add(a,b); /调用相加函数/printf("the first:");display(a); /输出第一个多项式/ printf("the second:");display(b); /输出第二个多项式/ printf("sum is:");display(c); /输出两多项式相加的结果/相加局部见算法设计局部。三调试分析1.调试遇到的主要问题以及解决方案： a刚写程序时输出时没有分系数大于0和小于0分，输出的形式都为 printf("%f*%d, p->c,p->e ),结果两个多项式相加时当*相邻两项时，中间的加号没有表示出来。所以我就将系数分为大于0和小于0来分，输出形式为if(p->c>0)printf("+%f*%d",p->c,p->e);else if(p->c<0)printf("%f*%d",p->c,p->e);b 刚开场多项式输入时没有按升幂的形式输入，结果运行的结果怎么都不对，然后将它按升幂的形式输入后就可以了。c 刚开场时没有考虑完毕多项式的输入时该则么弄，结果运行时一直都在输入第一个多项式，怎么都完毕不了，直到将完毕位的系数和指数都设置为0时才解决了这个问题。2.时间和空间复杂度的分析：时间复杂度为：On空间复杂度为：On3 改进设想 A 由于两个多项式的*两项相加为0时是不输出数的，所以当两个多项式相加为0时，结果什么都不输出为空值，一直想方法改进，却没有什么结果，所以想在这方面改进一下； B 由于多项式的系数为正时，输出的形式中带有一个"+，所以当多项式的第一项的系数为正值时总会带有一个"+，觉得很别扭。但如果输出形式中不带"+，结果中两个不同项之间有没有"+，与偶以很苦恼。C由于没有菜单函数，所以每次只能显示本次相加的两的多项式，而不能显示前一次货前几次的多项式，所以想在此方面做一些改进，产生一个菜单，包括：进去多项式相加程序帮助功能 .退出。让用户在没有退出之前都能看见每一次多项式相加的过程和结果，并在不懂的时候能获得帮助。4 .经历与体会：一直都知道C语言学的很差，但是最根本的编程还是能完成的，但是这次实习让我知道原来的我的编程能力是如此之差，它让我很深刻的认识到我的根底功没有打扎实，我还要多下功夫。学数据构造式好多东西都是纸上谈兵，以为懂了，结果上机的时候什么都不知道。这次实习也让我认识到时间的重要性，我知道光有利临时没有用的，必须将理论与实际结合起来。四运行结果验证1(1+*+*2+*3+*4+*5)+(-*3-*4)=(1+*+*2+*5)截图为验证2(*+*100)+(*100+*200)=(*+2*100+*200)截图为验证3(2*+5*8-3*11)+(7-5*8+11*9)=(7+2*+11*9-3*11)截图为六源程序清单*include<stdio.h>*include<malloc.h>*include<stdlib.h>*include<conio.h>typedef struct pnode /定义构造体/float c; /系数/int e; /指数/struct pnode *ne*t; /指向多项式下一项的指针/pnode;pnode * creat() /创立多项式/int m;float n; pnode *head,*rear,*s;head=(pnode *)malloc(sizeof(pnode); /申请存空间/ rear=head; printf("input c:"); scanf("%f",&n); /输入系数/ printf("input e:"); /输入指数/scanf("%d",&m); while(n!=0) /当系数不为0时输入多项式/s=(pnode *)malloc(sizeof(pnode); /申请存空间/ s->c=n; s->e=m;s->ne*t=NULL; /ne*t指针置空/rear->ne*t=s; /定义ne*t指针/ rear=s; printf("input c:");scanf("%f",&n); /输入下一项的系数/ printf("input e:");scanf("%d",&m); /输入下一项的指数/head=head->ne*t;return head; /返回头结点/void display(pnode *head) /多项式输出/pnode *p;int one_time=1; p=head; while(p!=NULL) /判断头结点非空/if(one_time=1)if(p->e=0) /当指数为0即*o时只需要输出系数c/printf("%f",p->c); else if(p->c=1) /系数为1时输出*ei/printf("*%d",p->e);else if(p->c=-1 ) /系数为-1时输出-*ei/printf("-*%d",p->e);else if(p->c>0) /系数大于0时系数前面带"+/printf("+%f*%d",p->c,p->e);else if(p->c<0) /系数为副时原样输出/printf("%f*%d",p->c,p->e);one_time=0;elseif(p->e=0)if(p->c!=0)printf("+%f",p->c);else if(p->c=1) /系数为1时输出*ei/printf("+*%d",p->e);else if(p->c=-1 ) /系数为-1时输出-*ei/printf("-*%d",p->e);else if(p->c>0) /系数大于0时系数前面带"+printf("+%f*%d",p->c,p->e); else if(p->c<0) /系数为副时原样输出/;printf("%f*%d",p->c,p->e) p=p->ne*t;printf("n");pnode * add(pnode *heada,pnode *headb) /多项式相加/pnode *headc,*p,*q,*s,*r;float *;p=heada; /p指针指向第一个多项式的第一项/q=headb; /q指针指向第二个多项式的第一项/ headc=(pnode *)malloc(sizeof(pnode); /为两式相加的结果c申请存/ r=headc; /r指向结果/ while(p!=NULL&&q!=NULL) /判断两个式子都合法/if(p->e=q->e ) /指数一样时系数相加/*=p->c+q->c;if(*!=0)s=(pnode *)malloc(sizeof(pnode); s->c=*;s->e=p->e;r->ne*t=s;r=s;q=q->ne*t;p=p->ne*t; /指向多项式的下一项/else if(p->e>q->e) /多项式按升幂排序/s=(pnode *)malloc(sizeof(pnode);s->c=q->c;s->e=q->e;r->ne*t=s;r=s;q=q->ne*t;elses=(pnode *)malloc(sizeof(pnode);s->c=p->c;s->e=p->e;r->ne*t=s;r=s;p=p->ne*t;while(p!=NULL) /第一个式子不为0时的相加法则/s=(pnode *)malloc(sizeof(pnode);s->c=p->c;s->e=p->e;r->ne*t=s;r=s;p=p->ne*t;while(q!=NULL) /第二个式子不为0的相加法则/s=(pnode *)malloc(sizeof(pnode);s->c=q->c;s->e=q->e;r->ne*t=s;r=s;q=q->ne*t;r->ne*t=NULL;headc=headc->ne*t; /c的指向依次指向下一项/return headc; /返回两式相加的结果/void main()pnode * a,*b,*c; /定义三个多项式/ printf("input the first:n"); /输入第一个多项式/ a=creat(); /调用创立函数，创立第一个多项式/ printf("input the second:n"); /输入第二个多项式/b=creat(); /调用创立函数，创立第二个多项式/ c=add(a,b); /调用相加函数/printf("the first:");display(a); /输出第一个多项式/ printf("the second:");display(b); /输出第二个多项式/ printf("sum is:");display(c); /输出两多项式相加的结果/. z.