《一元多项式计算器课设报告.docx》由会员分享，可在线阅读，更多相关《一元多项式计算器课设报告.docx（53页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、,上 海 电 机 学 院 课 程 设 计 报 告课设课题： 算法设计与分析一元多项式计算器学 院： 电 子 信 息 学 院 1专 业： 软件工程 1姓 名： 许家隆 班 级： BX1211 1指导老师： 王淮亭 1报告日期： 2015年7月18日 年 月 制目录第1章 绪论31.1设计目的31.2课程基本要求31.3运行环境21.4开发目标2第2章 需求分析32.1可行性分析32.2功能需求32.3性能需求3第3章 总体结构设计43.1一元多项式计算器4第4章 子模块设计54.1算法概述54.2一元多项式创建84.3 一元多项式相加94.4一元多项式相减104.5一元多项式相乘104.6一元多
2、项式输出114.7一元多项式删除124.8退出12第5章 编程实现135.1一元多项式计算器135.2克鲁斯卡尔算法17第6章 测试结果206.1运行环境206.2一元多项式计算器运行结果206.3克鲁斯卡尔算法22小结24参考文献25附录26第1章 绪论1.1设计目的算法设计与分析是一门实践性较强的软件基础课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。1.2课程基本要求（1）设计一个稀疏多项式简单
3、计算器基本要求：1) 输入并分别建立多项式A和B2) 输入输出多项式，输入形式为整数序列：c1,e1,c2,e2，ci和ei是第i项的系数和指数，序列按指数降序排列。3) 完成两个多项式的相加、相减、相乘，并将结果输出；（2）若要在n个城市之间建设通信网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。基本要求：1) 利用克鲁斯卡尔算法求网的最小生成树。2) 以文本形式输出生成树中各条边以及他们的权值。3) 以此图为例设计程序1.3运行环境开发平台：Visual C+6.0，Eclipse开发语言：C+，java运行平台：Windows 71.4开发
4、目标本系统属于使用者对一元多项式计算的各种操作的系统，可以有效地对一元多项式进行计算，本系统应达到以下目标：（1）系统采用人机交互的方式，界面美观友好，信息查询灵活、方便，数据存储安全可靠。（2）实现对多项式的建立保存。（3）可输出多项式，以及进行多项式的运算并输出。第2章 需求分析2.1可行性分析一元多项式的运算，虽然无法直接在除数学外的其他领域作出贡献，但是在数学上，它可以为人们解决一些自己动笔动手很难解决的问题，比如说那些很长很长的多项式，用笔算可能要算半天，但是用该程序，只需短短的几秒钟，所以它给人们带来了不少方便，同时相信它也能间接地为其他领域做出贡献，所以研究此课题也是非常必要的。
5、2.2功能需求此算法预计达到功能：（1）建立两个多项式进行保存；（2）可输入输出多项式；（3）两个多项式可进行相加、减以及乘法的运算。2.3性能需求为了保证系统能够长期、安全、稳定、可靠、高效的运行，本系统应满足以下性能需求。（1）系统处理的准确性和及时性系统处理的准确性和及时性是系统的必要性能。在系统设计和开发工程中，要充分考虑系统当前和将来可能承受的工作量，使系统的处理能力和相应时间能够满足使用者对系统的需求。（2）系统相应速度一元多项式计算器在日常处理中的速度为秒级，达到实时要求，以及时反馈信息。在进行计算分析时，根据所需数量的不同而从秒级到分钟级，原则是保证使用人员不会应速度问题而影响
6、工作效率。第3章 总体结构设计3.1一元多项式计算器3.1.1设计思路该系统使用C+语言进行开发和实现，程序中的各个功能分别由不同的的函数实现，然后在main函数中调用实现。其设计思路基于结构化的程序设计和链表的存储等，应用了高级语言程序设计中的基本控制结构，如循环和选择等。3.1.2设计方案 先定义链表类型结点和一元多项式，然后申明各功能函数并分别编写这些功能函数的算法，然后定义一个菜单函数Menu()，最后在main()函数中分别调用这些函数，其中输入的数据则由链表进行储存。3.1.3总体设计框架图其系统结构图如图3-1所示：图3-1 一元多项式的四则运算第4章 子模块设计4.1算法概述4
7、.1.1递归算法调用子程序的含义：在过程和函数的学习中，我们知道调用子程序的一般形式是：主程序调用子程序A，子程序A调用子程序B，如图如示，这个过程实际上是：当主程序执行到调用子程序A语句时，系统保存一些必要的现场数据，跳转到子程序A（为了说得简单些，我这里忽略了参数传递这个过程）。当子程序A执行到调用子程序B语句时，系统作法如上，跳转到子程序B。子程序B执行完所有语句后，跳转回子程序A调用子程序B语句的下一条语句，子程序A执行完后，跳转回主程序调用子程序A语句的下一条语句，主程序执行到结束。做个比较：我在吃饭（执行主程序）吃到一半时，某人叫我（执行子程序A），话正说到一半，电话又响了起来（执
8、行子程序B），我只要先接完电话，再和某人把话说完，最后把饭吃完认识递归函数我们在高中时都学过数学归纳法，例：求 n！ 我们可以把n！这么定义 也就是说要求3！，我们必须先求出2！，要求2！，必须先求1！，要求1！，就必须先求0！，而0!=1，所以1!=0!*1=1，再进而求2!，3!。分别用函数表示，则如图： 我们可以观察到，除计算0！子程序外，其他的子程序基本相似，我们可以设计这么一个子程序：int factorial(int i) int res; res=factorial(I-1)*i; return res; 那么当执行主程序语句s=factorial(3)时，就会执行factori
9、al(3),但在执行factorial(3)，又会调用factorial(2)，这时大家要注意，factorial(3)和factorial(2)虽然是同一个代码段，但在内存中它的数据区是两份！而执行factorial(2)时又会调用factorial（1），执行factorial（1）时又会调用factorial（0），每调用一次factorial函数，它就会在内存中新增一个数据区，那么这些复制了多份的函数大家可以把它看成是多个不同名的函数来理解；但我们这个函数有点问题，在执行factorial（0）时，它又会调用factorial（1）。造成死循环，也就是说，在factorial函数中，我
10、们要在适当的时候保证不再调用该函数，也就是不执行res=factorial(I-1)*i;这条调用语句。所以函数要改成： int factorial(int i) int res; if (I0) res=factorial(I-1)*i; else res=1;return res; 那么求3!的实际执行过程如图所示： 算法分析递归是一种很古老的算法，其应用的也十分的广泛，在很多复杂的程序中也是经常性的使用，虽然其的程序编写相对的简单，但其确消耗很多的资源，在没有好的算法的前提下，这是相对能够运行的算法，当然这也是在编程着能够拥有一定的编写能力的基础上的。递归的优点是：编写简单，缺点是：消耗
11、资源大。八皇后问题是一个经典的数据结构问题用递归是最为常见的方法，由于递归是自己套自己，把八皇后问题的调用函数在代码界面上融合到了一个函数中。该算法中所有语句的频度之和(即算法的时间耗费)为： T(n)=2n3+3n2+2n+1当n趋向于无穷时，其时间复杂度为O(n3)。4.1.2克鲁斯卡尔算法此次我们设计的这个在n个城市之间建设的通信网络，用最小生成树的方法，算出经济代价最小的网络。我们首先要把通信网络所有的带权值的边生成出来，即所有城市顶点间的全连接。接着，利用堆排序算法把所有的带权值的边，从小到大排列起来。然后，用克鲁斯卡尔算法，求出最小生成树。类的设计：我们抽象出一个带权值边的类cla
12、ss Edge，它有三个属性（private int start, end, value;），即起点、终点和权值。其余的都放到main（）函数里了。例如图为依照克鲁斯卡尔算法构造一棵最小生成树的过程。代价分别为1，2，3，4的四条边由于满足上述条件，则先后被加入到T中，代价为5的两条边（1，4）和（3，4）被舍去。因为它们依附的两顶点在同一连通分量上，它们若加入T中，则会使T中产生回路，而下一条代价（=5）最小的边（2，3）联结两个连通分量，则可加入T。因此，构造成一棵最小生成树。上述算法至多对e条边各扫描一次，假若以“堆”来存放网中的边，则每次选择最小代价的边仅需O（loge）的时间（第一次
13、需O（e）。又生成树T的每个连通分量可看成是一个等价类，则构造T加入新的过程类似于求等价类的过程，由此可以以“树与等价类”中介绍的mfsettp类型来描述T，使构造T的过程仅需用O（eloge）的时间，由此，克鲁斯卡尔算法的时间复杂度为O（eloge）4.2一元多项式创建创建操作流程图如下图所示： N Y图4-1 一元多项式创建4.3 一元多项式相加先判断多项式的系数与项数之间大小关系，流程图如下所示：NN Y Y N N Y N图4-2一元多项式相加流程图4.4一元多项式相减相减即取第二个的相反数，然后进行加法运算，操作流程图如下图所示： 图4-3一元多项式相减流程图4.5一元多项式相乘相乘
14、操作流程图如下图所示：将运算的结果相加并输出图4-4一元多项式相乘流程图4.6一元多项式输出先判断录入的两个多项式是否有空项，如果两个多项式都不是空的，那么顺序输出多项式A和多项式B，否则多项式创建不成功，提示重新输入。操作流程图如下图所示： Y N图4-5一元多项式输出流程图4.7一元多项式删除先判断存储多项式的链表类型结点是否都不为空结点，若有空结点，则提示重新选择，否则，按顺序销毁多项式A,B。操作流程图如下图所示： N Y 图4-6一元多项式销毁流程图4.8退出本过程较为简单，用exit(0)强制终止程序，返回状态码0表示正常结束。其操作流程图如下图所示：提示退出图4-7一元多项式退出
15、流程图第5章 编程实现5.1一元多项式计算器5.1.1功能函数void CreateLink(Link &L,int n);void PrintList(Link L);void PolyAdd(Link &pc,Link pa,Link pb);void PolySubstract(Link &pc,Link pa,Link pb);void CopyLink(Link &pc,Link pa);void PolyMultiply(Link &pc,Link pa,Link pb);int JudgeIfExpSame(Link pa,Link e);void DestroyLink(Lin
16、k &L);int CompareIfNum(int i);5.1.2主函数void main()int n;Link L,La=NULL,Lb=NULL;/La,Lb分别为创建的两个多项式int choose;while(1) Menu(); /调用菜单函数cinchoose;switch(choose)case 1:coutn;if(CompareIfNum(n)=1)cout 您的输入有误，请重新输入endl;Clear();break;CreateLink(La,n);coutn;if(CompareIfNum(n)=1)cout 您的输入有误，请重新输入endl;Clear();br
17、eak;CreateLink(Lb,n);Clear();break; case 2:if(La=NULL|Lb=NULL)cout 您的多项式创建有误，请重新选择endl;Clear();break;PolyAdd(L,La,Lb);coutendl;cout 设相加的两个一元多项式为和则：endl;coutendl;cout A的多项式为：;PrintList(La);coutendl;cout B的多项式为：;PrintList(Lb);coutendl; cout 相加后的结果为：;PrintList(L);coutendl;Clear();DestroyLink(L);break;c
18、ase 3:if(La=NULL|Lb=NULL)cout 您的多项式创建有误，请重新选择endl;Clear();break;PolySubstract(L,La,Lb);cout 设相减的两个一元多项式为和则：endl;coutendl;cout A的多项式为：;PrintList(La);coutendl;cout B的多项式为：;PrintList(Lb);coutendl;cout 相减后的结果为：;PrintList(L);coutendl;Clear();DestroyLink(L);break; case 4:if(La=NULL|Lb=NULL)cout 您的多项式创建有误，
19、请重新选择endl;Clear();break;PolyMultiply(L,La,Lb);cout 设相乘的两个一元多项式为和则：endl;coutendl;cout A的多项式为：;PrintList(La);coutendl;cout B的多项式为：;PrintList(Lb);coutendl;cout 相乘后的结果为：;PrintList(L);DestroyLink(L);coutendl;Clear();break;case 5:if(La=NULL|Lb=NULL) cout 您的多项式创建有误，请重新选择endl;Clear();break;cout 一元多项式A为：;Pri
20、ntList(La);coutendl;cout 一元多项式B为：;PrintList(Lb);coutendl;Clear();break;case 6:if(La&Lb)DestroyLink(La);DestroyLink(Lb);cout 多项式删除成功！endl;Clear();else cout 多项式不存在，请重新选择endl;Clear();break;case 7:exit(0); /exit(0)强制终止程序，返回状态码0表示正常结束default:cout 您的输入有误，请重新选择操作endl;Clear();break; 5.2克鲁斯卡尔算法5.2.1输入所有城市的权值
21、首先，我们设计一个Scanner输入所需要的顶点和边的权值。然后设计结束语句，即当输入-1，-1，-1时结束。并把输入的值赋值给边。代码：public void init() Scanner scan = new Scanner(System.in); int p,q; double w; System.out.println(请输入结点个数：); n = scan.nextInt(); System.out.println(请输入各条边及权值（每次输入一组数据按回车确认， + 最后输入-1 -1 -1 结束输入过程）); while(true) p = scan.nextInt(); q =
22、 scan.nextInt(); w = scan.nextDouble(); if(p 0 | q 0 | w 0) break; Edge e = new Edge(); e.start = p; e.end = q; e.cost = w; edge.add(e); 5.2.2判断两个顶点是否属于形成换路定义两个集合，刚开始没选取的顶点在一个集合，每选取一个就放入里一个集合。public void union(int j, int k) for(int i = 1; i = n; +i) if(parenti = j) parenti = k; 5.2.3用克鲁斯卡尔算法实现最小生成树
23、将图中的边按权值从小到大依次选取，若选取的边没有使生成树形成回路，则加入边集中；否则舍去，直到边集中包含了n-1条边为止。public void kruskal() /找剩下的n-2条边 int i = 0; while(i 0) /每次取一最小边，并删除 double min = INFINITY; int tag = 0; Edge tmp = null; for(int j = 0; j edge.size(); +j) Edge tt = edge.get(j); if(tt.cost min) min = tt.cost; tmp = tt; /删除边 int jj = parent
24、tmp.start; int kk = parenttmp.end; /判断顶点是否属于同一个集合，是就删除重新选取最小权值边 if(jj != kk) +i; target.add(tmp); mincost += tmp.cost; union(jj,kk); edge.remove(tmp); if(i != n-1) System.out.println(没有最小生成树); System.exit(0); 5.2.4打印结果 public void print() double sum=0; System.out.println(最小生成树：) for(int i = 0; i tar
25、get.size(); +i) Edge e = target.get(i); System.out.println(第 + (i+1) + 条边: + e.start + - + e.end + 权值： + e.cost); sum=sum+e.cost; System.out.println(最小生成树的权值： + sum); 第6章 测试结果6.1运行环境在本课程设计中，系统开发平台为Windows 7,程序设计语言为 C+，程序的运行环境为Visual C+ 6.0。题2程序设计语言为Java，程序的运行环境为Eclipse。6.2一元多项式计算器运行结果（1）在程序开始运行时，会出现
26、一个编号1-7的菜单并提示选择，如下图所示：图6-1 初始界面（2）选择1创建两个一元多项式，按顺序操作，录入两个一元多项式，结果如下图所示：图6-2 创建一元多项式（3）选择5显示两个一元多项式，操作后结果如下图所示：图6-3 显示一元多项式（4）选择2将两个一元多项式相加，操作后结果如下图所示：图6-4 一元多项式相加（5）选择3将两个一元多项式相减，操作后结果如下图所示：图6-5 一元多项式相减（6）选择4将两个一元多项式相乘，操作后结果如下图所示：图6-6 一元多项式相乘（7）选择6删除所创建的两个多项式，操作后结果如下图所示：图6-7 删除创建的两个一元多项式6.3克鲁斯卡尔算法此算
27、法测试如下图所示：图6-8 生成树权值小结这次课设圆满结束了，这次课设我们做了一元多项式计算器，是一种特别的计算器。这次课程设计，是我们实践能力的重要环节,是对学生实际工作能力的具体训练和考察过程。一开始遇到了很多困难，但是我们小组并没轻易放弃，在我们的共同努力下，查找资料，编写程序，最终顺利的完成了这次课程设计，这次课设对我们受益匪浅。参考文献1苏运霖.数据结构与算法.中南工业大学出版社，20022Shaffer.数据结构与算法分析(C+版).电子工业出版社，19993严蔚敏，吴伟民数据结构(C语言版).北京：清华大学出版社，20054刘小晶,杜选.数据结构（java语言描述）.北京：清华大
28、学出版社，2011.25朱振元，朱承，刘聆.数据结构教程：Java语言描述.西安：西安电子科技大学出版社，2007.12附录代码1:#include/标准输入输出流#include/使程序中可用键盘输入函数#include/使程序中可用系统标准输出函数using namespace std;/命名空间std内定义的所有标识符均有效struct Nodefloat coef;/结点类型，系数int exp;/指数;typedef Node polynomial;struct LNodepolynomial data;/链表类型LNode *next;typedef LNode* Link;/*申
29、明各功能函数*/ void CreateLink(Link &L,int n);void PrintList(Link L);void PolyAdd(Link &pc,Link pa,Link pb);void PolySubstract(Link &pc,Link pa,Link pb);void CopyLink(Link &pc,Link pa);void PolyMultiply(Link &pc,Link pa,Link pb);int JudgeIfExpSame(Link pa,Link e);void DestroyLink(Link &L);int CompareIfNum
30、(int i);/*删除链表类型结点*/void DestroyLink(Link &L)/Link p;p=L-next;while(p) L-next=p-next;delete p;p=L-next;delete L;L=NULL;/*创建含有n个链表类型结点的项，即创建一个n项多项式*/void CreateLink(Link &L,int n)if(L!=NULL)DestroyLink(L);Link p,newp;L=new LNode;L-next=NULL;(L-data).exp=-1;/创建头结点p=L;for(int i=1;i=n;i+)newp=new LNode;
31、cout 请输入第i项的系数和指数:endl;cout(newp-data).coef;cout(newp-data).exp;if(newp-data.exp0)cout 您输入有误，指数不允许为负值!next=NULL;p=L;if(newp-data.coef=0)cout 系数为零，重新输入!next!=NULL)&(p-next-data).expdata).exp) p=p-next; /p指向指数最小的那一个if(!JudgeIfExpSame( L, newp)newp-next=p-next;p-next=newp;else cout 输入的该项指数与多项式中已存在的某项相同
32、,请重新创建一个正确的多项式next;while(p!=NULL&(e-data.exp!=p-data.exp)p=p-next;if(p=NULL)return 0;else return 1;/*输出链表*/void PrintList(Link L)Link p;if(L=NULL|L-next=NULL) cout 该一元多项式为空！next;/项的系数大于0的5种情况if(p-data).coef0) if(p-data).exp=0)coutdata).coef;/如果指数为0则直接输出系数else if(p-data).coef=1&(p-data).exp=1)coutdat
33、a).coef=1&(p-data).exp!=1)coutxdata).exp;/如果系数为1，指数不为1，则输出x的指数次方else if(p-data).exp=1&(p-data).coef!=1)coutdata).coefx;/如果系数不为1，指数为1，则输出系数倍xelse coutdata).coefxdata).exp;/如果系数和指数都不为1，则输出系数乘以x的指数次方/项的系数小于0的5种情况if(p-data).coefdata).exp=0)coutdata).coef;/如果指数为0，则直接输出系数else if(p-data.coef=-1&p-data.exp=1)coutdata.coef=-1&p-data.exp!=1)cout-xdata.exp;/如果系数为-1，指数不为1，则输出x的指数次方的相反数else if(p-data.exp=1)coutdata.coefx;/如果指数为1，则输出系数倍xelse coutdat