一元稀疏多项式计算器课程设计

1、软件学院课程设计报告书课程名称数据结构设计题目 一元稀疏多项式计算器专业班级软件工程11级1班学 号 07姓 名指导教师2013年 1月目录1设计时间经2设计目的43设计任务44设计内容4需求分析4程序所能达到的功能4输入的形式和输入值的范围4输出的形式4测试数据5总体设计5本程序中用到的所有抽象数据类型的定义5主程序的流程7各程序模块之间的层次（调用）关系7详细设计7实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法7对主程序和其它主要函数伪码算法11函数的调用关系图12测试与分析12测试12分析13附录135总结与展望19参考文献20成绩评定201设计时间2013年1月21日至

2、2013年1月27日2设计目的数据结构是计算机专业的核心课程，是计算机科学的算法理论基础和软件设计的技术 基础。数据结构是实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段。 要求学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并上机调试的 基本方法。课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格 实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训 练，将起到显著的促进作用。3设计任务设计一个一元稀疏多项式简单计算器4设计内容需求分析4. 1. 1.程序所能达到的功能一元稀疏多项式简单计算器的基本功能是：(1) 输入并建立

3、多项式CreatPOIynO ;(2) 输出多项式,输出形式为整数序列：n,cl,el,c2,e2,，cn,en,其中n是多项式的 项数，Ci和ei分别是第i项的系数和指数，序列按指数升序排列一一printpoIyn ()；(3) 多项式a和b相加，建立多项式a+b,输出相加的多项式addpolyn()；(4) 多项式a和b相减，建立多项式a-b,输出相减的多项式SUbPOIyno o4. 1. 2.输入的形式和输入值的范围一元稀疏多项式计算器需要输入多项式的各项的系数和指数。系数可以用实数来表 示，指数可以用整数来表示，由于整形数据在内存里占用两个字节，所以它的取值范围为 -32768327

4、6704. 1.3.输出的形式本程序要输出的是分别把创建的第一个多项式和第二个多项式按指数升序排序，并且 把计算加减后的运算结果按指数升序排列输出。4. 1.4.测试数据o回Ia(1)正确：* CU¾ersn,Pe UctopDeb sq.exe*«菽件“7班忤胜臣¾¾A82 3 12 3 X X 与与与 12糸5¾系 的敷的Es J?顶顶戏W输岀多项式42*WXF输岀多项式 b)T"2rS3×r5 岀多项式之和 0 b-3X*3 3X4*2X*5*3X *7 输出多项式之差df-5T3 3×4-2×5-

5、3X思谢梗用此程斥！Pre88 any My to COAtInlW图1程序输出(2)错误:图2程序输出总体设计4. 2. 1.本程序中用到的所有抽象数据类型的定义ADT List数据对象：D=ai aiR,i=l,2,，n,nM0数据关系：Rl=< ai-l, ai>l ai-l,aiD, ai-l,<ai, i=l,2,3,.n 基本操作：InitLiSt ()操作结果：构造一个空的有序表L。DeStrOyLiSt(L)初始条件：有序表L已存在。操作结果：销毁有序表L。LiStLength(L)初始条件：有序表L已存在。操作结果：返回有序表L的长度。CIearLiSt(

6、L )初始条件：有序表L已存在。操作结果：清空链表内容。InSbefOre ( N,N )初始条件：有序表L已存在。操作结果：插入节点到链表。 ADT OrdereCILiStADT PoIy 数据对象：D=ai iai为实数,i=l, 2,，n数据关系：Rl=O基本操作：CreatePoly( L,N )初始条件：N为节点，L为有序表。操作结果：将N插入多项式的适当位置。GetPOIy( L )操作结果：将用户输入转换为节点。PrintPoly( L )初始条件：多项式L已存在。操作结果：显示多项式。AddPoIy( L_1,L_2,L_add ) 初始条件：多项<L_l,L_2,L_

7、add已存在。I操作结果：生成L_1,L_2之和的多项式L_addDiffPOIy( L ,L diff)初始条件：多项L ,L_diff已存在。 操作结果：生成L的导圾多项式L_addoAlterPoly( L )初始条件：多项式L已存在。操作结果：将L多项式取相反数。 ADT PoIy4. 2. 2.主程序的流程图3主程序流程4. 2. 3.各程序模块之间的层次（调用）关系ma in ()图4模块层次调用关系详细设计4. 3.1实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法TyPedef POIynOmiaI4. 3. 2主程序和其它主要函数伪码算法主函数和其他函数：VOi

8、Cl Inain()int m,n；POlyn Pa=OtPb=O,pc；Printf(Hnu)；Printfcr I 软件 IlT 班*n,r);Printf(Hn)；Printf ("欢迎使用多项式操作程序n"):Printf ("请输入a的项数:");scanf (,%d, &m)；Pa=CreatePOIyn(pa,m) ；4. 3. 3 数的调用关系图图5函数调用关系测试与分析4. 4. 1测试输入：a=2X+3X2;b=2X3+7X'4输出：a+b=2X+3X2+ 2X3+7X4a-b=2X+3X2-2X3-7X4女迎使用多顶

9、式操作程序感谢便灌序！PreSS <uy key to COntinUC输岀多顶式之差Xb-2XVJT2 - 2X%7X"辑岀多顶式之和Hb=2礬3/2核八3册八4常岀多顶式b-2XA37XA4窃岀多顶式a=2X*3X2!软件门7班韩胜臣 *H 'CUscr5hscDetopDcbugj5q.cxc,Io回丸图6程序输出匕EaI Im 与与11 2 3 42 3 2 7 匕 OBruI O4XA5:2一參尔:2一基糸 顶顶顶顶 .4. 4. 2分析此一元稀疏计算器系统基本可能实现计算功能，其“加”与“减”方法都相对比较完 整，在调试程序的时候总出现错误，由于知识不全面，

10、不熟练，总需要看书但在输入数 据时，要按照严格的格式输入，否则有可能出现死去或崩溃。若本系统能加上保存功能就 更好了，因为一个系统在使用过程中总会关机等，而此系统的缺点却是没有保存功能，关 闭之后就要重新建立了。会慢慢完善。附录SinCIUdeO#include<>插入函数按指数增序插入*/VOid InSert ( POIyn p, Polyn h)/将 P 插入到 h 中if (p->coef=0) free(p):/若P的系数是O则释放该节点elsePOIyn ql,q2;ql=h;q2=h->next;WhiIe (q2&&q2->exp-

11、>expn) 找ql=q2;q2=q2->next;if(q2&&q2->expn=p->expn) 的系数相加并且赋给q2q2->coef+=p->coef； free(p)； if (!q2>coef)； ql->next=q2->next； free(q2)；elseql->next=p;p->next=q2;若P的指数大于q2的指数，则继续查若q2的指数等于P的指数则将两者把P插入到h当中建立一个头指针为POiyn CreatePOIyn(POlyn head,int m) head、项数为m的一元多项式

12、int i;POIyn p；p=head= (POlyn)ma1Ioc(SiZeOf(StrUCt POIynOmial)； head->next=NULL;for(i=0;i<m；i+)P= (POIyn)InalIOC (SiZeOf (StrUCt POIynOnliaI) ；/建立新结点以接收数据Printf ("输入第d项的系数与指数："，i+l)；SCanf (,%f %du,&p->coef ,&p->expn)；InSert (p,head)；/调用InSert函数插入结点return head；VOid DeStrO

13、yPOIyn(POIyn P) /销毁多项式 PPOlyn ql,q2;ql=p->next； q2=ql->next;WhiIe(ql->next)free(ql);ql=q2;q2=q2->next；)VOiCl PrintPOIyn(POIyn P) POIyn q=P->next；int flag=l;/项数计数器if (!q)若多项式为空，输出0PUtChar (r0,)；Print f("n")；return；Wh 订 e(q)if (q->coef>0& flag!=l) PUtChar (, + r):/系数

14、大于 O 且不是第一项if(q->coef!=l&&q->coef!=-1)/系数非1或-1的普通情况printf("%g",q->coef)；if(q->expn=l) PUtChar(rX,)；else if (q->expn) Printf CX°, q->expn)；elseif(q->coef=l)if(!q->expn) PUtChar(F1,);else if(q->expn=l) PUtChar(rXr)；else Printf(nX%dntq->expn):if(q-&g

15、t;coef=-l)if (!q->expn) Printf (,r-ln)；else if(q->expn=l) Printf("-Xn)； else Printfcr-X %du»q->expn):)q=q->next; flag+；Printf (,n)；)int COmPare(POIyn atPolyn b) if(a&&b)if(!b a->expn>b->expn) return T； else if(!a a->expn<b->expn) return 1； else return

16、0；/a多项式已空，但b多项式/b多项式已空，但a多项式求解并建立多项式a+b,返else if (!a&&b) return T；非空else return 1 ；非空POlyn AddPOIyn(POlyn PatPOIyn Pb) 回其头指针POIyn qa=pa->next；POIyrI qb=pb->next ；POIyn headcthe,qc；hc= (Polyn)malIoc (SiZeOf (StrUCt POlynOmiaI): /建立头结点 hc->next=NULL;headc=hc;WhiIe(qa qb)qc= (Polyn)mal

17、Ioc(SiZeOf(StrUCt POIynOmiaI)； SWitCh(COnlPare(qa,qb) CaSe 1:qc->coef=qa->coef；qc->expn=qa->expn;qa=qa>next； break；)CaSe 0： qc->coef=qa->coef+qb->coef ； qc->expn=qa->expn; qa=qa>next； qb=qb->next； break；CaSe 一1：qc->coef=qb->coef ； qc->expn=qb->expn; qb

18、=qb->next； break；if (qc->coef!=0)qc->next=hc->next； hc->next=qc;hc=qc;/当相加系数为O时，释放求解并建立多项式a-b,返 else free(qc)； 该结点return headc；)POlyn SUbtraCtPOIyn(POlyn pa,Polyn Pb) 回其头指针POlyn h=pb;POIyn P=Pb->next;POIyn pd；Whiie(P)将Pb的系数取反p->coef*二-1； p=p->next；Pd=AddPOIyn (Pa,h)；for (p=h-

19、>next ； p； p=p->next)恢复 Pb 的系数p->coef*=-l;return pd；)VOid Inain()int m,n;POIyn Pa=OtPb=Otpc；Printf ("n");Printf(" I 软件 11-1 班*n");Printf ("n")；Printf(M欢迎使用多项式操作程序n")；Printf ("请输入a的项数：")；SCanf("%d",&m)；Pa=CreatePOIyn(Patnl) ；/建立多项式 a

20、Printf ("请输入b的项数：")；SCanf("%d",&n)；Pb=CreatePOIyn(pb, n) ；/建立多项式 bPrintf (hn 输出多项式 a=11);PrintPOlyn(Pa)；Printf(',n 输出多项式 b=")； PrintPOIyn(Pb)；PC=ACIdPO 1 yn (Pa, Pb);Printf ("n输出多项式之和a+b=")；PrintPOlyn(PC)；PC=SUbtraC t Po1yn(Pa,Pb)；Printf ("n输出多项式之差ab=")； PrintPOIyn(PC)；Printf("n感谢使