数据结构课程设计-一元多项式的计算.docx

课程设计成果学院: 计算机工程学院 班 级: 13计科一班 学生姓名: 学 号: 设计地点（单位）： 设计题目： 一元多项式的计算 完成日期： 年 月 日 成绩(五级记分制): _教师签名:_目 录1 需求分析12 概要设计22.1一元多项式的建立22.2显示一元多项式22.3一元多项式减法运算22.4一元多项式加法运算22.5 设计优缺点23详细设计33.1一元多项式的输入输出流程图33.2一元多项式的加法流程图33.3 一元多项式的减法流程图43.4用户操作函数54编码65调试分析64测试结果及运行效果85系统开发所用到的技术10参考文献11附录 全部代码121、需求分析建立一元多项式并按照指数降序排列输出多项式，将一元多项式输入并存储在内存中，能够完成两个多项式的加减运算并输出结果。随着科学技术的发展，计算机领域不断取得新的研究成果。计算机在代替和延伸脑力劳动方面发挥越来越重要的作用，不仅在工业方面而且在日常生活中也越来越离不开计算机。尤其是在学校里，要处理大量的学生数据。随着科学技术的不断提高,计算机科学日渐成熟,其强大的功能已为人们深刻认识,它已进入人类社会的各个领域并发挥着越来越重要的作用.一元多项式在日常生活中应用也比较广泛，在数学领域，我们看似简单的问题，用程序编码出来其实要考虑很多思想，一元多项式的表示在计算机内可以用链表来表示，为了节省存储空间，只存储多项式中系数非零的项，链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数，指数以及指向下一个多项式结点的指针，创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加，相减操作。算法不像我们平时用眼睛直观观察到的，电脑只会运行在逻辑上有条理合理的东西，不会进行变通，在编写算法时，要认真考虑算法的每一步的运算，之后程序该做什么等问题。 能够按照多项式变量的指数降序创建一个多项式； 能够对已创建的多项式进行显示； 能够对已创建的多项式之间的加法运算； 能够对已创建的多项式之间的减法运算； 能够对已创建的多项式进行删除； 能够实现计算器退出操作；2 概要设计2.1一元多项式的建立输入多项式采用头插法的方式，输入多项式中一个项的系数和指数，就产生一个新的节点，建立起它的右指针，并用头结点指向它；为了判断一个多项式是否输入结束，定义一个结束标志，当输入非0时就继续，当输入0时，就结束一个多项式的输入。2.2显示一元多项式如果系数是大于0的话就直接输出系数，如果系数是正的话前面就要加+号，如果系数是1的话就直接输出+x，如果系数是-1的话就直接输出-x号，如果系数是大于0的话就输出+系数x指数的形式，如果系数小于0的话就输出系数x指数的形式。2.3一元多项式减法运算它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相等的话，系数就相减；相加的和不为零的话，用头插法建立一个新的节点，p的指数小于q的指数的话，就应该复制q的节点到多项式中，p的指数大于q的指数的话就应该复制p的节点到多项式中，并且建立的节点的系数为原来的相反数，当第二个多项式空，第一个多项式不为空时，将第一个多项式用新节点产生，当第一个多项式空，第二个多项式不为空时，将第二个多项式用新节点产生，并且建立的节点的系数为原来的相反数。2.4一元多项式加法运算它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相等的话，系数就相加；相加的和不为零的话，用头插法建立一个新的节点，p的指数小于q的指数的话，就应该复制q的节点到多项式中，p的指数大于q的指数的话就应该复制p的节点到多项式中，当第二个多项式空，第一个多项式不为空时，将第一个多项式用新节点产生，当第一个多项式空，第二个多项式不为空时，将第二个多项式用新节点产生。2.5 设计优缺点优点：1.能够实现一元多项式的加，减运算，算法也不是很复杂，容易理解，在空间复杂度上比较节省存储空间。2.所有的操作大多是在内存中实现，增加操作的速度，在操作的时候我们可以利用链表来实现随机的操作，十分的方便。 缺点：1.这个算法具有一般性，对于有些特殊的一元多项式采用顺序存储会比较方便，在时间复杂度上可以节省很多算法的时间。2.在最坏的情况下，即n+1个系数都不为零，则比只存储系数的方法（顺序存储）多存储一倍的数据，对于非零系数多的多项式则不宜采用这种表示。3详细设计3.1一元多项式的输入输出流程图1、输入输出（1） 功能：将要进行运算的多项式输入输出。（2） 数据流入：要输入的多项式的系数与指数。（3） 数据流出：合并同类项后的多项式。程序流程图：多项式输入流程图如图3-1所示。（4） 测试要点：输入的多项式是否正确，若输入错误则从新输入。 图3-1 多项式输入流程图3.2一元多项式的加法流程图2、一元多项式的加法（1） 功能：将两多项式相加。（2） 数据流入：输入函数。（3） 数据流出：多项式相加后的结果。（4） 程序流程图：多项式的加法流程图如图3-2所示。测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运算图3-2 多项式的加法流程图3.3 一元多项式的减法流程图3、一元多项式的减法（5） 功能：将两多项式相减。（6） 数据流入：输入函数。（7） 数据流出：多项式相减后的结果。（8） 程序流程图：多项式的减法流程图如图3-3所示。测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运算图3-3 多项式的减法流程图3.4用户操作函数Typedef struct pnode/项的表示，多项式的项作为pnode的数据元素Float xishu; /系数Int zhishu；/指数/*用头插法生成一个多项式，系数和指数输入0时退出输入*/pnode *creat()/*调整多项式*/void tiaozhen(pnode *head)/*输出一元多项式函数：*/void shuchu(pnode *head)/*两个多项式的加法运算*/pnode*add(pnode*heada,pnode*headb)/*相加的函数*/ void add_main()/*减法函数*/ void sub_main()4编码函数流程： pnode L=NULL; /定义一个链表，即我们所操作的链表信息都可从这个变量获得void main()/初始化链表InitList(L );/调用用户界面，接受用户的操作选择switch();创建链表(程序开始)初始化链表调用用户界面，接受用户的操作选择错误提示，请用户重新操作-#include#include#include#include5调试分析主要的调试过程有三个：1. 对一元多项式的输出，输出函数void shuchu(pnode *head)，在开始界面上调整，字段的布局，刚开始时由于换行没有加上，界面如下图5-1 调试之前 经过修改之后，界面变得整洁一点，用户更能接受一点，修改之后的图如下： 图5-2 调试之后测试输入“1“页面正常，说明逻辑设计正确。2. 链表的调试。总得来说链表的调试是相对简单的，毕竟都是在内存里运行的，记录和显示数据的。调试阶段最重要的还是耐性和细心。要有足够的耐性去对待令人烦躁的错误，一步步细心的调试，就会查出错误的所在。我们进行调试、测试是为了让我们的代码、程序更加健壮，质量更高。所以，我们不要畏惧报错，这是个学习进步的过程。我们应在错误中，认识到自己的不足与薄弱的知识点，提高自己的编写代码能力和改正错误的能力。6.测试结果及运行效果运行程序后的登陆后的界面，在其中，可以选择：两个一元多项式相加、两个一元多项式相减，可以按1,2，或者按0键退出。图6-1登陆后的界面输入1进入一元多项式相加页面后，需要输入第一个一元多项式的系数和指数，注意这里的指数是按降序排列的，系数可以是正的，负的也可以是小数，以输入0 0为结束标志，再按Enter键，输入第二个一元多项式的系数和指数。图6-2 进入一元多项式的操作界面 操作完成之后，界面出现的结果如图所示： 图6-3 一元多项式运行的结果界面 一元多项式的减法操作也是一样的进行，运行的结果如下： 图6-4一元多项式减法的运行结果 图6-5退出界面7.系统开发所用到的技术操作系统： Windows 7开发软件: Devc+技术：功能模块（函数）；指针；结构；链表；模块与函数:功能模块：求解较小问题的算法与程序称作“功能模块”，各功能模块可以先单独设计，然后将求解所有的子问题的模块组合成求解原问题的程序。将一个大问题分解成多个解决小问题的模块的设计思想。由功能模块组成程序的结构：主控模块和模块组成。模块还可细分。自顶向下，逐步分解的设计思想函数：完成相对独立功能和程序。模块独立：功能独立的子功能模块之间的关系简单，使用独立变量，模块规模适当：分解模块要注意层次：(1)对问题抽象化(2)设计时细化设计原则：高内聚，低耦合指针就是指向变量和对象的地址。指针的用途非常广泛，比如如果你想通过函数改变一个变量的值，就得用指针而不能用值传递。还有在很多时候变量，特别是对象的数据量实在太大，程序员就会用指针来做形参，只需要传递一个地址就行，大大提高了效率。指针就是指向变量和对象的地址。指针的用途非常广泛，比如如果你想通过函数改变一个变量的值，就得用指针而不能用值传递。还有在很多时候变量，特别是对象的数据量实在太大，程序员就会用指针来做形参，只需要传递一个地址就行，大大提高了效率。c语言之所以强大，以及其自由性，很大部分体现在其灵活的指针运用上。因此，说指针是c语言的灵魂，一点都不为过。链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。相比于线性表顺序结构，链表比较方便插入和删除操作。参考文献1 李素若,陈万华等编著.数据结构（c语言描述）.北京：中国水利水电出版社,2014.2 李素若,琚辉,严永松等编著.数据结构习题解答及上机指导.北京：中国水利水电出版社,2014.3 任正云，李素若编著.C语言程序设计.北京：中国水利水电出版社,2011.附录 全部代码/一元多项式计算/程序功能：能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输出/提示；输入完一个多项式之后，输入“00”结束本一元多项式的输入/注意；系数只精确到百分位，最大系数只能为999.99，指数为整数，如果需要输入更大的系数，可以对程序中5.2%f进行相应的修改#include#include#include#include/建立结构体typedef struct pnode float xishu;/系数 int zhishu;/指数 struct pnode *next;/下一个指针pnode;void open_()printf(n*n);printf(功能项:n 1 两个一元多项式相加；n 2 两个一元多项式相减:n 0 退出*n);printf(*nn请选择操作：);/调整多项式void tiaozhen(pnode *head) pnode *p,*q,*t; float temp; p=head; while(p!=NULL) q=p; t=q-next; while(t!=NULL) if(t-zhishuq-zhishu) q=t; t=t-next; temp=p-xishu;p-xishu=q-xishu;q-xishu=temp;temp=p-zhishu;p-zhishu=q-zhishu;q-zhishu=temp;p=p-next; /用头插法生成一个多项式，系数和指数输入0时退出输入pnode *creat() int m; float n; pnode *head,*rear,*s;/head为头指针，rear和s为临时指针 head=(pnode*)malloc(sizeof(pnode); rear=head;/指向头 scanf(%f,&n);/系数 scanf(%d,&m);/输入指数 while(n!=0)/输入0退出 s=(pnode *)malloc(sizeof(pnode); s-xishu=n; s-zhishu=m; s-next=NULL; rear-next=s;/头插法 rear=s; scanf(%f,&n);/输入系数 scanf(%d,&m);/输入指数 /12/head=head-next;/第一个头没有用到return head;/输出一元多项式函数：void shuchu(pnode *head)pnode *p;int one_time=1;p=head;while(p!=NULL)/如果不为空if(one_time=1)if(p-zhishu=0)/如果指数为0的话，直接输出系数printf(%5.2f,p-xishu);/如果系数是正的话前面就要加+号else if(p-xishu=1|p-xishu=-1)printf(X%d,p-zhishu);/如果系数是1的话就直接输出+x/如果系数是-1的话就直接输出-x号else if(p-xishu0)/如果系数是大于0的话就输出+系数x指数的形式printf(%5.2fX%d,p-xishu,p-zhishu);else if(p-xishuxishu,p-zhishu);one_time=0;elseif(p-zhishu=0)/如果指数为0的话，直接输出系数if(p-xishu0)printf(+%5.2f,p-xishu);/如果系数是正的话前面就要加+号elseprintf(%5.2f,p-xishu);else if(p-xishu=1)/如果系数是1的话就直接输出+x号printf(+X%d,p-zhishu);else if(p-xishu=-1)/如果系数是-1的话就直接输出-x号printf(X%d,p-zhishu);else if(p-xishu0)/如果系数是大于0的话就输出+系数x指数的形式printf(+%5.2fX%d,p-xishu,p-zhishu);else if(p-xishuxishu,p-zhishu);p=p-next;/指向下一个指针printf(n);/两个多项式的加法运算pnode*add(pnode*heada,pnode*headb)pnode*headc,*p,*q,*s,*r;/headc为头指针，r,s为临时指针，p指向第一个多项式并向右移动，q指向第2个多项式并向右移动float x;/x为系数的求和p=heada;/指向第一个多项式的头q=headb;/指向第二个多项式的头headc=(pnode*)malloc(sizeof(pnode);/开辟空间r=headc;while(p!=NULL&q!=NULL)/2个多项式的某一项都不为空时if(p-zhishu=q-zhishu)/指数相等的话x=p-xishu+q-xishu;/系数就应该相加if(x!=0)/相加的和不为0的话s=(pnode*)malloc(sizeof(pnode);/用头插法建立一个新的节点s-xishu=x;s-zhishu=p-zhishu;r-next=s;r=s;q=q-next;p=p-next;/2个多项式都向右移动 else if(p-zhishuzhishu)/p的系数小于q的系数的话，就应该复制q节点到多项式中s=(pnode*)malloc(sizeof(pnode);s-xishu=q-xishu;s-zhishu=q-zhishu;r-next=s;r=s;q=q-next;/q向右移动else/p的系数大于q的系数的话，就应该复制p节点到多项式中s=(pnode*)malloc(sizeof(pnode);s-xishu=p-xishu;s-zhishu=p-zhishu;r-next=s;r=s;p=p-next;/p向右移动 /当第二个多项式空，第1个数不为空时，将第一个数剩下的全用新节点产生while(p!=NULL)s=(pnode *)malloc(sizeof(pnode);s-xishu=p-xishu;r-next=s;r=s;p=p-next; /当第一个多项式空，第一个数不为空时，将第2个数剩下的全用新节点产生while(q!=NULL)s=(pnode *)malloc(sizeof(pnode);s-xishu=q-xishu;s-zhishu=q-zhishu;r-next=s;r=s;q=q-next;r-next=NULL;/最后剖指向空headc=headc-next;/第一个头没右用到return headc;/返回头节点/两个多项式的减法函数 pnode *sub(pnode *heada,pnode *headb) pnode *headc,*p,*q,*s,*r;/headc为头指针，r,s为临时指针，p指向第一个多项式并向右移动，q指向第二个多项式并向右移动float x;/x为系数的求和p=heada;/指向第一个多项式的头q=headb;/指向第二个多项式的头headc=(pnode*)malloc(sizeof(pnode);/开辟空间r=headc;while(p!=NULL&q!=NULL) /两个多项式的某一项都不为空时 if(p-zhishu=q-zhishu)/指数相等的话 x=p-xishu-q-xishu;/系数就应该相减if(x!=0) s=(pnode*)malloc(sizeof(pnode);/用头插法建立一个新的节点s-xishu=x;s-zhishu=p-zhishu;r-next=s;r=s; q=q-next;p=p-next;/2个多项式都向右移 else if(p-zhishuzhishu)/p的指数小于q的指数的话，就应该复制q节点到多项式 s=(pnode*)malloc(sizeof(pnode);s-xishu=-q-xishu;s-zhishu=q-zhishu;r-next=s;r=s;q=q-next;/q向右移动 else if(p-zhishuq-zhishu)/p的系数大于q的系数的话，就应该复制p节点到多项式 s=(pnode*)malloc(sizeof(pnode);s-xishu=p-xishu;s-zhishu=p-zhishu;r-next=s;r=s;p=p-next;/p向右移动 /当第二个多项式空，第一个数不为空时，将第一个数剩下的全用新节点产生while(p!=NULL) s=(pnode*)malloc(sizeof(pnode);s-xishu=p-xishu;s-zhishu=p-zhishu;r-next=s;r=s;p=p-next; /当第一个多项式空，第一个数不为空时，将第二个数剩下的全用新节点产生while(q!=NULL) s