数据结构-迷宫实验报告

1、云南大学软件学院 数据结构实验报告 （本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助） 实验难度： A B C 实验难度A B C 承担任务（难度为C时填写）指导教师评分 （签名）【实验题目】实验4.数组的表示极其应用【问题描述】以一个mn的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。【基本要求】首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i，j，d)的形式输出，其中:(i，j)指示迷宫中的一个坐标，d表示走到下一坐标的方向。如；

2、对于下列数据的迷宫，输出的一条通路为：(l，1，1)，(1，2，2)，(2，2，2)，(3，2，3)，(3，1，2)，。（下面的内容由学生填写，格式统一为，字体: 楷体, 行距: 固定行距18，字号: 小四，个人报告按下面每一项的百分比打分。难度A满分70分，难度B满分90分）一、【实验构思（Conceive）】(10%)（本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计、算法等相关知识）本实验的目的是设计一个程序，实现手动或者自动生成一个nm矩阵的迷宫，寻找一条从入口点到出口点的通路。我们将其简化成具体实验内容如下：选择手动或者自动生成一个nm的迷宫，将迷宫的左

3、上角作入口，右下角作出口，设“0”为通路，“1”为墙，即无法穿越。假设从起点出发，目的为右下角终点，可向“上、下、左、右、左上、左下、右上、右下”8个方向行走。如果迷宫可以走通，则用“”代表“1”，用“”代表“0”，用“”代表行走迷宫的路径。输出迷宫原型图、迷宫路线图以及迷宫行走路径。如果迷宫为死迷宫，输出信息。可以二维数组存储迷宫数据，用户指定入口下标和出口下标。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。二、【实验设计(Design)】(20%)（本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块

4、与各子程序模块间的调用关系）1. 设定迷宫的抽象数据类型定义：ADT Maze 数据对象：D = ai, j | ai, j 、 , 0 irow+1, 0jcol+1, row, col18 数据关系：R = ROW, COL ROW = | ai-1, j, ai, j D, i=1, , row+1, j=0, , col+1COL = | ai, j-1, ai, j D, i=0, , row+1, j=1, , col+1 基本操作： Init_hand_Maze( Maze, row, col) 初始条件：二维数组Maze已存在。 操作结果：手动初始化迷宫，0表示通路，1表示障碍

5、。 Init_automatic_Maze( Maze, row, col)初始条件：二维数组Maze已存在。 操作结果：自动初始化迷宫，0表示通路，1表示障碍。 PrintMaze( Maze) 初始条件：迷宫Maze已存在。 操作结果：将迷宫输出到屏幕，“”表示通路，“”表示障碍。 MazePath( Maze)初始条件：迷宫Maze已存在。 操作结果：计算路径。 PrintPath( Maze)初始条件：迷宫Maze已存在。 操作结果：若迷宫存在一条通路，将路径输出至屏幕，以“”“”“”“”表示可行路径，“”表示途径过却无法到达出口的位置；若不存在通路，报告相应信息。 ADT Maze；

6、2. 设定栈的抽象数据类型定义：ADT Stack 数据对象：D = ai | ai CharSet, i=1, 2, , n, n0 数据关系：R1 = | ai-1, ai D, i=2, , n 基本操作： InitStack(&S) 操作结果：构造一个空栈。 Push(&S, e) 初始条件：栈S已存在。 操作结果：在栈S的栈顶插入新的栈顶元素e。 Pop(&S, &e) 初始条件：栈S已存在 . 操作结果：删除S的栈顶元素，并以e返回其值。 ADT Stack；3. 本程序包含三个模块1)主程序模块：void main() 初始化; do 接受命令; 处理命令; while (命令!

7、 = 退出); 2)栈模块实现栈抽象数据类型；3)迷宫模块实现迷宫抽象数据类型。4各模块之间的调用关系如下：主程序模块迷宫模块栈模块三、【实现描述（Implement）】(30%)（本部分应包括：抽象数据类型具体实现的函数原型说明、 关键操作实现的伪码算法、 函数设计、函数间的调用关系，关键的程序流程图等，给出关键算法的时间复杂度分析。）1. 迷宫与栈类型int mazeMN, row, col ; typedef struct /存放迷宫访问到点的行，列，方向 int m,n,direc;MazeType,*LMazeType;typedef struct LMazeType top; /路

8、径第一个元素的位置 LMazeType base; /路径最后一个元素的位置 int stacksize; /栈大小 int over; /溢出Stack;2. 栈操作函数void Init_hand_Maze(int mazeMN,int m,int n) int i,j; for(i=1;i=m+1;i+) for(j=1;j=n+1;j+) mazeij=1; cout请按行输入迷宫，0表示通路，1表示障碍:endl; for(i=1;im+1;i+) for(j=1;jmazeij; for(i=1;im+1;i+) for(j=1;jn+1;j+) if(mazeij!=0&maze

9、ij!=1) cout 您输入有误，请重新输入; Init_hand_Maze(maze,m,n); 时间复杂度为O(m*n)void Init_automatic_Maze(int mazeMN,int m,int n) /自动生成迷宫int i,j;coutn迷宫生成中nn;system(pause);for(i=1;im+1;i+)for(j=1;j=S.stacksize) S.base=(LMazeType)realloc(S.base,(S.stacksize+STACKINCREMENT) * sizeof(MazeType); if(!S.base)exit(OVERFLOW)

10、; S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return OK;Status Pop(Stack &S, MazeType &e) /将能走通的路径的点依次出栈 if(S.top=S.base)return ERROR; e=*-S.top; return OK;3. 求解迷宫Status MazePath(Stack &S, MazeType &e, int mazeMN, int m, int n) do if(mazee.me.n=0)/0可通，1不可通，2为已走过 Push(S,e); maze

11、e.me.n=2; if(e.m=m&e.n=n) S.over=1;/表示存满一条路径 return OK; else e.n+; e.direc=0;/来这一点时的方向，0右1下2左3上 MazePath(S,e,maze,m,n); else if(S.top!=S.base&S.over!=1) switch(e.direc) /回到上一位置并同时改变方向走下一步 case 0: /退回后，列坐标减一，行坐标加一，下一方向向下 e.n-; e.m+; e.direc=1; break; case 1: /退回后，行坐标减一，列坐标减一，下一方向向左 e.m-; e.n-; e.dire

12、c=2; break; case 2: /退回后，列坐标加一，行坐标减一，下一方向向上 e.n+; e.m-; e.direc=3; break; case 3: /无需退回，路径，出栈 Pop(S,e); break; while(S.top!=S.base&S.over!=1); return OK; 时间复杂度为O(m*n)4. 打印路径int PrintPath(Stack S,int mazeMN,int row,int col) if(S.top=S.base) coutn=n; cout此迷宫无解nn; return ERROR; MazeType e; while(S.top!

13、=S.base) Pop(S,e); mazee.me.n=(e.direc+10); coutn=n; cout路径为:endl; int i,j; for(i=1;irow+1;i+) for(j=1;jcol+1;j+) switch(mazeij) case 0: cout; break; case 1: cout; break; case 2: cout; break; case 10: cout; break; case 11: cout; break; case 12: cout; break; case 13: cout; break; coutendl; cout完成!end

14、l; return OK; 5. 主函数int main() switch(i) case 1: Init_hand_Maze(maze,m,n); PrintMaze(maze,m,n); InitStack(S); MazePath(S,start,maze,end.m,end.n); PrintPath(S,maze,m,n); break; case 2: Init_automatic_Maze(maze,m,n); PrintMaze(maze,m,n); InitStack(S); MazePath(S,start,maze,end.m,end.n); PrintPath(S,ma

15、ze,m,n); break; case 3: cycle=(-1);break; default: coutn;cout你的输入有误!n; break; 四、【测试结果（Testing）】(10%)（本部分应包括：对实验的测试结果，应具体列出每次测试所输入的数据以及输出的数据，并对测试结果进行分析总结）手动生成迷宫寻找路径结果正确。自动声称迷宫寻找路径结果正确。四、【实验总结】(10%)（本部分应包括：自己在实验中完成的任务，注意组内的任意一位同学都必须独立完成至少一项接口的实现；对所完成实验的经验总结、心得）1. 本次实验核心算法明晰，思路明确，易于实现。遇到的问题是，迷宫的外围若未设置障

16、碍，用此程序采用的求解迷宫路径的算法无法获得正确结果。2. 本程序的MazePath算法代码不够简洁，但不影响算法实现。3. 本次实验由于时间问题和知识水平有限，还存在一些问题，比如：界面比较单调，整个程序的功能还不完善，还有界面做的有些简单，菜单没有做好，可进行的操作太少，这些都有待进一步改善。4本次实验使我对迷宫游戏的原理有了一定的了解，但做出的结果离真正的迷宫还有很大差距，还需要进一步完善，需要自己课下学习更多的知识。五、【项目运作描述（Operate）】(10%)（本部分应包括：项目的成本效益分析，应用效果等的分析。）本程序可基本实现题目的要求，但仍不够完善。比如对于有多种路径的迷宫只

17、能显示一条路径，当输入的路径超过范围时只能取前几个范围内的数据，而无法将这一消息告诉用户，这些问题还有待解决。六、【代码】(10%)（本部分应包括：完整的代码及充分的注释。 注意纸质的实验报告无需包括此部分。格式统一为，字体: Georgia , 行距: 固定行距12，字号: 小五）#include /库中包含system(pause)和rand()函数#include /c语言里的库#include#include #define OK 1#define ERROR 0#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define OV

18、ERFLOW -1#define M 49#define N 49using namespace std;int mazeMN; typedef int Status;typedef struct int m,n,direc;MazeType,*LMazeType;typedef struct LMazeType top; LMazeType base; int stacksize; int over;Stack; void Init_hand_Maze(int mazeMN,int m,int n) int i,j; for(i=1;i=m+1;i+) for(j=1;j=n+1;j+) m

19、azeij=1; cout请按行输入迷宫，0表示通路，1表示障碍:endl; for(i=1;im+1;i+) for(j=1;jmazeij; for(i=1;im+1;i+) for(j=1;jn+1;j+) if(mazeij!=0&mazeij!=1) cout 您输入有误，请重新输入; Init_hand_Maze(maze,m,n); void Init_automatic_Maze(int mazeMN,int m,int n) /自动生成迷宫int i,j;coutn迷宫生成中nn;system(pause);for(i=1;im+1;i+)for(j=1;jn+1;j+)ma

20、zeij=rand()%2; /随机生成0、1void PrintMaze(int mazeMN,int row,int col) int i,j; cout迷宫如图所示.endl; for(i=1;irow+1;i+) for(j=1;jcol+1;j+) if(mazeij=1) cout; else cout; cout=S.stacksize) S.base=(LMazeType)realloc(S.base,(S.stacksize+STACKINCREMENT) * sizeof(MazeType); if(!S.base)exit(OVERFLOW); S.top=S.base+

21、S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return OK;Status Pop(Stack &S,MazeType &e) if(S.top=S.base)return ERROR; e=*-S.top; return OK;Status MazePath(Stack &S,MazeType &e,int mazeMN,int m,int n) do if(mazee.me.n=0)/0可通，1不可通，2为已走过 Push(S,e); mazee.me.n=2; if(e.m=m&e.n=n) S.over=1;/表示存满一条

22、路径 return OK; else e.n+; e.direc=0;/来这一点时的方向，0右1下2左3上 MazePath(S,e,maze,m,n); else if(S.top!=S.base&S.over!=1) switch(e.direc) /回到上一位置并同时改变方向走下一步 case 0: e.n-; e.m+; e.direc=1; break; case 1: e.m-; e.n-; e.direc=2; break; case 2: e.n+; e.m-; e.direc=3; break; case 3: Pop(S,e); break; while(S.top!=S.

23、base&S.over!=1); return OK; int PrintPath(Stack S,int mazeMN,int row,int col) if(S.top=S.base) coutn=n; cout此迷宫无解nn; return ERROR; MazeType e; while(S.top!=S.base) Pop(S,e); mazee.me.n=(e.direc+10); cout完成!endl; coutn=n; cout路径为:endl; int i,j; for(i=1;irow+1;i+) for(j=1;jcol+1;j+) switch(mazeij) cas

24、e 0: cout; break; case 1: cout; break; case 2: cout; break; case 10: cout; break; case 11: cout; break; case 12: cout; break; case 13: cout; break; coutendl; cout入口endl; cout完成!endl; return OK; int main() int i,m,n,mazeMN,cycle=0; while(cycle!=(-1) cout*n; cout 欢迎进入迷宫求解系统n; coutendl; cout 设计者:冯静懿 20091120080n; cout*n; cout 手动生成迷宫 请按：1n; cout 自动生成迷宫 请按：2n; cout 退出 请按：3nn; cout*n; coutn; couti; switch(i) case 1: coutm; coutn; coutn; while(m49)|(n49) coutn抱歉，你输入的行列数超出预设范围(1-49,1-49),请重新输入：nn; coutm; coutn; coutn; Init_hand_Maze(maze,m,n); PrintMaze(maze,m,n); MazeType start,end; cout请输入起点