数据结构课程设计-顺序结构动态链表结构下的一元多项式的加法、减法、乘法的实现.doc

安徽省巢湖学院计算机与信息工程学院课程设计报告课程名称 数据结构 课题名称 顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现专业 计算机科学与技术 班级 10计本2班 学号10012116姓名 联系方式 指导教师20 11 年 12 月 28 日目 录1、数据结构课程设计任务书1.1、题目1.2、要求2、总体设计2.1、功能模块设计2.2、所有功能模块的流程图3、详细设计3.1、程序中所采用的数据结构及存储结构的说明3.2、算法的设计思想3.3、稀疏矩阵各种运算的性质变换4、调试与测试：4.1、调试方法与步骤：4.2、测试结果的分析与讨论：4.3、测试过程中遇到的主要问题及采取的解决措施：5、时间复杂度的分析：6、源程序清单和执行结果7、c程序设计总结8、致谢9、参考文献1、数据结构课程设计任务书1.1、题目要求顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现2、总体设计2.1、功能模块设计2.2、所有功能模块的流程图3、详细设计1顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现。可以分为几个模块：输入模块、输出模块（升幂降幂）、数据处理模块（多项式的加减乘）、主程序模块。2在程序过程中加入汉字提示符，让读者清楚明白的操作该程序。运行程序时看起来简洁有序，操作简单明了。3程序执行时的命令：选择创建两个一元多项式输入第一个一元多项式的项数依次输入一元多项式的系数和指数以相同方式输入第二个一元多项式选择操作方式选择降幂或升幂排序输出结果是否退出4.测试数据。输入的一元多项式系数指数分别为7 0,3 1,9 8,5 17和8 1,22 7，-9 8。加法结果为；升幂 降幂减法结果为：升幂 降幂乘法结果为：升幂 降幂 3.1、程序中所采用的数据结构及存储结构的说明#include#includetypedef struct float coef; /系数 int expn; /指数#include#includetypedef struct float coef; /系数 int expn; /指数term;typedef struct lnode term data; /term多项式值 struct lnode *next;lnode,*linklist;typedef linklist polynomail;/*比较指数*/int cmp(term a,term b) if(a.expnb.expn) return 1; if(a.expn=b.expn) return 0; if(a.expnnext!=null;p=p-next); r=p; for(h=pa;h-next!=r;)/大的沉底 for(p=h;p-next!=r&p!=r;p=p-next) if(cmp(p-next-data,p-next-next-data)=1) q=p-next-next; p-next-next=q-next; q-next=p-next; p-next=q; r=p;/r指向参与比较的最后一个，不断向前移动 /*由大到小排序*/void arrange2(polynomail pa) polynomail h=pa,p,q,r; if(pa=null) exit(-2); for(p=pa;p-next!=null;p=p-next); r=p; for(h=pa;h-next!=r;)/小的沉底 for(p=h;p-next!=r&p!=r;p=p-next) if(cmp(p-next-next-data,p-next-data)=1) q=p-next-next; p-next-next=q-next; q-next=p-next; p-next=q; r=p;/r指向参与比较的最后一个，不断向前移动 /*打印多项式,求项数*/int printpolyn(polynomail p) int i; polynomail q; if(p=null) printf(无项！n); else if(p-next=null) printf(y=0n); else printf(该多项式为y=);q=p-next;i=1; if(q-data.coef!=0&q-data.expn!=0) printf(%.2fx%d,q-data.coef,q-data.expn); i+; if(q-data.expn=0&q-data.coef!=0) printf(%.2f,q-data.coef);/打印第一项 q=q-next; if(q=null) printf(n);return 1; while(1)/while中，打印剩下项中系数非零的项， if(q-data.coef!=0&q-data.expn!=0) if(q-data.coef0) printf(+); printf(%.2fx%d,q-data.coef,q-data.expn); i+; if(q-data.expn=0&q-data.coef!=0) if(q-data.coef0) printf(+); printf(%f,q-data.coef); q=q-next; if(q=null) printf(n); break; return 1;/*1、创建并初始化多项式链表*/polynomail creatpolyn(polynomail p,int m) polynomail r,q,p,s,q; int i; p=(lnode*)malloc(sizeof(lnode); r=p; for(i=0;idata.coef,&s-data.expn); r-next=s; r=s; r-next=null; if(p-next-next!=null) for(q=p-next;q!=null/*&q-next!=null*/;q=q-next)/合并同类项 for(p=q-next,r=q;p!=null;) if(q-data.expn=p-data.expn) q-data.coef=q-data.coef+p-data.coef; r-next=p-next; q=p;p=p-next; free(q); else r=r-next; p=p-next; return p;/*2、两多项式相加*/polynomail addpolyn(polynomail pa,polynomail pb) polynomail s,newp,q,p,r;int j; p=pa-next;q=pb-next; newp=(lnode*)malloc(sizeof(lnode); r=newp; while(p&q) s=(lnode*)malloc(sizeof(lnode); switch(cmp(p-data,q-data) case -1: s-data.coef=p-data.coef; s-data.expn=p-data.expn; r-next=s; r=s; p=p-next; break; case 0: s-data.coef=p-data.coef+q-data.coef; if(s-data.coef!=0.0) s-data.expn=p-data.expn; r-next=s; r=s; p=p-next; q=q-next; break; case 1: s-data.coef=q-data.coef; s-data.expn=q-data.expn; r-next=s; r=s; q=q-next; break; /switch /while while(p) s=(lnode*)malloc(sizeof(lnode); s-data.coef=p-data.coef; s-data.expn=p-data.expn; r-next=s; r=s; p=p-next; while(q) s=(lnode*)malloc(sizeof(lnode); s-data.coef=q-data.coef; s-data.expn=q-data.expn; r-next=s; r=s; q=q-next; r-next=null; for(q=newp-next;q-next!=null;q=q-next)/合并同类项 for(p=q;p!=null&p-next!=null;p=p-next) if(q-data.expn=p-next-data.expn) q-data.coef=q-data.coef+p-next-data.coef; r=p-next; p-next=p-next-next; free(r); printf(升序 1 , 降序 2n); printf(选择:); scanf(%d,&j); if(j=1) arrange1(newp); else arrange2(newp); return newp;/*3、两多项式相减*/polynomail subpolyn(polynomail pa,polynomail pb) polynomail s,newp,q,p,r,q; int j; p=pa-next;q=pb-next; newp=(lnode*)malloc(sizeof(lnode); r=newp; while(p&q) s=(lnode*)malloc(sizeof(lnode); switch(cmp(p-data,q-data) case -1: s-data.coef=p-data.coef; s-data.expn=p-data.expn; r-next=s; r=s; p=p-next; break; case 0: s-data.coef=p-data.coef-q-data.coef; if(s-data.coef!=0.0) s-data.expn=p-data.expn; r-next=s; r=s; p=p-next; q=q-next; break; case 1: s-data.coef=-q-data.coef; s-data.expn=q-data.expn; r-next=s; r=s; q=q-next; break; /switch /while while(p) s=(lnode*)malloc(sizeof(lnode); s-data.coef=p-data.coef; s-data.expn=p-data.expn; r-next=s; r=s; p=p-next; while(q) s=(lnode*)malloc(sizeof(lnode); s-data.coef=-q-data.coef; s-data.expn=q-data.expn; r-next=s; r=s; q=q-next; r-next=null; if(newp-next!=null&newp-next-next!=null)/合并同类项 for(q=newp-next;q!=null;q=q-next) for(p=q-next,r=q;p!=null;) if(q-data.expn=p-data.expn) q-data.coef=q-data.coef+p-data.coef; r-next=p-next; q=p;p=p-next; free(q); else r=r-next; p=p-next; printf(升序 1 , 降序 2n); printf(选择:); scanf(%d,&j); if(j=1) arrange1(newp); else arrange2(newp); return newp;/*4两多项式相乘*/polynomail mulpolyn(polynomail pa,polynomail pb) polynomail s,newp,q,p,r; int i=20,j; newp=(lnode*)malloc(sizeof(lnode); r=newp; for(p=pa-next;p!=null;p=p-next) for(q=pb-next;q!=null;q=q-next) s=(lnode*)malloc(sizeof(lnode); s-data.coef=p-data.coef*q-data.coef; s-data.expn=p-data.expn+q-data.expn; r-next=s; r=s; r-next=null; printf(升序 1 , 降序 2n); printf(选择:); scanf(%d,&j); if(j=1) arrange1(newp); else arrange2(newp); for(;i!=0;i-) for(q=newp-next;q-next!=null;q=q-next)/合并同类项 for(p=q;p!=null&p-next!=null;p=p-next) if(q-data.expn=p-next-data.expn) q-data.coef=q-data.coef+p-next-data.coef; r=p-next; p-next=p-next-next; free(r); return newp;/*5、销毁已建立的两个多项式*/void delpolyn(polynomail pa,polynomail pb) polynomail p,q; p=pa; while(p!=null) q=p; p=p-next; free(q); p=pb; while(p!=null) q=p; p=p-next; free(q); printf(两个多项式已经销毁n);void main() polynomail pa=null,pb=null; polynomail p,q; polynomail addp=null,subp=null,mulp=null; int n,m; int sign=y; printf(1、创建两个一元多项式n); printf(2、两多项式相加得一新多项式n); printf(3、两多项式相减得一新多项式n); printf(4、两多项式相乘得一新多项式n); printf(5、销毁已建立的两个多项式n); printf(6、退出n); printf(n); while(sign!=n) printf(请选择：); scanf(%d,&n); switch(n) case 1: if(pa!=null) printf(已建立两个一元多项式，请选择其他操作！); break; printf(请输入第一个多项式：n); printf(要输入几项：); scanf(%d,&m); while(m=0) printf(m不能为0，请重新输入m:); scanf(%d,&m); pa=creatpolyn(pa,m); printpolyn(pa); printf(请输入第二个多项式：n); printf(要输入几项：); scanf(%d,&m); pb=creatpolyn(pb,m); printpolyn(pb); break; case 2: if(pa=null) printf(请先创建两个一元多项式！n); break; addp=addpolyn(pa,pb); printpolyn(addp); break; case 3: if(pa=null) printf(请先创建两个一元多项式！n); break; subp=subpolyn(pa,pb); printpolyn(subp); break; case 4: if(pa=null) printf(请先创建两个一元多项式！n); break; mulp=mulpolyn(pa,pb); printpolyn(mulp); break; case 5: if(pa=null) printf(请先创建两个一元多项式！n); break; delpolyn(pa,pb); pa=pb=null; break; case 6: if(addp!=null) p=addp; while(p!=null) q=p; p=p-next; free(q); if(subp!=null) p=subp; while(p!=null) q=p; p=p-next; free(q); exit(-2); /switch /while3.2、算法的设计思想a) 相加运算对于两个稀疏矩阵相加，即行与行，列与列相加b）相乘运算若设q=m*n 其中m是m1*n1矩阵，n是m2*n2矩阵，只有当n1=m2时才可以相乘。乘积矩阵q中元素 q（i，j）=m（i，k）*n（k，j） 1im1，1jn2在算法中，不论m（i，k）和 n（k，j）的值是否为零，都要进行一次乘法运算，而实际上，这两者有一个值为零时，其乘积也为零。因此，在对稀疏矩阵进行运算时，应免去这种无效操作，只需在m.data和n.data中找到相应的各对元素(即m.data中的j值和 n.data中的i值相等的各对元素)相乘即可。c) 转置运算 对于一个m*n的矩阵m，它的转置矩阵t是一个n*m的矩阵，且t（i，j）=m（j，i），1in，1jm。完成一个稀疏矩阵的转置分为三步：（1）将矩阵的行列值相互交换；（2）将每个三元组中的i和j相互调换；（3）重排三元组之间的次序便可实现矩阵的转置；3.3、稀疏矩阵各种运算的性质变换a)加法运算两个稀疏矩阵的加和矩阵仍然是稀疏矩阵b）乘法运算两个稀疏矩阵的乘积矩阵不是稀疏矩阵c）转置运算一个稀疏矩阵的转置矩阵仍然是稀疏矩阵4、调试与测试：4.1、调试方法与步骤：1、数据结构的设计 在该程序中分别分为顺序存储和链式存储结构。2、算法的设计本程序主要分为四大模块主程序模块输入模块：通过getpolyn函数输入输出模块（升幂降幂）：printpolyn函数实现输出数据处理模