搜索
数据结构与算法课程设计报告设计题目:一元稀疏多项式计算器院系：信息工程学院专业班级：物联1301学生姓名：滕玲指导教师：刘维2014年6月16日任务分工阐述在这次程序设计中，我的任务是对于已经建立好的多项式a和b进行加减的运算。要解决多项式相加，必须要有多项式，所以必须首先建立两个多项式。我采用链表的方式存储链表，定义结点结构体。序数coef指数expn指针域next数据按照降序排列。如果指数相等则直接将系数相加；如果所插入指数大于所指数据，就将此数据插入到当前指向的前面，否则将数据插入到最后。考虑到空间存储效率，将相加系数为0时，释放该结点。成绩评定：年月日目录1.设计内容..........................................11.1问题描述....................................................................................................11.2设计要求....................................................................................................11.3开发环境....................................................................................................11.4研究思路....................................................................................................12.设计步骤..........................................32.1需求分析....................................................................................................32.2概要设计....................................................................................................32.3详细设计....................................................................................................52.4调试分析....................................................................................................62.5测试结果....................................................................................................73.设计成果展示.....................................133.1用户手册..................................................................................................133.2程序运行部分截图..................................................................................134.总结与心得体会...................................16附录..............................................17参考文献........................................26一元稀疏多项式计算器11.设计内容1.1问题描述一元稀疏多项式计算器1.2设计要求一元稀疏多项式简单计算器的功能是：1.输入并建立多项式；2.输出多项式，输出形式为整数序列：n，c1,e1,c2,e2,………cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列；3.求多项式a、b的导函数；4.计算多项式在x处的值；5.多项式a和b相加，建立多项式a+b；6.多项式a和b相减，建立多项式a-b。1.3开发环境本程序开发环境为VisualC++6.01.4研究思路1.定义线性表的动态分配顺序存储结构；2.建立多项式存储结构，定义指针*next3.利用链表实现队列的构造。每次输入一项的系数和指数，可以输出构造的一元多项式4.演示程序以用户和计算机的对话方式执行，即在计算机终站上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运行命令；最后根据相应的输入数据（滤去输入中的非法字符）建立的多项式以及多项式相加的运行结果在屏幕上显示。多项式显示的格式为：c1x^e1+c2x^e2+…+cnx^en要解决多项式相加，必须要有多项式，所以必须首先建立两个多项式。采用链表的方式存储链表，定义结点结构体。所以我将结点结构体定义为一元稀疏多项式计算器2序数coef指数expn指针域next运用尾插法建立两条单链表，以单链表polynp和polynh分别表示两个一元多项式a和b，a+b的求和运算等同于单链表的插入问题（将单链表polynp中的结点插入到单链表polynh中），因此“和多项式”中的结点无须另生成。为了实现处理，设p、q分别指向单链表polya和polyb的当前项，比较p、q结点的指数项，由此得到下列运算规则：①若p-expnq-expn，则结点p所指的结点应是“和多项式”中的一项，令指针p后移。②若p-expn=q-expn，则将两个结点中的系数相加，当和不为0时修改结点p的系数。③若p-expnq-expn，则结点q所指的结点应是“和多项式”中的一项，将结点q插入在结点p之前，且令指针q在原来的链表上后移。一元稀疏多项式计算器32.设计步骤2.1需求分析数学在实际生活运用中非常广泛，因此多项式的计算以被广泛运用。普通计算浪费时间，消耗精力。然而，借助计算机，我们可以快速的计算出所需要的答案，既节省了时间，计算结果又准确。基于以上问题，我们可以利用数据结构这一门技术编写出一元稀疏多项式计算程序，以便快速准确的计算出多项式的结果。我们利用单链表来存储，定义结点结构体，实现一元稀疏多项式计算器程序的实现。本演示程序，主要是用于实现一元稀疏多项式的简单计算，主要有多项式的加法和减法，求导数和带入x的值。只要简单的按照提示，输入多项式的项数，系数和指数，便可以实现用户所需要的简单计算。演示程序一用户和计算机的对话方式执行，即用户只要在计算机显示屏上看到程序的提示信息后，使用键盘逐步输入程序中规定的命令，则由用户所输入的数据将会在演示程序执行后并显示结果程序的执行命令：（1）建立多项式（2）输出多项式（3）输出多项式的导数（4）带入x的值计算（5）求两个多项式之和并输出（6）求两个多项式之差并输出2.2概要设计函数CreatePolyn建立一个头指针为head、项数为m的一元多项式，然后调运函数Insert向生成链表中保存多项式项数及每项的指数、系数。函数CreatePolyn生成多项式a和多项式b。通过函数compare和函数PrintPolyn对多项式a和多项式b指数、系数进行分析。当多项式a指数指数大于多项式b指数时，链表保存多项式a系数；当多项式b指数指数大于多项式a指数时，链表保存多项式b系数；当多项式b指数指数等于多项式a指数时，对多项式a和多项式b系数进行加减运算，之后将系数保存在链表中。函数PolynAddPolyn对多项式a和多项式b进行加运算，调运函数compare、函数PrintPolyn、函数CreatePolyn。函数SubtractPolyn对多项式a和多项式b进行减运算，其对多项式b中各系数正负取反，然后调用函数PolynAddPolyn进行a+(-b)。主函数运行分别输入多项式和多项式的项数、系数和指数，然后选择对多项式操作A：a+b或B：a-b，从而实现对多项式的加减运算。一元稀疏多项式计算器4程序流程设计图：一元稀疏多项式计算器52.3详细设计针对主要功能，我们首先要设计可视化界面，然后在控件上添加事件过程，再编写代码。1.数据结构的选用typedefstructPolynomial{floatcoef;//系数intexpn;//指数structPolynomial*next;}*Polyn,Polynomial;2.多项式的输入PolynCreatePolyn(Polynhead,intm){......for(i=0;im;i++){p=(Polyn)malloc(sizeof(structPolynomial));printf(请输入第%d项的系数与指数:,i+1);scanf(%f%d,&p-coef,&p-expn);Insert(p,head);}returnhead;}3.主函数和其它函数voidmain(){intm,n,a,x;charflag;Polynpa=0,pb=0,pc;}voidDestroyPolyn(Polynp)voidPrintPolyn(PolynP)intcompare(Polyna,Polynb)PolynAddPolyn(Polynpa,Polynpb)PolynSubtractPolyn(Polynpa,Polynpb)一元稀疏多项式计算器62.4调试分析1、刚开始的时候由于对多项式的减法考虑不周全，代码很复杂，后来经过仔细思考，减法时把每项的系数变成它的相反数，然后调用加法的函数即可，但是实现了减法之后要把系数恢复，不然会影响后面的运算。求多项式在x处的值的函数在刚开始的时候出现过警告，虽然警告不会影响程序的运行，但是运算的结果不精确。之前函数的类型是int，但是里面的多项式的系数是浮点型的，而sum又是整型的，但是这样得不到小数点后面的数值，导致结果不精确。后来经改进，把函数的类型及sum的类型均改为float型，在后面的命令函数里也要把输出控制格式改为%.2f。修改前：修改后：2、程序的调试过程中我们也遇到了好多好多的问题，有的问题出现了以后我们从网上几乎查遍了所有的比较有影响力的论坛，也问了不少的这方面的朋友。当然大部分的问题我们能够通过这种方式解决，有些不能够得到解决的问题我们也采取了其他的方式解决了一部分问题。由于时间的限制还没有解决的问题，我们也一定会随着我们知识的增长去逐渐的完善这个问题。3、再就是在这次的课程设计过程中，学会了利用专业的调试工具进行分析，这也能很快的帮我们解决问题。还有就是调试并不仅仅是一个最后测试的问题，而是伴随着程序开发的整个过程，边写边调，每写完一个过程就该调试一下，否则最后到所有的程序结束在进行调试，调试过程将变的异常复杂。4、我们程序调试过程中也发现了一定的问题，在编写过程中，由于粗心会出现低级错误，通过测试，不断改正，才能使程序完成。通过我们测试我们测试自己的程序，发现了太多的问题，用起来是那么的粗糙，跟那些真正的好程序差距还太远，但是通过这次的课程设计，使我们了解了算法设计的思考过程以及运行的调用过程，这也使我们更多的去了解数据结构算法，并进一步开发一些有一定价值的程序。一元稀疏多项式计算器72.5测试结果1.(2x+5x^8-3.1x^11)+(7-5x^8+11x^9)一元稀疏多项式计算器82.(6x^-3-x+4.4x^2-1.2x^9+1.2x^9)-(-6x^-3+5.4x^2-x^2+7.8x^1