C - 数据结构迷宫寻路（栈实现）

数据结构迷宫寻路（栈实现）

#include <stdio.h>  
#include <stdlib.h>  

#define INIT_SIZE 100
#define STACKINCREMENT 20
#define M 15
#define N 30
//- 基本要求：能够走到，正确显示路径；
//- 自选内容：检验迷宫路径的问题，对你的方法进行优化。 
//定义位置结构 
typedef struct {
	int x,y;
} PosType;
//定义栈点结构 
typedef struct{
	PosType pos;
	int d;
}SElemType;
//定义栈结构 
typedef struct{
	SElemType *base;
	SElemType *top;
	int stacksize;
} SeqStack;

//创建空栈
SeqStack *InitStack(){
	SeqStack *S; 
	S=(SeqStack *)malloc(sizeof(SeqStack));
	S->base = (SElemType *)malloc(INIT_SIZE * sizeof(SElemType));
	if(!S->base) printf("内存分配出错！");
	S->top = S->base;
	S->stacksize = INIT_SIZE;
	return S; 
}
//元素e入栈
void Push(SeqStack *S, SElemType e){
	if(S->top - S->base >= S->stacksize){
		S->base = (SElemType *) realloc (S->base, (S->stacksize + STACKINCREMENT)*sizeof(SElemType));
		if(!S->base) printf("内存分配出错！");
		S->top = S->base + S->stacksize;
		S->stacksize += STACKINCREMENT ;
	}
	*S->top++ = e;
}
//出栈
SElemType Pop(SeqStack *S){
	if(S->top == S->base) printf("栈为空！");
	SElemType *e;
	e = --S->top;
	return *e; 
}
//根据当前位置pos和行进方向计算下一个位置坐标
PosType NextPos(PosType pos,int d){
	switch(d){
		case 0:pos.y += 1;break;
    	case 1:pos.x += 1;break;
	    case 2:pos.y -= 1;break;
	    case 3:pos.x -= 1;break;
	}
	return pos;
}

//显示■、□组成的迷宫，路径可以用*(不带方向)，也可以考虑方向→ ↓ ← ↑
void PrintMaze(int maze[M][N],int pos[M][N]){
	int i,j;
	for(i=0; i<M; i++){
		for(j=0; j<N; j++){
			switch(maze[i][j]){
				case 1:printf("■");break;
				case 0:printf("□");break;
				case 2:{  //路径上的点进行方向输出 
					switch(pos[i][j]){
						case 0:printf("* ");break;
						case 1:printf("→");break; 
						case 2:printf("↓");break;
						case 3:printf("←");break;
						case 4:printf("↑");break;
						default:printf("%d ",pos[i][j]);break;
					} break;
				
				}
				default:printf("□");break;
			}
		}
		printf("\n");
	}
}

//搜索从起点到终点的路径
int FindPath(int maze[][N],int pos[M][N],PosType startpos,PosType endpos)
{
	SeqStack *s = InitStack();
	SElemType e;
	PosType curpos;
	curpos = startpos;
	e.d = 0;
	//按照书中伪代码思路进行 
	do{
		if(maze[curpos.x][curpos.y]==0){
			e.pos = curpos;
			e.d = pos[curpos.x][curpos.y];
			Push(s,e);
			maze[curpos.x][curpos.y]=3;
			if ((curpos.x == endpos.x)&&(curpos.y == endpos.y)){
				while(!(s->top == s->base)){
					SElemType elem = Pop(s);
					maze[elem.pos.x][elem.pos.y]=2;
				}
				break;
			}
			curpos = NextPos(curpos,pos[curpos.x][curpos.y]++);
		}
		else{
			if(!(s->top == s->base)){
				e = Pop(s);
				maze[e.pos.x][e.pos.y]=-1;
				while(e.d == 4 && (!(s->top == s->base))){
						e = Pop(s);
						maze[e.pos.x][e.pos.y]=-1;
				}
				if(e.d < 4){
					e.d = pos[e.pos.x][e.pos.y];
					curpos = e.pos; 
					Push(s,e);
					maze[curpos.x][curpos.y]=3;
					curpos = NextPos(curpos,pos[e.pos.x][e.pos.y]++);
				}				
			}
		}
	}while(!(s->top == s->base));
}


int main(){
    int a,i,j;
    PosType startpos, endpos;

	//描述迷宫（人大校园）
	int maze[M][N]=
	{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,
	 1,1,1,1,1,1,1,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,1,1,1,0,1,0,1,1,
	 1,1,1,1,1,1,1,0,1,1,1,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,1,1,
	 1,1,1,1,0,1,1,0,1,1,1,0,0,0,0,0,1,1,1,0,1,1,1,1,1,0,0,1,1,1,
	 1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,1,1,1,
	 1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,
	 1,1,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,1,1,
	 1,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,1,1,0,0,0,0,1,1,
	 1,1,1,1,1,0,0,0,0,1,0,1,0,0,1,0,0,0,0,0,1,1,0,1,1,0,0,0,1,1,
	 1,1,0,0,0,0,0,0,0,1,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,
	 1,1,0,0,0,0,1,1,1,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
	 1,1,1,1,0,0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,
	 1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,0,1,1,1,0,1,1,1,0,1,1,0,1,1,1,
	 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};

	int place[8][2]= //作为示例,可自行增加,注意应该是0处
{	    8,1,//人大西门
        4,4,//明德楼
        9,15,//人文楼
        1,25,//北门
        6,23,//图书馆
        2,27,//邮局
        11,28,//东门
        3,23};//足球场
        
    int pos[M][N];  //新建数组表示每个点的前进方向 
	for(i=0; i<M; i++){
		for(j=0; j<N; j++){
		pos[i][j]=0;
		}
	}

	printf("\n简版人大地图\n");
    PrintMaze(maze,pos);
    printf("1.人大西门 2.明德楼  3.人文楼  4.北门\n");
    printf("5.图书馆   6.邮局    7.东门    8.足球场\n\n");

    printf("请选择起点位置： \n");
 	scanf("%d",&a);
    startpos.x=place[a-1][0];
    startpos.y=place[a-1][1];
    printf("请选择终点位置： \n");
 	scanf("%d",&a);
    endpos.x=place[a-1][0];
    endpos.y=place[a-1][1];
	
	if(FindPath(maze,pos,startpos,endpos)){
	    printf("\n路线如下所示:\n");
	    PrintMaze(maze,pos);
	}
	else
        printf("Sorry, no path found.\n");

    return 1;
}