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

1、.课程设计报告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)=(

2、-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|aiTermSet, i=1,2,m,m0,TermSet中的每个元素包含一个表示系数的实数和表示指数的整数数据对象: R1=|ai,ai-1D,且ai-1中的指数值小于ai中的指数,i=2,m基本操作：Cre

3、atePolyn(void)Result: 指数由大到小输入m项的系数和指数,建立一元多项式pPrintPoly (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. 详细设计【数据类型定义】t

4、ypedef 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)

5、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(p

6、re-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(LN

7、ode); 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-coef0) pri

8、ntf(+%d,pre-coef); else if(pre-coefcoef); else/指数不为0 if(pre-coef0) printf(+%d*X(%d),pre-coef,pre-expn); else if(pre-coefcoef,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

9、=NULL; /建立一个空的多项式 p1=H1-next; /第一个多项式的第一项 p2=H2-next; pre=H3; / while(p1&p2) if(p1-expnp2-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)

10、; 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;

11、 while(p2) 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; while(p1) 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; return H3;Substract()LNode SubstractPolyn(LNo

12、de H1,LNode H2) /表达式相减/让系数变负，代入加法 LNode H3,pre; pre=H2-next; while(pre) pre-coef=-pre-coef; pre=pre-next; H3=AddPolyn(H1,H2); pre=H2-next; while(pre) pre-coef=-pre-coef; pre=pre-next; return H3;【函数调用关系】main()调用CreatePoly()，PrintPoly()，AddPoly()，scanf()函数输入，printf()函数输出。4. 运行记录5. 总结首次做课程设计的题目，小激动，小紧张，编程的基础比较差，所以把第二章学习