迷宫求解课程设计报告.docx

《迷宫求解课程设计报告.docx》由会员分享，可在线阅读，更多相关《迷宫求解课程设计报告.docx（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构实验报告题目：迷宫问题姓名学号任务分配孙盛问题分析罗剑代码实现杨滢钢论文编写一 需求分析1 以结构体Maze表示迷宫，其中BuideMaze调用建立迷宫；Seat用来记录迷宫坐标；SqTack用来记录当前路径；数组；SElemType表示当前位置； Display用于显示栈中所有元素；BuideMaze用于根据用户要求建立一个迷宫地图。2 本程序根据需要产生一个迷宫，0表示有障碍，1表示通路；MazePath为求解迷宫。3 迷宫的入口为左上角，出口为右下角。4 本程序只求出一条成功的通路。 二 概要设计为了实现上述操作，以栈为存储结构。本程序包含三个模块：（1） 主程序模块:实现人机交

2、互。（2） 迷宫生产模块：根据需要产生一个迷宫模型。（3） 路径查找模块：实现通路的查找。（4） 求解迷宫中一条通路的伪代码：do 若当前位置可同， 则将当前位置插入栈顶；若该位置是出口位置，则结束；否则切换当前位置的东临方块为新的当前位置； 否则若栈不空且栈顶位置尚有其他方向未被探索，则设定新的的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块若栈不空但栈顶位置的四周均不可通，则 删去栈顶位置； 若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空。 while(栈不空)三详细分析与源程序#include #include #include #define STACK_

3、INIT_SIZE 100 /初始栈大小 #define STACKINCREAMENT 10 /添加栈的长度 #define SIZE_OF_MAPH 20 /迷宫高度 #define SIZE_OF_MAPW 20 /迷宫长度 / MazeCell功能：用来描述迷宫组成单元的信息 typedef struct int Pass; / Pass: 当Pass为1时，表示导通块；为0则表示障碍块； bool Footprint; / Footprint: 当 Footprint为1时，表示留下足迹，反之，表示未经此地。 MazeCell; / SElemType功能： 此为栈的元素，用来表示当

4、前位置，（栈用来描述当前路径） typedef struct int ord; / ord: 通道块的序号int x; / x : 当前位置的横坐标int y; / y : 当前位置的纵坐标int di; / di : 搜索方向 1向东，2向南，3向西，4向北SElemType; / SqTack功能： 此为栈，用来记录当前路径typedef struct SElemType *base; / *base 栈底指针，指向起点SElemType *top; / *top 栈顶指针，指向路径的末点int stacksize; / stacksize 栈的容量SqStack; / Seat功能： 用

5、来记录迷宫坐标，此结构体为中间变量，纯粹为方便编程而建立typedef struct int x; / x: 用来记录横坐标int y; / y: 用来记录纵坐标Seat; / InitStack功能： 此函数用于初始化一个栈bool InitStack(SqStack &S) / 函数参数： SqStack &S / 函数返回值类型： boolS.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!S.base) return 0; S.top=S.base; S.stacksize=STACK_INIT_SIZE;

6、 return 0; / BuideMaze功能： 此函数的功能是用于根据用户要求建立一个迷宫地图，将用户输入的/ 整形数组形状给迷宫数组 / 函数参数： MazeCell MapSIZE_OF_MASIZE_OF_MAP/ Seat &start 起点坐标 / Seat &end 终点坐标/ 函数返回值类型： bool 建立成功则返回1，反之返回0。VoidBuideMaze(MazeCellMapSIZE_OF_MAPHSIZE_OF_MAPW,int maSIZE_OF_MAPHSIZE_OF_MAPW) for(int i=0;iSIZE_OF_MAPH;i+) for(int j=0

7、;j=S.stacksize) S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREAMENT)*sizeof(SElemType); if(!S.base) return 0; S.top=S.base+S.stacksize; S.stacksize=S.stacksize+STACKINCREAMENT; *S.top+=e; return 1; bool Pop(SqStack &S,SElemType &e)/栈取出最上面的元素，将值给e if(S.base=S.top)return false; S.top-; e=*

8、S.top; return true; / NextPos功能： 此函数用于将坐标为x,y位置的di方向位置切换为当前位置。/ Seat curpos 当前坐标， int di 方向，int x,y 坐标，函数返回值类型： 无void NextPos(int x,int y,Seat &curpos,int di) if(di=1) curpos.y=y+1; curpos.x=x; else if(di=2) curpos.x=x+1; curpos.y=y; else if(di=3) curpos.y=y-1; curpos.x=x; else if(di=4) curpos.x=x-1

9、; curpos.y=y; / PutIn功能： 向数组里输入元素/ int map 将得到的数组给map, int Wei 迷宫的长度, int Hig 迷宫的高度,返回值类型：无void PutIn(int map,int &Wei,int &Hig) int w,h; cout如果您想输入的迷宫大于所规定的大小，您只需修改SIZE_OF_MAPH和SIZE_OF_MAPendl; cout请输入迷宫的长度(长度小于等于SIZE_OF_MAPW-2w; cout请输入迷宫的高度(高度小于等于SIZE_OF_MAPW-2h; cout1表示导通块；0表示障碍块endl; Wei=w; Hig

10、=h; for(int i=0;iSIZE_OF_MAPH;i+) for(int j=0;jSIZE_OF_MAPW;j+) *(map+i*SIZE_OF_MAPW+j)=0; for(int is=1;ish+1;is+) cout请输入第is行:; for(int js=1;jspoint; *(map+is*SIZE_OF_MAPW+js)=point; coutendl; / Display功能： 用于显示栈中所有元素void Display(SqStack S) int i=1; SElemType *p; p=S.base; cout从base到top:endl; coutdi

11、搜索方向:di=1向东，di=2向南，di=3向西，di=4向北endl; while(p!=S.top) /从base到top打印元素 cout第i步: ; cout(*p).y; cout,(*p).x; cout,(*p).di)endl; p+; i+; void DisplayMaze(int maSIZE_OF_MAPHSIZE_OF_MAPW,int w,int h) cout迷宫为(1代表可以通过；0代表不可以通过): endl; for(int i=0;ih+2;i+) for(int j=0;jw+2;j+) coutmaij ; coutendl; coutendl; /

12、 MazePath功能： 组织所有子函数，求解迷宫/ 函数返回值类型： int 迷宫有解则返回1，反之则返回0；int MazePath(MazeCell MapSIZE_OF_MAPHSIZE_OF_MAPW,Seat start,Seat end) SElemType e; SqStack S; /定义一个栈 InitStack(S); /初始化栈 Seat curpos; /定义当前位置 int curstep; /计步器 curstep=1; /计步器计1 curpos.x=start.x; / curpos.y=start.y; /当前位置设为起点 cout起点是:start.y s

13、tart.xendl; cout终点是:end.y end.xendl; / / / 下面的循环是求解迷宫的核心程序 / do if(Pass(curpos,Map) /如果当前块可通，则进行如下操作 FootPrint(curpos,Map); /留下脚印 e.ord=curstep; /记下计步器 e.x=curpos.x; /记下行数 e.y=curpos.y; /记下列数 e.di=1; /设一个方向为东方 Push(S,e); /压栈操作，将当前位置纳入当前路径 if(curpos.x=end.x&curpos.y=end.y) /如果当前块为终点，进行如下操作 / coutok!;

14、 / Display(S); /调用显示栈的子程序显示结果 return 1; /函数返回1 / else /如果当前位置不是终点，进行如下操作 / NextPos(curpos.x,curpos.y,curpos,1); /切换东方向的位置为当前位置 curstep+; /计步器自增1 /if else if(S.base!=S.top) /如果当前块不通，且栈不为空（说明还有解） Pop(S,e); /将栈顶元素弹出进行观察 while(e.di=4&(S.top-S.base) /如果栈顶元素四方均不通 Pop(S,e); /弹出下一个栈顶元素进行观察 /while if(e.di4)

15、/如果栈顶元素还有其他方向没有走过 / e.di+; /切换下一个方向为当前方向 Push(S,e); /压入栈 NextPos(e.x,e.y,curpos,e.di); /切换下一个方向位置为当前位置 /if /if /else while(S.base!=S.top); /只要栈不空则说明有解，重复循环 cout没找到路径endl; return 0; / main功能： 组织所有子函数，求解迷宫/ 函数返回值类型： bool 迷宫有解则返回1，反之则返回0；void main() MazeCell MapSIZE_OF_MAPHSIZE_OF_MAPW; /定义一个迷宫数组 /*int

16、 migongSIZE_OF_MAPHSIZE_OF_MAPW= 0,0,0,0,0,0,0,0,0,0, 0,1,1,0,0,0,0,0,0,0, /1 0,0,1,1,1,0,1,1,1,0, /2 0,0,1,0,1,1,1,0,1,0, /3 0,0,1,0,0,0,0,0,1,0, /4 0,0,1,0,1,1,1,0,0,0, /5 0,0,1,1,1,0,1,1,1,0, /6 0,0,0,0,0,0,0,0,0,0, ; /以数组表示的迷宫*/ int w,h; int migongSIZE_OF_MAPHSIZE_OF_MAPW; PutIn(migong0,w,h); Bu

17、ideMaze(Map,migong); /调用建立迷宫的子函数 DisplayMaze(migong,w,h); /显示迷宫的形状 Seat start,end; /定义当前位置，起点位置，终点位置的结构体 /*start.x=1; /起点 start.y=1; / end.x=2; /终点 end.y=2; /*/ coutstart.y; coutstart.x; coutend.y; coutend.x; MazePath(Map,start,end); 四 运行结果分析 五. 课设设计总结通过数据结构课程设计，使我们更好的了解了数据结构这门课程，以及对问题过程的思考，程序调试，都有很好的帮助。此次课程设计中，我们遇到了很多困难，但最终通过我们三个人共同的努力，最后还是完成了任务，使我们更好的了解了团队的重要性。