数据结构课程报告汉诺塔

《数据结构课程报告汉诺塔》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、目录1课题需求32概要设计32.1递归32.2非递归43详细设计和实现44调试与测试134.1启动窗口134.2递归实现134.3非递归实现154.4退出165致谢176参考文献18152概要设计汉诺塔是一个经典的问题，曾被称为“世界末日问题”。此次程序设计全面讨论了解决此问题的方案，详细研究，了解，解决问题的算法设计，给出了具体算法，最后由手工输入测试数，运用递归与非递归算法得出结果。2.1递归若只有一个圆盘的话直接将圆盘移至C杆；若为N个圆盘的话将N-1个圆盘当作整体借助C杆移至B杆，将N号盘移至C杆，再借助A杆重复上面的操作即可将圆盘

2、移至C杆。2.2非递归看出二叉树实现，假设‘A’一开始有n个圆盘，前n-1个‘A’通过‘C’移到‘B’上看出左孩子，第n个移到‘C’看出根，将‘B’中n-1通过‘A’移到‘C’看成右孩子，建立完全二叉树。主要借助二叉树的非递归中序遍历方法实现，利用栈堆来实现。3详细设计和实现15DiGui.cpp文件：#include//递归法解决汉诺塔问题voidHanNuoTaDiGui(intn,chara,charb,charc){if(n<2){cout<<"圆盘"<

3、eturn;}HanNuoTaDiGui(n-1,a,c,b);//n-1个圆盘移到bcout<<"圆盘"<voidmunu(){cout<<"**************************************************"<

4、"<

5、#include//from指要转移的盘子的柱子，pass指经过的中间柱子，aim指目的盘子所在的柱子structTree//树结点{intn;charfrom;15charpass;charaim;//构造函数Tree(intm,chara,charb,charc){n=m;from=a;pass=b;aim=c;}Tree(){}//判断是否为空结点boolIsNullNode(){if(n<1)returntrue;returnfalse;}};//栈，用来存放盘子classStack{Tr

6、ee*data;inttop;intmaxSize;public:Stack(intsz);~Stack();15boolIsEmpty();//判断是否为空栈boolIsFull();//判断是否为满栈boolPush(Treex);//进栈boolPush(intm,chara,charb,charc);//进栈boolPop(Tree&x);//出栈boolGetTop(Tree&x);//取栈顶};Stack::Stack(intsz)//构造函数{maxSize=sz;data=newTree[maxSize];top=-1;}S

7、tack::~Stack()//析构函数{delete[]data;}//判断是否为空栈boolStack::IsEmpty(){if(top==-1)returntrue;returnfalse;}//判断是否为满栈15boolStack::IsFull(){if(top==maxSize-1)returntrue;returnfalse;}//出栈boolStack::Pop(Tree&x){if(IsEmpty())returnfalse;x=data[top--];returntrue;}boolStack::Push(Treex)

8、{if(IsFull())returnfalse;data[++top]=x;returntrue;}boolStack::Push(intm,chara,charb,charc