栈的应用解决汉诺塔问题.doc

xx大学 xx学院 算法与数据结构试验报告 设计名称： 算法与数据结构 设计题目： 栈的应用 学生学号： xx 专业班级： xx 学生姓名： xx 学生成绩： 指导教师（职称）： 课题工作时间： 2012年4月10日 说明： 实验课程类别：课程内实验 实验课程性质：必修 适用专业、年级：2010级计算机工程、计算机网络 开课院、系：计算机科学与工程学院计算机工程教研室 学时：18 编写依据：《算法与数据结构》实验教学大纲 修订时间：2012年2月 《算法与数据结构》课程实验指导书（以下简称：指导书）是针对计算机学院所开设的对应课程的上机实验而编写的教学文件，供学生上机实验时使用。 上机的工作环境要求：Windows 2000或以上操作系统、VC++ 6.0或者其它高级程序设计语言。 学生应按指导教师的要求独立完成实验，并按要求撰写实验报告。 每一个实验，编程上机调试并且提交电子文档实验报告，以学号姓名作为文件名上传。报告内容至少包含如下内容： 学生基本情况：专业班级、学号、姓名 实验题目、实验内容 设计分析 源程序代码 测试用例（尽量覆盖所有分支） 实验总结 一．实验内容与学时分配 序次 实验 题目 实验 类型 基本技能训练 学时 一 线性结构综合应用 综合性 （1）掌握线性结构的常用操作； （2）能够应用线性结构解决比较简单的问题。 10 二 非线性结构综合应用 综合性 （1）掌握树形、图形结构的插入、删除、查找等算法； （2）能够应用二叉树解决比较简单的问题。 4 三 查找技术综合应用 综合性 （1）熟练熟练掌握常用的排序方法，并掌握用高级语言实现排序算法的方法；深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用；了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。Hanoi塔问题。（要求4个盘子移动，输出中间结果） 试验分析 三个盘子Hanoi求解示意图如下： 三个盘子汉诺塔算法的运行轨迹： Hanio算法如下： 1 void Hanoi(int n, char A, char B, char C) //第一列为语句行号 2 { if (n==1) Move(A, C); //Move是一个抽象操作，表示将碟子从A移到C上 else { Hanoi(n-1, A, C, B); Move(A, C); Hanoi(n-1, B, A, C); } } 源程序代码 #includestdio.h #includestdlib.h #define MaxSize 30 typedef struct { int data[MaxSize]; char name; int top; }SqStack; void Move(SqStack * a,SqStack * b); int Hanoi(int n,SqStack * a,SqStack * b,SqStack * c); void InitStack(SqStack * s); int Push(SqStack * s,int e); /*进栈*/ int Pop(SqStack * s,int e); /*出栈*/ void main() { int n,i; SqStack *a,*b,*c; InitStack(a); InitStack(b); InitStack(c); a-name=A; b-name=B; c-name=C; printf(请输入汉诺塔中圆环的个数n: ); scanf(%d,n); for(int t=n;t0;t--) Push(a,t); printf(\n\t假设有三根柱子A、B、C，开始时A柱子上有1~%d环，并且它们是按照从小到大的顺序放在A柱子上的，按照汉诺塔规则，将A柱子上所有环通过B柱子，移动到C柱子的则移动方法为：\n\n,n); i=Hanoi(n,a,b,c); free(a); free(b); free(c); printf(总共需要移动的次数为：%d次\n,i); } void InitStack(SqStack * s) /*初始化栈*/ {