数据结构课程设计报告一元稀疏多项式计算器.doc

. . 课程设计报告 需求分析 【问题描述】 设计一个一元稀疏多项式简单计算器. 【基本要求】 一元稀疏多项式基本功能包括： 输入并建立多项式； 输出多项式，输出形式为整数序列：n, c1, e1, c2, e2, … , cn, en，其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列； 多项式a和b相加，建立多项式a+b； 多项式a和b相减，建立多项式a-b； 【测试数据】 (2x+5x8-3.1x11)+(11x9-5x8+7)=(-3.1x11+11x8+2x+7) (-1.2x9+6x-3+4.4x2-x)-(7.8x15+4.4x2-6x-3)=(-7.8x15-1.2x9+12x-3-x) (x5+x4+x3+x2+x+1)-(-x4-x3)=(x5+x2+x+1) (x3+x)-(-x3-x)=0 (x100+x)+(x200+x100)=(x200+2x100+x) (x3+x2+x)+0=x3+x2+x 互换上述测试数据中的前后两个多项式. 概要设计 ADT Polynomial{ 数据对象: D={ai|ai?TermSet, i=1,2,…,m,m≥0,TermSet中的每个元素包含一个表示系数的实数和表示指数的整数} 数据对象: R1={ai,ai-1|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 Polynomial 详细设计 【数据类型定义】 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-nextpre-next-expn=z)//原有项指数大于插入项 { pree=pre; pre=pre-next; } p-next=pre-next;//插入项 pre-next=p; if(pre-expn==p-expn)//原有项指数等于插入项 { pre-coef+=p-coef;