数据结构课程设计报告汉诺威塔

1、 数据结构实验课程设计报告题 目： 汉诺威塔 学生姓名： 学 号： 专业班级： 同组姓名： 指导教师： 设计时间： 大二上学期十七周 指导老师意见: 评定成绩: 签名: 日期:目录一. 设计目的与要求 021.1设计目的 021.2设计要求 02 二. 设计分析 022.1汉诺威塔问题 022.2算法分析 032.3流程图 062.4模块及其功能介绍 07三. 设计实现 08四. 心得体会 09五. 参考文献 101.设计目的与要求1.1设计目的随着计算机技术以及外围设备的发展，计算机在辅助设计制造，计算机教育，计算机信息化应用中，图形的作用和魅力愈加显现。如何运用计算机技术、运用算法编程来优

2、化解决低阶汉诺威塔问题对我们学生来说具有可实现和可操作性。本次课程设计的目的就是利用所学习到得算法知识和编程语言知识来解决、实现低阶汉诺威塔问题。1.2设计要求功能：编程序显示n（n<=9）层汉诺威塔的调整过程。分步实施：1.初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2.完成最低要求：实现5层汉诺威塔的调整过程；3.进一步要求：直至实现n9时的情况。有兴趣的同学可以自己扩充系统功能。要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的

3、。2.设计分析2.1汉诺威塔问题n阶汉诺威塔问题：有三个柱子A, B, C。A柱子上叠放有n个盘子，每个盘子都比它下面的盘子要小一点，可以从上到下用1, 2, ., n编号。要求借助柱子C，把柱子A上的所有的盘子移动到柱子B上。移动条件为：1、一次只能移一个盘子；2、移动过程中大盘子不能放在小盘子上，只能小盘子放在大盘子上如3阶汉诺塔的移动：AC,AB,CB,AC,BA,BC,AC2.2算法分析为满足题目中盘子的移动问题，必须遵循的条件是：一次仅能移动一个盘，且不允许大盘放在小盘的上面。设A上有n个盘子。 当n=1时，则将圆盘从A直接移动到C。 当n>=2时，移动的过程可分解为三个步骤：

4、 1) 把A上的n-1个圆盘移到B上； 2) 把A上的一个圆盘移到C上； 3) 把B上的n-1个圆盘移到C上；其中第一步和第三步是相同的。 为了更清楚地描述算法，用图示法描述如下：要将N个盘子从A杆上借助C杆移动到B杆上。这样移动N个盘子的工作就可以按照以下过程进行： 第一次调用递归 将一个盘子从A移动到B上； 第二次调用递归 重复以上过程，直到将全部的盘子移动到位时为止。由递归算法我们可以得到递推关系：移动n个圆盘需要步，如：移动4个圆盘需要15步，移动64个圆盘需要264-1示意图:递归运行的层次递归工作栈状态（n值，x值，y值，z值）塔与圆盘的状态分析说明13，a，b，c 3 21a b

5、 c 有主函数进入第一层递归后，运行至 语句（行）5，因递归调用而进入下一层由第一层的语句行5进入第二层递归，执行至行5 。22，a，c，b3，a，b，c31，a，b，c2，a，c，b3，a，b，c321a b c由第二层行5进入第三层递归，执行行3，将1号盘由a移至c后从行9退出第三层递归，返回二层行6 。22，a，c，b3，a，b，c321a b c将2号盘由a移至b后，从行7进入下一层递归。31，c，a，b2，a，c，b3，a，b，c321a b c将1号盘由c移至b后，从行9退出第三层。返回到第二层的行8。22，a，c，b3，a，b，c从行9退出第二层。返回第一层行6 。13，a，b，

6、c321a b c将3号盘由a移至c后，从行7进入下一层递归。22，b，a，c3，a，b，c从第二层行5进入第三层递归。31，b，c，a2，b，a，c3，a，b，c123a b c将1号盘由b移至a后，从行9退出第三层递归。返回至第二层行6 。22，b，a，c3，a，b，c132a b c将2号盘由b移至c后，从行7进入下一层递归。31，a，b，c2，b，a，c3，a，b，ca b 321 c将1号盘由a移至c后，从行9退出第三层。返回至第二层行8 。22，b，a，c3，a，b，c从行9退出至第二层。返回至第一层行8 。13，a，b，c从行9退出递归行数。返回至主函数。0栈空继续运行主程序当N

7、=3时的递归调用树状图，可以使我们更清楚的了解递归的调用过程。Hanoi(3,A,B,C)Hanoi(2,A,C,B)Hanoi(2,B,A,C)Hanoi(1,A,B,C)Hanoi(1,B,C,A)Hanoi(1,C,A,B)Hanoi(1,A,B,C)Print “disk 3:AC”Print “disk 2:AB”Print “disk 2:BC”disk 1:ACdisk 2:ABdisk 1:CBdisk 1:BAdisk 2:BCdisk 1:ACdisk 3:AC图2.3流程图开始定义结构体数组M存放盘号和塔座高度程序初始化输入要演示的盘块数nn<1|n>10n=

8、10绘制塔座和盘块调用递归函数move()结 束实现递归的部分如下：开 始n= =1?将盘块从A座移到C座将前n-1个盘块从A座移到B座再将A座的第n个盘块移到C座最后将B座上的n-1个盘块移到C座结 束2.4模块及其功能介绍 首先定义队列的结构体和的函数，void Init(Queue &que)；void Clear(Queue &que)；bool Empty(Queue que)；void Pop(Queue &que)；Node *Front(Queue &que)；void Push(Queue &que,Node e)；然后定义队列变量qu

9、e，用来存放移动时开始和终止的盘子，并且记下相应的步骤，；调用递归函数，当递归函数运行结束之后，就输出队列中所有的步骤。3. 设计实现3.1系统运行界面：当n=5时，当n=9时，结果如下：4. 心得体会程序的算法设计与分析，是我在本阶段学完理论课程之后对自己该方面的能力的一次很好的检验，从开始的算法思路到运行调试后的运行结果以及另人兴奋的可用程序，都是一个很好的学习和锻炼的过程。通过这次课程设计，让我对数据结构有了新一层的了解，让我明白各种函数以及类的应用，明白了算法对程序的重要性。通过这次课程设计，使我认识到，仅仅是学会书面知识是不行的，一方面，对程序设计语言本身的理解不够透彻，另一方面，由

10、于对数据结构及常用算法的理解上的欠缺，再加上我自己在这方面的练习相当少，这些都不同程度地添加了我完成这个题目的困难度。要做算法的设计首先是对程序设计语言的相当的熟悉，而且能够实际熟练地运用，要能够把自己的想法，转换为由程序设计语言来表达。这就要求自己不仅仅要会解决实际问题，而且要有能够将实际问题抽象化，数学建模，以及能用计算机程序设计语言来表达实现。这对我们的程序设计水平和对程序语言代码的敏感度以及专业修养是一个很好的挑战。算法设计的要求也不仅仅是程序设计语言，前面讲到了由实际具体问题抽象建模，由于计算机内部是由二进制来表示和存储数据，程序设计语言实现了计算机内部表示和程序员和计算机交流的语言断层，而程序设计语言和自然语言之间又有一个断层，这个断层就需要靠程序员的集体或个人脑力劳动来弥补。软件总体质量的好坏除了对软件工程的设计者相关，程序设计者的水平至关重要。从自然语言到计算机能够读懂的程序设计语言，是对程序设计能力的考验。经过反复的测试比较，还能找出这个设计的很多不足甚至于错误，也就是说，我现在所