数据结构课程设计---汉诺塔问题

《数据结构课程设计---汉诺塔问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、目录目录11．系统需求分析21.1问题描述22．概要设计42.1设计思路42.2系统总体设计52.3程序流程图62.3.1塔盘数量设置62.3.2移动速度调节62.3.3操作对象选择72.3.4汉诺塔求解流程图83．详细设计93.1模块设计93.1.1塔和塔显示的定义93.1.2塔盘移动的定义113.1.3塔盘移动规律的定义123.1.4主函数main()124.系统调试145.运行结果146.心得体会197.附录207.1参考书目207.2源程序208评分表25251．系统需求分析1.1问题描述（一）、课程设计题

2、目：汉诺塔问题（二）、目的与要求：1、目的：（1）要求学生达到进一步熟练掌握C语言的基本知识和技能；（2）基本掌握利用VC++6.0制作页面的基本思路和方法；（3）能够利用所学的基本知识和技能，解决简单的汉诺塔问题。2、基本要求：（1）要求利用VC++6.0以及MFC控件来完成系统的设计；（2）要求在设计的过程中，建立清晰的类层次；（3）在系统中定义类，每个类中要有各自的属性和方法；（4）在系统的设计中，至少要用到C中的一种算法。3、创新要求：在基本要求达到后，可进行创新设计，如根据查找结果进行修改的功能。4、写出

3、设计说明书（三）、设计方法和基本原理：1、问题描述（功能要求）：界面划出大小不等，颜色不同的矩形块分别代表各盘子，盘子规模n为1~10，并可以选择人工控制演示和系统自动运行演示，如果是自动则还要输入演示速度。在界面的上方显示正在移动的盘子的源座和目标座。用人工操作时，按任意键移动一个盘子，这样可以清楚每一步过程。如果是自动运行，可以选择移动一步的暂停时间。要求用TurboC或VC6.0MFC实现的汉诺塔问题的图形程序。设计思路：用栈存放塔，定义三个堆栈，用来表示三个塔座，栈的每个结点类型为结构体，其中数据域存放盘子

4、的代号，根据代号计算盘子的大小。Top为塔的栈顶指针，即每个塔的具体高度。例如，结构体可以定义如下：StructH{intdata[15];/*存放每个盘的代号*/25inttop;/*每个塔的具体高度*/}num[3];2、问题的解决方案：根据系统功能要求，可以将问题解决分为以下步骤：（1）利用VC++中的MFC控件制作出汉诺塔运行页面；（2）完成类中各个成员函数的定义；（3）完成系统的应用模块，根据不同按键的功能，在源程序中填入相应的代码；（4）功能调试；（5）完成系统总结报告以及系统使用说明书。252．概要设

5、计2.1设计思路对于一个类似的这样的问题，任何一个人都不可能直接写出移动盘子的每一个具体步骤。可以利用这样的统筹管理的办法求解：我们假设把该任务交给一个僧人，为了方便叙述，将他编号为64。僧人自然会这样想：假如有另外一个僧人能有办法将63个盘子从一个座移到另一个座，那么问题就解决了，此时僧人64只需这样做：1.命令僧人63将63个盘子从A座移到C座2.自己将最底下的最大的一个盘子从A座移到C座3.再命令僧人63将63个盘子从B座移到C座为了解决将63个盘子从A座移到B座的问题，僧人63又想：如果能再有一个僧人62能

6、将62个盘子移动到另一座，我就能将63个盘子从A座移动到B座。他是这样做的：1.命令僧人62将62个盘子从A移动到C2.自己将一个盘子从A座移动到B座3.再命令僧人62将62个盘子移到B座再进行一次递归。如此“层层下放”，直到后来找到第2个僧人，让他完成将2个盘子从一个座移到另一个座，进行到此，问题就解决了。最后找到第1个僧人，让他完成将一个盘子从一个座移动到另一个座，至此，全部工作已经完成，都是可以执行的。按照如此的思路设计递归算法，很容易得出盘子的移动方案。另外是图形演示盘子的移动过程。为了能够更加形象的表示盘

7、子的移动过程。在设计图形演示的时候，我们采用了图形动态演示。首先我们将字幕、柱子、以及提示信息等等屏幕内容设置成固定不变，我们这里称之为舞台。我们将盘子看作对象，一个盘子一个对象。在设计演示过程的时候，只需要将盘子对象放置于二维界面中的不同信置，通过刷新屏幕，实现动画显示。252.2系统总体设计先对程序进行各功能类的定义，定义汉诺塔，显示塔的定义，运行盘子移动的函数，一般可以使用移动、显示等功能，运用数据结构的相关知识，利用一定的算法制作出汉诺塔程序。能输入塔盘的数量（10以内）和塔盘移动速度，支持人和电脑操作，并

8、且显示移动过程和移动次数，实现汉诺塔的动态掩饰，总的设计思路如下图所示：该出租车计费系统由四个模块组成，分别是：塔盘数量设置：在1到10之间移动速度调节：以1000为一秒，输入移动速度操作对象选择：有人和电脑连个对象选择移动过程显示：将盘子移动的过程显示出来各模块之间的关系为：汉诺塔游戏塔盘数量设置移动速度调节操作对象选择移动过程显示图1.汉诺塔功能结构体图