课程设计报告1. 需求分析【问题描述】设计一个一元稀疏多项式简单计算器.【基本要求】一元稀疏多项式基本功能包括：1) 输入并建立多项式；2) 输出多项式，输出形式为整数序列：n, c1, e1, c2, e2, … , cn, en，其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列；3) 多项式a和b相加，建立多项式a+b；4) 多项式a和b相减，建立多项式a-b；【测试数据】1) (2x+5x8-3.1x11)+(11x9-5x8+7)=(-3.1x11+11x8+2x+7)2) (-1.2x9+6x-3+4.4x2-x)-(7.8x15+4.4x2-6x-3)=(-7.8x15-1.2x9+12x-3-x)3) (x5+x4+x3+x2+x+1)-(-x4-x3)=(x5+x2+x+1)4) (x3+x)-(-x3-x)=05) (x100+x)+(x200+x100)=(x200+2x100+x)6) (x3+x2+x)+0=x3+x2+x7) 互换上述测试数据中的前后两个多项式.2. 概要设计 ADT Polynomial{数据对象: D={ai|aiÎTermSet, i=1,2,…,m,m≥0,TermSet中的每个元素包含一个表示系数的实数和表示指数的整数} 数据对象: R1={|ai,ai-1ÎD,且ai-1中的指数值小于ai中的指数,i=2,…,m} 基本操作： CreatePolyn(void) Result: 指数由大到小输入m项的系数和指数,建立一元多项式p PrintPoly (LNode Head) Result: 输出一元多项式 AddPoly (LNode H1,LNode H2) Condition: 一元多项式pa,pb已存在 Result: 完成多项式相加运算,即pa=pa+pb,并销毁一元多项式pb. SubtractPoly (LNode H1,LNode H2) Condition: 一元多项式pa,pb已存在 Result: 完成多项式相减运算,即pa=pa-pb,并销毁一元多项式pb. }ADT Polynomial3. 详细设计【数据类型定义】typedef struct node{ int expn,coef; struct node *next;}Nodetype,*LNode; //定义结点类型【函数原型定义】LNode CreatePolyn(void);Void PrintPoly (LNode Head);LNode AddPolyn(LNode H1,LNode H2);LNode SubPolyn(LNode H1,LNode H2);【核心算法描述】CreatePolyn()LNode CreatePolyn(void) //创建表达式{ LNode Head,p,pre,pree; int x,z; Head=(LNode)malloc(sizeof(Nodetype)); Head->next=NULL; printf("当你输入的系数为0时，输入将结束！\n"); printf("请输入第一项系数:"); scanf("%d",&x); if(x==0) { p=(LNode)malloc(sizeof(LNode)); p->coef=0; p->expn=0; Head->next=p; p->next=NULL; } while(x!=0) { printf("请输入指数:"); scanf("%d",&z); p=(LNode)malloc(sizeof(Nodetype)); p->coef=x; p->expn=z; pre=Head; while(pre->next&&pre->next->expn>=z)//原有项指数大于插入项 { pree=pre; pre=pre->next; } p->next=pre->next;//插入项 pre->next=p; if(pre->expn==p->expn)//原有项指数等于插入项 { pre->coef+=p->coef; pre->next=p->next; free(p); } if(pre->coef==0)//系数为0 { pree->next=pre->next; free(pre); } printf("请输入系数:"); scanf("%d",&x); } if(Head->next==NULL)//多项式空 { pre=(LNode)malloc(sizeof(LNode)); pre->coef=0; pre->expn=0; pre->next=Head->next; Head->next=pre; } return Head;}PrintPolyn()void PrintPolyn(LNode Head) //输出表达式{ LNode pre; pre=Head->next; if(pre->expn==0)//指数为0 printf("%d",pre->coef); else printf("%d*X(%d)",pre->coef,pre->expn); pre=pre->next; while(pre)//系数不为0 { if(pre->expn==0)//指数为0 { if(pre->coef>0) printf("+%d",pre->coef); else if(pre->coef<0) printf("%d",pre->coef); } else//指数不为0 { if(pre->coef>0) printf("+%d*X(%d)",pre->coef,pre->expn); else if(pre->coef<0) printf("%d*X(%d)",pre->coef,pre->expn); } pre=pre->next;//遍历每一项 } printf("\n");}AddPolyn()LNode AddPolyn(LNode H1,LNode H2) //表达式相加{ LNode H3,p1,p2,p3,pre;//p1第一个多项式的项，pre p的前一项 H3=(LNode)malloc(sizeof(LNode)); H3->next=NULL; //建立一个空的多项式 p1=H1->next; //第一个多项式的第一项 p2=H2->next; pre=H3; // while(p1&&p2) { if(p1->expn>p2->expn)//第一个多项式的项的指数大于第二个的 { p3=(LNode)malloc(sizeof(LNode)); p3->expn=p1->expn; p3->coef=p1->coef; p3->next=pre->next; pre->next=p3; pre=p3; p1=p1->next; } else if(p1->expnexpn)//第一个多项式的项的指数小于第二个的 { p3=(LNode)malloc(sizeof(LNode)); p3->expn=p2->expn; p3->coef=p2->coef; p3->next=pre->next; pre->next=p3; pre=p3; p2=p2->next; } else if(p1->coef+p2->coef!=0)//相加为不0，指数相同系数相加 { p3=(LNode)malloc(sizeof(LNode)); p3->expn=p1->expn; p3->coef=p1->coef+p2->coef; p3->next=pre->next; pre->next=p3; pre=p3; p1=p1->next; p2=p2->next; } else//相加为0 { p1=p1->next; p2=p2->next; } } while(p2) { p3=(LNode)malloc(sizeof(LNode)); p3->expn=p2->expn; p3->coef=p2->coef; p3->next=pre->next; pre->next=p3; pre=p3;。
