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

1软件学院课程设计报告书课程名称数据结构设计题目一元稀疏多项式计算器专业班级软件工程11级1班学号1120010107姓名指导教师2013年1月2目录1设计时间...............................................42设计目的...............................................43设计任务...............................................44设计内容...............................................44.1需求分析..........................................44.1.1.程序所能达到的功能...........................44.1.2.输入的形式和输入值的范围.....................44.1.3.输出的形式...................................44.1.4.测试数据.....................................54.2总体设计..........................................54.2.1.本程序中用到的所有抽象数据类型的定义.........54.2.2.主程序的流程.................................74.2.3.各程序模块之间的层次（调用）关系.............74.3详细设计..........................................74.3.1实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法.....................................74.3.2.对主程序和其它主要函数伪码算法..............114.3.3.函数的调用关系图............................124.4测试与分析.......................................124.4.1测试........................................124.4.2分析........................................1334.5附录.............................................135总结与展望...........................................19参考文献...............................................20成绩评定...............................................2041设计时间2013年1月21日至2013年1月27日2设计目的数据结构是计算机专业的核心课程，是计算机科学的算法理论基础和软件设计的技术基础。数据结构是实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段。要求学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并上机调试的基本方法。课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。3设计任务设计一个一元稀疏多项式简单计算器4设计内容4.1需求分析4.1.1.程序所能达到的功能一元稀疏多项式简单计算器的基本功能是：(1)输入并建立多项式——creatpolyn()；(2)输出多项式，输出形式为整数序列：n,c1,e1,c2,e2,…,cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数升序排列——printpolyn()；(3)多项式a和b相加，建立多项式a+b，输出相加的多项式——addpolyn()；(4)多项式a和b相减，建立多项式a-b，输出相减的多项式——subpolyn()。4.1.2.输入的形式和输入值的范围一元稀疏多项式计算器需要输入多项式的各项的系数和指数。系数可以用实数来表示，指数可以用整数来表示，由于整形数据在内存里占用两个字节，所以它的取值范围为-32768—32767。4.1.3.输出的形式本程序要输出的是分别把创建的第一个多项式和第二个多项式按指数升序排序，并且把计算加减后的运算结果按指数升序排列输出。54.1.4.测试数据(1)正确：图1程序输出(2)错误：图2程序输出4.2总体设计4.2.1.本程序中用到的所有抽象数据类型的定义ADTList{数据对象：D={ai|ai∈R,i=1,2,…,n,n≧0}数据关系：R1={ai-1,ai|ai-1,ai∈D,ai-1,ai,i=1,2,3,….n}基本操作：InitList()操作结果：构造一个空的有序表L。DestroyList(L)6初始条件：有序表L已存在。操作结果：销毁有序表L。ListLength(L)初始条件：有序表L已存在。操作结果：返回有序表L的长度。ClearList(L)初始条件：有序表L已存在。操作结果：清空链表内容。Ins_before(N,N)初始条件：有序表L已存在。操作结果：插入节点到链表。}ADTOrderedListADTPoly{数据对象：D={ai|ai为实数，i=1，2，…，n}数据关系：R1={}基本操作：CreatePoly(L,N)初始条件：N为节点，L为有序表。操作结果：将N插入多项式的适当位置。GetPoly(L)操作结果：将用户输入转换为节点。PrintPoly(L)初始条件：多项式L已存在。操作结果：显示多项式。AddPoly(L_1,L_2,L_add)初始条件：多项式L_1,L_2,L_add已存在。操作结果：生成L_1,L_2之和的多项式L_addDiffPoly(L,L_diff)初始条件：多项式L,L_diff已存在。操作结果：生成L的导数多项式L_add。AlterPoly(L)初始条件：多项式L已存在。操作结果：将L多项式取相反数。}ADTPoly74.2.2.主程序的流程图3主程序流程4.2.3.各程序模块之间的层次（调用）关系图4模块层次调用关系4.3详细设计4.3.1实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法TypedefPolynomial//定义结构体类型{floatcoef;//多项式系数开始输入创建链表输出a输出b输出a+b输出a-b退出结束main()printpolynaddpolynsubpolyncreatepolyn8intexpn;//多项式指数structPolynomial*next;//多项式的下一个指针域}*Polyn,Polynomial;voidInsert(&p,&h)//定义插入函数{if(p.coef==0)//若p的系数是则释放pfree(p);else{q1=h;q2=h-next;while(q2&&q2.expnp.expn)//找到链表中第一个指数大于p的指数的项{q1=q2;q2=q2.next;}if(q2&&q2.expn==p.expn){q2.coef+=p.coef;//若p的指数与q2的指数相等则合并其系数free(p);//并释放pif(!q2.coef);//若合并后q2的系数等于0q1.next=q2.next;free(q2);//释放q2}else//把p插入到q1和q2之间{q1.next=p;p.next=q2;}}}PolynCreatePolyn(&p,m){head=p=(Polyn)malloc(sizeof(structPolynomial));//为p开辟存储空间if(!head)exit(0);p.next=NULL;for(i=0;im;i++)//用for循环控制输入的个数{head=(Polyn)malloc(sizeof(structPolynomial));//建立新结点以接收数据printf(请输入第%d项的系数与指数:\n,i+1);scanf(head.coef,head.expn);//输入项的系数和指数Insert(head,p);//调用Insert函数插入结点}9returnp;//返回p}voidDestroyPolyn(&p){//销毁多项式pq1=p.next;q2=q1.next;while(q1.next){free(q1);q1=q2;q2=q2.next;}}voidPrintPolyn(&P){intflag=1;q=P-next;if(!q){//若多项式为空，输出0putchar('0');printf(\n);return;}while(q){if(q.coef0&&flag!=1)putchar('+');//系数大于0且不是第一项if(q.coef!=1&&q.coef!=-1)//系数非1或-1的普通情况{printf(%g,q.coef);if(q.expn==1)putchar('X');elseif(q.expn)printf(X^%d,q.expn);}else{if(q.coef==1){if(!q.expn)putchar('1');elseif(q.expn==1)putchar('X');elseprintf(X^%d,q.expn);}if(q.coef==-1){if(!q.expn)printf(-1);elseif(q.expn==1)printf(-X);10elseprintf(-X^%d,q.expn);}}q=q.next;flag++;}printf(\n);}intcompare(&a,&b){//比较函数if(a&&b){if(a.expnb.expn)return-1;elseif(a.expnb.expn)return1;elsereturn0;}elseif(!a&&b)return-1;//a多项式已空，但b多项式非空elsereturn1;//b多项式已空，但a多项式非空}PolynAddPolyn(&pa,&pb){//求解并建立多项式a+b，返回其头指针qa=pa.next;qb=pb.next;headc,hc,qc;hc=(Polyn)malloc(sizeof(structPolynomial));//建立头结点hc.next=NULL;headc=hc;while(qa||qb){qc=(Polyn)malloc(sizeof(structPolynomial));switch(compare(qa,qb)){case1:{qc.coef=qa.coef;qc.expn=qa.expn;qa=qa.next;break;}case0:{qc.coef=qa.coef+qb.coef;qc.expn=qa.expn;qa=qa.next;qb=qb.next;break;}11case-1:{qc.coef=qb.coef;qc.expn=qb.expn;qb=qb.next;break;}}if(qc.coef!=0){qc.next=hc.next;hc.next=qc;hc=qc;}elsefree(qc);//当相加系数为0时，释放该结点}returnheadc;}PolynSubPolyn(&pa,&pb){//求解并建立多项式a-b，返回其头指针h=pb;p=pb.next;Polynpd;while(p){//将pb的系数取反p.coef*=-1;p=p.next;}pd=AddPolyn(pa,h);for(p=h.next;p;p=p.next)//恢复pb的系数p.coef*=-1;returnpd;}4.3.2.对主程序和其它主要函数伪码算法主函数和