《数据结构课程设计,一元多项式》由会员分享，可在线阅读，更多相关《数据结构课程设计,一元多项式（19页珍藏版）》请在金锄头文库上搜索。
1、湖南工学院课程设计一元多项式计算班级：信息本1002学号： 09姓名：班级：信息本1002学号：26姓名：班级：信息本1002学号：34姓名：班级：信息本1002学号：41姓名：目 录一、课题任务1二、概要设计1三、详细设计2四、调试分析6五、测试结果6六、课程设计总结9七、参考文献9八、附录10一、课题任务功能： 1）能够按照指数降序排列建立并输出多项式； 2）能够完成两个多项式的相加，并将结果输出； 3）能根据输入的多项式及变量的值，能进行计算。并输出计算结果。 4）能对多个输入的表达式按照指数大小排序输出。二、概要设计一元多项式计算系统降序排列建立并输出多项式多项式的相加减并输出结果输入
2、的多项式及变量的值计算多个表达式按照指数大小排序输出按指数排序建立多项式相减建立多项式相加计算多项式建立多个多项式输出多式项或计算值排序后输出多个多项式排序三、详细设计一元多项式定义系数和指数结构如下： coefexpnnextcoef域-存放结点的系数值expn域-存放结点的指数值next域-存放结点的直接后继的地址（位置）的指针域（链域）一元多项式单链表存储结构：typedef struct term float coef; /系数 int expn; /指数 struct term *next; term;有了链表特定的数据类型term，接下来就需要建立这个链表。这里我们自定义一个构造函
3、数CreatePoly（）来构造链表。首先定义一个term型的指针变量h=p作为头结点，存储多项式的信息（项数），为h分配存储空间建立一个头结点并为其数据域赋值，分配存储空间用malloc()函数来实现；这时输入多项式的项数m，先给p的coef赋值为0，此时利用一个for循环将p链表的coef与expn值从键盘输入，用m来控制循环的次数，若该从键盘输入的coef值不为0，则将该数值插入链表新建链表q，用malloc（）分配给p空间，p=p-next继续从键盘输入coef与expn的值，直到满足p-next=null,输入完成，返回链表q即为多项式的系数与指数，创建多项式完成。在处理多项式相加的
4、问题上，由于事先建立的多项式函数已经按指数大小排好序，那么多项式的相加就变得不那么复杂了，我们只要找出两个相加多项式指数相同的项进行合并，即将指数相同的项的系数相加，其它的保持不变存好即可。而查找指数相同的项，只要按链表从头到尾进行扫描，若发现相同，则两个同时往下移，否则只将其中指数较大的往下移。假若两个指数相同的项进行合并时，其系数相加值为0，则消除该项，继续下去。在处理输入的多项式及变量的值计算结果的问题时，定义一个C（）函数实现，需要定义一个float变量sum来存储和值，再引用一个pow()函数来计算多项式的和，利用一个for循环来一一计算x的q-expn次方后与q-coef相乘的值，
5、并存储在sum中，q=q-next，直到q-next =unll，跳出for循环，返回 sum的值就是多项式在用x赋值后的值。对多个输入的表达式按照指数从大到小排序输出:，利用一个for（包含两个函数CreatPolyn(M,n);selsort(M);）循环，用scanf()输入k来控制for的次数可控制输入的多项式个数，并一个trem型数组Gi来保存每一个多项式，方便后来的按最高指数大小排序。排序的思想利用枚举排序法可将每个多项式最高次expn按从大到小排列并保存在Gi数组中，再次利用for将排序好的Gi多项式按指数从大到小输出。开始具体子功能流程图如下：输入变量x的值Nq不空Ysum+=
6、q-coef*pow(x,q-expn)q=q-nextreturn sum;完成多项式计算输出多项式的计算开始从键盘输入项数mmcoef*(-1)两多项式相加输出Pb？Pb=pb-nextYN 多个多项式排序 多项式相减 定义存储和链表h动态分配空间Pa&Pb?C=a-expn - b-expnh=UNLL返回系统C=1C=0h=Pb Pb = Pb-next;h=Pa Pa = Pa-next;sum = Pa-coef + Pb-coef;sum=0Pa-coef = sum;h=Pa;Pa=Pa-next;Pa = Pa-next;Pa=0Pb=0h-next = Pa;h-next
7、= Pa;h = h-next;Return hNYNYNYNYYNYYNN输出开始完成多项式相加调用函数查找同类项同类项系数相加进行合并合并后检查a b扫描是否完整输出多项式q流程图：putchar(1)printf(“x%d”,q-expn)Putchar(x)q-expn=0p=p-nextputchar (0);开始printf(“%g”,q-coef)q!=UNLLq-coef!=1q-expn=1q-coef=0q!=UNLLPutchar(+)退出 N Y N Y Y N Y N Y N Y N多项式输出主要是对已建立的多项式按链表从头到尾扫描指数跟系数进行多重判断，根据指数和系
8、数输出相应的数值与符号，直到多项式输出完成。四、调试分析程序的调试是程序顺利完成中非常关键的一步。通过程序的调试分析可以解决程序的运行错误也可以对程序的性能进行分析。这个多项式运算问题研究的程序最重要的就是看输出的链表是否正确，是否带有空结点，运行结果输出是否正确。决定程序成功与否的第一步是定义的CreatPolyn()函数操作是否正确，如果这一步中出现错误，那么接下来的操作可以说是错上加错。在调试的时候可以在程序中加入删除、释放空结点操作，此操作是由Delet()与free()函数完成的，若输出的多项式没有空结点说明函数正确，可以继续向下进行。接下来就是函数相加，控制此操作的关键是一个A (
9、)函数，其中调用APolyn（）函数是决定成功与否的关键，而函数的相减正是相加一个负数，将减数多项式的coef变为负值便实现了多项式的相减。可以先在本上写出两个正确的简单的多项式，使其具有相加后出现空结点的特点，然后变换循环变量的范围，当输出吻合时则说明操作正确。对于根据输入的多项式及变量的值进行计算，控制此操作的关键是如何计算多项式中多次方的值，此操作关键是一个C()函数，调用pow()函数来实现计算次方的功能，其中sum值的计算是否正确起关键作用。而对多个输入的表达式按照指数从大到小排序输出，这个主要是用到了一个trem型数组对各已按指数排序好的多项式保存，然后对数组中的每个多项式的第一个
10、p-expn值利用枚举排序法进行比较将多项式排序。各个关键部分都已检查完毕，剩下的就是对程序的进一步细心的完善化、美观化、清晰化直到满足要求。下面我们分析一下程序的性能。在主函数中，首先调用构造单链表函数CreatePoly()，在这个函数中需要通过一个for循环为每个结点分配存储空间，变换节点的next域，时间复杂度为O（n）。接下来执行selsort()函数对多项式进行按指数排序，其中一个双重for循环，在内部的for循环中是对相邻结点指数大小比较进行操作，所以每个结点的操作都需要m次，共n个结点，则需要mn次操作，时间复杂度为O（nn）。其后的for循环是比较将指数相同的数进行合并，时间复杂度为O（n）。五、测试结果系统选择界面如图 6-1图6-1测试按照指数降序排列输出多项式 8*x1+9*x0+7*x2+6*x3 输入数据为：1（enter）4（enter）8 1 9 0 7 2 6 3（enter）输出结果为：6*x3+7*x2+8*x1+9测试结果如图6-2图6-2测试两个多项式相加8*x1+9*x0+7*x2+6*x3; 0*x0+1*x3+5*x2；输入数据为：2（enter）4（enter）8 1 9 0 7 2 6 3 （enter）3（enter）0 0 1 3 5 2（
