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

《迷宫问题实验报告用栈解决迷宫问题.doc》由会员分享，可在线阅读，更多相关《迷宫问题实验报告用栈解决迷宫问题.doc（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

4、i=0;iN;+i) for(j=0;jpos=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;jpos=X; (*(p+N-1)+j)-pos=X; for(i=1;ipos=X; (*(p+i)+N-1)-pos=X; srand(int)time(NULL); for(conter=0;conterpos=X; if(i=1&j=1|i=N-1&j=N-1) (*(p+i)+j)-pos=0; printmaze(p)

5、;3.路径查找模块。Maze *testnewpos(Maze (*p)N,Stack *s,int *i,int *j)Maze *q=NULL;int select=0;*i=*j=0;for(;q=NULL&selecttop-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-x+0; *j=s-top-y+1; / 退回前一步检查东方向是否可通 break; case 1: if( (*(p+s-top-x)+s-top-y)-move1!=1 ) (*(p

6、+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+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)-mov

7、e3!=1 ) (*(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=*; for(i=0;iN;+i) for(j=0;jpos); if(conter%12=0) TURNLINE; TURNLINE

8、; 完整的程序：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 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 *,i

9、nt *);void printpath(Stack *s,Maze (*p)N);void makemaze(Maze (*p)N) int i,j,conter; for(i=0;iN;+i) for(j=0;jpos=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;jpos=X; (*(p+N-1)+j)-pos=X; for(i=1;ipos=X; (*(p+i)+N-1)-pos=X; srand(int)time

10、(NULL); for(conter=0;conterpos=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;iN;+i) for(j=0;jpos); 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=initsta

11、ck();/初始化用来存储路径的栈 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-move0=1;/切换下一位置为东邻位置,并做标记，东邻位置已经使用 i=s-top-x+0; j=s-top-y+1; q=*(p+i)+j; else pushelem

12、(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 *testne

13、wpos(Maze (*p)N,Stack *s,int *i,int *j)Maze *q=NULL;int select=0;*i=*j=0;for(;q=NULL&selecttop-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-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)-mov

14、e1=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)-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)+

15、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=*; for(i=0;iN;+i) for(j=0;jpos); if(conter%12=0) TURNLINE; TURNLINE; #endifmazepath.h#ifn

16、def MAZEPATH_H#define MAZEPATH_H#include#include#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int ElemType;typedef int Status;typedef struct nodeElemType x;ElemType y;struct node *next;struct node *prior;Node,*Postion;typedef struct Node *bas

17、e,*top;int length;Stack;Stack *initstack(); /初始化栈void printstack(Stack *s); /打印栈Status destroy(Stack *); /销毁整个栈Status deltop(Stack *s); /出栈Status 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;r

18、eturn 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-length=

19、0;return OK;Status deltop(Stack *s)Node *p;if(!s-length) printf(Underflown); /已经是空栈else p=s-top; s-top=p-prior; free(p); -s-length; s-top-next=NULL;return OK; Status pushelem(Stack *s,ElemType i,ElemType j)Node *n;n=(Node *)malloc(sizeof(Node);if(!n) return ERROR;n-x=i;n-y=j；if(s-length=0) s-base=s-

20、top=n; n-prior=NULL;else n-prior=s-top; s-top-next=n; s-top=n;n-next=NULL; +s-length;return OK;#endifMyMain.cpp#include maze.hint main() printf(随机产生一个1212的迷宫，X字符表示障碍，空符表示通路：n); Maze aNN; makemaze(a); printf(输入回车键显示路径,*字符表示路径。n); getchar(); findpath(a); while(1); return 0;四 调试结果及说明1 说明:本程序的运行环境为VC+6.0，执行文件为MgProblem.exe。2 测试结果实际程序执行过程如下图所示：13_