迷宫问题实验报告用栈解决迷宫问题

1、精选优质文档-倾情为你奉上数据结构实验报告题目：用栈解决迷宫问题一 需求分析1 以结构体Maze表示迷宫，其中pos表示该位置是否有障碍； freq记录该位置被经过的次数；数组move表示下一步的方向。2 本程序自动随机生成一个12×12大小的迷宫，字符“H”表示有障碍，空符表示通路。3 迷宫的入口为左上角，出口为右下角。4 本程序只求出一条成功的通路。二 概要设计为了实现上述操作，以栈为存储结构。本程序包含三个模块：（1） 主程序模块:实现人机交互。（2） 迷宫生产模块：随机产生一个12×12的迷宫。（3） 路径查找模块：实现通路的查找。（4） 求解迷宫中一条通路的伪代码

2、：do 若当前位置可同， 则将当前位置插入栈顶；若该位置是出口位置，则结束；否则切换当前位置的东临方块为新的当前位置； 否则若栈不空且栈顶位置尚有其他方向未被探索，则设定新的的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块若栈不空但栈顶位置的四周均不可通，则 删去栈顶位置； 若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空。 while(栈不空)三 详细设计栈的设计：typedef struct Node *base,*top;int length;Stack;Stack *initstack(); /初始化栈void printstack(Stack *s); /

3、打印栈Status destroy(Stack *); /销毁整个栈Status deltop(Stack *s); /出栈Status pushelem(Stack *,ElemType ,ElemType); /进栈 1. 主程序模块： int main() printf("随机产生一个12×12的迷宫，X字符表示障碍，空符表示通路：n"); Maze aNN; makemaze(a); printf("输入回车键显示路径,*字符表示路径。n"); getchar(); findpath(a); while(1); return 0;2.

4、迷宫生产模块； void makemaze(Maze (*p)N) int i,j,conter; for(i=0;i<N;+i) for(j=0;j<N;+j) (*(p+i)+j)->pos=0; (*(p+i)+j)->freq=0; (*(p+i)+j)->move0=0; (*(p+i)+j)->move1=0; (*(p+i)+j)->move2=0; (*(p+i)+j)->move3=0; for(j=0;j<N;+j) (*p+j)->pos='X' (*(p+N-1)+j)->pos='

5、;X' for(i=1;i<N-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

6、 *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)->move0!=1 ) (*(p+s->top->x)+s->top->y)->move0=1; q=*(p+s->top->x)+s->top

7、->y+1; *i=s->top->x+0; *j=s->top->y+1; / 退回前一步检查东方向是否可通 break; case 1: if( (*(p+s->top->x)+s->top->y)->move1!=1 ) (*(p+s->top->x)+s->top->y)->move1=1; q=*(p+s->top->x+1)+s->top->y; *i=s->top->x+1; *j=s->top->y+0; / 退回前一步检查南方向是否可通 b

8、reak; case 2: if( (*(p+s->top->x)+s->top->y)->move2!=1 ) (*(p+s->top->x)+s->top->y)->move2=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)->move3!=1 )

9、(*(p+s->top->x)+s->top->y)->move3=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=

10、9;*' for(i=0;i<N;+i) for(j=0;j<N;+j) +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 <time.h>#define N 12/10+2#define FORMAT "%2c"#define TURNLINE printf("n&

11、quot;)typedef structchar pos;int freq;int move4;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<N;+i) for(j=0;j<N;+j) (*(

12、p+i)+j)->pos=0; (*(p+i)+j)->freq=0; (*(p+i)+j)->move0=0; (*(p+i)+j)->move1=0; (*(p+i)+j)->move2=0; (*(p+i)+j)->move3=0; for(j=0;j<N;+j) (*p+j)->pos='X' (*(p+N-1)+j)->pos='X' for(i=1;i<N-1;+i) (*(p+i)->pos='X' (*(p+i)+N-1)->pos='X' s

13、rand(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<N;+i) for(j=0;j<N;+j) +conter; printf(

14、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&&am

15、p;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->move0=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/当前位置不通，则在前一步(栈顶)检查是否有其他方

16、向可行 /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

17、,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)->move0!=1 ) (*(p+s->top->x)+s->top->y)->move0=1; q=*(p+s->top->x)+s->top->y+1; *i=s->top-

18、>x+0; *j=s->top->y+1; / 退回前一步检查东方向是否可通 break; case 1: if( (*(p+s->top->x)+s->top->y)->move1!=1 ) (*(p+s->top->x)+s->top->y)->move1=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+

19、s->top->x)+s->top->y)->move2!=1 ) (*(p+s->top->x)+s->top->y)->move2=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)->move3!=1 ) (*(p+s->top->x)+s

20、->top->y)->move3=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<N

21、;+i) for(j=0;j<N;+j) +conter; printf(FORMAT,(*(p+i)+j)->pos); if(conter%12=0) TURNLINE; TURNLINE; #endifmazepath.h#ifndef MAZEPATH_H#define MAZEPATH_H#include<stdio.h>#include<stdlib.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2t

22、ypedef int ElemType;typedef int Status;typedef struct nodeElemType x;ElemType y;struct node *next;struct node *prior;Node,*Postion;typedef struct Node *base,*top;int length;Stack;Stack *initstack(); /初始化栈void printstack(Stack *s); /打印栈Status destroy(Stack *); /销毁整个栈Status deltop(Stack *s); /出栈Status

23、 pushelem(Stack *,ElemType ,ElemType); /进栈Stack *initstack()Stack *s;s=(Stack *)malloc(sizeof(Stack);if(!s) return ERROR;s->base=s->top=NULL; /栈空s->length=0;return s;void printstack(Stack *s) Node *N;N=s->base;for(;N;N=N->next) printf("%2d %2d ",N->x,N->y);printf("nn");Status destroy(Stack *s)Node *p;p=s->base; while(s->base->next) s->base=s->base->next; /N=N->next和free(P)不能倒换位置，当释放p时， free(p); /如果不将N移向下一个位置，将导致N指向的内存释放，N->next不再有效 p=s->base; s->base=s->top=NULL; s-&