数据结构 多项式求导.doc

1 孝感学院计算机科学系孝感学院计算机科学系 11 级级 课程设计课程设计报告课程设计课程设计报告 题目题目：多项式求导 班级班级：1017142 学号学号：101714201 姓名姓名： 指导教师：李志敏：李志敏 2012 年 2 月 12 日 2 目录目录 1 需求分析需求分析.2 1.1 功能需求分析.2 1.2 设计平台.3 2 概要设计概要设计.3 2.1 涉及到的知识基础(概述).5 2.2 定义的函数的部分功能.7 3 详细设计和实现详细设计和实现.7 3.1 功能模块.7 3.2 系统流程图.8 4 调试与操作说明调试与操作说明.9 5、总、总结结.10 6. 参考文献参考文献.10 7、源程序、源程序.11 3 1 需求分析需求分析 1.1 功能需求分析功能需求分析 1.本演示程序中，多项式的系数为浮点型，指数为整型。输入多项式时， 先输入多项式的项数系数和指数，该多项式若为 0，则输入 0。多项式的输出形 式为类数学表达式且按指数降序排列，系数值为 1 的非零次项的输出形式中略 去系数 1。 2.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提 示信息”之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入 数据和运算结果显示在其后。 3.程序执行的命令： 输入为一个一元多项式，按照降幂依次输入每个单项式的系数和指数，并以-1 -1 作为 结束。系数和指数均为整数，指数不小于 0。 1.2 设计平台设计平台 Visual C+ 6.0 , Windows XP 平台， 2 概要设计概要设计 为实现上述程序功能，用带表头结点的单链表存储多项式。为此，需要两 个抽象数据类型：线性表和多项式。 1.有序表的抽象数据类型定义为： ADT List 数据对象：D=ai|aiElemset,i=1,2,，n,n0 数据关系：R1=|ai-1,aiD,i=2,n 基本操作： PolyNode *p,*q,*r,*head; 操作结果:构造一个空的线性表。 。 4 Listinsert( switch() 处理命令； goto strat； 5 2）多项式单元模块：实现多项式的抽象数据类型； 3）线性表单元模块：实现线性表的抽象数据类型； 4）结点结构单元模块：定义线性表的结点结构； 各模块之间的调用关系如下: 主程序模块 多项式单元模块 结点结构单元模块 图 2-1 模块调用关系 2.1 涉及到的知识基础涉及到的知识基础(概述概述) 1.结点类型、指针类型 typedeftypedef structstruct polynodepolynode intint c;c; intint e;e; structstruct polynodepolynode *next;*next; poly;poly; 2.线性表设计 p=h; 6 while(p-next!=NULL /如果输 入的指数小于 p 的下一个接点，p 向后指 if (e=p-expn) p-coef+=c;continue;/如 果相等，直接加上去，继续循环 q=new PolyNode; q-coef=c,q-expn=e; if (p-next!=NULL p-next=q; q-next=r; continue; p-next=q;/如果输入 的值小于所有接点，接在最后一个接点之后 p=p-next; p-next=NULL; 3.多项式基本操作部分 poly *qiudao(poly *p)/求导 poly *s; s = p; while (p) 7 p-c = (p-c)*(p-e); p-e = (p-e) - 1; p = p-next; return s; 2.2 定义的函数的部分功能定义的函数的部分功能 在设计程序的时候，考虑到一元稀疏多项式计算器的功能，我们按照其功能划 分为几个模块，在程序开始后，先进行多项式的输入,再选择一种运算法则进行 运算。然后输出运算结果。具体的模块关系如表程序结构框图: 表 2-1 基本模块表 模块输入输出 实现功能填入多项式的系数 和指数 输出运算后多项式的系 数和指数 3 详细设计和实现详细设计和实现 3.1 功能模块功能模块 8 多项式求导 计算器 开始运行 输入多项式 求导退出 建立2个多项式 输入结束返回 多项式求导 输出求导结果 关闭运行 按任意键退出 图 3-1 功能图 3.2 系统流程图系统流程图 9 退出 函数调用 开始 选择模块 输出结果 图 3-2 系统流程图 4 调试与操作说明调试与操作说明 运行结果如图所示 10 5、总、总 结结 再学完数据结构后做此题，自觉就想到用带头结点的单链表来存储多项式，只需用结 点记录多项式的系数和指数，此数据结构即节省空间又好进行操作，且进行运算的主要设 计思路也易想到，大体设计结构在较短时间内能够完成。但当设计到具体细节代码时遇到 了不少困难，主要困难是进行结点操作时，对指针考虑得不够细致，调试时常出现指针指 错的情况，没有认真理清条件层次。完成此程序后，受益匪浅，它巩固了线性表一章学到 的知识，而且重温了指针，函数传参等重点知识。尽管对程序进行大量的调试分析修改， 可还有些代码写得十分啰嗦，程序也不够健壮，对多项式的操作只限于 2 个多项式，还有 在界面设计上没花太大心思，界面不美观。这些问题在日后还需进行改善。本次课程设计 采用 C+语言实现.这次设计基本上能实现指导书上的要求。我们可以通过这个程序实现计 算器的一些基本功能,实现相关操作。通过本次课程设计,让我进一步了解了 c+的一些知识, C/C+的字符串处理功能完全依靠字符串数组来实现，很多在其他高级语言中实现的字符 串比较等操作，在这里完全依靠函数来实现，因此调试中字符串处理函数的调试很多多本次 课程设计培养了我们对这些实际问题的分析能力以及解决一些实际问题的能力。通过编程， 巩固了我们对编程思想和写程序的能力。课程设计是对我们的学习很有利的一个环节。在 这个阶段，我们学会把理论与实际的结合、懂得人与人沟通的重要性，明白合作的可贵。 当然，在编写的过程中也出现了很多问题，但通过调试和看书解决了，大大的提高了我自 学的能力，学会了遇到问题，如何利用资源去解决问题也明白了要完成一项设计，首先要 有扎实的基础知识，这就要求我们在平时的学习中要不断提高自己。其次，要充分利用身 边的各种资源，图书馆有很多相关的书，网上也有不少的知识解答，要好好的利用。第三， 要多向身边的同学多请教，在交流中提高自己的实力。理论联系实践，在实践中提高。通 过这次课程设计中，我加深了对课本知识的理解。 6. 参考文献参考文献 1C+程序设计 钱能 清华大学出版社 2C+程序设计试验指导 钱能 清华大学出版社 11 3C 程序设计 谭浩强 清华大学出版社 4数据结构（C 语言版） 严蔚敏 吴伟民 清华大学出版社 7、源程序、源程序 #include #include typedef struct polynode int c; int e; struct polynode *next; poly; poly *creatpoly() poly *p, *q, *h; q = NULL, h = NULL; int c; int e; while (e!=-1) scanf(%d%d, /*将 scanf 位置改变下*/ h = (poly*)malloc(sizeof(poly); h-c = c; h-e = e; h-next = NULL; if (q = NULL) q = h; else p-next = h; p = h; return q; poly *qiudao(poly *p) poly *s; s = p; while (p) 12 p-c = (p-c)*(p-e); p-e = (p-e) - 1; p = p-next; return s; void print(poly *p) int i = 0; if (p-e = - 1) printf(0); i+; while (p-next != NULL) if (p-c != 0) printf(%d %d , p-c, p-e); i+; else ; p = p-ne