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

xx大学 xx学院算法与数据结构试验报告设计名称： 算法与数据结构 设计题目： 栈的应用 学生学号： xx 专业班级： xx 学生姓名： xx 学生成绩： 指导教师（职称）： 课题工作时间： 2012年4月10日 说明：实验课程类别：课程内实验实验课程性质：必修适用专业、年级：2010级计算机工程、计算机网络开课院、系：计算机科学与工程学院计算机工程教研室学时：18编写依据：算法与数据结构实验教学大纲修订时间：2012年2月算法与数据结构课程实验指导书（以下简称：指导书）是针对计算机学院所开设的对应课程的上机实验而编写的教学文件，供学生上机实验时使用。上机的工作环境要求：Windows 2000或以上操作系统、VC+ 6.0或者其它高级程序设计语言。学生应按指导教师的要求独立完成实验，并按要求撰写实验报告。每一个实验，编程上机调试并且提交电子文档实验报告，以学号姓名作为文件名上传。报告内容至少包含如下内容：1、 学生基本情况：专业班级、学号、姓名2、 实验题目、实验内容3、 设计分析4、 源程序代码5、 测试用例（尽量覆盖所有分支）6、 实验总结一实验内容与学时分配序次实验题目实验类型基本技能训练学时一线性结构综合应用综合性（1）掌握线性结构的常用操作；（2）能够应用线性结构解决比较简单的问题。10二非线性结构综合应用综合性（1）掌握树形、图形结构的插入、删除、查找等算法；（2）能够应用二叉树解决比较简单的问题。4三查找技术综合应用综合性（1）熟练掌握查找的常用算法；（2）熟练设计和应用查找算法解决简单的实际问题。2四排序技术综合应用综合性（1）熟练掌握常用的排序方法，并掌握用高级语言实现排序算法的方法；（2）深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用；（3）了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。2一、 试验课题栈的应用实验目的：（1）掌握栈的特点及其存储方法； （2）掌握栈的常见算法以及程序实现； （3）了解递归的工作过程。二、 试验内容Hanoi塔问题。（要求4个盘子移动，输出中间结果） 三、 试验分析三个盘子Hanoi求解示意图如下：BAABACAABACAACAABACA(a)(b)(c)(d)三个盘子汉诺塔算法的运行轨迹：Hanio(3,A,B,C)Hanio(3,A,B,C)Hanio(2,A,C,B)Hanio(2,A,C,B)Hanio(1,A,B,C)Hanio(1,A,B,C)Move (A,C)Move (A,B)Hanio(1,C,A,B)Hanio(1,C,A,B)Move (C,B)Move (A,B)Hanio(2,B,A,C)Hanio(2,B,A,C)Hanio(1,B,C,A)Hanio(1,B,C,A)Move (B,C)Hanio(1,A,B,C)Hanio(1,A,B,C)Move (A,C)Move (B,A)递归第一层递归第二层递归第三层Hanio算法如下：1 void Hanoi(int n, char A, char B, char C) /第一列为语句行号2 3 if (n=1) Move(A, C); /Move是一个抽象操作，表示将碟子从A移到C上4 else 5 Hanoi(n-1, A, C, B);6 Move(A, C);7 Hanoi(n-1, B, A, C);8 9 四、 源程序代码#include#include#define MaxSize 30typedef structint dataMaxSize;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(nt假设有三根柱子A、B、C，开始时A柱子上有1%d环，并且它们是按照从小到大的顺序放在A柱子上的，按照汉诺塔规则，将A柱子上所有环通过B柱子，移动到C柱子的则移动方法为：nn,n);i=Hanoi(n,a,b,c);free(a);free(b);free(c);printf(总共需要移动的次数为：%d次n,i);void InitStack(SqStack * &s) /*初始化栈*/s=(SqStack *)malloc(sizeof(SqStack);s-top=-1;int Push(SqStack * &s,int e) /*进栈*/if(s-top=MaxSize-1)return 0;s-top+;s-datas-top=e;return 1;int Pop(SqStack * &s,int &e) /*出栈*/if(s-top=-1)return 0;e=s-datas-top;s-top-;return 1;int Hanoi(int n,SqStack * &a,SqStack * &b,SqStack * &c)static int i=0;if(n=1)Move(a,c);i+;elseHanoi(n-1,a,c,b);Move(a,c);i+;Hanoi(n-1,b,a,c);return i;void Move(SqStack * &a,SqStack * &b)int i;Pop(a,i);printf(ttt%d环-%c柱子n,i,b-name);Push(b,i);五、 测试用例1.当输入2时，运行结果如下：2. 当输入3时，运行结果如下：3. 当输入4时，运行结果如下：4. 当输入5时，运行结果如下：4. 当输入10时，运行结果如下：几次测试都表明试验设计的正确性。六、 试验总结本次试验中，在解决汉诺塔问题中，结合了最近刚学的栈的知识，并且运用到之前C语言中学到的函数的递归的运用，很好的解决了这一类问题。其中，每一个“汉诺塔”就形如一个栈一样，环先进“汉诺塔”的要后出来，所以把它看成一个栈，运用栈的相关算法，实现高效快速的解决汉诺塔