数据结构课程设计报告顺序结构动态链表结构下的一元多项式的加法减法乘法的实现.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的定义：第四章 详细设计#include<iostream>using 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.zhishu>p->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.zhishu<p->next->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.zhishu>1)xi=true;p=p->next;return xi;/*打印多项式,求项数*/void printpolyn(polynomail P)int i;polynomail q;if(P=NULL)cout<<"无项"<<endl;else if(P->next=NULL)cout<<"Y=0"<<endl;elsecout<<"该多项式为Y="q=P->next;i=1;if(q->data.xishu!=0&&q->data.zhishu!=0)cout<<q->data.xishu<<"X"<<q->data.zhishu;i+; if(q->data.zhishu=0&&q->data.xishu!=0)cout<<q->data.xishu;/打印第一项q=q->next;if(q=NULL)cout<<endl;return ;while(1)/while中，打印剩下项中系数非零的项， if(q->data.xishu!=0&&q->data.zhishu!=0)if(q->data.xishu>0) cout<<"+"cout<<q->data.xishu<<"X"<<q->data.zhishu;i+;if(q->data.zhishu=0&&q->data.xishu!=0) if(q->data.xishu>0) cout<<"+"cout<<q->data.xishu;q=q->next;if(q=NULL)cout<<endl;break; /*1、创建并初始化多项式链表*/polynomail creatpolyn(int m)polynomail Head,r,s;int i;Head=new LNode;r=Head;for(i=0;i<m;i+) s=new LNode;cout<<"请输入第"<<i+1<<"项的系数和指数："cin>>s->data.xishu>>s->data.zhishu;r->next=s; r=s;r->next=NULL;if(m>1)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 , 降序 2"<<endl;cout<<"选择:"cin>>j;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 , 降序 2"<<endl;cout<<"选择:"cin>>j;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 , 降序 2"<<endl;cout<<"选择:"cin>>j;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)cout<<"1、创建两个一元多项式"<<endl;cout<<"2、两多项式相加得一新多项式"<<endl;cout<<"3、两多项式相减得一新多项式"<<endl;cout<<"4、两多项式相乘得一新多项式"<<endl;cout<<"5、销毁已建立的两个多项式"<<endl;cout<<"6、退出"<<endl;cout<<"请选择："cin>>n;switch(n)case 1:if(pa!=NULL) cout<<"已建立两个一元多项式，请选择其他操作！"break;cout<<"请输入第一个多项式:"<<endl;cout<<"要输入几项："cin>>m;while(m=0) cout<<"m不能为0，请重新输入m:"cin>>m;pa=creatpolyn(m);printpolyn(pa);if(judge(pa)cout<<"该多项式稀疏"<<endl;elsecout<<"该多项式稠密"<<endl;cout<<"请输入第二个多项式:"<<endl;cout<<"要输入几项："<<endl;cin>>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:delpolyn(pa,pb);exit(0);第五章 运行与测试程序开始界面分别输入两个多项第一项：7+3x+9x8+5x17第二项：2x4+4x3+5x6第六章 总结与心得 通过这次的课程设计，让我深有感触。以前总是不注重基本的知识，到了真正应用的时候才知道自己知识的匮乏，才意识到自己对于课本都不是非常了解，这些让我在真实构造程序框架的时候真的是大费周章，后来经过查询资料，才恍然大悟，原来都是一些自己原本很熟悉的东西，知识因为自己对于知识的认识不够深刻才使得自己在真正用到他们的时候不能得心应手。 另外，在刚刚把程序做完的时候，自己好像成功了一般，但是我错了，因为程序的运行时一项非常重要的过程，而我才刚刚意识到，如此当然是漏洞百出，那是我真的一时都不知所措，错误太多了，后来我才知道，程序需要一步一步的运行，保证每一个小项都没有错误才能使得整个程序没有错误，就这样，这个程序才能真正的运行了。 其实，我明白一个程序可以运行固然重要，但是如果可以在这基础上令程序简洁而有效将是一个质的提高，我也是在不断的思考不断的改进，让这个程序能够简单有效。参考文献:1 严蔚敏、吴伟民主编 数据结构（C语言版） 清华大学出版社 20022 殷人昆等著 数据结构（C+版） 清华大学出版社 20013 金远平著 数据结构（C+描述） 清华大学出版社 2005 4 许卓群等著 数据结构与算法 高等教育出版社 20045 Frank M.Carrano 等著 数据结构与+高级教程清华大学出版社 20046 严蔚敏、吴伟民 数据结构习题集（C语言版）清华大学出版社