算法分析与设计的课程设计(一元多项式的加法、减法、乘法的实现).doc

湖南师范大学电子与信息工程系课程设计报告书一元多项式的加法、减法、乘法的实现2010-09-25hunan normal universityelectronic & information engineering department课程设计题目一元多项式的加法、减法、乘法的实现指导教师姓名指导老师职称学生姓名所属班级任务要求1) 首先判定多项式是否稀疏；2) 分别采用顺序和动态存储结构实现；3) 结果m(x)中无重复阶项和无零系数项；4) 要求输出结果的升幂和降幂两种排列情况主要实施步骤1) 9月13日9月14日：分析题目，查阅书籍，理解一元多项式加减乘的思想，对如何实现该题进行一个整体构思；2) 9月15日9月16日：确定实验所用到的数据结构，并给出抽象定义3) 9月17日9月20日：编写各模块的代码，并整合成一个系统4) 9月21日：对程序进行调试与编译5) 9月22日9月24日：美化界面，对部分不合理的地方进行修改6) 9月25日：实验完成，撰写结论结论通过课程设计，基本上完成了老师所要求的功能，但系统还有不足之处，给操作者一个不很直观的操作，希望下一步的完善中，能够改用窗体界面，从而使界面更友好；此次课程设计让我们得到了实践，不再局限于理论的学习之中。湖南师范大学工学院电子与信息工程系课程设计登记表注：此表格内容中的任务要求为指导教师提供的课程设计要求，主要实施步骤是指课程设计的时间安排，结论是指通过课程设计得出的有关结论及课程设计不足之处或进一步开发方向。目 录1引言41.1课程设计目标41.2编程工具（编程环境）介绍51.3实施时间及主要实施步骤52需求分析53系统总体设计64数据结构设计75详细设计与实现95.1功能模块1输入一元多项式详细设计105.1.1详细设计105.1.2界面设计及测试结果105.2功能模块2 创建一元多项式 详细设计105.2.1详细设计105.2.2界面设计及测试结果115.3功能模块3主菜单详细设计115.3.1详细设计115.3.2界面设计及测试结果125.4功能模块4 顺序存储的一元多项式运算 详细设计125.4.1详细设计125.4.2算法流程125.4.3界面设计及测试结果135.5功能模块5顺序存储的一元多项式运算 详细设计135.5.1详细设计135.5.2算法流程135.5.3界面设计及测试结果146 算法分析(5)7 用户手册 .(58 结论 )9 参考文献.10 附录课程设计的题目名称1引言1.1 课程设计目标设计一个一元多项式运算的系统，主要包括：加减乘法的运算。 本文是关于一个一元稀疏多项式计算器的问题。内容包括输入并建立多项式,多项式相加，多项式求导，多项式求值以及输出多项式。本文使用链式存储结构存储一元稀疏多项式，可以方便的计算简单的一元稀疏多项式的基本运算。本课程设计运用所学的一些c+知识，构成整个计算器的形成框架。在程序中定义了各种类型的运算的模块，通过主程序的调用来完成他们之间的配合，进而完善了计算器。1.2 编程工具（编程环境）介绍编程工具：microsoft visual c+编程环境：microsoft windows xp1.3 实施时间及主要实施步骤l 实施时间： 9月13日至9月25日l 基本步骤大致为： 前期分析 中期编码 后期调试2 需求分析l 本问题描述本实验要求利用带头结点的有序链表实现任意两个一元实系数的加减乘法运算。基本功能要求1首先，根据键盘输入的一元实系数多项式的系数与指数序列，对多项式进行初始化，并按未知数x的升幂形式排序。2对于从键盘输入的任意两个一元多项式，正确计算它们的和，差，积多项式，并输出结果。l 测试数据见test.txt3 系统总体设计进入界面，系统提示用户输入多项式的指数和系数并选择存储方式。然后出现操作界面，由用户选择相关操作以及按照升幂还是降幂输出。具体实现见流程图： 本程序包括5个模块：1、 输入一元多项式该模块主要是用户根据提示输入一元多项式的指数和系数2、 根据输入创建一元多项式并存储并且判断是否稀疏该模块主要是将输入的一元多项式按顺序存储方式存储，并判断是否稀疏，如果稀疏，则转换为链式方式存储3、 主菜单该模块主要是显示菜单信息，并且由用户显示要进行的步骤4、 顺序存储的一元多项式的加减乘法并输出结果 该模块主要是实现多项式的运算5、 链式存储的一元多项式的加减乘法并输出结果 该模块主要是实现多项式的运算4 数据结构设计本程序主要应用了链表，结构体和类模板。用结构体来定义多项式的结点（即每一项），它包含三个域，分别存放该项的系数、指数以及指向下一项结点的指针；用链表来存储多项式，为了节省空间，只存储多项式中系数非0 的项，用多项式链表类来实现设定的程序的基本功能。为实现上述功能定义一元多项式的抽象数据类型如下：adt polynomial数据对象：d=ai |aitermset, i=1,2,m, m10，termset中的元素包含一个实系数和一个表示指数的整数数据关系：r1= |ai-1,aid, 且ai-1中的指数值lb?la:lb; for(i=0;i=la&i=lb;i+) m.ai=a.ai+b.ai; /此处若为稀疏式，则会浪费大量时间 while(i=la) m.ai=a.ai;i+; while(ilb?la:lb; for(i=0;i=la&i=lb;i+) m.ai=a.ai-b.ai; while(i=la) m.ai=a.ai;i+; while(i=lb) m.ai=0-b.ai;i+; /b的相反数 print(m); /=/m(x)=a(m)*b(n)/void mul(polynomial a,polynomial b,polynomial &m) int i,j; for(i=0;i=a.len+b.len+1;i+) m.ai=0; /为什么要多1 for(i=0;i=a.len;i+) for(j=0;jxspb-xs) ha=pb; hb=pa; else ha=pa; hb=pb; hc=pc=(lpolynomial)malloc(sizeof(lnode); qa=ha-next; qb=hb-next; while(qa-next!=null)&(qb-next!=null) qc=(lpolynomial)malloc(sizeof(lnode); qc-next=null; switch(cmp(qa-expn,qb-expn) case -1: qc-ceof=qa-ceof; qc-expn=qa-expn; pc-next=qc; pc=qc; qa=qa-next; break; case 0: sum=qa-ceof+qb-ceof; if(sum!=0.0) qc-ceof=sum; qc-expn=qa-expn; pc-next=qc; pc=qc; qa=qa-next; qb=qb-next; break; else free(qc); qa=qa-next; qb=qb-next; break; case 1: qc-ceof=qb-ceof; qc-expn=qb-expn; pc-next=qc; pc=qc; qb=qb-next; break; if(qa-next!=null) while(qa!=null) qc=(lpolynomial)malloc(sizeof(lnode); qc-next=null; qc-ceof=qa-ceof; qc-expn=qa-expn; pc-next=qc; pc=qc; qa=qa-next; else while(qb!=null) qc=(lpolynomial)malloc(sizeof(lnode); qc-next=null; qc-ceof=qb-ceof; qc-expn=qb-expn; pc-next=qc; pc=qc; qb=qb-next; qc=(lpolynomial)malloc(sizeof(lnode); qc-next=null; prints(hc); pc-next=qc; qc-ceof=0; pa=ha; pb=hb;/=/-相减，构成和多项式 hc-/lpolynomial subtractpolyn(lpolynomial pa,lpolynomial pb) float result; lpolynomial ha,hb,hc,qa,qb,qc,pc; if(pa-xspb-xs)ha=pb; hb=pa; else ha=pa; hb=pb; qa=ha-next; qb=hb-next;hc=pc=(lpolynomial)malloc(sizeof(lnode); while(qa-next!=null)&(qb-next!=null) qc=(lpolynomial)malloc(sizeof(lnode); qc-next=null; switch(cmp(qa-expn,qb-expn) case -1: qc-ceof=qa-ceof; qc-expn=qa-expn; pc-next=qc; pc=qc; qa=qa-next; break; case 0: result=qa-ceof-qb-ceof; if(result!=0.0) qc-ceof=result; qc-expn=qa-expn; pc-next=qc; pc=qc; qa=qa-next; qb=qb-next; break; else free(qc); qa=qa-next; qb=qb-next; break; case 1: qc-ceof=0-qb-ceof; qc-expn=qb-expn; pc-next=qc; pc=qc; qb=qb-next; break; if(qa-next!=null) while(qa!=null) qc=(lpolynomial)malloc(sizeof(lnode); qc-next=null; qc-ceof=qa-ceof; qc-expn=qa-expn; pc-next=qc; pc=qc; qa=qa-next; else while(qb!=null) qc=(lpolynomial)malloc(sizeof(lnode); qc-next=null; qc-ceof=0-qb-ceof; qc-expn=qb-expn; coutceof; pc-next=qc; pc=qc; qb=qb-next; if(pa-xspb-xs) for(qc=hc;qc-next!=null;qc=qc-next) qc-ceof=0-qc-ceof; qc-ceof=0-qc-ceof; coutceof; prints(hc); pa=ha; pb=hb;lpolynomial multiplypolyn(lpolynomial pa,lpolynomial pb)/相乘，pa构成积多项式hc lpolynomial s,hc,q,p,r,ha,hb; ha=pa; hb=pb; hc=(lpolynomial)malloc(sizeof(lnode); r=hc; for(p=pa-next;p!=null;p=p-next) for(q=pb-next;q!=null;q=q-next) s=(lpolynomial)malloc(sizeof(lnode); s-ceof=p-ceof*q-ceof; s-expn=p-expn+q-expn; r-next=s; r=s; r-next=null; for(int i=20; i!=0;i-) for(q=hc;q-next!=null;q=q-next)/合并同类项 for(p=q-next;p!=null&p-next!=null;p=p-next) if(q-expn=p-next-expn) q-ceof=q-ceof+p-next-ceof; r=p-next; p-next=p-next-next; free(r); lascend(hc); prints(hc); pa=ha; pb=hb;计算多项式加减，其算法思想是相同的。以多项式加法为例，先对两多项式排序，再将两多项式的每一项逐项相加，在相加之前，先比较两项的指数是否相等，若相等则将系数相加，再判断系数是否为零，若为零则删除，否则存储在和多项式中。若两项指数不相等，当多项式pa指数大于多项式pb指数时，则将pa结点副本插入到和多项式polyc尾部；当pa指数小于pb指数时，则将pb结点副本插入到和多项式polyc尾部，最后插入剩余结点。（8）计算多项式乘法时，先判断两多项式是否为空，若为空，则返回乘多项式，否则要先对两多项式进行合并排序，先将两多项式的第一项相乘，即系数相乘，指数相加，其值作为乘多项式的第一结点，其后使用双重循环将一多项式的每一项与另一多项式的每一项分别相乘，结果存到乘多项式中。5.5.3 界面设计及测试结果6 算法分析主要的算法是对多项式的计算，分别有1、a+b：用了一个循环，循环n次，即t=o(n)2、a-b：a-b即为a+（-b），即t=o(n)3、a*b：用了两个循环来完成计算，第二个循环嵌套在第一个循环里面，即时间复杂度t=o(n2)7 结论 课程设计终于做完了，虽然有些疲劳和困倦，但带给我很多的收获。数绝结构已经学了一个学期，大概三个多月了，有许多知识