汉诺塔试验报告.doc

计算机学院实验报告课程名称： 数据结构 实验名称： 汉诺塔 学生姓名： 朱孝彬 学生学号： 20110511001 实验日期： 2012 一、实验目的1理解数据结构中汉诺塔2掌握汉诺塔的C+描述。二、实验内容1 编制汉诺塔的程序。三、实验步骤1需求分析本演示程序用C+6.0编写，完成汉诺塔的生成，2概要设计1）为了实现上述程序功能，需要定义单链表的抽象数据类型： （1）insert 3. 源代码#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时，运行结果如下： 四、实验总结（结果分析和体会）本次试验中，在解决汉诺塔问题中，结合了最近刚学的栈的知识，并且运用到之前学到的函数的递归的运用，很好的解决了这一类问题。其中，每一个“汉诺塔”就形如一个栈一样，环先进“汉诺塔”的要后出来，所以把它看成一个栈，运用栈的相关算法，实现高效快速的解决汉诺塔问题。通过本次试验，学会了栈的应用，加深了对栈的理解，知道了栈是一种先进栈的后出栈的储存结构。本次试