当前位置:文档之家› 数据结构-迷宫实验报告

数据结构-迷宫实验报告

云南大学软件学院数据结构实验报告(本实验项目方案受“教育部人才培养模式创新实验区(X3108005)”项目资助)实验难度: A □ B □ C □实验难度 A □ B □ C □承担任务(难度为C时填写)指导教师评分(签名)【实验题目】实验4.数组的表示极其应用【问题描述】以一个m×n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。

设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。

【基本要求】首先实现一个以链表作存储结构的栈类型,然后编写一个求解迷宫的非递归程序。

求得的通路以三元组(i,j,d)的形式输出,其中:(i,j)指示迷宫中的一个坐标,d 表示走到下一坐标的方向。

如;对于下列数据的迷宫,输出的一条通路为:(l,1,1),(1,2,2),(2,2,2),(3,2,3),(3,1,2),…。

•(下面的内容由学生填写,格式统一为,字体: 楷体, 行距: 固定行距18,字号: 小四,个人报告按下面每一项的百分比打分。

难度A满分70分,难度B满分90分)一、【实验构思(Conceive)】(10%)(本部分应包括:描述实验实现的基本思路,包括所用到的离散数学、工程数学、程序设计、算法等相关知识)本实验的目的是设计一个程序,实现手动或者自动生成一个n×m矩阵的迷宫,寻找一条从入口点到出口点的通路。

我们将其简化成具体实验内容如下:选择手动或者自动生成一个n×m的迷宫,将迷宫的左上角作入口,右下角作出口,设“0”为通路,“1”为墙,即无法穿越。

假设从起点出发,目的为右下角终点,可向“上、下、左、右、左上、左下、右上、右下”8个方向行走。

如果迷宫可以走通,则用“■”代表“1”,用“□”代表“0”,用“→”代表行走迷宫的路径。

输出迷宫原型图、迷宫路线图以及迷宫行走路径。

如果迷宫为死迷宫,输出信息。

可以二维数组存储迷宫数据,用户指定入口下标和出口下标。

为处理方便起见,可在迷宫的四周加一圈障碍。

对于迷宫中任一位置,均可约定有东、南、西、北四个方向可通。

•二、【实验设计(Design)】(20%)(本部分应包括:抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明,主程序模块与各子程序模块间的调用关系)1. 设定迷宫的抽象数据类型定义:ADT Maze {数据对象:D = { ai, j | ai, j∈ { ‘■’、‘□’、‘※’、‘→’、‘←’、‘↑’、‘↓’ } , 0≤ i≤row+1, 0≤j≤col+1, row,col≤18 }数据关系:R = { ROW, COL }ROW = { < ai-1, j , ai, j> | ai-1, j, ai, j∈D, i=1, … , row+1, j=0, … ,col+1}COL = { < ai, j-1, ai, j> | ai, j-1, ai, j∈D, i=0, … , row+1, j=1, … ,col+1}基本操作:Init_hand_Maze( Maze, row, col)初始条件:二维数组Maze[][]已存在。

操作结果:手动初始化迷宫,0表示通路,1表示障碍。

Init_automatic_Maze( Maze, row, col)初始条件:二维数组Maze[][]已存在。

操作结果:自动初始化迷宫,0表示通路,1表示障碍。

PrintMaze( Maze)初始条件:迷宫Maze已存在。

操作结果:将迷宫输出到屏幕,“□”表示通路,“■”表示障碍。

MazePath( Maze)初始条件:迷宫Maze已存在。

操作结果:计算路径。

PrintPath( Maze)初始条件:迷宫Maze已存在。

操作结果:若迷宫存在一条通路,将路径输出至屏幕,以“→”“←”“↑”“↓”表示可行路径,“※”表示途径过却无法到达出口的位置;若不存在通路,报告相应信息。

} ADT Maze;2. 设定栈的抽象数据类型定义:ADT Stack {数据对象:D = { ai | ai∈ CharSet, i=1, 2, … , n, n≥0 }数据关系:R1 = { < ai-1, ai> | 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 (命令! = 退出);}2)栈模块——实现栈抽象数据类型;3)迷宫模块——实现迷宫抽象数据类型。

4各模块之间的调用关系如下:主程序模块栈模块三、【实现描述(Implement)】(30%)(本部分应包括:抽象数据类型具体实现的函数原型说明、关键操作实现的伪码算法、函数设计、函数间的调用关系,关键的程序流程图等,给出关键算法的时间复杂度分析。

)1. 迷宫与栈类型int maze[M][N], row, col ;typedef struct 栈操作函数void Init_hand_Maze(int maze[M][N],int m,int n){int i,j;for(i=1;i<=m+1;i++)for(j=1;j<=n+1;j++){maze[i][j]=1;}cout<<"请按行输入迷宫,0表示通路,1表示障碍:"<<endl;for(i=1;i<m+1;i++)for(j=1;j<n+1;j++)cin>>maze[i][j];for(i=1;i<m+1;i++){for(j=1;j<n+1;j++){if(maze[i][j]!=0&&maze[i][j]!=1){cout<<" 您输入有误,请重新输入";Init_hand_Maze(maze,m,n);}}}}时间复杂度为O(m*n)void Init_automatic_Maze(int maze[M][N],int m,int n) 求解迷宫Status MazePath(Stack &S, MazeType &e, int maze[M][N], int m, int n){do{if(maze[][]==0)打印路径int PrintPath(Stack S,int maze[M][N],int row,int col){if=={cout<<"\n===============================================\n";cout<<"此迷宫无解\n\n";return ERROR;}MazeType e;while!={Pop(S,e);maze[][]=+10);}cout<<"\n===============================================\n";cout<<"路径为:"<<endl;int i,j;for(i=1;i<row+1;i++){for(j=1;j<col+1;j++){switch(maze[i][j]){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;}}cout<<endl;}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,,;PrintPath(S,maze,m,n);break;case 2:Init_automatic_Maze(maze,m,n);PrintMaze(maze,m,n);InitStack(S);MazePath(S,start,maze,,;PrintPath(S,maze,m,n);break;case 3:cycle=(-1);break;default:cout<<"\n";cout<<"你的输入有误!\n";break;}}}四、【测试结果(Testing)】(10%)(本部分应包括:对实验的测试结果,应具体列出每次测试所输入的数据以及输出的数据,并对测试结果进行分析总结)手动生成迷宫寻找路径结果正确。

自动声称迷宫寻找路径结果正确。

四、【实验总结】(10%)(本部分应包括:自己在实验中完成的任务,注意组内的任意一位同学都必须独立完成至少一项接口的实现;对所完成实验的经验总结、心得)1. 本次实验核心算法明晰,思路明确,易于实现。

遇到的问题是,迷宫的外围若未设置障碍,用此程序采用的求解迷宫路径的算法无法获得正确结果。

2. 本程序的MazePath算法代码不够简洁,但不影响算法实现。

3. 本次实验由于时间问题和知识水平有限,还存在一些问题,比如:界面比较单调,整个程序的功能还不完善,还有界面做的有些简单,菜单没有做好,可进行的操作太少,这些都有待进一步改善。

4.本次实验使我对迷宫游戏的原理有了一定的了解,但做出的结果离真正的迷宫还有很大差距,还需要进一步完善,需要自己课下学习更多的知识。

五、【项目运作描述(Operate)】(10%)(本部分应包括:项目的成本效益分析,应用效果等的分析。

)本程序可基本实现题目的要求,但仍不够完善。

比如对于有多种路径的迷宫只能显示一条路径,当输入的路径超过范围时只能取前几个范围内的数据,而无法将这一消息告诉用户,这些问题还有待解决。

相关主题