山东理工大学计算机学院
课 程 设 计
(数据结构)
班 级
姓 名
学 号
指导教师
二○一二年一月十日
课程设计任务书及成绩评定
课题名称
顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现。
Ⅰ、题目的目的和要求:
1. 巩固和加深对数据结构的理解,通过上机实验、调试程序,加深对课本知识的理解,最终使学生能够熟练应用数据结构的知识写程序。
1)通过本课程的学习,能熟练掌握几种基本数据结构的基本操作。
2)能针对给定题目,选择相应的数据结构,
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
并设计算法,进而给出问题的正确求解过程并编写代码实现。
2.设计题目要求:
1) 首先判定多项式是否稀疏
2) 分别采用顺序和动态存储结构实现;
3) 结果M(x)中无重复阶项和无零系数项;
4) 要求输出结果的升幂和降幂两种排列情况;
Ⅱ、设计进度及完成情况
日 期
内 容
1.2-1.3
选取参考书,查阅有关文献资料,完成资料搜集和系统分析工作。
1.4~1.5
创建相关数据结构,录入源程序。
1.6~1.7
调试程序并记录调试中的问题,初步完成课程设计报告。
1.9
上交课程设计报告打印版并进行课程设计答辩,要求每个同学针对自己的设计回答指导教师3-4个问题。
考核结束后将课程设计报告和源程序的电子版交班长统一刻光盘上交。
Ⅲ、主要参考文献及资料
[1] 严蔚敏 数据结构(C语言版)清华大学出版社 1999
[2] 严蔚敏 数据结构题集(C语言版)清华大学出版社 1999
[3] 谭浩强 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
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;//释放p
}
else
{
r=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.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)//逻辑变量字符bool
{
arrange2(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<<"无项"<next==NULL)
cout<<"Y=0"<next;
i=1;
if(q->data.xishu!=0&&q->data.zhishu!=0)
{
cout<data.xishu<<"X^"<data.zhishu;
i++;
}
if(q->data.zhishu==0&&q->data.xishu!=0)
cout<data.xishu;//打印第一项
q=q->next;
if(q==NULL)
{
cout<data.xishu!=0&&q->data.zhishu!=0)
{
if(q->data.xishu>0)
cout<<"+";
cout<data.xishu<<"X^"<data.zhishu;
i++;
}
if(q->data.zhishu==0&&q->data.xishu!=0)
{
if(q->data.xishu>0) cout<<"+";
cout<data.xishu;
}
q=q->next;
if(q==NULL)
{
cout<>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"<>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"<>j;
if(j==1)
arrange1(newHead);
else
arrange2(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"<>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<<"两个多项式已经销毁"<>n;
switch(n)
{
case 1:
if(pa!=NULL)
{
cout<<"已建立两个一元多项式,请选择其他操作!";
break;
}
cout<<"请输入第一个多项式:"<>m;
while(m==0)
{
cout<<"m不能为0,请重新输入m:";
cin>>m;
}
pa=creatpolyn(m);
printpolyn(pa);
if(judge(pa))
cout<<"该多项式稀疏"<>m;
pb=creatpolyn(m);
printpolyn(pb);
if(judge(pb))
cout<<"该多项式稀疏"<
本文档为【数据结构课程设计报告顺序结构动态链表结构下的一元多项式的加法减法乘法的实现】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。