数据结构实验（八）

exp5-1

#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
//递归算法
void Hanoi1(int n,char a,char b,char c)
{
	if (n==1) 
		printf("	将第%%d个盘片从%%c移动到%%c
",n,a,c);
    else 
	{
		Hanoi1(n-1,a,c,b);
		printf("	将第%%d个盘片从%%c移动到%%c
",n,a,c);
		Hanoi1(n-1,b,a,c);
	}
}
//----非递归算法----------------------------------------
typedef struct
{	int n;							//盘片个数
	char x,y,z;						//3个塔座
	bool flag;						//可直接移动盘片时为true，否则为false
} ElemType;							//顺序栈中元素类型
typedef struct
{	ElemType data[MaxSize];			//存放元素
	int top;						//栈顶指针
} StackType;						//声明顺序栈类型

//--求解Hanoi问题对应顺序栈的基本运算算法--------------
void InitStack(StackType *&s)			//初始化栈
{	s=(StackType *)malloc(sizeof(StackType));
	s->top=-1;
}
void DestroyStack(StackType *&s)		//销毁栈
{
	free(s);
}
bool StackEmpty(StackType *s)			//判断栈是否为空
{
	return(s->top==-1);
}
bool Push(StackType *&s,ElemType e)		//进栈
{	if (s->top==MaxSize-1)
		return false;
	s->top++;
	s->data[s->top]=e;
	return true;
}
bool Pop(StackType *&s,ElemType &e)		//出栈
{	if (s->top==-1)
		return false;
	e=s->data[s->top];
	s->top--;
	return true;
}
void Hanoi2(int n, char x, char y, char z)
{	StackType *st;							//定义顺序栈指针
	ElemType e,e1,e2,e3;
	if (n<=0) return;						//参数错误时直接返回
	InitStack(st);							//初始化栈
	e.n=n; e.x=x; e.y=y; e.z=z; e.flag=false;
	Push(st,e);								//元素e进栈
	while (!StackEmpty(st))					//栈不空循环
	{	Pop(st,e);							//出栈元素e
		if (e.flag==false)					//当不能直接移动盘片时
		{
			e1.n=e.n-1; e1.x=e.y; e1.y=e.x; e1.z=e.z;
			if (e1.n==1)					//只有一个盘片时可直接移动
				e1.flag=true;
			else							//有一个以上盘片时不能直接移动
				e1.flag=false;
			Push(st,e1);					//处理Hanoi(n-1,y,x,z)步骤
			e2.n=e.n; e2.x=e.x; e2.y=e.y; e2.z=e.z; e2.flag=true;
			Push(st,e2);					//处理move(n,x,z)步骤
			e3.n=e.n-1; e3.x=e.x; e3.y=e.z; e3.z=e.y;
			if (e3.n==1)					//只有一个盘片时可直接移动
				e3.flag=true;
			else
				e3.flag=false;				//有一个以上盘片时不能直接移动
			Push(st,e3);					//处理Hanoi(n-1,x,z,y)步骤
		}
		else								//当可以直接移动时
			printf("	将第%%d个盘片从%%c移动到%%c
",e.n,e.x,e.z);
	}
	DestroyStack(st);						//销毁栈
}
//----------------------------------------------------
int main()
{
	int n=3;
	printf("递归算法： %%d个盘片的移动过程
",n);
	Hanoi1(n,'X','Y','Z');
	printf("非递归算法：%%d个盘片的移动过程:
",n);
	Hanoi2(n,'X','Y','Z');
	return 1;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

exp5-2

#include <stdio.h>
#define MaxSize 100
int pathnum(int m,int n)		//求解(m,n)到(1,1)的路径条数
{
	if (m<1 || n<1) return 0;
	if (m==1 && n==1) return 1;
	return pathnum(m-1,n)+pathnum(m,n-1);
}
typedef struct
{
	int i,j;
} PathType;							//路径元素类型
int count=0;						//路径编号
void disppath(int m,int n,PathType path[],int d) // 输出从(m,n)到(1,1)的所有路径
{	
	if (m<1 || n<1) return;
	if (m==1 && n==1)				//找到目的地，输出一条路径
	{
		d++;						//将当前位置放入path中
		path[d].i=m; path[d].j=n;
		printf("路径%%d: ",++count);
		for (int k=0;k<=d;k++)
			printf("(%%d,%%d) ",path[k].i,path[k].j);
		printf("
");
	}
	else
	{
		d++;						//将当前位置放入path中
		path[d].i=m; path[d].j=n;
		disppath(m-1,n,path,d);		//向下走一步
		disppath(m,n-1,path,d);		//退回来，向右走一步
	}
}
int main()
{
	int m=2,n=5;
	printf("m=%%d,n=%%d的路径条数:%%d
",m,n,pathnum(m,n));
	PathType path[MaxSize];
	int d=-1;
	disppath(m,n,path,d);
	return 1;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43