数据结构课程报告汉诺塔.doc

目 录1 课题需求32 概要设计32.1 递归32.2 非递归43 详细设计和实现44 调试与测试134.1 启动窗口134.2 递归实现134.3 非递归实现154.4 退出165 致谢176 参考文献182 概要设计汉诺塔是一个经典的问题，曾被称为“世界末日问题”。此次程序设计全面讨论了解决此问题的方案，详细研究，了解，解决问题的算法设计，给出了具体算法，最后由手工输入测试数，运用递归与非递归算法得出结果。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文件：#include/递归法解决汉诺塔问题void HanNuoTaDiGui(int n,char a,char b,char c)if(n2)cout 圆盘n : 从a移到cendl;return;HanNuoTaDiGui(n-1,a,c,b);/n-1个圆盘移到bcout 圆盘n : 从a移到cendl;HanNuoTaDiGui(n-1,b,a,c);munu.cpp文件：/目录菜单#includevoid munu()cout*endl;cout*endlendl;cout 汉诺塔 endlendl;cout*endl;cout*endl;cout请选择实现的方法：endl;cout 1 代表递归方法。endl;cout 2 代表非递归方法。endl;cout 0 代表退出。endl;主程序：#include#include /from指要转移的盘子的柱子，pass指经过的中间柱子，aim指目的盘子所在的柱子struct 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 IsNullNode()if(n1)return true;return false;/栈，用来存放盘子class Stack Tree *data;int top;int maxSize;public:Stack(int sz);Stack();bool IsEmpty();/判断是否为空栈bool IsFull();/判断是否为满栈bool Push(Tree x);/进栈bool Push(int m,char a,char b,char c);/进栈bool Pop(Tree &x);/出栈bool GetTop(Tree &x);/取栈顶;Stack:Stack(int sz)/构造函数maxSize=sz;data=new TreemaxSize;top=-1;Stack:Stack()/析构函数delete data;/判断是否为空栈bool Stack:IsEmpty()if(top=-1)return true;return false;/判断是否为满栈bool Stack:IsFull()if(top=maxSize-1)return true;return false;/出栈bool Stack:Pop(Tree &x)if(IsEmpty()return false;x=datatop-;return true;bool Stack:Push(Tree x)if(IsFull()return false;data+top=x;return true; bool Stack:Push(int m,char a,char b,char c)if(IsFull()return false;top+;datatop.n=m;datatop.aim=c;datatop.from=a;datatop.pass=b;return true;bool Stack:GetTop(Tree &x)if(IsEmpty()return false;x=datatop;return true;/from指要转移的盘子，aim指目的盘子，pass指经过上午中间盘子void HanNuoTa(int n,char a,char b,char c)Stack s(n+1);Tree p;int i=1;s.Push(n,a,b,c);while(!s.IsEmpty()s.GetTop(p);while(!p.IsNullNode()s.Push(p.n-1,p.from,p.aim,p.pass);/左孩子 进栈s.GetTop(p);s.Pop(p);/退栈if(!s.IsEmpty()/栈不空s.Pop(p);/退栈cout第i+次t圆盘p.n p.fromp.aimendl;/输出s.Push(p.n-1,p.pass,p.from,p.aim);/右孩子void HanNuoTaDiGui(int n,char a,char b,char c);void munu();void main()system(color 1f); /*设置系统颜色，本系统为蓝底亮白色字*/munu();while(true)int n,num;coutn;switch(n)case 0:goto loop;case 1:/1代表递归方法coutnum;HanNuoTaDiGui(num,A,B,C);munu();break;case 2:/2代表非递归方法coutnum;HanNuoTa(num,A,B,C);munu();break;default:cout您的选择不符合要求，请重新输入！endl;break;loop:cout欢迎再次使用本程序！endl;4 调试与测试4.1 启动窗口4.2 递归实现输入圆盘个数为5（也可以是其他数，但不要太大，时间花销大）4.3 非递归实现输入圆盘个数为5（也可以是其他数，但不要太大，时间花销大）4.4 退出5 致谢*6 参考文献1 殷人昆.数据结构 用面向