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

山东理工大学计算机学院课 程 设 计（数据结构）班 级姓 名学 号 指导教师二一二年一月十日课程设计任务书及成绩评定课题名称顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现。、题目的目的和要求： 1. 巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。2设计题目要求：1) 首先判定多项式是否稀疏2) 分别采用顺序和动态存储结构实现；3) 结果M(x)中无重复阶项和无零系数项；4) 要求输出结果的升幂和降幂两种排列情况；、设计进度及完成情况日 期内 容1.2-1.3选取参考书，查阅有关文献资料，完成资料搜集和系统分析工作。1.41.5创建相关数据结构,录入源程序。1.61.7调试程序并记录调试中的问题，初步完成课程设计报告。1.9上交课程设计报告打印版并进行课程设计答辩，要求每个同学针对自己的设计回答指导教师3-4个问题。考核结束后将课程设计报告和源程序的电子版交班长统一刻光盘上交。、主要参考文献及资料1 严蔚敏 数据结构（C语言版）清华大学出版社 19992 严蔚敏 数据结构题集（C语言版）清华大学出版社 19993 谭浩强 C语言程序设计 清华大学出版社4 与所用编程环境相配套的C语言或C+相关的资料、成绩评定：设计成绩： （教师填写）指导老师： （签字）二一二 年 一 月 十 日目 录第一章 概述1第二章 系统分析2第三章 概要设计3第四章 详细设计4第五章 运行与测试17第六章 总结与心得19参考文献20第一章 概述课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。数据结构是一门重要的专业基础课，是计算机理论和应用的核心基础课程。数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。在这次的课程设计中我选择的题目是顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现。分别采用顺序结构和链式存储结构，利用多项得结果，最后得多项式中不含有重复阶项和零系数得项。除此之外，还得分为降幂和升幂两种排序方式。第二章 系统分析1 顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现。可以分为几个模块：输入模块、输出模块（升幂降幂）、数据处理模块（多项式的加减乘）、主程序模块。2 在程序过程中加入汉字提示符，让使用者清楚明白的操作该程序。运行程序时看起来简洁有序，操作简单明了。3 程序执行时的命令：选择创建两个一元多项式输入第一个一元多项式的项数依次输入一元多项式的系数和指数以相同方式输入第二个一元多项式选择操作方式选择降幂或升幂排序输出结果是否退出。4. 测试数据。输入的一元多项式系数指数分别为7 0,3 1,9 8,5 17和8 1,22 7，-9 8。加法结果为；升幂 降幂减法结果为：升幂 降幂乘法结果为：升幂 降幂 第三章 概要设计1、数据结构的设计 在该程序中分别分为顺序存储和链式存储结构。2、算法的设计本程序主要分为四大模块主程序模块输入模块：通过main函数输入输出模块（升幂降幂）：PrintPolyn函数实现输出数据处理模块（多项式的加减乘）：通过一元多项式的Polynomial基本操作实现3、抽象数据类型的设计一元多项式抽象数据类型的定义：抽象数据类型Polynomial的定义：第四章 详细设计#includeusing namespace std;struct term/顺序表和链表的的定义float xishu; /系数int zhishu; /指数;struct LNode term data; /term多项式值struct LNode *next;typedef LNode* polynomail;/*合并同类项*/polynomail hebing(polynomail Head)polynomail r,q,p,Q;for(q=Head-next;q!=NULL;q=q-next)/合并同类项for(p=q-next,r=q;p!=NULL;)if(q-data.zhishu=p-data.zhishu)/指数相等 系数相加 q-data.xishu=q-data.xishu+p-data.xishu;r-next=p-next;Q=p;p=p-next;delete Q;/释放pelser=r-next;p=p-next;return Head;/得到不含同类项的多项式/*又小到大排列*/void arrange1(polynomail pa)polynomail h=pa,p,q,r;for(p=pa;p-next!=NULL;p=p-next);r=p;/r指向参与比较的最后一个while(h-next!=r)/大的沉底for(p=h;p-next!=r&p!=r;p=p-next)if(p-next-data.zhishup-next-next-data.zhishu)/比较指数的大小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;for(p=pa;p-next!=NULL;p=p-next); r=p;while(h-next!=r)/小的沉底for(p=h;p-next!=r&p!=r;p=p-next)if(p-next-data.zhishunext-next-data.zhishu)/指数比较大小 q=p-next-next;p-next-next=q-next;/指数小的向后移动q-next=p-next;p-next=q;r=p;/r指向参与比较的最后一个，不断向前移动 /*判断多项式的稀疏 */bool judge(polynomail Head)/逻辑变量字符boolarrange2(Head);polynomail p;p=Head-next;bool xi=false;while(p!=NULL&p-next!=NULL&!xi)if(p-data.zhishu-p-next-data.zhishu1)xi=true;p=p-next;return xi;/*打印多项式,求项数*/void printpolyn(polynomail P)int i;polynomail q;if(P=NULL)cout无项next=NULL)coutY=0endl;elsecoutnext;i=1;if(q-data.xishu!=0&q-data.zhishu!=0)coutdata.xishuXdata.zhishu;i+; if(q-data.zhishu=0&q-data.xishu!=0)coutdata.xishu;/打印第一项q=q-next;if(q=NULL)coutdata.xishu!=0&q-data.zhishu!=0)if(q-data.xishu0) cout+;coutdata.xishuXdata.zhishu;i+;if(q-data.zhishu=0&q-data.xishu!=0) if(q-data.xishu0) cout+;coutdata.xishu;q=q-next;if(q=NULL)coutendl;break; /*1、创建并初始化多项式链表*/polynomail creatpolyn(int m)polynomail Head,r,s;int i;Head=new LNode;r=Head;for(i=0;im;i+) s=new LNode;cout请输入第i+1s-data.xishus-data.zhishu;r-next=s; r=s;r-next=NULL;if(m1)Head=hebing(Head);return Head;/*2、两多项式相加*/polynomail addpolyn(polynomail pa,polynomail pb)polynomail s,newHead,q,p,r;int j;p=pa-next;q=pb-next;newHead=new LNode;r=newHead;while(p) s=new LNode;s-data.xishu=p-data.xishu;s-data.zhishu=p-data.zhishu;r-next=s; r=s;p=p-next;while(q) s=new LNode;s-data.xishu=q-data.xishu;s-data.zhishu=q-data.zhishu;r-next=s; r=s;q=q-next;r-next=NULL;if(newHead-next!=NULL&newHead-next-next!=NULL)/合并同类项newHead=hebing(newHead);cout升序 1 , 降序 2endl;coutj;if(j=1) arrange1(newHead);else arrange2(newHead);return newHead;/*3、两多项式相减*/polynomail subpolyn(polynomail pa,polynomail pb)polynomail s,newHead,q,p,r; int j;p=pa-next;q=pb-next;newHead=new LNode;r=newHead;while(p)s=new LNode;s-data.xishu=p-data.xishu;s-data.zhishu=p-data.zhishu;r-next=s; r=s;p=p-next;while(q)s=new LNode;s-data.xishu=-q-data.xishu;s-data.zhishu=q-data.zhishu;r-next=s; r=s; q=q-next;r-next=NULL; if(newHead-next!=NULL&newHead-next-next!=NULL)/合并同类项newHead=hebing(newHead);cout升序 1 , 降序 2endl;coutj;if(j=1) arrange1(newHead); elsearrange2(newHead);return newHead;/*4两多项式相乘*/polynomail mulpolyn(polynomail pa,polynomail pb) polynomail s,newHead,q,p,r; int j;newHead=new LNode;r=newHead;for(p=pa-next;p!=NULL;p=p-next)for(q=pb-next;q!=NULL;q=q-next)s=new LNode;s-data.xishu=p-data.xishu*q-data.xishu;s-data.zhishu=p-data.zhishu+q-data.zhishu;r-next=s;r=s;r-next=NULL;cout升序 1 , 降序 2endl;coutj;if(j=1) arrange1(newHead);else arrange2(newHead);if(newHead-next!=NULL&newHead-next-next!=NULL)/合并同类项newHead=hebing(newHead);return newHead;/*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);cout两个多项式已经销毁endl;void main() polynomail pa=NULL,pb=NULL;polynomail addp=NULL,subp=NULL,mulp=NULL;int n,m;while(1)cout1、创建两个一元多项式endl;cout2、两多项式相加得一新多项式endl;cout3、两多项式相减得一新多项式endl;cout4、两多项式相乘得一新多项式endl;cout5、销毁已建立的两个多项式endl;cout6、退出endl;coutn;switch(n)case 1:if(pa!=NULL) cout已建立两个一元多项式，请选择其他操作！;break;cout请输入第一个多项式:endl;coutm;while(m=0) coutm;pa=creatpolyn(m);printpolyn(pa);if(judge(pa)cout该多项式稀疏endl;elsecout该多项式稠密endl;cout请输入第二个多项式:endl;cout要输入几项：m;pb=creatpolyn(m);printpolyn(pb);if(judge(pb)cout该多项式稀疏endl;elsecout该多项式稠密endl;break;case 2:if(pa=NULL) cout请先创建两个一元多项式！endl;break;addp=addpolyn(pa,pb);/多项式相加printpolyn(addp);break;case 3:if(pa=NULL)cout请先创建两个一元多项式!endl;break;subp=subpolyn(pa,pb);/多项式相减printpolyn(subp);/打印输出break;case 4:if(pa=NULL)cout请先创建两个一元多项式!endl;break; mulp=mulpolyn(pa,pb);/多项式相乘printpolyn(mulp);/打印输出break;case 5: if(pa=NULL)cout请先创建两个一元多项式endl;break;delpolyn(pa,pb);/多项式的删除pa=pb=NULL;break;case 6:de