搜索
一元多项式一、需求分析实现实系数一元多项式的创建，打印以及两个一元多项式的加、减、乘运算。（1）程序所能达到的功能：a.实现一元多项式的输入；b.实现一元多项式的输出；c.计算两个一元多项式的和并输出结果；d.计算两个一元多项式的差并输出结果；e.计算两个一元多项式的积并输出结果。（2）输入的形式和输入值的范围：输入要求：分行输入，每行输入一项，先输入多项式的指数，再输入多项式的系数，以00为结束标志，结束一个多项式的输入。输入形式：23-12301200输入值的范围：系数为int型，指数为float型。（3）输出的形式：要求：第一行输出多项式1；第二行输出多项式2；第三行输出多项式1与多项式2相加的结果多项式；第四行输出多项式1与多项式2相减的结果多项式；第五行输出多项式1与多项式2相乘的结果多项式注：多项式的每一项形如：2.0x^3,注意指数应保留一位小数；多项式按照升幂次序排列；系数为1的非零次项应略去系数，系数为0的项不能出现在结果中；指数为0的项应只输出系数；多项式的第一项系数符号为正时，不要输出“+”，其他项要输出“+”，“-”符号。-3.0x^-1-6.0x-2.0x^2-9.0x^3-4.0x^4-6.0x^6二、概要设计（1）：程序实现a.功能：将要进行运算的二项式输入输出；b.数据流入：要输入的二项式的系数与指数；c.数据流出：合并同类项后的二项式；d.程序流程图：二项式输入流程图；e.测试要点：输入的二项式是否正确，若输入错误则重新输入。（2）：数据类型ADTPolynomial{数据对象：D={ai|ai∈TermSet,i=1,2,…,m,m≥0TermSet中的每个元素包含一个表示系数的实数和表示指数的整数}开始申请结点空间输入二项式各项的系数x,指数y输入二项式的项数输出已输入的二项式是否输入正确合并同类项结束是否数据关系：R1={ai-1,ai|ai-1,ai∈D,且ai-1中的指数值＜ai中的指数值，i=2,…,n}基本操作：sort(Polyn&h);//对多项式进行排序print(Polynh);//输出多项式delZeroCoef(Polyn&h);//判断系数为零的情况merge(Polyn&h);//合并指数相同的项createList();//创建多项式addPoly(Polynh1,Polynh2);//多项式相加subPoly(Polynh1,Polynh2);//多项式相减multPoly(Polynh1,Polynh2);//多项式相乘}ADTPolynomial三、详细设计（1）：存储结构一元多项式的表示在计算机内可以用链表来表示，为了节省存储空间，只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减操作。（2）：数据链表由于采用链表的方法，我们可以建立3条链；一条用于存放多项式HA，一条用于存放多项式HB，还有一条用于存放新形成的HC。此外，我们的程序应具备以下几个功能：建立链表，撤销链表，打印链表，按要求插入一个新的结点，复制链表；为了使上面程序结构分析进一步细化，为了使程序结构更加清晰，我们可以把上面的内容都编写成函数形式。1、建立链表该程序建立链表的函数与大多数建立链表的操作基本一致，但是由于实体是一元多项式的关系。我们更希望，在处理客户输入的数据的同时，能对数据进行适当的处理。也就是数学上所说的，“对一元多项式进行化简，并按照降幂排序。”由于在前面的练习中，我们得知，在链表中插入一个结点的函数，具有对链表的成员进行排序与合并的功能。如此一来，我们可以巧妙地处理，在建立链表的同时，调用”在链表中插入一个结点的函数”，对新建立的链表进行化简。该函数的算法描述如下；1)声明指针变量，并作为头指针的指针变量赋初值NULL；2)创建一个新的结点，并输入链表的信息；3)若输入的系数值与函数值同不为0时，调用”在链表中插入一个结点的insert函数”，将结点插入链表中；(注：这里建立链表的函数与以往的不同，我们是通过假想有一条空链，不断地调用insert函数来实现建立链表的功能。简言之；链表中成员的链接全都靠insert函数来实现，而该函数仅仅是不断地提供建立链表所要的数据罢了。)4)若还要继续插入结点，转到步骤2继续进行；5)否则，程序结束，把头指针返回主程序。2、撤销链表撤销链表是为了把链表所占用的地址回收起来，防止造成浪费。我们该程序可以采用从链表的始端逐步销去结点。在这个过程中，我们需要链表的头地址作为形式参数，还需要建立一个指针用来指向新头地址。该函数的算法描述如下：1)指针变量；并把头地址指针赋给新指针变量；2)把头地址指针指向下一个结点；3)删除新指针变量；4)若还要继续删除结点，转到步骤1继续执行；5)否则，结束程序。3、打印链表为了直观地了解链表的内容，我们设计出依次输出链表结点的函数。由于该题目对链表的输出格式又有了一定的要求，因此该函数设计也有着不一样的地方。依题意得；首先输出系数，系数后面紧跟着一个符号”X”；再输出指数，指数的前面带有符号”^”；而且相邻的结点都要用”+”或”-”链接起来，因此我们还要对系数的正负进行判断（由于头地址比较特殊，所以头地址除外）。系数为正，要输出符号”+”；系数为负时，编译时会自动加入符号”-”,所以不必再输出符号”-”。该函数的算法描述如下：1)建立一个新的指针变量，并把头指针赋给它；2)如果为空，则打印出”全空”的语句；3)由于该程序没有删除结点的函数，所以碰到系数为”0”时，我们直接跳到步骤7；4)否则，先以”系数X^指数”的形式输出头结点的成员；5)若还要继续输出结点，就判断系数的正负；1，若系数为正，以”+系数X^指数”的形式输出；2，若系数为负，以”系数X^指数”的形式输出；6)把新指针指向下一个结点；7)若还要继续输出结点，转到步骤3继续执行；8)否则，结束程序。4、按要求插入一个新的结点由于前面的建立链表的creat函数，调用了该函数，所以我们这个函数的设计思想也明朗多了，由于建立的链表是有序的，并且需要合并指数相同的结点，所以要新结点需要按指数值降幂的顺序插入链表中。判断链表是否为空，如果为空则直接插入即可；否则按照要插入结点指数值的大小在链表中寻找他要插入的位置，对于插入位置有第一个节点、最后一个结点和链表中间这三种情况分别进行处理。函数的形式参数：链表的头地址，指向要插入结点的指针；返回结果：插入结点后新链表的头地址。该函数的算法描述如下：1）声明指针变量并令它指向连头结点；2）判断指向要插入结点的指针是否为空；3）如果是，则不需要插入新结点，直接返回头地址，程序结束；4）否则再判断链表是否为空；5）如果是，则直接插入结点，然后返回链表的头地址，程序结束；6）否则，在链表中寻找待插入结点的插入位置：1，若链表中存在着与“插入的结点”的指数相同的情况，我们依然插入链中，只是把该结点的系数修改为”0”，把链中的结点系数修改为”两系数之和”。(为了方便，我们并没有把结点进行删除的操作，只是在输出的操作里加入权限设置。)2，若链表中不存在着与“插入的结点”的指数相同的情况，我们正常地插入链中。7）返回插入结点后链表的头地址，程序结束。5、主函数主函数主要负责输出界面的指引语句，并合理地调用各个函数，还要有适当的循环操作以及停止循环的语句，以致可以方便地达到合并两个一元多项式的功能。（3）：函数的调用关系：四、调试分析（1）调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析:在输入诸如“0,3”，“2,0”时，程序无法正常运行或总是出错.解决：对指数或系数为0的情况应单独讨论。为此，建立了delZeroCoef函数来解决问题。（2）算法的时间复杂度及改进算法的时间复杂度：一元多项式的加法运算的时间复杂度为O(m+n）,减法运算的时间复杂度为O(m-n)，其中m，n分别表示二个一元多项式的项数。createListprintaddPolysubPolymultPolymainprintmergeprintprintmergemergemergesortdelZeroCoef问题和改进思想：在设计该算法时，出现了一些问题，例如在建立链表时头指针的设立导致了之后运用到相关的指针时没能很好的移动指针出现了数据重复输出或是输出系统缺省值，不能实现算法。实现加法时该链表并没有向通常那样通过建立第三个链表来存放运算结果，而是再度利用了链表之一来进行节点的比较插入删除等操作。为了使输入数据按指数降序排列，可在数据的输入后先做一个节点的排序函数，通过对链表排序后再进行之后加减运算。五、总结与分析一元多项式的表示与其运算设计，运行结果能表达多项式，包括其系数及指数，也实现了多项式的相加、相减以及相乘，运行结果符合一元多项式的在实际运用中的运算法则。使用该程序能快捷方便计算出多个复杂的一元多项式的计算，体现了本设计的可行性以及实用性。集合的表示与运算设计，运行结构能表达出输入的集合元素并以集合形式输出，也实现了集合的相并、相交、求差集，运行结果符合集合运算法则，操作简单方便，体现了本设计的可行性以及实用性。两个设计具有一定共同点，均运用了数据结构中线性结构的内容。一元多项式构造链表存放数据与集合构造链表存放集合元素原理相仿，而两者均运用到switch语句实现运算操作，由于两者要求的运算操作较多，使用switch语句实行多分支选择则可简化程序，同时使程序显得精辟。设计期间，翻阅资料让我对数据结构有了重新的认识，比如说能区分出C语言以及C++语言，操作时，常常会出现程序无误确无法运行，这就是程序中含有C语言又含有C++，语句无误但是程序是不正确的。有时候是因为没有调用好语句。而设计中另外的收获就是可以趁着上机的机会巩固数据结构的知识，尤其是线性表一章的内容。要想学好数据结构以及课程设计，多操作是难免的，熟悉掌握各种类型的设计思路。刚开始要从基础程序入手，以课本上的例题为准，反复练习打好基础，再找一些课外的资料，以帮助开拓思路，提高自己的分析、解决能力，掌握一般的规律。今后的学习也要继续这样的学习态度，不断钻研，力争上游，为将来的大设计、大项目打下扎实的基础。五、源程序代码#includestdlib.h#includestdio.h#includectype.htypedefstructLNode{floatcoef;intexpn;structLNode*next;}LNode;LNode*InitPolyn(LNode*La,intn){if(n=0)returnNULL;LNode*h=La=(LNode*)malloc(sizeof(LNode)),*Lb;La-coef=0.0;inti;printf(依次输入%d个非零项（每项前一个为系数，后一个为指数）\n,n);for(i=1;i=n;++i){scanf(%f%d,&La-coef,&La-expn);if(La-coef)Lb=La;La=La-next=(LNode*)malloc(sizeof(LNode));}Lb-next=NULL;free(La);returnh;}LNode*selsort(LNode*h){LNode*g,*La,*Lb;if(!h)returnNULL;floatf;inti,fini=1;for(g=h;g-next&&fini;g=g-next){fini=0;for(La=h,Lb=h-next;Lb;La=La-next,Lb=Lb-next)if(La-expnLb-expn){f=La-coef;i=La-expn;La-coef=Lb-coef;La-expn=Lb-expn;Lb-coef=f;Lb-expn=i;fini=1;}}fo