《数据结构课程设计-一元多项式》由会员分享，可在线阅读，更多相关《数据结构课程设计-一元多项式（23页珍藏版）》请在金锄头文库上搜索。
1、一元多项式计算1设计目的(1) 掌握数据结构的应用、算法的编写方法。(2) 掌握类C语言的算法转换成C程序并用VC+上机调试的基本方法。(3) 学会结构体的定义和调用。(4) 学会单链表的初始化和建立。(5) 通过C语言使用链式存储结构实现一元多项式加法、减法和乘法的运算。按指数 降序排列。(6) 本课程设计是为了配合数据结构课程的开设，通过设计一完整的程序，使学 生掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并用TC上机调试 的基本方法。2 设计方案论证211设计思路实现的方法是先定义多项式结点的结构，该多项式每个结点由三个元素：输入的系数、 输入的指数、以及指向下一个结点的指
2、针构成。该链表采用链式存储结构。然后通过多 次的输入，依次得到两个一元多项式的各个项的系数与指数。该输入以零结尾。然后通 过对结点的判断是否为零后，进行运算或者终止的操作。再初始化一个链表LC,将LC 的各项系数和指数的指针指向LA+LB所得的结果的值，完成了最后的输出。(1) 定义结构体s true t结构体为表示一个对象的不同属性提供了连贯一致的方法，结构体类型的说明从关 键词struct开始，成员可以由各种数据类型混合构成，成员甚至还可以是数组或者其他 类型的结构，但是，结构体中不能包含自身定义类型的成员。使用typedef和struct定义 的新类型名称，其用途与内建类型的名称相同，可
3、以用来：声明和初始化结构体变量； 创建并根据自己的意愿初始化结构数组；(2) 单链表的建立单链表有两个域，data域和next域，一个是存放数据，一个是存放指针而且指向它的 后继。并且还有个head，称表结点，它一般不存放数据，只是做个特殊标记。表的结束 是NULL，也就是最后的那个链域next为空单链表的插入运算有两种，一种是头插法， 另一种是尾插法，这里运用的是尾插法（3）一元多项式的建立输入多项式采用插头的方式，输入多项式中一个项的系数和指数，就产生一个新的节点， 建立起它的右指针，并用头节点指向它；为了判断一个多项式是否结束，定义一个结束 标志，并输入非0时就继续，当输入0时，就结束一
4、个多项式的输入（4）显示一元多项式如果系数是大于0的话就输出+系数x指数形式；如果系数小于0的话输出系数x指数 形式；如果指数为0的话，直接输出系数；如果系数是的话就直接输出+x；如果系数是 -1的话直接输出-x输出多项式（5）一元多项式的加法计算它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果数相等的话，系数 就应该相加；相加的和不为0的话，用头插法建立一个新的节点。p的指数小于q的指 数的话，就应该复制q节点到多项式中。p的指数大于q的指数的话，就应该复制p节 点到多形式中。当第二个多项式为空时，第一个多项式不为空时，将第一个多项式用心 节点产生。当第一个多项式为空，第二个多项
5、式不为空时，将第二个多项式用新节点产 生（6）一元多项式的减法计算它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果数相等的话，系数 就应该相减；相加的和不为0的话，用头插法建立一个新的节点。p的指数小于q的指 数的话，就应该复制q节点到多项式中。p的指数大于q的指数的话，就应该复制p节 点到多形式中。并且建立的节点的系数为原来的相反数；当第二个多项式为空时，第一 个多项式不为空时，将第一个多项式用心节点产生。当第一个多项式为空，第二个多项 式不为空时，将第二个多项式用新节点产生，并且建立的节点系数为原来的相反数。（7）元多项式乘法运算它从两个多项式的头部开始，两个多项式的某一项都不
6、为空时，如果指数相等的话，系 数就应该相乘；相加的和不为0的话，用有插法建立一个新的节点p的指数小于q的指 数的话，就应该复制q节点到多形式中。p的指数大于q的指数的话，就应该复制p节 点到多项式中，当第二个多项式为空，第一个多项式不为空时，将第一个多项式用新节点产生。当第二个多项式为空，将第二个多项式用新节点产生。输入模块加法模块减法模块乘法模块输出模块输入系数和项 数，生成多项式对生成的多项式进行加法运算对生成的多项式进行减法运算对生成的多项式进行乘法运算输出多项式，并释放结点图1基本模块表元多项式计算一元多项式的建立一元多项式的加法一元多项式的减法图2总体功能模块图2.1.2数学模型在数
7、学上，一个一元多项式Pn（x）可按升幂写成：Pn（X）=Po+PlX+P2X2+Pnxn它由n+1个系数唯一确定，因此，在计算机中它可用一个线性表P来表示： P=（P，P1，P2,必）每一项的指数i隐含在其系数Pi的序号里，每一项的值顺序为各个多项式的系数值。加法模型假设Qm(X)是一元m次多项式，同样可用线性表Q来表示：Q=(q，qi，q2,qm)不失一般性，设mvn,则两个多项式相加的结果Rn(x)=P(x)+Q(x)也可用线性表R来表示， 为了更具一般性，设nm，相加的结果也可以用单链表来表示，规则是相同指数的项的 系数相加，所以P(x)+Q(x)=(p0+q0,p1+q1Pm+qm，P
8、m+1Pn)，例如：P(x)=2x4+5x2+3x+l,Q(x)=3x2+l,相加后 R(x)= 2x4+8x2+3x+2，用一维向量表表示分别为(1，3，5，0，2)+(1，0,3,) =(2,3,8,0，2),写成数学形式即为2x4+8x2+3x+2,结论正 确。减法模型假设Qm(X)是一元m次多项式，若以线性表Q表示，同上所述：Q=(q,qi，q2,q“)则两个多项式相减的结果可表示为Rn(x)=P(x)-Q(x)，和加法的数学模型相似，可以描述 为Rn(x)=P(x)+ (-Q(x),其相减的原理和加法一样，以数学表达式为P(x)-Q(x)=(p0-q0,p1-q1pm-qm，pm+1
9、pn)举例说明：设两个一元多项式分别为P(x)=2x4+5x2+3x+1 和Q(x)=3x2+1，Rn(x)=P(x)-Q(x)= 2x4+2x2+3x;写成一维向量形式计算 为(1, 3，5，0，2)-(1，0，3)=(0，3，2，0，2)，即证明该算法是可行的。乘法模型设两个一元多项式的线性表表示分别为Q=(q0,q1,q2, qm)和 P=(p0,P1,P2, ,Pn)，则 两个多项式相乘的结果可以表示为R=P*Q，为了根据更具一般性，设nm(以下同)，(P,P1,P2,，Pn)*(q，q1，q2,qm)=(P，P1，P2,必)* q0+(0，P0，P1，P2,，Pn)*q1+ +(0,
10、0,0,0 p0 ,p1,p2, ,pn)* qm，上述表达式中，每次相乘均要使第一个线性表表 示的多项式右移一位，显然，乘最后一项Pm时将右移m位0，两个多项式相乘的结果 可以表示为m+1个一元n次多项式乘以一个单项式，而单项式乘以一元n次多项式还 是一个一元n次多项式，最终将这m+1个一元多项式在相加，所以乘法的数学实现可 以依靠一元n次多项式的加法模型。为了能够清晰的表示上述过程，现简单举例如下: 设P(x)=2x2 +3和Q(x)=3x2+2x,用数学表达式相乘的结果R(x)=6x4+4x3+9x2+6x,但在计算 机中可以表示为(3, 0，2)*(0，2，3)=(3，0，2)*0+(
11、0，3，0，2)*2+(0，0,6)；显然，按照数6x4+4x3+9x2+6x,3,0,2) *3=(0,6,0,4) +(0,0,9,0,6) =(0,6, 9, 4,学模型的定义，可以将最终的结果是(0, 6, 9, 4, 6)写成数学式 结果与笔算结果一致，该算法是可行的。2.2.1定义函数及说明struct定义结构体createPoly-创建一个多项式链表outp_poly-输出一个多项式链表。Addpoly-多项式和的计算；Decpoly-多项式差的计算；Mulpoly-多项式积的计算；DelPoly-删除多项式；2.2.2输入一个一元多项式的项数#includevstdlib.h#
12、includevstdio.h#includevctype.htypedef struct term /项的表示，多项式的项作为LinkList的数据元素 float coef; 系数int expn; 指数struct term *next;term2.2.3输入n个非零项term* CreatPolyn(term *P,int m) / 算法 2.22/输入m项的系数和指数，建立表示一元多项式的有序链表Pif(m coef = 0.0;int i;printf(依次输入d个非零项n,m);for (i = 1; i coef, &P-expn);if(P-coef)q = P;P = P-
13、next = (term*)malloc(sizeof(term);q-next = NULL;free(P);return h; / CreatPolynterm* selsort(term *h) term *g, *p, *q;if(!h) return NULL;float f;int i, fini = 1;for(g = h;g-next&fini;g = g-next) fini = 0;for(p = h,q = h-next;q;p = p-next,q = q-next)if (p-expn expn) f = p-coef;i = p-expn;p-coef = q-co
14、ef;p-expn = q-expn;q-coef = f;q-expn = i;fini = 1;for(g = h,p = g-next;p;)if(g-expn=p-expn) g-coef += p-coef;g-next = p-next;q = p;p = p-next;free(q);else if(g-next) g = g-next;p = p-next;return h;2.2.4排序表示多项式，最好按照习惯，以次数的降序来排列各项。通过Xiang*Paixu(Xiang *h)函数，使一元多项式按照次数从大到小排列输出。其算法如下：Xiang* Paixu(Xiang *h)flag = 1;for(g = h;g-next&flag;g = g-next)flag = 0;for(p = h,q = h-next;q;p = p-next,q = q-next)if (p-Zhishu Zhishu)pq;flag = 1;for(g = h,p = g-next;p;)if(g-Zhishu = p-Zhishu)g=g+P；elseg = g
