迷宫设计实验报告.doc

《迷宫设计实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、.天津商业大学《数据结构》课程设计报告题目：迷宫问题学院：信息工程学院专业：计算机科学与技术班级：13-01班姓名：王Word资料.同组人员：谭陈指导教师：黄2014年12月26日Word资料.目录1.课程设计的内容12.需求分析13.概要设计13.1抽象数据类型定义13.2模块划分14.详细设计14.1数据类型的定义14.2主要模块的算法描述14.3函数之间的调用关系25.程序运行说明与测试25.1用户手册25.2测试结果及分析26.课程设计总结2附录（源程序清单）2Word资料.1.课程设计的内容【问题描述】以一个m×n的长方阵表示迷宫，0

2、和1表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条入口到出口的通路，或得出没有通路的结论。【基本要求】首先实现一个栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出，其中：(i,j)指示迷宫中的一个坐标，d表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为：(1,1,1)，（1,2,2）,（2,2,2）（3,2,3），（3,1,2）……2.需求分析(1)以二维数组maze[M+2][N+2]表示迷宫，其中maze[i][0]和maze[i][N+1](0=

3、ze[0][j]和maze[M+1][j](0=

4、ai∈CharSet，i=1,2，…,n，n>=0}数据关系：R1{

5、a(i-1),ai∈D,i=2,3…n}基

6、本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始结果：栈S已存在。操作结果：销毁栈S。ClearStack(&S)初始结果：栈S已存在。操作结果：将S清为空栈。StackLength(S)初始结果：栈S已存在。操作结果：返回栈S的长度StackEmpty(S)初始条件：栈S已存在。Word资料.操作结果：若S为空栈，则返回TRUE，否则返回FALSEGetTop(S,&e)初始条件：栈S已存在。操作结果：若栈S不空，则以e返回栈顶元素e。Push(&S,e)初始条件：栈S已存在。操作结果：在栈S的

7、栈顶插入新的栈顶元素。Pop(&S,&e)初始条件：栈S已存在。操作结果：删除S的栈顶元素，并以e返回其值。StackTraverse(S,visit())初始条件：栈S已存在。操作结果：从栈底到栈顶依次对S中的每个元素调用visit()}ADTStack(2)设定迷宫的抽象数据类型为：ADTmaze{数据对象：D={a(i,j)

8、a(i,j)∈{0,1}，0=

9、a(i-1,j)，a(i,j)∈Word资料.D,i=1,2,…,m

10、+1,j=0,1,…n+1}N={

11、a(i,j-1),a(i,j)∈D,I=0,1,…m+1,j=1,2,…n+1}基本操作：InitMaze(&M,maze,m,n)初始条件：二维数组maze[m+1][n+1]已存在，其中自第一行至第m+1行、每行中自第一列至第n+1列的元素已有值，并且以值0表示通路，以值1表示障碍。操作结果：构成迷宫的字符型数组，以字符0表示通路，以字符1障碍，并在迷宫四周加上一圈障碍。MazePath(&M)初始条件：迷宫M已被赋值。操作结果：若迷宫M中存在一条通路，则按如下规定改变迷

12、宫M的状态：以数字0代表可通过，数字1代表不可通过。　　3.1模块划分(1)主程序模块：voidmain(){intsto[M][N];Word资料.structmarkstart,end;//start,end入口和出口的坐标intadd[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//行增量和列增量方向依次为东西南北initmaze(sto);//建立迷宫printf("输入入口的横坐标,纵坐标[逗号隔开]");scanf("%d,%d",&start.x,&start.y);printf("输入出口的横坐标,纵

13、坐标[逗号隔开]");scanf("%d,%d",&end.x,&end.y);MazePath(start,end,sto,add);//fin