数据结构课程设计一元稀疏多项式计算器

软 件 学 院课程设计报告书课程名称 数据结构课程设计 设计题目 一元稀疏多项式计算器 专业班级 学 号 姓 名 指导教师 2010 年 12 月目录1 设计时间22 设计目的23设计任务24 设计内容24.1需求分析24.2总体设计24.3详细设计54.4测试与分析6测试6分析84.5 附录95、 总结与展望11参考文献13成绩评定131 设计时间2010年12月27日2 设计目的实现一元多项式的相加，相减，输出结果。3设计任务设计一个一元稀疏多项式简单计算器。4 设计内容 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()。2、输入的形式和输入值的范围；输入形式：多项式输入值范围：实数3、输出的形式：输出多项式，输出形式为整数序列：n,c1,e1,c2,e2,cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数升序排列 printpolyn()4、测试数据：输入：a=2X+3X2; b=2X3+7X4输出：a+b=2X+3X2+ 2X3+7X4a-b=2X+3X2-2X3-7X44.2总体设计内容包括：1、说明本程序中用到的所有抽象数据类型的定义； typedef struct Polynomial float coef; int expn; struct Polynomial *next; *Polyn,Polynomial;void Insert(Polyn p,Polyn h)Polyn CreatePolyn(Polyn head,int m)void PrintPolyn(Polyn P)Int compare(Polyn a,Polyn b)Polyn AddPolyn(Polyn pa,Polyn pb)Polyn AddPolyn(Polyn pa,Polyn pb)Polyn Derivative(Polyn head)2、主程序的流程；开始运行选择输入求和求差建立两个多项式多项式相加减输出求和结果输出求差结果3、说明各程序模块之间的层次（调用）关系。Main()InsertCreatePolynPrintPolynAddPolynSubtractPolyncompareDerivative4.3详细设计内容包括：函数CreatePolyn建立一个头指针为head、项数为m的一元多项式，然后调运函数Insert向生成链表中保存多项式项数及每项的指数、系数。函数CreatePolyn生成多项式a和多项式b。通过函数compare和函数PrintPolyn对多项式a和多项式b指数、系数进行分析。当多项式a指数指数大于多项式b指数时，链表保存多项式a系数；当多项式b指数指数大于多项式a指数时，链表保存多项式b系数；当多项式b指数指数等于多项式a指数时，对多项式a和多项式b系数进行加减运算，之后将系数保存在链表中。函数Polyn AddPolyn对多项式a和多项式b进行加运算，调运函数compare、函数PrintPolyn、函数CreatePolyn。函数SubtractPolyn对多项式a和多项式b进行减运算，其对多项式b中各系数正负取反，然后调用函数Polyn AddPolyn进行a+(-b)。主函数运行分别输入多项式和多项式的项数、系数和指数，然后选择对多项式操作A：a+b或 B：a-b，从而实现对多项式的加减运算。，3、函数的调用关系图。Main()InsertCreatePolyn你PrintPolynAddPolynSubtractPolyncompareDerivative4.4测试与分析4.4.1测试：输入：a=2X+3X2; b=2X3+7X4输出：a+b=2X+3X2+ 2X3+7X4a-b=2X+3X2-2X3-7X44.4.2分析：1、调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析；认真观察自己的算法，看错误来自哪里，找出错误，并加以修改。2、算法的时间复杂度和空间复杂度的分析，改进设想。Insert的时间复杂度O(1)空间复杂度O(1)； Derivativ的时间复杂度O(1)空间复杂度O(1)；CreatePolyn的时间复杂度O(n)空间复杂度O(1)；compare的时间复杂度O(1)空间复杂度O(1)；PrintPolyn的时间复杂度O(1)空间复杂度O(1)；AddPolyn 的时间复杂度O(n)空间复杂度O(1)；SubtractPolyn的时间复杂度O(n)空间复杂度O(1)；Main()的时间复杂度O(n)空间复杂度O(1)。4.5 附录定义多项式的项typedef struct Polynomial float coef; int expn; struct Polynomial *next; *Polyn,Polynomial;void Insert(Polyn p,Polyn h)向链表中插入多项式的项数、系数、指数。Polyn CreatePolyn(Polyn head,int m)建立一个头指针为head、项数为m的一元多项式。调运函数Insert生成多项式a和多项式b。void PrintPolyn(Polyn P)当多项式指数为“1”时，对多项式a和多项式b系数进行加减。Polyn AddPolyn(Polyn pa,Polyn pb)求解并建立多项式a+b，返回其头指针。调运函数compare对多项式a和多项式b进行降幂输出。Polyn SubtractPolyn(Polyn pa,Polyn pb)求解并建立多项式a-b，返回其头指针。对多项式b中各项系数正负取反，然后调运函数Polyn AddPolyn，对多项式a和多项式b进行a+(-b)降幂输出。Polyn Derivative(Polyn head)求解并建立导函数多项式，并返回其头指针。void main()/主函数 int m,n,a,x; char flag; Polyn pa=0,pb=0,pc; printf( 欢迎使用多项式操作程序nn); printf(请输入a的项数:); scanf(%d,&m); pa=CreatePolyn(pa,m);/建立多项式a printf(请输入b的项数:); scanf(%d,&n); pb=CreatePolyn(pb,n);/建立多项式b /输出菜单printf( *n);printf( * 多项式操作程序 *n);printf( * A:输出a+b B:输出a-b *n);printf( * *n);printf( *n);while(a) printf(n请选择操作：); scanf( %c,&flag);/空格符号一定要注意 switch(flag) caseA: casea: pc=AddPolyn(pa,pb); printf(n a+b=); PrintPolyn(pc); break; caseB: caseb: pc=SubtractPolyn(pa,pb); printf(n a-b=); PrintPolyn(pc); break; default:printf(n 您的选择错误，请重新选择!n); 5 总结与展望在编程过程中很容易发现程序中的错误，要尽快找出这些错误，使程序能正确运行。平时缺乏锻炼即使在明确的出错提示下也往往找不出错误，不知道该怎么办，而求救于别人。但更重要的是通过自己的直接实践来累积。因此，在实验时千万不要在程序通过后就认为万事大吉、完成任务了，而应当在已通过的程序基础上作一些改动，再进行编译、连接和运行。我觉得我们对于数据结构的学习不仅包括理论部分的学习，还要让我们勤动手，多实践。刚开始学的时候确实有很多地方我很不理解，每次上课时老师都会给我们出不同的设计题目，对于我们来说，无疑是一个具大的挑战，撞了几次壁之后，我决定静下心来，仔细去写程序。老师会给我们需要编程的内容一些讲解，顺着老师的思路，来完成自己的设计，我们可以开始运行自己的程序，可是好多处的错误，还看不出到底是哪里出现了错误，但是程序还是得继续下去，我多次和同学讨论研究，逐渐能自己找出错误，并加以改正。此次的程序设计能够成功，是我和我的同学共同努力作用的结果。在这一段努力学习的过程中，收获还真是不少，虽然说以前非常不懂这门语言，在它上面花费了好多心血，觉得它很难，是需用花费了大量的时间编写出来的。现在真正的明白了一些代码的应用，每个程序都有一些共同点，通用的结构，相似的格式。只要努力去学习，就会灵活的去应用它。参考文献1严蔚敏，吴伟民 数据结构（c语言版）清华大学出版社；2谭浩强 c程序设计（第三版）清华大学出版社；3徐孝凯 数据结构 电子工业出版社；4徐翠霞，崔玲玲，邵回祖 数据结构案例教程 北京大学出版社； 成绩评定成绩 教师签字