数据结构-迷宫实验报告

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

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

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

4、序模块、各子程序模块的伪码 说明，主程序模块与各子程序模块间的调用关系)1. 设定迷宫的抽象数据类型定义：ADT Maze 数据对象：D = ai, j | ai,j 、0 j col+1, row, colf、J 18 、厂 , 0 i row+1,数据关系： 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 已存在。操作

5、结果：手动初始化迷宫， 0 表示通路， 1表示障碍。Init_automatic_Maze( Maze, row, col) 初始条件：二维数组 Maze 已存在操作结果：自动初始化迷宫， 0 表示通路， 1 表示障碍。 PrintMaze( Maze)初始条件：迷宫 Maze 已存在。 操作结果：将迷宫输出到屏幕， “表”示通路， “表”示障碍。MazePath( Maze) 初始条件：迷宫 Maze 已存在。 操作结果：计算路径。PrintPath( Maze) 初始条件：迷宫 Maze 已存在。操作结果：若迷宫存在一条通路，将路径输出至屏幕，以“-”“J”“T表示可行路径， “”表示途径

6、过却无法到达出口的位置； 若不 存在通路，报告相应信息。 ADT Maze ；2. 设定栈的抽象数据类型定义：ADT Stack 数据对象：D = ai | ai CharSet, i=1,2,，n, n 0 数据关系：R1 = | ai-i, ai D, i=2,，n基本操作：InitStack(&S) 操作结果：构造一个空栈。Push(&S, e) 初始条件：栈 S 已存在。 操作结果：在栈 S 的栈顶插入新的栈顶元素 e。Pop(&S, &e) 初始条件：栈 S 已存在 . 操作结果：删除 S 的栈顶元素，并以 e 返回其值。 ADT Stack ；3. 本程序包含三个模块1)主程序模块

7、：void main()初始化 ;do 接受命令 ;处理命令; while （命令!=退出）；2）栈模块一一实现栈抽象数据类型；3）迷宫模块一一实现迷宫抽象数据类型4各模块之间的调用关系如下:主程序模块 迷宫模块 栈模块、【实现描述（Implement）】 （30%）（本部分应包括：抽象数据类型具体实现的函数原型说明、法、函数设计、函数间的调用关系，关键的程序流程图等,关键操作实现的伪码算给出关键算法的时间复杂度分析。）1.迷宫与栈类型int mazeMN, row, col; typedef structint m,n ,direc;MazeType,*LMazeType; typedef

8、structLMazeType top;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(

9、j=1;jn+1;j+)if(mazeij!=0&mazeij!=1) cout 您输入有误，请重新输入 Init_hand_Maze(maze,m,n);/自动生成迷宫/随机生成0、 1时间复杂度为 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(

10、MazeType);if(!S.base)exit(OVERFLOW);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) doif (mazee.me.n=0)/0

11、可通， 1 不可通， 2 为已走过Push(S,e);mazee.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);elseif (S.top!=S.base&S.over!=1)switch (e.direc) / 回到上一位置并同时改变方向走下一步下一方向向下case 0:/退回后，列坐标减一，行坐标加一，e.n-;e.m+;e.direc=1;break ;case 1: / 退回后，行坐标减一

12、，列坐标减一，下一方向向左 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.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 ER

13、ROR;MazeType e;while(S.top!=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 T： break;Case 11:cout J； break;case 12:cout Q： break；case 13:cout T; break；c

14、outendl;cout 完成 !endl;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(

15、S,maze,m,n);break;case 3:cycle=(-1);break;default:coutn;cout 你的输入有误 !n; break;四、【测试结果（Testi ng）】（10%）（本部分应包括：对实验的测试结果， 应具体列出每次测试所输入的数据以及输出的数据，并对测试结果进行分析总结）C:Documents and Settings Adm in is trator面迷宫程序2.exe欢迎逬入迷宫求解系统设计者=再静懿200J1120080请请请请选择你的操作:1晴输入行数：3ig輸入列数：3请檢行输入迷宫，D表示通路，久表示障碍:B 1 10 0 11 9 S迷宫如图

16、所示.1寻找路径 完成y为- .任 径f J 口成按 路T入完请手动生成迷宫寻找路径结果正确自动声称迷宫寻找路径结果正确。四、【实验总结】 (10%)(本部分应包括：自己在实验中完成的任务， 注意组内的任意一位同学都必须独立完 成至少一项接口的实现 ；对所完成实验的经验总结、心得)1. 本次实验核心算法明晰，思路明确，易于实现。遇到的问题是，迷宫的外围 若未设置障碍，用此程序采用的求解迷宫路径的算法无法获得正确结果。2. 本程序的 MazePath 算法代码不够简洁，但不影响算法实现。3. 本次实验由于时间问题和知识水平有限，还存在一些问题，比如：界面比较 单调，整个程序的功能还不完善，还有界

17、面做的有些简单，菜单没有做好，可进行的 操作太少，这些都有待进一步改善。4本次实验使我对迷宫游戏的原理有了一定的了解，但做出的结果离真正的迷 宫还有很大差距，还需要进一步完善，需要自己课下学习更多的知识。五、【项目运作描述( Operate)】(10%)本部分应包括：项目的成本效益分析，应用效果等的分析。 ) 本程序可基本实现题目的要求， 但仍不够完善。 比如对于有多种路径的迷宫只能显示 一条路径， 当输入的路径超过范围时只能取前几个范围内的数据， 而无法将这一消息 告诉用户，这些问题还有待解决。六、【代码】 (10%)(本部分应包括：完整的代码及充分的注释。 注意纸质的实验报告无需包括此部分

18、行距: 固定行距 12，字号 : 小五)/ 库中包含 system(pause) 和 rand() 函数 /c 语言里的库格式统一为，字体 : Georgia , #include#include #include #include #define OK 1#define ERROR 0#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define OVERFLOW -1#define M 49#define N 49 using namespace std; int mazeMN;typedef int Status;typedef s

19、tructint m,n,direc;MazeType,*LMazeType;typedef structLMazeType 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+)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

20、;j+)if(mazeij!=0&mazeij!=1) cout 您输入有误，请重新输入 ;Init_hand_Maze(maze,m,n);/ 自动生成迷宫/ 随机生成 0、 1void Init_automatic_Maze(int mazeMN,int m,int n)int i,j;coutvn 迷宫生成中nn;system(pause);for(i=1;ivm+1;i+)for(j=1;jvn+1;j+)mazeij=rand()%2;void PrintMaze(int mazeMN,int row,int col) int i,j;coutvv 迷宫如图所示 .vvendl;fo

21、r(i=1;ivrow+1;i+)for(j=1;jcol+1;j+)if(mazeij=1)cout ;elsecout ;cout=S.stacksize)S.base=(LMazeType)realloc(S.base,(S.stacksize+STACKINCREMENT) * sizeof(MazeType); if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;Status Pop(Stack &S,MazeType &e)if(S.to

22、p=S.base)return ERROR;e=*-S.top;return OK;Status MazePath(Stack &S,MazeType &e,int mazeMN,int m,int n)doif(mazee.me.n=0)/0可通， 1 不可通， 2 为已走过 Push(S,e); mazee.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);elseif(S.top!=S.bas

23、e&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.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;r

24、eturn ERROR;MazeType e;while(S.top!=S.base)Pop(S,e); mazee.me.n=(e.direc+10);cout 完成 !endl; coutn=n; cout 路径为 :endl;coutvvI*coutvv手动生成迷宫请按：1n；coutvv自动生成迷宫请按：2n；coutvv退出请按：3nn*n；*n；coutvvint 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: 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 请输入起点 m