作者:fgsZHdgsz | 来源:互联网 | 2023-07-03 14:39
Hanoi塔 栈与递归C编程实现
参考书 严蔚敏 数据结构
#include
#include
#include
typedef int ElemType;
typedef int Status;
#define STACK_SIZE 10
#define STACK_INCREMENT 10
#define OK 1
#define ERROR -1
typedef struct{
ElemType *base;
ElemType *top;
int stacksize;
char tag;
}Stack;
Status InitStack(Stack &S,char tag)
{
S.base=(ElemType*)malloc(STACK_SIZE*sizeof(ElemType));
if (!S.base)
return ERROR;
S.top=S.base;
S.tag=tag;
S.stacksize=STACK_SIZE;
return OK;
}
Status Pop(Stack &S,ElemType &e)
{
if (S.base==S.top)//判断是否非空
return ERROR;
S.top--;//栈顶元素降低
e=*S.top;//输出
return OK;
}
Status Push(Stack &S,ElemType e)
{
if ((S.top-S.base)>=S.stacksize)//栈满追加数据元素
{
S.base=(ElemType *)realloc(S.base,(S.stacksize+STACK_INCREMENT)*sizeof(ElemType));
//指针名=(数据类型*)realloc(要改变内存大小的指针名,新的大小)。//新的大小一定要大于原来的大小不然的话会导致数据丢失!
if (!S.base)
exit(ERROR);
S.top=S.base+S.stacksize;
S.stacksize+=STACK_INCREMENT;
}
*S.top=e;
S.top++;
return OK;
}
Status StackEmpty(Stack &S)
{
if (S.base==S.top)
return 1;
else
return 0;
}
int c=0;//全局变量记录搬运次数
void Move(Stack &x,ElemType n,Stack &z)
{
Pop(x,n);
Push(z,n);
}
void hanoi(ElemType n,Stack &x,Stack &y,Stack &z)
{
printf("%d:Move disk %d from %c to %c\n",++c,n,x.tag,z.tag);
if (n==1)
Move(x,1,z);
else
{
hanoi(n-1,x,z,y);//将x上编号为1至n-1的圆盘移到y,z作为补助塔
Move(x,n,z);//将编号为n的圆盘从x移到z
hanoi(n-1,y,x,z);//将y上编号为1至n-1的圆盘移到z,x作为补助塔
}
}
void main()
{
int n;
Stack x,y,z;
char tagx='x';//给栈打标签
char tagy='y';//给栈打标签
char tagz='z';//给栈打标签
ElemType e;
InitStack(x,tagx);
InitStack(y,tagy);
InitStack(z,tagz);
printf("请输入Hanoi塔的高度\n");
scanf("%d",&n);
hanoi(n,x,y,z);
printf("搬运结束,输入罗汉塔Z:\n");
while(!StackEmpty(z))
{
Pop(z,e);
printf("%d\n",e);
}
getch();
}
输入塔高3
输出
请输入Hanoi塔的高度
3
1:Move disk 3 from x to z
2:Move disk 2 from x to y
3:Move disk 1 from x to z
4:Move disk 1 from z to y
5:Move disk 2 from y to z
6:Move disk 1 from y to x
7:Move disk 1 from x to z
搬运结束,输入罗汉塔Z:
1
2
3