搜索
理学院课程设计说明书课程名称:数据结构与算法A设计实践课程代码:6015059题目一:一元多项式加法、减法、乘法年级/专业/班:2013/信科/2班学生姓名:冯金慧学号:3120130902209开始时间:2015年12月28日完成时间:2016年01月10日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书撰写质量（45）总分（100）指导教师签名：年月日数据结构与算法A设计实践任务书学院名称：理学院课程代码：_6015059________专业：信科年级：2012一、设计题目一元多项式的加法、减法、乘法的实现（限最多1人完成）二、主要内容完成一无多项式的基本运算功能。三、具体要求及提交的材料设有一元多项式Am(x)和Bn(x).Am(x)=A0+A1x1+A2x2+A3x3+…+AmxmBn(x)=B0+B1x1+B2x2+B3x3+…+Bnxn请实现求M(x)=Am(x)+Bn(x)、M(x)=Am(x)-Bn(x)和M(x)=Am(x)×Bn(x)。要求：1)首先判定多项式是否稀疏2)分别采用顺序和动态存储结构实现；3)结果M(x)中无重复阶项和无零系数项；要求输出结果的升幂和降幂两种排列情况测试数据及测试结果请在上交的资料中写明；必须上机调试通过按《数据结构课程设计大纲》中的要求完成课程设计报告格式。设计结束后，每个学生必须上交的材料有：1《课程设计报告》打印稿一份2．课程设计的源代码电子文档一份四、主要技术路线提示稀疏的多项式最好采用链式存储结构；两式相减与相加的算法是一致的，只是减式的数据项反号；两式相乘是两式相加的变形。五、进度安排共计两周时间，建议进度安排如下：1．选题，应该在上机实验之前完成2.需求分析、概要设计可分配4学时完成2．详细设计可分配4学时4.调试和分析可分配10学时。2学时的机动，可提前安排部分提前结束任务的学生答辩六、推荐参考资料1.冯博琴等编著，《软件技术基础》（修改版），西安交通大学出版社，19972.严蔚敏等著，《数据结构》，清华大学出版社，20033.李芸芳等著，《软件技术基础》（第二版），清华大学出版社，20004.徐孝凯等著，《数据结构（C语言描述）》，清华大学出版社，2004指导教师签名日期年月日系主任审核日期年月日西华大学理学院课程设计说明书目录摘要...................................................................11问题的背景分析..........................................................21.1问题的提出.........................................................21.2任务与分析.........................................................22系统分析................................................................32.1功能需求...........................................................32.2总体要求...........................................................72.3数据需求...........................................................73、详细设计与实现.........................................................73.1设计思路...........................................................73.2详细编码...........................................................94．系统测试和结果分析....................................................234.1设计测试数据......................................................234.2调试的详细过程....................................................23总结...................................................................30致谢...................................................................31一元多项式的加法、减法、乘法1摘要一元多项式计算是用C语言设计一个一元多项式简单计算机，它能够实现按指数降幂排列或者按指数升幂排列建立并输出多项式，并且能够完一元多项式的四则运算，并将其运算结果输出的功能。一元多项式的存储方式分为静态数组存储和动态链表存储两种方式，两种方式的特点各不相同，顺序存储简单明了，但是缺乏灵活性，当多项式为稀疏多项式时，顺序存储则会浪费许多存储空间，链式存储动态分配内存，但操作起来比顺序存储稍微复杂一些，所以具体内容具体分析，该选择哪一种方式进行存储还需进一步分析；通过一元多项式链式存储和顺序存储的比较与体会，可以体会到对一元多项式链式存储和顺序存储各自的的优缺点和适用性。一元多项式的运算，包含四个方面，多项式的加、减、乘、除，然而那，在具体计算中，我们需要考虑很多因素。首先，我们需要判断多项式是否稀疏，其次，考虑对多项式的存储方式（顺序存储或者链式存储），并且，我们还需要保证在计算结果中，不能有重复阶的出现和零项系数的出现，在输出结果时，我们可以让其升序或者降序输出。本程序用VS2010编写，可以实现对多项式的加减乘的运算，采用顺序存储和链式存储两种方式分别可以进行多项式的加、减、乘的运算以及判断该多项式是否稀疏，最后再将运算结果以升序或者降序排列情况输出。关键词：多项式，顺序存储，链式存储，升序降序西华大学理学院课程设计说明书2引言1问题的背景分析为了更好的学习《数据结构》这一门理论和实践性均较强的基础课程，熟练掌握理论知识的同时更需要加强上机的实践。本课程就是要达到理论和实践相互结合，培养学生的动手能力，在实践中理解各种算法，在创作中提升，使我们能够在数据结构课程中，学会数据结构和算法设计解决问题的思想。1.1问题的提出本课程设计主要是探究一元多项式的四则运算，而与此同时，首先，需要我掌握和理解的是对一元多项式的不同的存储方式（链式存储和顺序存储）中，如何有效的对其进行加、减、乘的运算。其次，需要解决的问题就是给定一个一元多项式，要怎么去判断多项式的稀疏和稠密性。再者，打印多项式时可如何进行升幂和降幂的打印出多项式。这些问题都需要我逐一解决。C语言C语言既有高级语言的特点，又具有汇编语言的特点；既是一个成功的系统设计语言，有时一个使用的程序设计语言；既能用来编写不依赖计算机硬件的应用程序，又能用来编写各种系统程序；是一种受欢迎、应用广泛的程序设计语言。C语言发展过程1973年，美国贝尔实验室的D.M.RITCHIE在B语言的基础上最终设计出了一种新的语言，他取了BCPL的第二个字母作为这种语言的名字，这就是C语言。1977年DennisM.Ritchie发表了不依赖于具体机器系统的C语言编译文本《可移植的C语言编译程序》。1978年BrianW.Kernighian和DennisM.Ritchie出版了名著《TheCProgrammingLanguage》，从而使C语言成为目前世界上流行最广泛的高级程序设计语言。1.2任务与分析任务是实现求M(x)=Am(x)+Bn(x)、M(x)=Am(x)-Bn(x)和M(x)=Am(x)×Bn(x)。4)首先判定多项式是否稀疏5)分别采用顺序和动态存储结构实现；6)结果M(x)中无重复阶项和无零系数项；一元多项式的加法、减法、乘法3要求输出结果的升幂和降幂两种排列情况分析：（1）用一维数组cp1[n1]和cp2[n2]存储一元多项式Am(x)和Bn(x)的系数，用for循环来计算顺序结构中的加法、减法、乘法的结果。而顺序存储的加减乘运算则分为三个模块函数来解决这三种运算。（2）用指针*d,*q来存储一元多项式的内容，再利用指针计算动态链表下一元多项式的加法、减法、乘法的结果。（3）在用降幂升幂两种排列输出结果时，用expn和coef表示一元多项式的系数和指数，输出两种排列结果。而链式存储的加减乘运算也是分为三个模块函数来解决这三种运算2系统分析2.1功能需求此课题是主要任务是创建一元多项式，并可以选择不同的存储方式对一元多项式进行存储并且可以进行多项式的加、减、乘基本运算，最后将结果可以按照升序或者降序排列。首先需要创建两个一元多项式，才能继续下一步的进行基本的多项式运算（加、减、乘）。然后将两种不同的存储方式各自分成一个子快，编写出相应的2个函数（顺序存储、链式存储），然后在主程序里面提示各个选项对相应的功能，用户输入相应的操作数，分别调用不同的函数，打印出相应的排列结果（升幂排列或者降幂排列）。因此，实际需要设计的任务就是创建一元多项式，以及不同存储方法的函数编写，还有不同存储模式下各自的加减乘的函数编写，为了直观和方便，画出流程图如下图：一元多项式的计算主流程图1.1：西华大学理学院课程设计说明书4图1.1一元多项式的计算主流程图为顺序结构为动态链表结构结束打印输出处理后的结果一元多项式的加法、减法、乘法5（2）顺序存储结构流程图如图1.2所示图1.2顺序存储结构流程图减法？调用升幂输出函数调用降幂输出函数打印输出处理后的结果结束西华大学理学院课程设计说明书6（3）动态链表结构流程图如图1.3所示图1.3动态链表结构流程图减法？调用升幂输出函数调用降幂输出函数打印输出处理后的结果结束一元多项式的加法、减法、乘法7流程图很直观的描述了整个程序服务过程。2.2总体要求首先主函数中必须成功创建两个一元多项式，然后查阅资料知道多项式的存储方法，结合数据结构课程，我选择了比较熟悉的顺序存储和链式存储，用户想要对两个多项式进行不同的运算，首先就必须按照先序成功创建一元多项式。用户要对多项式进行运算，那就需要知道他想怎么运算（加减乘）。这需要用户手动输入选择序号。通过用户输入的信息，计算机就可以进行相关的操作，根据用户输入的信息调用对应的函数进行加减乘的运算，最后再按照用户输入的选择升序或者降序输出结果供用户浏览了；我就要用相应的程序去实现这个过程,这才是我最后的目的。2.3数据需求输入一元多项式的项数，系数和对应的次数3、详细设计与实现3.1设计思路要完成一元多项式顺序存储和链式存储的加、减、乘这几个基本的运算，有很多种方法可以实现。但结合数据结构课程，我选择了比较适合自己的算法，其他的算法还有很多，只是都不是很熟悉，我的思想大多都来源于书上，对一元多项式的顺序存储和链式存储的算法做了分析，下一步自然就是完成它的程序了，不能用程序描述出来那在好也没有用的。详细设计如下：//定义顺序存储结构类型intn1,n2;intcp1[n1];intcp2[n2]//定义动态链表结构类型#defineINFEX10000#defineINFCO10000doublecoef;intexpn;p_pol*next;//顺序存储结构的抽象数据类型定义intn1,n2;利用一维数组cp1[n1]和cp2[n2]存储多项式的系数西华大学理学院课程设计说明书8//基本操作：voidcreatpoly1(double*a,intpt)操作结果：建立顺序结构voidaddpoly(double*a,double*b,double*c)