migong.cpp

关于数据结构的课程设计：迷宫问题

/*迷宫问题*/
#include "stdio.h"
#include "stdlib.h"
#define STACKSIZE 100
#define r 64  
#define m2 8                                    /*定义 m+2为m2*/
#define n2 10                                   /*定义 n+2为n2*/
int m=m2-2,n=n2-2; 
int maze[m2][n2];
typedef struct 
{int x,y;                                        /*行，列坐标*/
 int pre;                                        /*链域*/ 
}sqtype;
sqtype sq[r];
struct moved
{int x,y;                                        /*坐标增量，取值-1，0，1*/
}move[8];                                        /*迷宫数组*/

typedef struct
{
	int x;                                      /*行值*/
	int y;                                      /*列值*/
}PostType; 
                                    /*通道位置存储结构*/
typedef struct                                 /*栈的元素类型*/
{
	int ord;                   /*通道块在路径上的"序号"，为了方便输出返回，从新的方向重新探测*/
	int di;                    /*从此通道块走向下一通道块的"方向"(0-3表示东南西北四个方向)*/
	PostType seat;             /*通道块在迷宫中的"坐标位置"*/
}SElemType; 
                                   /*栈中元素存储结构*/
typedef struct
{SElemType elem[STACKSIZE];
int top;
}SqStack;                                      /*栈的顺序存储结构定义*/


int creat()                                     /*用二维数组maze[m][n]来模拟迷宫*/
 {int i,j;
 for(i=0;i<10;i++)
 {maze[0][i]=1;
  maze[7][i]=1;
 }
 for(i=0;i<8;i++)
 {maze[i][0]=1;
  maze[i][9]=1;
 }
 printf("请输入maze[6][8]的值:\n");
  printf("输完一个数据后回车隔开:\n");
 for(i=1;i<7;i++)
	 for(j=1;j<9;j++)
	 {
	 printf("%d,%d,",i,j);
	 scanf("  %d",&maze[i][j]);
	 }
	 printf("\n");
printf("输出模拟迷宫的二维数组maze[m][n]：\n");
 for(i=0;i<8;i++)
 {	 for(j=0;j<10;j++)
     printf("%2d",maze[i][j]);
     	 printf("\n");
}
 return(1);
 }/*creat end*/

int PATH(int maze[][n2])                          /*找迷宫maze的路径*/
{int i,j,k,v,front,rear,x,y;
 int mark[m2][n2];
 for(i=0;i<m2;i++)
	 for(j=0;j<n2;j++)
		 mark[i][j]=0;

     printf("以逗号间隔，输完一个数据即(0,1)(1,1)(1,0)(1,-1)(0,-1)(-1,-1)(-1,0)(-1,1)后回车隔开:\n");
	 printf("Please Input move array:\n");
	 for(i=0;i<8;i++)
	 scanf("%d,%d",&move[i].x,&move[i].y);
	 sq[1].x=1;sq[1].y=1;sq[1].pre=0;
	 front=1;rear=1;
	 mark[1][1]=1;                                  /*标志入口点已到过*/
	 while(front<=rear)                             /*队列非空*/
	 {x=sq[front].x;
	  y=sq[front].y;                                /*(x,y)为出发点*/
	  	 for(v=0;v<8;v++)                           /*搜索(x,y)的8个相邻点(i,j)是否可到达*/
		 {i=x+move[v].x;
		  j=y+move[v].y;
		  if(maze[i][j]==0 && mark[i][j]==0)        /*(i,j)为可达点，入对列*/
		  {rear++;
		   sq[rear].x=i;
           sq[rear].y=j;
		   sq[rear].pre=front;
		   mark[i][j]=1;                            /*标志(i,j)已到达过*/
		  }
		  if((i==m)&&(j==n))                        /*到达出口点*/
		  {printf("THE PATH:\n");
		  k=rear;                                   /*打印输出路径*/
		  do
		  {
		   printf("(%d,%d)<-",sq[k].x,sq[k].y);
		   k=sq[k].pre;                             /*找到前一点*/
		  }while(k!=0);                             /*k=0时已到达入口点*/
		  printf("\n输出sq的最终状态: \n");
          printf("\n输出sq[i]: \n");
		  for(i=1;i<27;i++)
			  printf("%3d",i);
	      printf("\n");
		  printf("\n输出sq[i].x: \n");
		  for(i=1;i<27;i++)
              printf("%3d",sq[i].x);
		      printf("\n");
          printf("\n输出sq[i].y: \n");
		  for(i=1;i<27;i++)
              printf("%3d",sq[i].y);
		      printf("\n");
		   printf("\n输出sq[i].pre: \n");
          for(i=1;i<27;i++)
              printf("%3d",sq[i].pre);
		      printf("\n");
		 return(1);                                /*成功，返回*/
		  }/*if*/
		 }/*for(v=0...)*/
		 front++;                                  /*出队，front指出向新的出发点*/
	 }/*while*/                                    /*队空，循环结束*/
	 printf("There is no path!\n");
        return(0);                                   /*迷宫无路径，返回0*/
}/*PATH end*/



void InitStack(SqStack &S)
{//初始化操作
 //操作结果：构造一个空栈S
 S.top=0;
 return;
}
int StackEmpty(SqStack S)
{//判断操作
 //初始条件：顺序栈已存在
 //操作结果：若栈S为空栈，则返回1，否则返回0
 return(S.top==0);
}
int GetTop(SqStack S,SElemType &e)
{//取栈顶元素操作
 //初始条件：栈S已存在
 //操作结果：若栈S不空，则用e返回S的栈顶元素，并返回1，否则返回0
 if(!StackEmpty(S))
{e=S.elem[S.top-1];
 return 1;                           /*当栈非空时，操作成功*/
}
 return 0;                            /*空表，操作失败*/   
}
int Push(SqStack &S,SElemType e)
{//进栈操作
 //初始条件：栈S已存在
 //操作结果：插入元素e为新的栈顶元素，返回1;若S已满，则为空操作，返回0
 if(S.top>STACKSIZE-1) return 0;       /*上溢，操作失败*/
 S.elem[S.top++]=e;
 return 1;                             /*操作成功*/
}
int Pop(SqStack &S,SElemType &e)
{//出栈操作
 //初始条件：栈S已存在
 //操作结果：若S非空，则从栈顶删除栈顶元素，返回1;否则操作失败，返回0
 if(StackEmpty(S)) return 0;            /*栈空，操作失败*/
 e=S.elem[--S.top];
 return 1;                              /*操作成功*/
}
 void StackTraverse(SqStack S)
{//输出操作
 //初始条件：栈S已存在
 //操作结果：若S非空，则输出栈中所有元素
 while(!StackEmpty(S))
 printf("%d",S.elem[--S.top]);
 return;
}


void mazePath(PostType start,PostType end)
{//求解迷宫操作
 //操作结果：输出迷宫中一条路经，或不能通过迷宫的信息
 int direction[4][2]={{0,1},{1,0},{0,-1},{-1,0}};  /*初始化方向数组*/
 int i,j,k;
 int g,h;
 int curstep=1;                   /*通道位置在路经上序号的初始值为1*/
 PostType curpos;
 SElemType element;
 SqStack S;
 InitStack(S);
 maze[start.x][start.y]=2;         /*从入口开始，走过的通道作标记*/
 curpos=start;
 element.ord=curstep;
 element.seat=curpos;
 element.di=0;
 Push(S,element);                     /*入口信息入栈*/
 while(!StackEmpty(S))                 /*栈S非空*/
 {
	 Pop(S,element);  
	 //位置(i,j)在迷宫中的坐标位置
	 i=element.seat.x;                
	 j=element.seat.y;
	 k=element.di;
	 while(k<4)//0-3表示东南西北四个方向
	 {//若位置(i,j),则进入先从东-北中判断位置得出(g,h)
	  g=i+direction[k][0];
	  h=j+direction[k][1];
	  if(g==end.x && h==end.y && maze[g][h]==0)
	  {
		  printf("迷宫中从出口到入口的逆路径:\n");
		  printf("第%d个通道为:(%d,%d)\n",element.ord+1,end.x,end.y);
		  while(!StackEmpty(S))
		  {Pop(S,element);
		    printf("第%d个通道为:(%d,%d)\n",element.ord,element.seat.x,element.seat.y);
		  }
		  printf("第%d个通道为:(%d,%d)\n",1,start.x,start.y);
		  return;
	  }
	  if(maze[g][h]==0)                              /*走到没走过的点*/           
	  {maze[g][h]=2;                                /*走过此处位置，作标记*/
	   curstep++;
	   element.ord=curstep;
       element.seat.x=g;
	   element.seat.y=h;
	   element.di=k;
	   Push(S,element);
	   i=g;
	   j=h;
	   k=0;
	  }
	  else k++;
	 }
 }
 printf("迷宫中不存在一条通路！\n");
 return;
}
 
void main()
{   
int cord;	
PostType start,end;
	start.x=1;
	start.y=1;
	end.x=6;
	end.y=8;
 do{ printf("\n");
      printf("\n         主菜单\n");               /*建立一个主菜单*/
      printf("\n   1  输入用二维数组maze[m][n]模拟迷宫\n");
      printf("\n   2  采用广度搜索算法\n");
      printf("\n   3  采用深度搜索算法\n");
      printf("\n   4  结束程序运行\n");
      printf("\n——————————\n");
      printf("请输入您的选择(1,2,3,4):");
      scanf("%d",&cord);
	  switch(cord){
	     case 1:{ creat();		
				}break;
         case 2:{PATH(maze);
				}break;
          case 3:{mazePath(start,end);
				}break;
         case 4:exit(0);
		 }
	}while(cord<=4);

 }/*main end*/