数据结构课程设计顺序结构动态链表结构下的一元多项式的加法、减法、乘法的实现.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<stdio.h>#include<stdlib.h>typedef struct float coef; /系数 int expn; /指数#include<stdio.h>#include<stdlib.h>typedef 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.expn>b.expn) return 1; if(a.expn=b.expn) return 0; if(a.expn<b.expn) return -1; else exit(-2);/*又小到大排列*/void arrange1(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->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.coef>0) printf("+"); printf("%.2fX%d",q->data.coef,q->data.expn); i+; if(q->data.expn=0&&q->data.coef!=0) if(q->data.coef>0) 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;i<m;i+) s=(LNode*)malloc(sizeof(LNode); printf("请输入第%d项的系数和指数：",i+1); scanf("%f%d",&s->data.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函数实现输出数据处理模块（多项式的加减乘：通过一元多项式的Polynomial基本操作实现4.2、测试结果的分析与讨论：运行与测试：本章主要说明：1、算法的性能分析2、设计了哪些测试数据？测试结果是什么？请考虑选取有代表性的界面贴图说明。3、在调试程序的过程中遇到什么问题，是如何解决的？程序开始界面分别输入两个多项式7、C程序设计总结本程序在刚开始调试时有许多错误，但在我的努力及同学的帮助下都被一一克服，现在在操作本程序时可根据提示进行相关操作，能正确输出结果。在刚开始的几次调试中曾经出现过不能运行、不能产生十以内随机数字、不能随机出现加减、不会正确输出结果、不能进行循环练习等等问题。经过我的努力及同学的帮助，这些问题得到克服，并且使程序的功能也得到了一定的完善。现在它能对出错的题目发出报警声，并且给出正确答案。最后还能分别输出对错的题数及所得分数。在这次设计过程中，不仅复习课本上所学知识，还通过查资料、问同学学到了课本上没有的知识。从而启发我，要想写好程序，在写好课本知识的同时还需要多读和专业有关的一些书籍，同时还需要多动脑子，尽量把所学的知识综合起来应用，力争写出完美的程序。除此之外，我还得到了一些有用的教训：写程序时必须要细心，不能输错一个字符标点，就连全角半角也得注意。在修改时要有耐心，编译出错后必须逐个错误去改正，绝不能心急浮躁，否则修改之后还会有新的错误。8、致谢能够完成这次课程设计必须感谢C语言课程老师，同学（他们帮我修改了几处重要错误，同时启发我完善了该程序的功能）。9、参考文献1 严蔚敏，吴伟民数据结构（C语言版）清华大学出版社，20072 殷人昆数据结构（C+版）清华大学出版社，20013 金远平数据结构（C+描述）清华大学出版社，20054 许卓群数据结构与算法高等教育出版社，20045 Frank M.Carrano数据结构与C+高级教程清华大学出版社，20046 严蔚敏，吴伟民数据结构习题集（C语言版）清华大学出版社，2007