3-3-2maze.txt

数据结构源程序

/*迷宫的最短路径*/
#include <stdio.h>
#include <malloc.h>
#define MAXSIZE 256
#define M 6
#define N 8
typedef struct /*横纵坐标及它的前驱*/
{
	int x,y;
	int pre;
} SqType;
typedef struct /*方向数组的结构*/
{
	int x;
	int y;
} item;
typedef struct /*将队列、头尾指针和队中元素个数封装起来*/
{
	SqType sq[MAXSIZE];
	int front,rear;
	int num;
} C_SeQueue;

void menu();
C_SeQueue *init_SeQueue();
void maze_init(int (*maze)[N+2]);
void move_init(item *move);
int path(int (*maze)[N+2],item *move,C_SeQueue *Q);
void printpath(C_SeQueue *Q);
void reatore(int (*maze)[N+2]);

void main()
{
	int n,m=1;
	C_SeQueue *Q;
	/*clrscr();*/
	while(m)
	{
		menu();
		scanf("%d",&n);
		switch(n)
		{
			case 1:Q=init_SeQueue();break;
			case 2:{
				int maze[M+2][N+2]; /*迷宫数组*/
				int success;
				item move[8];       /*坐标增量数组*/
				maze_init(maze);
				move_init(move);
				success=path(maze,move,Q);
				if(success==0)
				{
					printf("\nmaze have not road!\n");
				}
				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;
}

C_SeQueue *init_SeQueue()
{
	C_SeQueue *q;
	q=(C_SeQueue*)malloc(sizeof(C_SeQueue));
	q->front=q->rear=0;
	q->num=0;
	return q;
}

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[2][6]=0;
	maze[3][1]=0;
	maze[3][3]=0;
	maze[3][4]=0;
	maze[4][1]=0;
	maze[4][5]=0;
	maze[4][6]=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,C_SeQueue *Q) /*迷宫最短路径*/
{
	int x,y,i,j,v;
	Q->sq[0].x=1;
	Q->sq[0].y=1;
	Q->sq[0].pre=-1;
	maze[1][1]=-1;
	while(Q->front<=Q->rear) /*队列不空*/
	{
		x=Q->sq[Q->front].x;
		y=Q->sq[Q->front].y;
		for(v=0;v<8;v++)
		{
			i=x+move[v].x;
			j=y+move[v].y;
			if(maze[i][j]==0)
			{
				Q->rear++;
				Q->sq[Q->rear].x=i;
				Q->sq[Q->rear].y=j;
				Q->sq[Q->rear].pre=Q->front;
				maze[i][j]=-1;
				if((i==M)&&(j==N))
				{
					printpath(Q);
					reatore(maze);
					return 1;
				}/*end if*/
			}/*end if*/
		} /*end for*/
		Q->front++;
	} /*end while*/
	return 0;
}
void printpath(C_SeQueue *Q)
{
	int i;
	i=Q->rear;
	printf("\n");
	do
	{
		printf("(%d,%d)<--",Q->sq[i].x,Q->sq[i].y);
		i=Q->sq[i].pre;
	}while(i!=-1); /* end while */
	printf("\n\n");
	return;
}
void reatore(int (*maze)[N+2])
{
	int i,j;
	for(i=0;i<M+2;i++)
	{
		for(j=0;j<N+2;j++)
		{
			if(maze[i][j]==-1)
				maze[i][j]=0;
		}
	}
	return;
}