数据结构课程报告汉诺塔[精品].doc
文本预览下载声明
目 录
1 课题需求 3
2 概要设计 3
2.1 递归 3
2.2 非递归 4
3 详细设计和?实现 4
4 调试与测试? 13
4.1 启动窗口 13
4.2 递归实现 13
4.3 非递归实现? 15
4.4 退出 16
5 致谢 17
6 参考文献 18
2 概要设计
汉诺塔是一?个经典的问?题，曾被称为“世界末日问?题”。此次程序设?计全面讨论?了解决此问?题的方案，详细研究，了解，解决问题的?算法设计，给出了具体?算法，最后由手工?输入测试数?，运用递归与?非递归算法?得出结果。
2.1 递归
若只有一个?圆盘的话直?接将圆盘移?至C杆；
若为N个圆?盘的话将N?-1个圆盘当?作整体借助?C杆移至B?杆，将N号盘
移至C杆，再借助A杆?重复上面的?操作即可将?圆盘移至C?杆。
2.2 非递归
看出二叉树?实现，假设‘A’一开始有n?个圆盘，前n-1个‘A’通过‘C’移到‘B’上看出左孩?子，第n个移到?‘C’看出根，将‘B’中n-1通过‘A’移到‘C’看成右孩子?，建立完全二?叉树。主要借助二?叉树的非递?归中序遍历?方法实现，利用栈堆来?实现。
3 详细设计和?实现
DiGui?.cpp文件?：
#inclu?deiostr?eam.h
//递归法解决?汉诺塔问题?
void HanNu?oTaDi?Gui(int n,char a,char b,char c)
{
if(n2)
{
cout 圆盘n : 从a移到cendl;
retur?n;
}
HanNu?oTaDi?Gui(n-1,a,c,b);//n-1个圆盘移?到b
cout 圆盘n : 从a移到cendl;
HanNu?oTaDi?Gui(n-1,b,a,c);
}
munu.cpp文件?：
//目录菜单
#inclu?deiostr?eam.h
void munu()
{
cout**************************************************endl;
cout********************************************endlendl;
cout 汉诺塔 endlendl;
cout**************************************************endl;
cout**************************************************endl;
cout请选择实现?的方法：endl;
cout 1 代表递归方?法。endl;
cout 2 代表非递归?方法。endl;
cout 0 代表退出。endl;
}
主程序：
#inclu?deiostr?eam.h
#inclu?de stdli?b.h
//from指?要转移的盘?子的柱子，pass指?经过的中间?柱子，aim指目?的盘子所在?的柱子
struc?t Tree//树结点
{
int n;
char from;
char pass;
char aim;
//构造函数
Tree(int m,char a,char b,char c)
{
n=m;
from=a;
pass=b;
aim=c;
}
Tree(){}
//判断是否为?空结点
bool IsNul?lNode?()
{
if(n1)
retur?n true;
retur?n false?;
}
};
//栈，用来存放盘?子
class? Stack?
{
Tree *data;
int top;
int maxSi?ze;
publi?c:
Stack?(int sz);
~Stack?();
bool IsEmp?ty();//判断是否为?空栈
bool IsFul?l();//判断是否为?满栈
bool Push(Tree x);//进栈
bool Push(int m,char a,char b,char c);//进栈
bool Pop(Tree x);//出栈
bool GetTo?p(Tree x);//取栈顶
};
Stack?::Stack?(int sz)//构造函数
{
maxSi?ze=sz;
data=new Tree[maxSi?ze];
top=-1;
}
Stack?::~Stack?()//析构函数
{
delet?e []data;
}
//判断是否为?
显示全部