数据结构课程设计-一元多项式.doc

课程设计说明书 no.22一元多项式计算1.设计目的（1）掌握数据结构的应用、算法的编写方法。（2）掌握类c语言的算法转换成c程序并用vc+上机调试的基本方法。（3）学会结构体的定义和调用。（4）学会单链表的初始化和建立。（5） 通过c语言使用链式存储结构实现一元多项式加法、减法和乘法的运算。按指数降序排列。（6）本课程设计是为了配合数据结构课程的开设，通过设计一完整的程序，使学生掌握数据结构的应用、算法的编写、类c语言的算法转换成c程序并用tc上机调试的基本方法。2 .设计方案论证2.1.1设计思路实现的方法是先定义多项式结点的结构，该多项式每个结点由三个元素：输入的系数、输入的指数、以及指向下一个结点的指针构成。该链表采用链式存储结构。然后通过多次的输入，依次得到两个一元多项式的各个项的系数与指数。该输入以零结尾。然后通过对结点的判断是否为零后，进行运算或者终止的操作。再初始化一个链表lc，将lc的各项系数和指数的指针指向la+lb所得的结果的值，完成了最后的输出。（1）定义结构体-struct结构体为表示一个对象的不同属性提供了连贯一致的方法，结构体类型的说明从关键词struct开始，成员可以由各种数据类型混合构成，成员甚至还可以是数组或者其他类型的结构，但是，结构体中不能包含自身定义类型的成员。使用typedef和struct定义的新类型名称，其用途与内建类型的名称相同，可以用来：声明和初始化结构体变量；创建并根据自己的意愿初始化结构数组； (2) 单链表的建立单链表有两个域，data域和next域，一个是存放数据，一个是存放指针而且指向它的后继。并且还有个head，称表结点，它一般不存放数据，只是做个特殊标记。表的结束是null，也就是最后的那个链域next为空单链表的插入运算有两种，一种是头插法，另一种是尾插法，这里运用的是尾插法（3）一元多项式的建立输入多项式采用插头的方式，输入多项式中一个项的系数和指数，就产生一个新的节点，建立起它的右指针，并用头节点指向它；为了判断一个多项式是否结束，定义一个结束标志，并输入非0时就继续，当输入0时，就结束一个多项式的输入（4）显示一元多项式如果系数是大于0的话就输出+系数x指数形式；如果系数小于0的话输出系数x指数形式；如果指数为0的话，直接输出系数；如果系数是的话就直接输出+x；如果系数是-1的话直接输出-x输出多项式 （5）一元多项式的加法计算它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果数相等的话，系数就应该相加；相加的和不为0的话，用头插法建立一个新的节点。p的指数小于q的指数的话，就应该复制q节点到多项式中。p的指数大于q的指数的话，就应该复制p节点到多形式中。当第二个多项式为空时，第一个多项式不为空时，将第一个多项式用心节点产生。当第一个多项式为空，第二个多项式不为空时，将第二个多项式用新节点产生（6）一元多项式的减法计算它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果数相等的话，系数就应该相减；相加的和不为0的话，用头插法建立一个新的节点。p的指数小于q的指数的话，就应该复制q节点到多项式中。p的指数大于q的指数的话，就应该复制p节点到多形式中。并且建立的节点的系数为原来的相反数；当第二个多项式为空时，第一个多项式不为空时，将第一个多项式用心节点产生。当第一个多项式为空，第二个多项式不为空时，将第二个多项式用新节点产生，并且建立的节点系数为原来的相反数。（7）一元多项式乘法运算它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相等的话，系数就应该相乘；相加的和不为0的话，用有插法建立一个新的节点p的指数小于q的指数的话，就应该复制q节点到多形式中。p的指数大于q的指数的话，就应该复制p节点到多项式中，当第二个多项式为空，第一个多项式不为空时，将第一个多项式用新节点产生。当第二个多项式为空，将第二个多项式用新节点产生。 输入模块加法模块减法模块乘法模块输出模块输入系数和项数，生成多项式对生成的多项式进行加法运算对生成的多项式进行减法运算对生成的多项式进行乘法运算输出多项式，并释放结点图1 基本模块表一元多项式计算一元多项式的建立一元多项式的加法一元多项式的减法一元多项式的乘法一元多项式的输出图2 总体功能模块图2.1.2 数学模型在数学上，一个一元多项式pn(x)可按升幂写成 ：pn(x)=p0+p1x+p2x2+pnxn它由n+1个系数唯一确定，因此，在计算机中它可用一个线性表p来表示：p=（p0 ,p1,p2,pn）每一项的指数i隐含在其系数pi的序号里，每一项的值顺序为各个多项式的系数值。加法模型假设 qm(x)是一元m次多项式，同样可用线性表q来表示：q=(q0,q1,q2,qm)不失一般性，设mm ，相加的结果也可以用单链表来表示，规则是相同指数的项的系数相加，所以p(x)+q(x)=（p0+q0,p1+q1pm+qm，pm+1pn），例如：p(x)=2x4+5x2+3x+1,q(x)=3x2+1,相加后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=(q0,q1,q2,qn)则两个多项式相减的结果可表示为rn(x)=p(x)-q(x)，和加法的数学模型相似，可以描述为rn(x)=p(x)+（-q(x)），其相减的原理和加法一样,以数学表达式为p(x)-q(x)=（p0-q0,p1-q1pm-qm，pm+1pn）举例说明：设两个一元多项式分别为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（以下同），（p0 ,p1,p2,pn）*(q0,q1,q2,qm)=（p0 ,p1,p2,pn）* q0+（0,p0 ,p1,p2,pn）*q1+（0,0,0,0p0 ,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+（0，3，0，2）*2+（0，0，3，0，2）*3=（0，6，0，4）+（0，0，9，0，6）=（0，6，9，4，6）；显然，按照数学模型的定义，可以将最终的结果是（0，6，9，4，6）写成数学式6x4+4x3+9x2+6x，结果与笔算结果一致，该算法是可行的。2.2.1 定义函数及说明struct-定义结构体createpoly-创建一个多项式链表outp_poly-输出一个多项式链表。addpoly-多项式和的计算；decpoly-多项式差的计算；mulpoly-多项式积的计算；delpoly-删除多项式；2.2.2输入一个一元多项式的项数#include #include #include typedef struct term /项的表示，多项式的项作为linklist的数据元素 float coef; /系数 int expn; /指数 struct term *next; term2.2.3输入n个非零项term* creatpolyn(term *p,int m) / 算法2.22 / 输入m项的系数和指数，建立表示一元多项式的有序链表p if(m coef = 0.0; int i; printf(依次输入%d个非零项n,m); for (i = 1; i coef,&p-expn); if(p-coef) q = p; p = p-next = (term*)malloc(sizeof(term); q-next = null; free(p); return h; / creatpolyn term* 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-coef;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; else g = g-next; p = p-next; return h; 然后调用xiang* jiafa(xiang *pa, xiang *pb)函数，再通过调用其子函数xiang* apolyn(xiang *pa, xiang *pb)，实现多项式加法，即pa = papb，利用两个多项式的结点构成多项式的和。通过对xiang* jianfa(xiang *pa, xiang *pb)函数和xiang* bpolyn(xiang *pa, xiang *pb)函数的调用，实现了多项式的减法，即pa = pa-pb，利用两个多项式的结点构成多项式的差。.通过调用xiang* chengfa(xiang *pa, xiang *pb)函数和xiang* cpolyn(xiang *pa, xiang *pb)函数，实现了多项式的乘法运算，即pa = pa*pb，利用两个多项式的结点构成多项式的积。通过对输出函数void shuchu(xiang *p)的调用，把各一元多项式和一元多项式的计算结果输出来2.2.5单连表的抽象数据类型定义：adt list数据对象：d=ai|aielemset,i=1,2,n,n0数据关系：r1=| ai-1, aid,i=2,n基本操作：initlist（l）/操作结果：构造一个空的线性表creatpolyn(&l)/操作结果：构造一个以单连表存储的多项试disppolyn(l)/操作结果：显示多项试polyn(&pa,&pb)/操作结果：显示两个多项试相加，相减的结果 adt list2.2.6 加法，减法，乘法模块加法模块函数功能：实现两个多项式想加，并将计算结果存储于pa中原理：将指数相同的项的系数加pa, 与pb的幂次序都要求是升序，否则可能得到错误的结果/加法模块函数如下:void addpoly(link pa,link pb) link pc,pre,u; float sum; pc=pa; pre=pa; pa=pa-next; u=pb; pb=pb-next; free(u); while(pa & pb) if (pa-exp exp) /如果当前pa的幂小于pb则指向pa中的下一个节点 pre=pa; pa=pa-next; else if (pa-exp pb-exp) u=pb-next; pb-next=pa; pre-next=pb; pre=pb; pb=u; else sum = pa-coef + pb-coef;/指数相加 if(sum!=0.0) pa-coef = sum; pre=pa; else pre-next = pa-next; free(pa); pa=pre-next; u=pb; pb=pb-next; free(u); if(pb) pre-next = pb;/end addpoly理论分析:加法模块的实现比较简单，在这里需要说明的是，对同指数的项进行运算，所以所加法实际上是四则运算的基础减法模块：函数功能：实现两个多项式相减原理：与加法类似，将指数相同的指数相减乘法模块：理论分析：多项式乘法可以由两个一元多项式相加的算法来实现，因为乘法运算可以分解为一系列的加法运算。假设a(x)和b(x)为如下的多项式，则m(x) =a(x)*b(x)=a(x)*b1xe1+b2xe2+bnxen则会分解成很多个单项式乘以多项式的问题，即每一项都是一个一元多项式，最后又是一元单项式相加的问题。2.3设计方法1输入一元多项式的个数2输入该多项式的非零项并显示出多项式3进行多项式的加 减 乘运算2.4源程序#include #include #include typedef struct term /项的表示，多项式的项作为linklist的数据元素 float coef; /系数 int expn; /指数 struct term *next; term; term* creatpolyn(term *p,int m) / 算法2.22 / 输入m项的系数和指数，建立表示一元多项式的有序链表p if(m coef = 0.0; int i; printf(依次输入%d个非零项n,m); for (i = 1; i coef,&p-expn); if(p-coef) q = p; p = p-next = (term*)malloc(sizeof(term); q-next = null; free(p); return h; / creatpolyn term* 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-coef;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; void printfpoly(term *p) term *q = p; if(!q) putchar(0); return; if(q-coef!=1) printf(%g,q-coef); if(q-expn=1) putchar(x); else if(q-expn) printf(x%d,q-expn); else if(!q-expn) putchar(1); else if(q-expn=1) putchar(x); else printf(x%d,q-expn); q = q-next; while (q) if(q-coef 0) putchar(+); if(q-coef!=1) printf(%g,q-coef); if(q-expn=1) putchar(x); else if(q-expn) printf(x%d,q-expn); else if(!q-expn) putchar(1); else if(q-expn=1) putchar(x); else printf(x%d,q-expn); q = q-next; compare(term *a, term *b) if (a-expn expn) return -1; if (a-expn b-expn) return 1; return 0; term* apolyn(term *pa, term *pb) / 算法2.23 / 多项式加法：pa = papb，利用两个多项式的结点构成和多项式。 term *h, *qa = pa, *qb = pb, *p, *q; float sum; h = p = (term*)malloc(sizeof(term); p-next = null; while (qa & qb) / pa和pb均非空 switch (compare(qa,qb) case -1: / 多项式pa中当前结点的指数值小 p-next = qb; p = qb; qb = qb-next; break; case 0: / 两者的指数值相等 sum = qa-coef + qb-coef; if (sum != 0.0) / 修改多项式pa中当前结点的系数值 p-next = qa; qa-coef = sum; p = qa; qa = qa-next; else / 删除多项式pa中当前结点 q = qa; qa = qa-next; free(q); q = qb; qb = qb-next; free(q); break; case 1: / 多项式pb中当前结点的指数值小 p-next = qa; p = qa; qa = qa-next; break; / switch / while if (pa) p-next = qa; / 链接pa中剩余结点 if (pb) p-next = qb; / 链接pb中剩余结点 q = h; h = h-next; free(q); return h; / apolyn term* a(term *pa, term *pb) int n; puts(再输入一一元多项式的项数); scanf(%d,&n); pb = creatpolyn(pb,n); pb = selsort(pb); printfpoly(pa); if(pb & pb-coef0) printf( + ); printfpoly(pb); pa = apolyn(pa,pb); printf( = ); pa = selsort(pa); printfpoly(pa); return pa; term* bpolyn(term *pa, term *pb) / 算法2.23 / 多项式减法：pa = pa-pb，利用两个多项式的结点构成差多项式。 term *p = pb; while(p) p-coef *= -1; p = p-next; return apolyn(pa,pb); / bpolyn term* b(term *pa, term *pb) int n; puts(再输入一一元多项式的项数); scanf(%d,&n); pb = creatpolyn(pb,n); pb = selsort(pb); printfpoly(pa); printf( - ); putchar();printfpoly(pb);putchar(); pa = bpolyn(pa,pb); printf( = ); pa = selsort(pa); printfpoly(pa); return pa; term* cpolyn(term *pa, term *pb) / 算法2.23 / 多项式乘法：pa = pa*pb，利用两个多项式的结点构成积多项式。 if(!pb) return null; term *pa = pa, *p, *q, *r, *s, *t; r = p = (term*)malloc(sizeof(term); while(pa) p-coef = pa-coef; p-expn = pa-expn; q = p; p = p-next = (term*)malloc(sizeof(term); pa = pa-next; q-next = null; free(p); pa = pa; t = s = (term*)malloc(sizeof(term); while(pa) q = s; s = s-next = (term*)malloc(sizeof(term); pa = pa-next; q-next = null; free(s); pa = pa; while(pa) pa-coef *= pb-coef; pa-expn += pb-expn; pa = pa-next; pb = pb-next; while(pb) p = r; s = t; while(p) s-coef = p-coef * pb-coef; s-expn = p-expn + pb-expn; p = p-next; s = s-next; pa = apolyn(pa,t); pb = pb-next; return pa; / cpolyn term* c(term *pa, term *pb) int n; puts(再输入一一元多项式的项数); scanf(%d,&n); pb = creatpolyn(pb,n); pb = selsort(pb); putchar();printfpoly(pa);putchar(); printf( * ); putchar();printfpoly(pb);putchar(); printf( = ); pa = cpolyn(pa,pb); pa = selsort(pa); printfpoly(pa); return pa; void main() term *m,*n; char s2; int i,n; puts(一元多项式计算:n输入一一元多项式的项数); scanf(%d,&n); m = creatpolyn(m,n); m = selsort(m); printfpoly(m); p: puts(n1:加n2:减n3:乘n4:退出); getchar(); q: gets(s); if(s1!=0 | !isdigit(*s) puts(输入有误,请重新输入!);goto q; i = *s-48; switch(i) case 1:m = a(m,n);goto p; case 2:m = b(m,n);goto p; case 3:m = c(m,n);goto p; case 4:break; default:puts(输入有误,请重新输入!);goto q; 3.设计结果与分析图1 输入一个一元多项式的项数图2 依次输入三个非零项图3 两个多项式相加图4 两个多项式相减图5 两个多项式相乘4.设计结论一元多项式的机器研究后我们将会看到一元n次多项式与n维线性空间同构，这极大的扩展了其在工程领域的计算问题，在计算机中能够实现n维空间的四则运算，这实际上是用计算机来解决数学问题，研究最基本的运算规律，为数学研究提供了很大的帮助。实现的方法是先定义多项式结点的结构，该多项式每个结点由三个元素：输入的系数、输入的指数、以及指向下一个结点的指针构成。该链表采用链式存储结构。然后通过多次的输入，依次得到两个一元多项式的各个项的系数与指数。该输入以零结尾。然后通过对结点的判断是否为零后，进行运算或者终止的操作。再初始化一个链表lc