《汉洛塔的实现-数据结构》由会员分享，可在线阅读，更多相关《汉洛塔的实现-数据结构（7页珍藏版）》请在金锄头文库上搜索。
1、 数据结构实验报告姓名：否 学号：2010468302班级：计科 1001题目：汉洛塔的实现完成日期：2012.04.24成绩：一，需求分析：1 需求分析本次试验是分别用栈和递归实现汉罗塔的实际问题，通过与 c 语言中的递归调用函数实现了塔间的转移，通过栈的存放实现了塔的从小到大的堆放。主要是函数的递归和栈的建立及出栈和入栈的实现。除此之外我还用另一种方法实现了汉罗塔，与栈实现汉罗塔做对比可以很清楚地看到栈的优点和缺点。2：程序执行命令包括：1）栈的建立 2）出栈返回一个整数 3）进栈 4）删除栈的元素3：测试数据：栈实现：请输入塔的层数:1；请输入塔的层数:2；请输入塔的层数:3；请输入塔的
2、层数:4。普通实现：请输入塔的层数:1；请输入塔的层数:2；请输入塔的层数:3请输入塔的层数:4。二 概要设计：1：顺序存储结构的抽象数据类型定义为：ADT hanoi数据对象：D= ai | ai ElemSet, i= 1,2,.n ,n=0数据关系：R1=|ai-1,ai D,i=1,2,.n基本操作：void initstack(sqstack &s)操作结果：构建一个空栈。void push(sqstack &s, int e)初始条件：栈s已存在 ，可能有部分元素存在操作结果：插入元素e到栈顶。Void pop(sqstack &s, int &e)初始条件：栈s已存在，可能有部分
3、元素存在 操作结果：删除栈顶元素int gottop(sqstack &s,int e)初始条件：线性表L已存在 ，可能有部分元素存在操作结果：获得栈顶指针。void hanoi(int n,sqstack x,sqstack y,sqstack z)初始条件：栈已经存在你，有元素操作结果：实现递归void move(sqstack &a,int m,sqstack &c)初始条件：栈已经存在你，有元素操作结果：递归函数中元素的具体实现。ADT List3：本程序包含以下 3 个模块：1）主程序模块void main()初始化；2）栈函数调用部分3）递归部分三，详细设计#include#inc
4、lude#include#include#define stack_init_size 100#define stackincrement 10typedef struct sqstackchar *elem;int *base;int *top;int stacksize;sqstack;void initstack(sqstack &s)s.base=(int*)malloc(stack_init_size*sizeof(int);s.top=s.base;s.stacksize=stack_init_size;void push(sqstack &s, int e)/将 e 进栈if(s
5、.top-s.base=s.stacksize)s.base=(int*)realloc(s.base,(s.stacksize+stackincrement)*sizeof(int); if(!s.base)printf(overflown);exit(1);s.top=s.base+s.stacksize;s.stacksize+=stackincrement;*s.top+=e;void pop(sqstack &s, int &e)/top 下移if(s.top=s.base) printf(空栈);elsee=*-s.top;/s.top=s.top-1;int gottop(sqs
6、tack &s,int e)/取栈顶元素，把值赋给 eif (s.top=s.base) printf(栈满n);elsee=*(s.top-1);return e;void move(sqstack &a,int m,sqstack &c) int e=0;e=gottop(a, m);/m 是编号/printf(%d ,e);push( c, e);/printf(%d n ,m);pop( a, e); printf(%c-%cn,*a.elem,*c.elem);void hanoi(int n,sqstack x,sqstack y,sqstack z)if(n=1) move(x,
7、1,z);/intf(%c-%cn,*x.elem,*z.elem);elsehanoi(n-1,x,z,y);move(x,n,y);/ntf(%c-%cn,*x.elem,*y.elem);hanoi(n-1,y,x,z);int main()int n;char x=a,y=b,z=c;sqstack a,b,c;initstack(a);initstack(b);initstack(c);printf(请输入塔的层数:);scanf(%d,for(int i=0;i%cn,a,b);elsehanoi(n-1,a,c,b);printf(%c-%cn,a,b);hanoi(n-1,c,
8、b,a);int main(void)int n;printf(请输入塔的层数:);scanf(%d,printf(the steps for %d disk are:n,n);hanoi(n,a,b,c);return 0;*/函数的调用关系图反映了程序的层次结构：main()hanoi(n-1,x,z,y)（递归函数）move(x,n,y)push( s, e) pop( s, e) gottop(s, m)四 调试分析：1：递归过程中出现很多问题，有事很难理解。2：move（）函数中栈的相关函数调用顺序不好确定。五 测试结果：塔数为 1 时：塔数为 2 时：塔数为 3 时：塔数为 4 时：
