顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现。

课 程 设 计 （ 数据结构 ） 班 级 姓 名 学 号 指导教师 二 一 年 七 月十日 课程设计任务书及成绩评定 课题名称 顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现。 、题目的目的和要求 1、设计目的 巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。 （ 1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。 （ 2）能针对给定题目，选择 相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。 2、设计题目要求 （给出你所选择的题目 的要求 描述） 1) 首先判定多项式是否稀疏 2) 分别采用顺序和动态存储结构实现； 3) 结果 M(x)中无重复阶项和无零系数项； 4) 要求输出结果的升幂和降幂两种排列情况； 、设计进度及完成情况 日 期 内 容 2010.6.28-6.30 选取参考书，查阅有关文献资料，完成 资料搜集和系统分析工作。 2010.7.17.3 创建相关数据结构 ,录入源程序 。 2010.7.57.7 调试程序并记录调试中的问题 ，初步完成课程设计报告。 2009.7.87.9 上交 课程设计报告 打印版 并进行课程设计答辩，要求每个同学针对自己的设计回答指导教师 3-4 个问题 。 考核结束后将课程设计报告和源程序的电子版交班长统一刻光盘上交。 、主要参考文献及资料 1 严蔚敏 数据结构（ C 语言版） 清华大学出版社 ， 2007 2 严蔚敏 数据结构题集（ C 语言版） 清华大学出版社 ， 2007 3 谭浩强 C 语言程序设计 清华大学出版社 ， 2005 4 与所用编程环境相 配套的 C 语言或 C+相关的资料 、成绩评定 设计成绩： （教师填写） 指导老师： （签字） 二 一 年 七 月 十 日 目 录 第一章 概述 . 1 第二章 系统分析 . 1 第三章 概要设计 . 2 第四章 详细设计 . 3 第五章 运行与测试 . 13 第六章 总结与心得 . 16 参考文献 . 17 本目录是根据 正文 文档自动生成的， 请在 报告完成后， 更新目录的页码，更新方法如下： 1.鼠标单击目录任意部分选中目录； 2.单击鼠标右键选择“更新域”； 3.在出现的“更新目录 ”的对话框中选择“只更新页码”， 见图 1-3， 单击“确定”按钮，目录页码将被更新。 更新完成后，最好再核对一下。 图 1-3 更新目录页码示意图 1 第一章 概述 课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。数据结构是一门重要的专业基础课，是计算机理论和应用的核心基础课程。 数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用 、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。 在这次的课程设计中我选择的题目是 顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现 。分别采用顺序结构和链式存储结构，利用多项得结果，最后得多项式中不含有重复阶项和零系数得项。除此之外，还得分为降幂和升幂 两种排序方式。 第二章 系统分析 1 顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现 。可以分为几个模块：输入模块、输出模块（升幂降幂）、数 据处理模块（多项式的加减乘）、主程序模块。 2 在程序过程中加入汉字提示符，让读者清楚明白的操作该程序。运行程序时看起来简洁有序 ，操作简单明了。 3 程序执行时的命令： 选择创建两个一元多项式 输入第一个一元多项式的项数 依次输入一元多项式的系数和指数 以相同方式输入第二个一元多项式 选择操作方式 选择降幂或升幂排序 输出结果 是否退出 2 4.测试数据。 输入的一元多项式 系数指数分别为 7 0,3 1,9 8,5 17 和 8 1,22 7， -9 8。加法结果为 ；升幂 降幂 减法结果为 ：升幂 降幂 乘法结果为：升幂 降幂 第三章 概要设计 1、数据结构的设计 在该程序中分别分为顺序存储和链式存储结构。 2、算法的设计 本程序主要分为四大模块 主程序模块 输入模块：通过 Getpolyn 函数输入 输出模块（升幂降幂）： PrintPolyn 函数实现输出 数据处理模块（多项式的加减乘）： 通过一元多项式的 Polynomial 基本操作实现 3 3、 抽象数据类型的设计 一元多 项式抽象数据类型的定义 ： 抽象数据类型 Polynomial 的定义： 第四章 详细设计 #include #include typedef struct float coef; /系数 int expn; /指数 term; typedef struct LNode 4 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 指向参与比较的最后一个，不断向前移动 /*打印多项式 ,求项数 */ 5 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; 6 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; 7 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) 8 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) 9 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; 10 /*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(要输入几项： ); 11 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(请先创建两