数据结构课程报告汉诺塔[精品].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; } //判断是否为?