资源描述：
《汉洛塔的实现-数据结构》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构实验报告姓名：否学号：2010468302班级：计科1001题目：汉洛塔的实现完成日期：2012.04.24成绩：一，需求分析：1需求分析本次试验是分别用栈和递归实现汉罗塔的实际问题，通过与c语言中的递归调用函数实现了塔间的转移，通过栈的存放实现了塔的从小到大的堆放。主要是函数的递归和栈的建立及出栈和入栈的实现。除此之外我还用另一种方法实现了汉罗塔，与栈实现汉罗塔做对比可以很清楚地看到栈的优点和缺点。2：程序执行命令包括：1）栈的建立2）出栈返回一个整数3）进栈4）删除栈的元素3：测试数据：栈实现：请输入塔的层数:1；请输入塔
2、的层数:2；请输入塔的层数:3；请输入塔的层数:4。普通实现：请输入塔的层数:1；请输入塔的层数:2；请输入塔的层数:3请输入塔的层数:4。二概要设计：1：顺序存储结构的抽象数据类型定义为：ADThanoi{数据对象：D={ai
3、ai∊ElemSet,i=1,2,...n,n>=0}数据关系：R1={
4、ai-1,aiD,i=1,2,...n}基本操作：voidinitstack(sqstack&s)操作结果：构建一个空栈。voidpush(sqstack&s,inte)初始条件：栈s已存在，可能有部分元素存在操作结果
5、：插入元素e到栈顶。Voidpop(sqstack&s,int&e)初始条件：栈s已存在，可能有部分元素存在操作结果：删除栈顶元素intgottop(sqstack&s,inte)初始条件：线性表L已存在，可能有部分元素存在操作结果：获得栈顶指针。voidhanoi(intn,sqstackx,sqstacky,sqstackz)初始条件：栈已经存在你，有元素操作结果：实现递归voidmove(sqstack&a,intm,sqstack&c)初始条件：栈已经存在你，有元素操作结果：递归函数中元素的具体实现。}ADTList3：本程序
6、包含以下3个模块：1）主程序模块voidmain()｛初始化；2）栈函数调用部分3）递归部分三，详细设计#include#include#include#include#definestack_init_size100#definestackincrement10typedefstructsqstack{char*elem;int*base;int*top;intstacksize;}sqstack;voidinitstack(sqstack&s){s.bas
7、e=(int*)malloc(stack_init_size*sizeof(int));s.top=s.base;s.stacksize=stack_init_size;}voidpush(sqstack&s,inte)//将e进栈{if(s.top-s.base>=s.stacksize){s.base=(int*)realloc(s.base,(s.stacksize+stackincrement)*sizeof(int));if(!s.base){printf("overflow");exit(1);}s.top=s.bas
8、e+s.stacksize;s.stacksize+=stackincrement;}*s.top++=e;}voidpop(sqstack&s,int&e)//top下移{if(s.top==s.base)printf("空栈");elsee=*--s.top;//s.top=s.top-1;}intgottop(sqstack&s,inte)//取栈顶元素，把值赋给e{if(s.top==s.base){printf("栈满");}elsee=*(s.top-1);returne;}voidmove(sqstack&a,int
9、m,sqstack&c){inte=0;e=gottop(a,m);//m是编号//printf("%d",e);push(c,e);//printf("%d",m);pop(a,e);printf("%c->%c",*a.elem,*c.elem);}voidhanoi(intn,sqstackx,sqstacky,sqstackz){if(n==1){move(x,1,z);//intf("%c->%c",*x.elem,*z.elem);}else{hanoi(n-1,x,z,y);move(x,n,y);//ntf
10、("%c->%c",*x.elem,*y.elem);hanoi(n-1,y,x,z);}}intmain(){intn;charx='a',y='b',z='c';sqstacka,b,c;initstack(a)
