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

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评分表.....................................................................................2521．系统需求分析1.1问题描述（一）、课程设计题目：汉诺塔问题（二）、目的与要求：1、目的：（1）要求学生达到进一步熟练掌握C语言的基本知识和技能；（2）基本掌握利用VC++6.0制作页面的基本思路和方法；（3）能够利用所学的基本知识和技能，解决简单的汉诺塔问题。2、基本要求：（1）要求利用VC++6.0以及MFC控件来完成系统的设计；（2）要求在设计的过程中，建立清晰的类层次；（3）在系统中定义类，每个类中要有各自的属性和方法；（4）在系统的设计中，至少要用到C中的一种算法。3、创新要求：在基本要求达到后，可进行创新设计，如根据查找结果进行修改的功能。4、写出设计说明书（三）、设计方法和基本原理：1、问题描述（功能要求）：界面划出大小不等，颜色不同的矩形块分别代表各盘子，盘子规模n为1~10，并可以选择人工控制演示和系统自动运行演示，如果是自动则还要输入演示速度。在界面的上方显示正在移动的盘子的源座和目标座。用人工操作时，按任意键移动一个盘子，这样可以清楚每一步过程。如果是自动运行，可以选择移动一步的暂停时间。要求用TurboC或VC6.0MFC实现的汉诺塔问题的图形程序。设计思路：用栈存放塔，定义三个堆栈，用来表示三个塔座，栈的每个结点类型为结构体，其中数据域存放盘子的代号，根据代号计算盘子的大小。Top为塔的栈顶指针，即每个塔的具体高度。例如，结构体可以定义如下：StructH{intdata[15];/*存放每个盘的代号*/3inttop;/*每个塔的具体高度*/}num[3];2、问题的解决方案：根据系统功能要求，可以将问题解决分为以下步骤：（1）利用VC++中的MFC控件制作出汉诺塔运行页面；（2）完成类中各个成员函数的定义；（3）完成系统的应用模块，根据不同按键的功能，在源程序中填入相应的代码；（4）功能调试；（5）完成系统总结报告以及系统使用说明书。42．概要设计2.1设计思路对于一个类似的这样的问题，任何一个人都不可能直接写出移动盘子的每一个具体步骤。可以利用这样的统筹管理的办法求解：我们假设把该任务交给一个僧人，为了方便叙述，将他编号为64。僧人自然会这样想：假如有另外一个僧人能有办法将63个盘子从一个座移到另一个座，那么问题就解决了，此时僧人64只需这样做：1.命令僧人63将63个盘子从A座移到C座2.自己将最底下的最大的一个盘子从A座移到C座3.再命令僧人63将63个盘子从B座移到C座为了解决将63个盘子从A座移到B座的问题，僧人63又想：如果能再有一个僧人62能将62个盘子移动到另一座，我就能将63个盘子从A座移动到B座。他是这样做的：1.命令僧人62将62个盘子从A移动到C2.自己将一个盘子从A座移动到B座3.再命令僧人62将62个盘子移到B座再进行一次递归。如此“层层下放”，直到后来找到第2个僧人，让他完成将2个盘子从一个座移到另一个座，进行到此，问题就解决了。最后找到第1个僧人，让他完成将一个盘子从一个座移动到另一个座，至此，全部工作已经完成，都是可以执行的。按照如此的思路设计递归算法，很容易得出盘子的移动方案。另外是图形演示盘子的移动过程。为了能够更加形象的表示盘子的移动过程。在设计图形演示的时候，我们采用了图形动态演示。首先我们将字幕、柱子、以及提示信息等等屏幕内容设置成固定不变，我们这里称之为舞台。我们将盘子看作对象，一个盘子一个对象。在设计演示过程的时候，只需要将盘子对象放置于二维界面中的不同信置，通过刷新屏幕，实现动画显示。52.2系统总体设计先对程序进行各功能类的定义，定义汉诺塔，显示塔的定义，运行盘子移动的函数，一般可以使用移动、显示等功能，运用数据结构的相关知识，利用一定的算法制作出汉诺塔程序。能输入塔盘的数量（10以内）和塔盘移动速度，支持人和电脑操作，并且显示移动过程和移动次数，实现汉诺塔的动态掩饰，总的设计思路如下图所示：该出租车计费系统由四个模块组成，分别是：塔盘数量设置：在1到10之间移动速度调节：以1000为一秒，输入移动速度操作对象选择：有人和电脑连个对象选择移动过程显示：将盘子移动的过程显示出来各模块之间的关系为：图1.汉诺塔功能结构体图汉诺塔游戏塔盘数量设置移动速度调节操作对象选择移动过程显示62.3程序流程图2.3.1塔盘数量设置图2.1塔盘数量设置部分2.3.2移动速度调节图2.2移动速度调节部分输入nn1||n10n=10NYta[0].h=n输入速度speedspeed是否小于1000？ynSpeed/1000（s）72.3.3操作对象选择图2.3操作对象选择部分输入操作对象：computerorpeoplecomputerorpeople!=1&&computerorpeople!=2？system(pause)system(pause)12Y82.3.4汉诺塔求解流程图图2.4汉诺塔求解流程图游戏开始输入塔盘数量n0n11调用while()进入主函数是否为人输入移动速度移动塔盘是否小盘在大盘之上塔盘全部在C座输出移动次数游戏结束93．详细设计3.1模块设计3.1.1塔和塔显示的定义structT{inth;//塔的高度intx;//塔的第一个盘的x坐标,y坐标等于(7+n-塔的高度h)intl;//塔的第一个盘的长度}ta[3]={{10,15,2},{0,0,0},{0,0,0}};charhnt[18][79]={{},{},{},{╔════════════════════════════════════╗},{║║},{║║},{║║},{║▆║},{║▆▆10║},{║▆▆▆║},{║▆▆▆▆║},{║▆▆▆▆▆║},{║▆▆▆▆▆▆║},{║▆▆▆▆▆▆▆║