3-1-2maze.txt

数据结构源程序

/*迷宫算法的实现*/
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 256
#define M 6
#define N 8
typedef struct  /*横纵坐标及方向*/
{
	int x;
	int y;
	int d;
} datatype;
typedef struct
{
	datatype data[MAXSIZE];
	int top;
} SeqStack;
typedef struct /*方向数组的结构*/
{
	int x;
	int y;
} item;
void menu();
SeqStack * init_SeqStack();
int Empty_SeqStack(SeqStack *S);
int Push_SeqStack(SeqStack *S,datatype x);
int Pop_SeqStack(SeqStack *S,datatype *p);
void maze_init(int (*maze)[N+2]);
void move_init(item *move);
int path(int (*maze)[N+2],item *move,SeqStack *S);
void main()
{
	int n,m=1;
	SeqStack *S;
	/*clrscr();*/
	while(m)
	{
		menu();
		scanf("%d",&n);
		switch(n)
		{
			case 1:S=init_SeqStack();break;
			case 2:{
				int maze[M+2][N+2];
				datatype temp;
				item move[8];
				maze_init(maze);
				move_init(move);
				path(maze,move,S);
				while(!Empty_SeqStack(S)) /*显示输出结果*/
				{
					Pop_SeqStack(S,&temp);
					printf("\n%4d%4d%4d\n",temp.x,temp.y,temp.d);
				}
				break;
				}
			case 0:m=0;
		}
	}
}
void menu()
{
	/*clrscr();*/
	printf("\n");
	printf("\t\t1.initialization\n\n");
	printf("\t\t2.maze\n\n");
	printf("\t\t0.exit\n\n");
	printf("\n\n\n\tplease select:");
	return;
}
SeqStack * init_SeqStack()
{
	SeqStack *S;
	S=(SeqStack*)malloc(sizeof(SeqStack));
	S->top=-1;
	return S;
}
int Empty_SeqStack(SeqStack *S)
{
	if(S->top==-1)
		return 1;
	else
		return 0;
}
int Push_SeqStack(SeqStack *S,datatype x)
{
	if(S->top==MAXSIZE-1)
	{
		return(0);
	}
	else
	{
		S->top++;
		S->data[S->top]=x;
		return(1);
	}
}
int Pop_SeqStack(SeqStack *S,datatype *p)
{
	if(Empty_SeqStack(S)==1)
	{
		return 0;
	}
	else
	{
		*p=S->data[S->top];
		S->top--;
		return 1;
	}
}
void maze_init(int (*maze)[N+2])
{
	int i,j;
	for(i=0;i<M+2;i++)
	{
		for(j=0;j<N+2;j++)
			maze[i][j]=1;
	}
	maze[1][1]=0;
	maze[1][5]=0;
	maze[2][2]=0;
	maze[2][4]=0;
	maze[3][1]=0;
	maze[3][3]=0;
	maze[3][4]=0;
	maze[3][5]=0;
	maze[3][6]=0;
	maze[3][7]=0;
	maze[4][1]=0;
	maze[4][5]=0;
	maze[5][2]=0;
	maze[5][3]=0;
	maze[5][6]=0;
	maze[5][7]=0;
	maze[5][8]=0;
	maze[6][1]=0;
	maze[6][4]=0;
	maze[6][5]=0;
	maze[6][8]=0;
	return;
}
void move_init(item *move)
{
	move[0].x=0  ; move[0].y=1;
	move[1].x=1  ; move[1].y=1;
	move[2].x=1  ; move[2].y=0;
	move[3].x=1  ; move[3].y=-1;
	move[4].x=0  ; move[4].y=-1;
	move[5].x=-1 ; move[5].y=-1;
	move[6].x=-1 ; move[6].y=0;
	move[7].x=-1 ; move[7].y=1;
}
int path(int (*maze)[N+2],item *move,SeqStack *S)
{
	datatype temp;
	int x,y,d,i,j;
	temp.x=1;      /*temp初始化*/
	temp.y=1;
	temp.d=-1;
	Push_SeqStack(S,temp);
	while(!Empty_SeqStack(S))
	{
		Pop_SeqStack(S,&temp);
		x=temp.x;
		y=temp.y;
		d=temp.d+1;
		while(d<8)
		{
			i=x+move[d].x;
			j=y+move[d].y;
			if(maze[i][j]==0)
			{
				temp.x=x;
				temp.y=y;
				temp.d=d;
				Push_SeqStack(S,temp); /*入栈*/
				x=i;
				y=j;
				maze[x][y]=-1; /*到达新点*/
				if((x==M)&&(y==N))
				{
					return 1; /*迷宫有路，返回*/
				}
				else
				{
					d=0;
				}
			}
			else
			{
				d++;
			}
		} /* end while(d<8)*/
	} /* end while */
	return 0; /*迷宫无路，返回*/
}