栈结构实现汉诺塔实验报告.doc

《栈结构实现汉诺塔实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构实验报告学院软件学院年级2009级班级班学号姓名2010年3月24日目录一、实验内容……………………………………….1二、实验过程……………………………………….X三、实验结果……………………………………….X一、实验内容：1、实验题目：栈结构实现汉诺塔2、实验要求：有三个柱子A、B、C，A柱子上叠放有n个盘子，每个盘子都比它下面的盘自己小一点，要求借助柱子B，将柱子A上的所有盘子移动到柱子C上。要求一次只能移动一个盘子，且移动过程中大盘子不能放在小盘子的上面，只能小盘子放在大盘子的上面。3、实验目标：了解并掌握栈的结构原理和基本操作，并用利用栈结构实现汉诺塔

2、。了解递归的工作过程。二、实验过程：1、任务分配2、设计思想（1）将A柱子上n-1个盘子借助C柱子移到B柱子上，把A上剩下的一个盘子移到C上，将B上的n-1个盘子借助A移到C上（2）建立三个栈作为汉诺塔，利用栈结构“先进后出”的特点，先进栈的盘子要后出来3、需求分析　(1)输入的形式和输入值的范围：输入盘子的个数n　(2)输出的形式：盘子的移动过程及最终的移动总次数　(3)程序所能达到的功能：将A上的n个盘子借助B移到C上　(4)测试数据：4、概要设计1).抽象数据类型2).算法a.栈模块：用来作为汉诺塔存入和去除圆盘，先进栈的圆盘后出来b.汉诺塔模块：建立汉诺塔模型

3、（将A上的n个盘子借助B移到C上）其中move函数用于实现圆盘的移动c.主函数模块：接收处理命令（初始化数据）5、详细设计程序代码（含注释）6、调试分析（1）调试中的问题分析：a.在定义汉诺塔函数的数据类型时，开始使用的是void，但是与后面main函数中定义的i类型不相符，且void函数无法返值，最后改为int型（2）算法的时空分析：a.时间复杂度：程序所花的时间正比于所输出的信息行数目，而信息行数目等价于盘子的移动次数，盘子移动的数目为move(n)，因此函数的时间复杂度为O(move(n))b.空间复杂度：3座塔在任何时候总共拥有的盘子个数都是n个，根据栈结构的

4、特点，只需要申请n个元素的空间。汉诺塔问题的复杂性是以n为指数的函数，因此只能接受n值比较小（n<20）的汉诺塔问题。7、测试结果列出你的测试结果，包括输入和输出。这里的测试数据应该完整和严格，最好多于需求分析中所列。8、说明（如果有）三、实验结果：（结果分析，心得体会等）1.结果分析：栈结构实现汉诺塔，充分体现栈结构“先进后出”的特点，利用这一基本特性，结合递归算法的适用，以达到实验目的。2.心得体会：这次栈结构实现汉诺塔代码的编写给了我深刻的体会，它不仅让我了解了栈结构的基本操作和相关知识点。在实验过程中出现了许多bug，需要不断调试才能找出问题，获得解决。虽然这

5、次实验已经达到了基本目的，但是让我发现了自己在相关知识点上的缺陷以及粗心的毛病，在以后的学习过程中，要更加细心，多练习，多思考。注：共三大项，具体每一项的内容可根据自己的报告内容分条叙述，自行安排得当即可。备注：（正文采用宋体小四，间距20磅）以上说明仅供参考。实验报告从这5部分展开，具体内容可自由发挥。如有雷同，均按零分处理。