数据结构实验报告
题目：用栈解决迷宫问题
．需求分析
1．以结构体 Maze 表示迷宫，其中 pos 表示该位置是否有障碍； freq 记录该位置被经过的次数；数组 move 表示下一步的方向。
2. 本程序自动随机生成一个12 × 12大小的迷宫，字符“ H”表示有障碍，空符表示通
路。
3. 迷宫的入口为左上角，出口为右下角。
4. 本程序只求出一条成功的通路。
.概要设计
为了实现上述操作，以栈为存储结构。
本程序包含三个模块：
1)主程序模块 :实现人机交互。
2)迷宫生产模块:随机产生一个12× 12的迷
宫。
3)路径查找模块：实现通路的查找。
4)求解迷宫中一条通路的伪代码：
do{
若当前位置可同，则{
将当前位置插入栈顶；若该位置是出口位置，则结束；否则切换当前位置的东临方块为新的当前位置；} 否则 {
若栈不空且栈顶位置尚有其他方向未被探索，则设定新的的当前位置为沿顺时针
方向旋转找到的栈顶位置的下一相邻块若栈不空但栈顶位置的四周均不可通，
则{
删去栈顶位置；
若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈
至栈空。
} }
} while( 栈不空 )
三. 详细设计栈的设计： typedef struct { Node *base,*top; int length; }Stack;
Stack *initstack(); // 初始化栈 void printstack(Stack *s); // 打印栈
Status destroy(Stack *); // 销毁整个栈
Status deltop(Stack *s); // 出栈
Status pushelem(Stack *,ElemType ,ElemType); // 进栈
1. 主程序模块：
int main()
{
printf(" 随机产生一个12× 12 的迷宫， X 字符表示障碍，空符表示通路：
\n");
Maze a[N][N];
makemaze(a);
printf(" 输入回车键显示路径 ,* 字符表示路径。 \n"); getchar();
findpath(a); while(1); return 0;
}
2. 迷宫生产模块；
void makemaze(Maze (*p)[N])
{
int i,j,conter; for(i=0;i (*(p+i)+j)->pos=0; (*(p+i)+j)->freq=0; (*(p+i)+j)->move[0]=0; (*(p+i)+j)->move[1]=0; (*(p+i)+j)->move[2]=0; (*(p+i)+j)->move[3]=0; } fo r( j= 0; j< N; ++ j) { (*p+j)->pos='X'; (*(p+N-1)+j)->pos='X'; } for(i=1;i { (*(p+i))->pos='X'; (*(p+i)+N-1)->pos='X'; } srand((int)time(NULL)); for(conter=0;conter<20;++conter) { i=rand()%(N-2); j=rand()%(N-2); (*(p+i)+j)->pos='X'; if(i==1&&j==1||i==N-1&&j==N- 1) { (*(p+i)+j)->pos=0; } } printmaze(p); } 3. 路径查找模块。 Maze *testnewpos(Maze (*p)[N],Stack *s,int *i,int *j) { Maze *q=NULL; int select=0; *i=*j=0; for(;q==NULL&&select<4;++select)// 在可行的方向上只选一个{ switch(select) { case 0: if( (*(p+s->top->x)+s->top->y)->move[0]!=1 ) { (*(p+s->top->x)+s->top->y)->move[0]=1; q=*(p+s->top->x)+s->top->y+1; *i=s->top->x+0; *j=s->top->y+1; }// 退回前一步检查东方向是否可通 break; case 1: if( (*(p+s->top->x)+s->top->y)->move[1]!=1 ) { (*(p+s->top->x)+s->top->y)->move[1]=1; q=*(p+s->top->x+1)+s->top->y; *i=s->top->x+1; *j=s->top->y+0; }// 退回前一步检查南方向是否可通 break; case 2: if( (*(p+s->top->x)+s->top->y)->move[2]!=1 ) { (*(p+s->top->x)+s->top->y)->move[2]=1; q=*(p+s->top->x)+s->top->y- 1; *i=s->top->x+0; *j=s->top->y-1; }// 退回前一步检查西方向是否可通 break; case 3: if( (*(p+s->top->x)+s->top->y)->move[3]!=1 ) { (*(p+s->top->x)+s->top->y)->move[3]=1; q=*(p+s->top->x-1)+s->top->y; *i=s->top->x-1; *j=s->top->y+0; }// 退回前一步检查北方向是否可通 } } return q; } void printpath(Stack *s,Maze (*p)[N]) { Node *n; int i,j,conter; conter=0; n=s->base; for(;n;n=n->next) { (*(p+n->x)+n->y)->pos='*'; } for(i=0;i { ++conter; printf(FORMAT,(*(p+i)+j)->pos); if(conter%12==0) TURNLINE; } TURNLINE; } 完整的程序： maze.h #ifndef MAZE_H #define MAZE_H #include "mazepath.h" #include #define N 12//10+2 #define FORMAT "%2c" #define TURNLINE printf("\n") typedef struct { char pos; int freq; int move[4]; }Maze; void makemaze(Maze (*p)[N]); void printmaze(Maze (*p)[N]); void findpath(Maze (*p)[N]); Maze *testnewpos(Maze (*p)[N],Stack *,int *,int *); void printpath(Stack *s,Maze (*p)[N]); void makemaze(Maze (*p)[N]) { int i,j,conter; for(i=0;i for(j=0;j { (*(p+i)+j)->pos=0; (*(p+i)+j)->freq=0; (*(p+i)+j)->move[0]=0; (*(p+i)+j)->move[1]=0; (*(p+i)+j)->move[2]=0; (*(p+i)+j)->move[3]=0; } for(j=0;j { (*p+j)->pos='X'; (*(p+N-1)+j)->pos='X'; } for(i=1;i { (*(p+i))->pos='X'; (*(p+i)+N-1)->pos='X'; } srand((int)time(NULL)); for(conter=0;conter<20;++conter) { i=rand()%(N-2); j=rand()%(N-2); (*(p+i)+j)->pos='X'; if(i==1&&j==1||i==N-1&&j==N-1) { (*(p+i)+j)->pos=0; } } printmaze(p); } void printmaze(Maze (*p)[N]) { int i,j,conter; conter=0; for(i=0;i for(j=0;j { ++conter; printf(FORMAT,(*(p+i)+j)->pos); if(conter%12==0) TURNLINE; } TURNLINE; } void findpath(Maze (*p)[N]) { Maze *q=NULL; int i=1,j=1,*pi=&i,*pj=&j,success=0; Stack *s; s=initstack();// 初始化用来存储路径的栈 q=*(p+1)+1;// 初始化当前位置为入口位置 do { if(q->pos!='X'&&!(q->freq))// 当前位置通且在当前路径中未被访问过，则入栈{ if(i==N-2&&j==N-2) { pushelem(s,N-2,N-2); success=1; } else if(i==1&&j==1) pushelem(s,i,j); q->freq=1;// 当前位置已经进栈，作标记，不能再入栈，不然就只能兜死胡同了q->move[0]=1;// 切换下一位置为东邻位置 , 并做标记，东邻位置已经使用i=s->top->x+0; j=s->top->y+1; q=*(p+i)+j; } else { pushelem(s,i,j); q->freq=1; q=*(p+i)+j; } } else// 当前位置不通，则在前一步 ( 栈顶 ) 检查是否有其他方向可行 { //printf("step here..."); if(s->base!=s->top) { do// 查找新的通路直到新通路出现或者回到初始位置 { { q=testnewpos(p,s,&i,&j);// 返回其它三个方向的其中一个和新的当前位置的 坐标 if(q==NULL) deltop(s);// 栈顶没有可继续往下走的通路，删除栈顶，在新的栈顶找 }while(q==NULL&&s->base!=s->top); } } }while(success!=1); printpath(s,p); } Maze *testnewpos(Maze (*p)[N],Stack *s,int *i,int *j) { Maze *q=NULL;
相关主题
文本预览