数据结构报告一元多项式.docx

1、数据结构报告一元多项式数据结构课程设计报告主题：实现一元多项式抽象数据类型学号：20091003768班级：计科四班姓名：熊金莲指导老师：郭艳内容概要（1） 题目要求（2） 实现该一元多项式抽象数据类型的要点（3） 函数模块及各函数可实现的功能简介（4） 具体的源代码（5） 使用说明（6） 实验心得一：题目要求如下：1 构造一个空的多项式2 多项式插入新的一项3 多项式合并同类项4 多项式加法5 多项式乘法6 打印多项式7 计算多项式的值二：构思要点以链表形式创建两个多项式a与b，a与b的加法与乘法用到链式结构的操作。因为系数coef设置为浮点类型，指数expn设置为整形，所以构思是输入多项式

2、的系数和指数时，以0 0为输入结束标志，并设置这一判断语句。在插入函数中，寻找多项式适当的插入位置，可以实现多项式的升序排列，同时也在该插入函数中实现多项式合并同类项的功能。为实现多项式相加相乘定义了相加函数及相乘函数，实现a与b的相加相乘时直接调用。还有就是定义输出函数，打印各多项式。再者计算多项式的值时，先输入x的值，带入多项式计算即可。在主函数中使用switch语句，在此为了让本一元多项式功能步步展示，省去了各个case后的break语句。三：各函数模块1) /*第一,二部分 构造一个空的多项式并用链表插入法创建多项式*/void Insertlinklist(linklist p,li

3、nklist q) /*第一部分 链表插入*/ if(p-coef=0)free(p); /系数为0则该项为空 释放结点空间 else linklist q1,q2; q1=q;q2=q-next; while(q2&p-expnq2-expn)q1=q2;q2=q2-next; /寻找将插入的位置 if(q2&p-expn=q2-expn) q2-coef+=p-coef;free(p); if(q2-coef=0)q1-next=q2-next;free(q2); /系数为0则该项为空 释放结点空间 else p-next=q2;q1-next=p; /指数异于其他项指数时将结点插入 li

4、nklist Createlinklist(linklist head) /*第二部分 创建链表*/ linklist p;int n;float m; p=head=(linklist)malloc(sizeof(struct lnode); p-next=NULL; scanf(%f%d,&m,&n); while(m!=0|n!=0) /当输入为0 0时结束输入 p=(linklist)malloc(sizeof(struct lnode); p-coef=m;p-expn=n; Insertlinklist(p,head); /*调用第一部分函数*/ scanf(%f%d,&m,&n)

5、; return head;2）/*第二部分 销毁链表*/void Destroylinklist(linklist p) linklist q1=p-next,q2=q1-next; while(q2)free(q1);q1=q2;q2=q2-next;3）/*第三部分 打印链表*/void Printlinklist(linklist p) linklist q=p-next; int c=1; if(!q)putchar(0);printf(n);return; while(q) if(q-coef0&c!=1)putchar(+); if(q-coef!=1&q-coef!=-1) p

6、rintf(%f,q-coef); if(q-expn=1)putchar(x); else if(q-expn)printf(x%d,q-expn); else if(q-coef=1) if(!q-expn)putchar(1); else if(q-expn=1)putchar(x); else printf(x%d,q-expn); else if(q-coef=-1) if(!q-expn)putchar(-1); else if(q-expn=1)printf(-x); else printf(-x%d,q-expn); q=q-next; c+; /项数自加1 printf(n)

7、;4）/*第四部分 多项式非空判断*/int Comparelinklist(linklist a,linklist b) if(a&b) if(a-expnb-expn|!b) return -1; else if(!a|a-expnexpn) return 1; else return 0; else if(!a&b) return -1; /多项式a为空 b不为空 else return 1; /多项式不a为空 b为空5）/*第五部分 多项式相加*/linklist Addlinklist(linklist pa,linklist pb) linklist head,x,y,qa=pa-

8、next,qb=pb-next; x=(linklist)malloc(sizeof(struct lnode); x-next=NULL; head=x; while(qa|qb) y=(linklist)malloc(sizeof(struct lnode); switch(Comparelinklist(qa,qb) case -1: y-coef=qb-coef; y-expn=qb-expn; qb=qb-next; break; case 0: y-coef=qa-coef+qb-coef; y-expn=qa-expn; qa=qa-next; qb=qb-next; break

9、; case 1: y-coef=qa-coef; y-expn=qa-expn; qa=qa-next; break; if(y-coef!=0) y-next=x-next; x-next=y; x=y; else free(y); return head;6）/*第六部分 多项式相乘*/linklist Multiplylinklist(linklist pa,linklist pb) linklist qa=pa-next,qb=pb-next,w,v; w=(linklist)malloc(sizeof(struct lnode); w-next=NULL; for(;qa;qa=q

10、a-next) for(qb=pb-next;qb;qb=qb-next) v=(linklist)malloc(sizeof(struct lnode); v-coef=qa-coef*qb-coef; v-expn=qa-expn+qb-expn; Insertlinklist(v,w); /调用Insertlinklist函数合并指数相同的项 return w;7）/*第七部分 多项式赋值*/int Valuelinklist(linklist head,int x) int sum=0,i,j;linklist p; for(p=head-next;p;p=p-next) j=1; f

11、or(i=p-expn;i!=0;) if(icoef)*j; return sum;8）/*将多项式每一项都定义为结构体类型 分别有系数 指数 和指向下一个结构体的指针*/typedef struct lnode float coef; int expn; struct lnode *next;lnode,*linklist; 四：具体的源代码工程分多项式Linklist.h及多项式.cpp两部分/*多项式LinkList*/void Insertlinklist(linklist p,linklist q) /*第一部分 链表插入*/ if(p-coef=0)free(p); /系数为0则

12、该项为空 释放结点空间 else linklist q1,q2; q1=q;q2=q-next; while(q2&p-expnq2-expn)q1=q2;q2=q2-next; /寻找将插入的位置 if(q2&p-expn=q2-expn) q2-coef+=p-coef;free(p); if(q2-coef=0)q1-next=q2-next;free(q2); /系数为0则该项为空 释放结点空间 else p-next=q2;q1-next=p; /指数异于其他项指数时将结点插入 linklist Createlinklist(linklist head) /*第二部分 创建链表*/

13、linklist p;int n;float m; p=head=(linklist)malloc(sizeof(struct lnode); p-next=NULL; scanf(%f%d,&m,&n); while(m!=0|n!=0) /当输入为0 0时结束输入 p=(linklist)malloc(sizeof(struct lnode); p-coef=m;p-expn=n; Insertlinklist(p,head); /*调用第一部分函数*/ scanf(%f%d,&m,&n); return head;void Destroylinklist(linklist p) /*第三

14、部分 销毁链表*/ linklist q1=p-next,q2=q1-next; while(q2)free(q1);q1=q2;q2=q2-next;void Printlinklist(linklist p) /*第四部分 打印链表*/ linklist q=p-next; int c=1; if(!q)putchar(0);printf(n);return; while(q) if(q-coef0&c!=1)putchar(+); if(q-coef!=1&q-coef!=-1) printf(%f,q-coef); if(q-expn=1)putchar(x); else if(q-e

15、xpn)printf(x%d,q-expn); else if(q-coef=1) if(!q-expn)putchar(1); else if(q-expn=1)putchar(x); else printf(x%d,q-expn); else if(q-coef=-1) if(!q-expn)putchar(-1); else if(q-expn=1)printf(-x); else printf(-x%d,q-expn); q=q-next; c+; /项数自加1 printf(n);int Comparelinklist(linklist a,linklist b) /*第五部分 链表

16、非空判断*/ if(a&b) if(a-expnb-expn|!b) return -1; else if(!a|a-expnexpn) return 1; else return 0; else if(!a&b) return -1; /多项式a为空 b不为空 else return 1; /多项式不a为空 b为空linklist Addlinklist(linklist pa,linklist pb)/*第六部分 多项式相加*/ linklist head,x,y,qa=pa-next,qb=pb-next; x=(linklist)malloc(sizeof(struct lnode);

17、 x-next=NULL; head=x; while(qa|qb) y=(linklist)malloc(sizeof(struct lnode); switch(Comparelinklist(qa,qb) case -1: y-coef=qb-coef; y-expn=qb-expn; qb=qb-next; break; case 0: y-coef=qa-coef+qb-coef; y-expn=qa-expn; qa=qa-next; qb=qb-next; break; case 1: y-coef=qa-coef; y-expn=qa-expn; qa=qa-next; bre

18、ak; if(y-coef!=0) y-next=x-next; x-next=y; x=y; else free(y); return head;linklist Multiplylinklist(linklist pa,linklist pb) /*第七部分 多项式相乘*/ linklist qa=pa-next,qb=pb-next,w,v; w=(linklist)malloc(sizeof(struct lnode); w-next=NULL; for(;qa;qa=qa-next) for(qb=pb-next;qb;qb=qb-next) v=(linklist)malloc(s

19、izeof(struct lnode); v-coef=qa-coef*qb-coef; v-expn=qa-expn+qb-expn; Insertlinklist(v,w); /调用Insertlinklist函数合并指数相同的项 return w;int Valuelinklist(linklist head,int x) /*第八部分 多项式带值函数*/ int sum=0,i,j;linklist p; for(p=head-next;p;p=p-next) j=1; for(i=p-expn;i!=0;) if(icoef)*j; return sum;#include#inclu

20、de#includetypedef struct lnode float coef; int expn; struct lnode *next;lnode,*linklist; / 将多项式每一项都定义为结构体类型 分别有系数 指数 和指向下一个结构体的指针 typedef linklist ploynominal;#include 多项式LinkList.hvoid main() int a=1,x; char c; linklist pa=0,pb=0,pc; printf(功能如下：n); printf(1:输入多项式a:n); /该一元多项式所能实现的所有的功能 printf(2:输入

21、多项式b:n); printf(3:输出多项式a:n); printf(4:输出多项式b:n); printf(5:代入x的值计算a:n); printf(6:代入x的值计算b:n); printf(7:输出a+b:n); printf(8:输出a*b:n); printf(9:退出程序n); printf(从操作1开始执行,请输入1:);while(a) scanf(%c,&c); switch(c) /本swith语句中并未写break语句 目的是让程序从功能1到9依次执行下去 case1: printf(请以0 0为结束标志输入多项式a各项系数与指数:); pa=Createlinkli

22、st(pa); /*调用第二部分函数 创建链表pa*/ case2: printf(请以0 0为结束标志输入多项式b各项系数与指数:); pb=Createlinklist(pb); /*调用第二部分函数 创建链表pb*/ case3: printf(多项式a为：); Printlinklist(pa); /*调用第四部分函数 打印多项式a */ case4: printf(多项式b为：); Printlinklist(pb); /*调用第四部分函数 打印多项式b */ case5: printf(请输入x给多项式a赋值：); scanf(%d,&x); printf(x=%d时，a=%dn,

23、x,Valuelinklist(pa,x); /*调用第八部分函数 求多项式a的值*/ case6: printf(请输入x给多项式b赋值：); scanf(%d,&x); printf(x=%d时，b=%dn,x,Valuelinklist(pb,x); /*调用第八部分函数 求多项式b的值*/ case7: pc=Addlinklist(pa,pb); /*调用第六部分函数 实现多项式相加*/ printf(a+b=); Printlinklist(pc); /*调用第四部分函数 打印a+b和的多项式*/ printf(请输入x给a+b和的多项式赋值：); scanf(%d,&x); pr

24、intf(x=%d时，a+b=%dn,x,Valuelinklist(pc,x); /*调用第八部分函数 求多项式a-b的值*/ case8: pc=Multiplylinklist(pa,pb); /*调用第七部分函数 实现多项式相乘*/ printf(a*b=); Printlinklist(pc); /*调用第四部分函数 打印a*b积的多项式*/ printf(请输入x给a*b和的多项式赋值：); scanf(%d,&x); printf(x=%d时，a*b=%dn,x,Valuelinklist(pc,x);/*调用第八部分函数 求多项式a*b的值*/ case9: printf(程序

25、结束!); /*调用第三部分函数 销毁链表*/ Destroylinklist(pa); Destroylinklist(pb); a=0; default:printf(n此选择无效，请重新选择); 五：使用说明 新建工程，将两个部分分别插入适当位置，source files 里插入cpp文件，header files里插入 .h文件。运行操作按输出提示输入即可。输出如下六：实验心得构造一个空的多项式，运用尾插法，将新申请的结点接到最后，用while语句实现输入0 0时停止输入。多项式相乘时将多项式系数coef相乘，将指数expn相加，并调用InsertLinklist实现多项式的合并。本次课程设计我掌握了建立链表和删除链表的方法，懂得了用链表方式实现多项式加法与乘法的方法。同时深切感受到耐心与毅力是调试程序时的必备素质。