数据结构课程设计多项式及猴子吃桃问题.docx
《数据结构课程设计多项式及猴子吃桃问题.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计多项式及猴子吃桃问题.docx（28页珍藏版）》请在冰点文库上搜索。
数据结构课程设计多项式及猴子吃桃问题
天津职业技术师范大学
课程设计任务书
理学院数学0902班学生邓吉利（0772*******）
课程设计课题：
第一题：
在顺序结构、动态链表结构下实现一元多项式的加法、减法、乘法运算。
设有一元多项式
和
请实现求：
要求：
1）首先判定多项式是否稀疏；
2）分别采用顺序和动态存储结构实现；
3）结果
中无重复阶项、无零系数项；
4）要求输出结果的升幂和降幂两种排列情况。
第二题：
猴子吃桃问题：
有一群猴子摘了一堆桃子，它们每天都吃当前桃子的一半再多吃一个，到了第10天就剩下一个桃子，用多种方法实现求出原来这群猴子共摘了多少桃子。
要求：
1）采用数组数据结构实现上述求解；
2）采用链式数据结构。
一、课程设计工作日自2012年2月21日至2012年3月2日
二、同组学生：
无。
三、课程设计任务要求（包括课题来源、类型、目的和意义、基本要求、完成时间、主要参考资料等）：
课题来源：
教师提供
课题类型：
设计
目的和意义：
通过数据结构课程设计掌握在C语言中结构体的建立和使用，并能用合适的数据结构设计大型程序
完成时间：
2012年2月29日
主要参考资料：
[1]严蔚敏．数据结构（C语言版）．清华大学出版社，2007
[2]严蔚敏．数据结构题集（C语言版）．清华大学出版社，2007
[3]谭浩强．C语言程序设计．清华大学出版社，2005
[4]与所用编程环境相配套的C语言或C++相关的资料
指导教师签字：
教研室主任签字：
2012年2月29日
天津职业技术师范大学
课程设计评审表
理学院数学0902班学生邓吉利
设计任务完成情况及指导教师评语
答辩情况
评定成绩
成绩：
指导教师签字：
日期：
教研室主任：
院长签字：
日期：
日期：
一、设计分析
1．顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现。
可以分为几个模块：
输入模块、输出模块（升幂降幂）、数据处理模块（多项式的加减乘）、主程序模块。
2．在程序过程中加入汉字提示符，让读者清楚明白的操作该程序。
运行程序时看起来简洁有序，操作简单明了。
3．程序执行时的命令：
①选择创建两个一元多项式②输入第一个一元多项式的项数③依次输入一元多项式的系数和指数④以相同方式输入第二个一元多项式⑤选择操作方式⑥选择降幂或升幂排序⑦输出结果⑧是否退出
4.测试数据。
输入的一元多项式系数指数分别为70,31,98,517和81,227，-98。
加法结果为；升幂降幂
减法结果为：
升幂降幂
乘法结果为：
升幂降幂
二、具体设计概要
1、数据结构的设计
在该程序中分别分为顺序存储和链式存储结构。
2、算法的设计
本程序主要分为四大模块
①主程序模块
②输入模块：
通过Getpolyn函数输入
③输出模块（升幂降幂）：
PrintPolyn函数实现输出
④数据处理模块（多项式的加减乘）：
通过一元多项式的Polynomial基本操作实现
3、抽象数据类型的设计
一元多项式抽象数据类型的定义：
抽象数据类型Polynomial的定义：
三、详细程序设计及运行结果：
第一题
程序及运行结果：
#include
usingnamespacestd;
structterm
{
floatxishu;//系数
intzhishu;//指数
};
structLNode
{
termdata;//term多项式值
structLNode*next;
};
typedefLNode*polynomail;
/*合并同类项*/
polynomailhebing（polynomailHead）
{
polynomailr,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;
deleteQ;
}
else
{
r=r->next;
p=p->next;
}
returnHead;
}
/*由小到大排列*/
voidarrange1（polynomailpa）
{
polynomailh=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指向参与比较的最后一个，不断向前移动
}
}
/*由大到小排序*/
voidarrange2（polynomailpa）
{
polynomailh=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指向参与比较的最后一个，不断向前移动
}
}
booljudge（polynomailHead）
{
arrange2（Head）;
polynomailp;
p=Head->next;
boolxi=false;
while（p!
=NULL&&p->next!
=NULL&&!
xi）
{
if（p->data.zhishu-p->next->data.zhishu>1）
xi=true;
p=p->next;
}
returnxi;
}
/*打印多项式,求项数*/
voidprintpolyn（polynomailP）
{
inti;
polynomailq;
if（P==NULL）
cout<<"无项\n";
elseif（P->next==NULL）
cout<<"Y=0\n";
else
{
cout<<"该多项式为Y=";
q=P->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<<"\n";
return;
}
while
（1）//while中，打印剩下项中系数非零的项，
{
if（q->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<<"\n";
break;
}
}
}
}
/*1、创建并初始化多项式链表*/
polynomailcreatpolyn（intm）
{
polynomailHead,r,s;
inti;
Head=newLNode;
r=Head;
for（i=0;i{
s=newLNode;
cout<<"请输入第"<";
cin>>s->data.xishu>>s->data.zhishu;
r->next=s;r=s;
}
r->next=NULL;
if（m>1）
{
Head=hebing（Head）;
}
returnHead;
}
/*2、两多项式相加*/
polynomailaddpolyn（polynomailpa,polynomailpb）
{
polynomails,newHead,q,p,r;intj;
p=pa->next;
q=pb->next;
newHead=newLNode;
r=newHead;
while（p）
{
s=newLNode;
s->data.xishu=p->data.xishu;
s->data.zhishu=p->data.zhishu;
r->next=s;r=s;
p=p->next;
}
while（q）
{
s=newLNode;
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\n";
cout<<"选择:
";
cin>>j;
if（j==1）
arrange1（newHead）;
else
arrange2（newHead）;
returnnewHead;
}
/*3、两多项式相减*/
polynomailsubpolyn（polynomailpa,polynomailpb）
{
polynomails,newHead,q,p,r;intj;
p=pa->next;q=pb->next;
newHead=newLNode;
r=newHead;
while（p）
{
s=newLNode;
s->data.xishu=p->data.xishu;
s->data.zhishu=p->data.zhishu;
r->next=s;r=s;
p=p->next;
}
while（q）
{
s=newLNode;
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\n";
cout<<"选择:
";
cin>>j;
if（j==1）
arrange1（newHead）;
else
arrange2（newHead）;
returnnewHead;
}
/*4两多项式相乘*/
polynomailmulpolyn（polynomailpa,polynomailpb）
{
polynomails,newHead,q,p,r;
intj;
newHead=newLNode;
r=newHead;
for（p=pa->next;p!
=NULL;p=p->next）
for（q=pb->next;q!
=NULL;q=q->next）
{
s=newLNode;
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\n";
cout<<"选择:
";
cin>>j;
if（j==1）arrange1（newHead）;
elsearrange2（newHead）;
if（newHead->next!
=NULL&&newHead->next->next!
=NULL）//合并同类项
newHead=hebing（newHead）;
returnnewHead;
}
/*5、销毁已建立的两个多项式*/
voiddelpolyn（polynomailpa,polynomailpb）
{
polynomailp,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";
}
voidmain（）
{
polynomailpa=NULL,pb=NULL;
polynomailaddp=NULL,subp=NULL,mulp=NULL;
intn,m;
while
（1）
{
cout<<"1、创建两个一元多项式\n";
cout<<"2、两多项式相加得一新多项式\n";
cout<<"3、两多项式相减得一新多项式\n";
cout<<"4、两多项式相乘得一新多项式\n";
cout<<"5、销毁已建立的两个多项式\n";
cout<<"6、退出\n";
cout<<"请选择：
";
cin>>n;
switch（n）
{
case1:
if（pa!
=NULL）
{
cout<<"已建立两个一元多项式，请选择其他操作！
";
break;
}
cout<<"请输入第一个多项式：
\n";
cout<<"要输入几项：
";
cin>>m;
while（m==0）
{
cout<<"m不能为0，请重新输入m:
";
cin>>m;
}
pa=creatpolyn（m）;
printpolyn（pa）;
if（judge（pa））
cout<<"该多项式稀疏\n";
else
cout<<"该多项式稠密\n";
cout<<"请输入第二个多项式：
\n";
cout<<"要输入几项：
";
cin>>m;
pb=creatpolyn（m）;
printpolyn（pb）;
if（judge（pb））
cout<<"该多项式稀疏\n";
else
cout<<"该多项式稠密\n";
break;
case2:
if（pa==NULL）
{
cout<<"请先创建两个一元多项式！
\n";
break;
}
addp=addpolyn（pa,pb）;
printpolyn（addp）;
break;
case3:
if（pa==NULL）
{
cout<<"请先创建两个一元多项式！
\n";
break;
}
subp=subpolyn（pa,pb）;
printpolyn（subp）;
break;
case4:
if（pa==NULL）
{
cout<<"请先创建两个一元多项式！
\n";
break;
}
mulp=mulpolyn（pa,pb）;
printpolyn（mulp）;
break;
case5:
if（pa==NULL）
{
cout<<"请先创建两个一元多项式！
\n";
break;
}
delpolyn（pa,pb）;
pa=pb=NULL;
break;
case6:
delpolyn（pa,pb）;
exit（0）;
}
}
}
s
第二题
程序及运行结果：
publicclassMonkey{
//主函数
publicstaticvoidmain（String[]args）{
Listl=newList（）;
l.array（）;
l.link（）;
}
}
//构成链表的结点定义
publicclassNode{
publicNodenext;
publicObjectdata;
publicNode（Objectdata,Nodenext）{
this.data=data;
this.next=next;
}
}
publicclassList{
privateNodeHead=null;
privateNodeTail=null;
privateNodePointer=null;
privateintLength=0;
//在当前结点前插入一个结点，并使其成为当前结点
publicvoidinsert（Objectd）{
Nodee=newNode（d,null）;
if（Length==0）{
Tail=e;
Head=e;
}else{
Nodetemp=cursor（）;
e.next=temp;
if（Pointer==null）
Head=e;
else
Pointer.next=e;
}
Length++;
}
//将当前结点移出链表，下一个结点成为当前结点，如果移出的结点是最后一个结点，则第一个结点成为当前结点
publicObjectremove（）{
Objecttemp;
if（Length==0）
return0;
elseif（Length==1）{
temp=Head.data;
deleteAll（）;
}
else{
Nodecur=cursor（）;
temp=cur.data;
if（cur==Head）
Head=cur.next;
elseif（cur==Tail）{
Pointer.next=null;
Tail=Pointer;
reset（）;
}
else
Pointer.next=cur.next;
Length--;
}
returntemp;
}
//返回当前结点的指针
privateNodecursor（）{
if（Head==null）
returnnull;
elseif（Pointer==null）
returnHead;
else
returnPointer.next;
}
//返回当前结点的值
publicObjectcurrentNode（）{
Nodetemp=cursor（）;
returntemp.data;
}
publicvoiddeleteAll（）{
Head=null;
Tail=null;
Pointer=null;
Length=0;
}
publicvoidreset（）{
Pointer=null;
}
//链表实现
publicvoidlink（）{
ints=0;
Lista=newList（）;
for（inti=1;i<=10;i++）{
if（a.Length==9）{
s=1;
while（a.Length!
=0）{
s=s*2+2;
a.remove（）;
}
System.out.println（"链表实现：
"）;
System.out.println（"桃子总数:
"+s）;
}elsea.insert（newInteger（i））;
}
}
//数组实现
publicvoidarray（）{
inta[]=newint[10];
a[9]=1;
for（inti=a.length-2;i>=0;i--）{
a[i]=2*a[i+1]+2;
}
System.out.println（"数组实现：
"）;
System.o
升级会员 