《迷宫设计实验报告》由会员分享，可在线阅读，更多相关《迷宫设计实验报告（32页珍藏版）》请在金锄头文库上搜索。
1、 .天津商业大学数据结构课程设计报告题 目：迷宫问题学 院：信息工程学院专 业：计算机科学与技术班 级：13-01班姓 名：王同组人员：谭 陈指导教师：黄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. 课程设计的内容【问题描述】以一个mn的长方阵表示迷宫，0和1表示迷宫中的通路和
2、障碍。设计一个程序，对任意设定的迷宫，求出一条入口到出口的通路，或得出没有通路的结论。【基本要求】首先实现一个栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出，其中：(i,j)指示迷宫中的一个坐标，d表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为：(1,1,1)，（1,2,2）,（2,2,2）（3,2,3），（3,1,2）2. 需求分析(1)以二维数组mazeM+2N+2表示迷宫，其中mazei0和mazeiN+1(0=i=N+1)以及maze0j和mazeM+1j(0=j=0数据关系：R1 | a(i-1),aiD,i = 2,3n基本操
3、作： InitStack(&S) 操作结果：构造一个空栈S。DestroyStack(&S) 初始结果：栈S已存在。 操作结果：销毁栈S。ClearStack(&S) 初始结果：栈S已存在。 操作结果：将S清为空栈。StackLength(S) 初始结果：栈S已存在。 操作结果：返回栈S的长度StackEmpty(S) 初始条件：栈S已存在。 操作结果：若S为空栈，则返回TRUE，否则返回FALSEGetTop(S,&e) 初始条件：栈S已存在。 操作结果：若栈S不空，则以e返回栈顶元素e。Push(&S,e) 初始条件：栈S已存在。 操作结果：在栈S的栈顶插入新的栈顶元素。Pop(&S,&e
4、) 初始条件：栈S已存在。 操作结果：删除S的栈顶元素，并以e返回其值。StackTraverse(S,visit() 初始条件：栈S已存在。 操作结果：从栈底到栈顶依次对S中的每个元素调用visit()ADT Stack(2) 设定迷宫的抽象数据类型为：ADT maze 数据对象：D = a(i,j) | a(i,j)0,1，0=i=m+1,0=j=n+1,m,n=10 数据关系：R = M，N M = |a(i-1,j)，a(i,j)D,i=1,2,m+1,j=0,1,n+1 N = | a(i,j-1),a(i,j)D,I = 0,1,m+1,j = 1,2,n+1 基本操作： Init
5、Maze(&M,maze,m,n) 初始条件：二维数组mazem+1n+1 已存在，其中自第一行至第m+1行、每行中自第一列至第n+1列的元素已有值，并且以值0表示通路，以值1表示障碍。 操作结果：构成迷宫的字符型数组，以字符0表示通路，以字符1障碍，并在迷宫四周加上一圈障碍。 MazePath(&M)初始条件：迷宫M已被赋值。 操作结果：若迷宫M中存在一条通路，则按如下规定改变迷宫M的状态：以数字0代表可通过，数字1代表不可通过。 3.1 模块划分(1) 主程序模块： void main() int stoMN; struct mark start,end; /start,end入口和出口的
6、坐标 int add42=0,1,1,0,0,-1,-1,0;/行增量和列增量 方向依次为东西南北 initmaze(sto);/建立迷宫 printf(输入入口的横坐标,纵坐标逗号隔开n); scanf(%d,%d,&start.x,&start.y); printf(输入出口的横坐标,纵坐标逗号隔开n); scanf(%d,%d,&end.x,&end.y); MazePath(start,end,sto,add); /find path system(PAUSE); (2) 栈模块实现栈抽象数据类型；(3) 迷宫模块实现迷宫抽象数据类型，建立迷宫，求解迷宫的一条路径。4. 详细设计4.1
7、 数据类型的定义(1) 坐标位置，类型：struct mark /定义迷宫内点的坐标类型 int x; int y; ;(2) 迷宫类型void initmaze(int mazeMN) /按照用户输入的M行和N列的二维数组（元素值为0或1）/设置迷宫maze的初值，包括加上边缘一圈的值void MazePath(struct mark start,struct mark end,int mazeMN,int diradd42)/求解迷宫maze中从入口Start到出口end的一条路径/若存在，则返回TRUE，否则返回FALSE(3) 栈类型struct Element int x,y; /x
8、行,y列 int d; /d下一步的方向 ; typedef struct LStack /链栈 Element elem; struct LStack *next; *PLStack;4.2 主要模块的算法描述(1) 求迷宫路径的伪码算法void MazePath(struct mark start,struct mark end,int mazeMN,int diradd42) int i,j,d;int a,b; Element elem,e; PLStack S1, S2; InitStack(S1); InitStack(S2); mazestart.xstart.y=2; /入口点
9、作上标记 elem.x=start.x; elem.y=start.y; elem.d=-1; /开始为-1 Push(S1,elem); while(!StackEmpty(S1) /栈不为空 有路径可走 Pop(S1,elem); i=elem.x; j=elem.y; d=elem.d+1; /下一个方向 while(d(%d,%d,%d),e.x,e.y,e.d); return; /跳出两层循环，本来用break,但发现出错，exit又会结束程序，选用return还是不错滴o(_)o. if(mazeab=0) /找到可以前进的非出口的点 mazeab=2; /标记走过此点 elem
10、.x=i; elem.y=j; elem.d=d; Push(S1,elem); /当前位置入栈 i=a; /下一点转化为当前点 j=b; d=-1; d+; printf(没有找到可以走出此迷宫的路径n); (2) 建立迷宫的伪码算法void initmaze(int mazeMN) int i,j; int m,n; /迷宫行,列 printf(请输入迷宫的行数 m=); scanf(%d,&m); printf(请输入迷宫的列数 n=); scanf(%d,&n); printf(n请输入迷宫的各行各列:n用空格隔开,0代表路,1代表墙n,m,n); for(i=1;i=m;i+) fo
11、r(j=1;j=n;j+)mazeij = (int) (rand() % 2); /scanf(%d,&mazeij); printf(你建立的迷宫为o(_)o.n); for(i=0;i=m+1;i+) /加一圈围墙 mazei0=1; mazein+1=1; for(j=0;j=n+1;j+) maze0j=1; mazem+1j=1; for(i=0;i=m+1;i+) /输出迷宫 for(j=0;j=n+1;j+) printf(%d ,mazeij); printf(n); (3) 主函数的伪码算法：void main() int stoMN; struct mark start,end; /start,end入口和出口的坐标 int add42
