《程序语言课程设计--任意两个高次多项式的加法和乘法运算.doc》由会员分享，可在线阅读，更多相关《程序语言课程设计--任意两个高次多项式的加法和乘法运算.doc（26页珍藏版）》请在金锄头文库上搜索。
1、 课程设计报告设计名称： 数据结构课程设计 设计题目： 两个高次多项式的加法和乘法 学生学号： 1402120135 专业班级： 软件工程1班 软件学院课程设计任务书学生姓名 学号1402120135专业班级软件工程1班设计题目任意两个高次多项式的加法和乘法运算内容概要： 设计或开发环境：Microsoft Visual Studio 2010 关键技术：C+语言 主要功能： 1建立一元多次多项式 2高次多项式相加 3高次多项式相乘 文献资料：1谭浩强C语言程序设计（第三版） 清华大学出版社 20072姜敏芝 余健 C语言程序设计案例精编 清华大学出版社 20083李健学 余健 数据结构课程设
2、计案例精编 20074唐国民 王国均数据结构（C语言版） 清华大学出版社5韩利凯 李军 数据结构 浙江大学出版社 20136网上相关文献资料设计要求：A.功能要求1）输入并建立多项式；2）输出多项式；3）两个多项式相加，输出和多项式；4）两个多项式相乘，输出积多项式。B.文档格式*.cpp工作期限：设计工作自2014年6月16日至2014年6月27日止。指导教师： 韩利凯 院长： 日 期：2014年6月16日软件学院课程设计进度安排表 起止日期内 容备注6月16日 6月 17日下任务书；收集、阅读、整理相关参考文献，并进行归纳和概括总结，完成项目/任务背景介绍部分文字内容。6月18日11月20
3、日系统功能设计和模块设计、系统体系结构构建。6月21日6月24日各功能模块编码实现，系统各功能模块调试与维护。6月25日6月26日系统功能集成、系统调试与测试，按照模板要求撰写课程设计/项目设计报告。6月27日课程设计/项目设计分组答辩，提交课程设计/项目设计报告以及相关文档，进行成绩评定。指导教师签名： 2014年6月16日摘 要摘要：本课程设计主要解决任意两个高次多项式的乘法运算。所设计的数据结构应尽可能节省存储空间，程序的运行时间应尽可能少。从题目看出所设计的程序应能达到的功能，设计好的程序要满足以上两点。在数据输入方面可以根据一元高次多项式的特征，从左到右开始，按每一项指数、系数的顺序
4、输入。这里要留意一个问题，因为要相乘的多项式项数是未知的，所以选择什么样的存储方式在本课程设计中尤为重要，这也是本程序好坏的一个评定。程序通过调试运行，初步实现了设计目标，并且经过适当完善后，将可以应用在商业中解决实际问题。关键词：高次多项式；加法；乘法；时间复杂度；空间复杂度西安文理学院软件学院 课程设计报告目 录目 录I第一章 课题背景21.1 绪论21.2 主要内容2第二章 设计简介及设计方案论述32.1 系统分析32.1.1 功能需求32.1.2 数据需求32.1.3 系统需求32.2 总体设计32.2.1 系统设计方案32.2.2 功能模块设计4第三章 详细设计53.1 主要流程图5
5、3.2 链表模块63.3 加法模块83.4 乘法模块10第四章 设计结果及分析124.1 调试与测试124.1.1 调试124.1.2 测试124.1.3 运行界面134.2 结果分析13总结14参考文献15附录16- 21 -第一章 课题背景1.1 绪论随着科技的进步，社会的不断发展，计算器已普遍应用于各行各业，为了帮助人们提高工作效率，节约运算时间，设计一个多功能的计算器是很有必要的，在此设计一个高次多项式计算器可以很方便的对多项式相加、相减、相乘，对提高人们的运算效率很有帮助。这样一个程序需要用到C+多方面的知识，要实现多项式的建立和输入输出等功能，必须要熟练的掌握C+，在此尤其是链表的
6、灵活运用和结点特点。1.2 主要内容用C+语言实现多项式的输入输出和多项式的加减乘等运算，其中主要用到链表和结点的相关知识,具体功能如下：1）输入并建立多项式；2）输出多项式；3）两个多项式相加，输出和多项式；4）两个多项式相减，输出差多项式。第二章 设计简介及设计方案论述2.1 系统分析2.1.1 功能需求 实现任意两个高次多项式的加法和乘法2.1.2 数据需求在输入过程中，首先要给定输入的数据，数据只能是数字，不能是字母或其他，不能连续输入数据，必须要求以空格分开要输入的数据。2.1.3 系统需求系统必须安全可靠，不会出现无故死机状态，运算速度要快。2.2 总体设计2.2.1 系统设计方案
7、用户输入高次多项式系数和指数，用单链表储存你输入的数据，输出两个多项式相加和相乘之后的结果。(1) 数据结构的选择本程序选择的数据结构是单链表，原因如下：当需要插入数据元素时，临时动态地为其申请一个存储空间，而不是将结点放在一个定义的数组中，删除数据元素时，可以释放该数据元素所占用的空间，即可以根据表的实际需要临时动态的分配存储空间以存储表中的数据元素。单链表是有限个具有相同数据类型的数据元素组成的链表且该链表的每一个结点只有一个指针域。带头结点的单链表是在单链表的第一个结点之前加一个同类型的结点，目的是为了使链表有一致的描述。本程序解决的是两多项式相乘的问题，多项式的项数本身就是不确定的，而
8、且相乘后的多项式可能含有指数相同的问题，这时就需要合并，合并后其中的一项就没有用了需要删除，不然就浪费内存空间。基于以上几点所以采用了链表。链表具有动态生成，灵活添加或删除结点的特点，尽可能节省存储空间。(2) 文件保存方式运用带头节点的单链表储存多项式。(3) 抽象数据类型定义主要定义多项式的系数和指数，系数项和指数项均用整型定义。(4) 存储结构采用链式结构，建立链表储存输入的多项式(5) 算法设计先将两个已知的多项式的指数和系数存放在指定链表中在执行乘法运算。乘法运算的过程是将A 式中的第一项与B 式的每一项相乘，在将A 式的第二项与B 式的每一项相乘，依次下去直到A 式的所有项与B 式
9、乘完为止。将相乘后所得的指数、系数存在预先建好的C 链表中。 C 链表中如果有指数相同的项就需要合并，合并时将结果放在前一个项中，将后一项删除。首先定义3个指针，x、y、z，x、y 指向首元素结点z 指向第二个结点，用z 结点中指数项与x 结点的指数项比较，如果不同指针z 向后移，若相同则将z 结点的系数加到x 上去然后将z 所在结点空间释放，并且指针z 后移。直到指针z 指向空后，将指针x 后移一项，并令z 指向x 的下一项，然后按上述步骤依次执行，直到x 指向空结束。这里指针y 是z 的前驱结点他的作用是合并后结点空间释放结点空间将此结点的前后两项链接起来。本程序核心部分全部是运用whil
10、e 循环语句实现的。2.2.2 功能模块设计高次多项式加法和乘法加法模块乘法模块输出模块输入模块链表模块图 2-1 功能模块第三章 详细设计多项式的建立主要需要建立新链表，并分配给这个新链表一定量的存储空间，分配的存储空间内进行运算；多项式加减乘等运算主要运用了链表的建立，链表存储空间分配，链表的查找，插入与连接进行计算。3.1 主要流程图此阶段是程序构建的思路，是本程序的结构图，同时也体现出本程序将要达到的功能，如图 3-1所示： 输入任意两个高次 多项式的系数、指数值 将输入值分别储存 在两个动态链表中 将相乘和相加的 结果存入C链表 将存放相乘多项式的各项 系数指数的链表置空 若有指数相
11、同 的项合并 输出两个要进行 运算的多项式 输出结果图 3-1 主流程图3.2 链表模块此阶段是程序中链表的主要流程，如图 3-2所示： Start list Poly_add(list&poly_list_first, list&poly_list_second) list:iterator iter_first = poly_list_first.begin();list:iterator iter_second = poly_list_second.begin(); iter_first!=poly_list_first.end() & iter_second != poly_list_second.end() term t_first = (term)*iter_first; term t_second = (term)*iter_second; t_first.expt_second.exp poly_list_result.push_back(t_first); iter_first+; t_second.exp t_first.exp
