迷宫的生成与路由

数据结构课程设计报告撰写要求数据结构课程设计报告撰写要求 （一）纸张与页面要求 1采用国际标准 A4 型打印纸或复印纸，纵向打印。 2封页和页面按照下面模板书写（正文为：小四宋体 1.5 倍行距） 。 3图表及图表标题按照模板中的表示书写。 （二） 课设报告书的内容应包括以下各个部分：（按照以下顺序装订） 1.封页(见课设模版) 2.任务书(学生教师均要签字,信息填写完整) 3.目录 4.正文一般应包括以下内容: （1)题目介绍和功能要求（或描述） 课程设计任务的详细描述(注意不能直接抄任务书),将内容做更详细的具体的分析与描述； （2) 系统功能模块结构图 绘制系统功能结构框图及主要模块的功能说明； （3) 使用的数据结构的描述: 数据结构设计及用法说明; （4) 涉及到的函数的描述 ; （5) 主要算法描述( 程序流程图) （6) 给出程序测试/运行的结果 设计多组数据加以描述（包括输入数据和输出结果） （7) 课程设计的总结及体会 （8) 参考文献 格式要求：1作者，等. 书名.出版地：出版社，出版年 5.附录：程序清单 (应带有必要的注释) 沈阳航空航天大学 课课 程程 设设 计计 报报 告告 课程设计名称：数据结构课程设计数据结构课程设计 课程设计题目： 迷宫的生成与路由 院（系）：计算机学院 专 业： 计算机科学与技术 班 级： 学 号： 姓 名： 指导教师： 沈阳航空航天大学课程设计报告 目目 录录 1 题目介绍和功能要求题目介绍和功能要求.1 1.1 题目介绍 .1 1.2 功能介绍 .1 2 系统功能模块结构图系统功能模块结构图.2 2.1 系统功能结构框图 .2 2.2 系统主要模块的功能说明 .错误！未定义书签。错误！未定义书签。 3 使用的数据结构的描述使用的数据结构的描述.3 3.1 数据结构设计.4 3.2 数据结构用法说明 .4 4 函数的描述函数的描述.5 4.1 主要函数设计 .6 4.2 主要函数流程图 .6 5 程序测试和运行的结果程序测试和运行的结果.11 5.1 程序测试.11 5.2 运行结果.13 参考文献参考文献.10 附附 录（关键部分程序清单）录（关键部分程序清单）.11 沈阳航空航天大学课程设计报告 0 1 题目介绍和功能要求 1.1 题目介绍题目介绍 设计算法生成一个 N*M(N 行 M 列）的迷宫，并完成迷宫的组织和存储。实 现两种不同的迷宫路由算法：广度搜索，深度优先搜索。 要求： 1.N 和 M 是用户可配置的，缺省值为 50 和 50。 2.迷宫的入口和出口分别在第 0 行和第 N-1 行上，随机选择。 3.生成的迷宫要求是连通的。 4.实现图像化界面（选作） 。 1.2 功能要求功能要求 (1)迷宫用二维数组表示； (2)rand()函数随机确定入口和出口，使用真随机数使得每次随机的结果不 同。 (3)入口和出口间的路径是连通的，使用数据结构的并查集来表示连通性。 (4)使用数据结构的两种搜索方式：深度和广度优先搜索来确定入口和出 口间的路径。 沈阳航空航天大学课程设计报告 1 2 系统功能模块结构图 2.1 系统功能结构框图系统功能结构框图 图图 2.12.1 系统功能结构框图系统功能结构框图 2.2 系统主要模块的功能说明系统主要模块的功能说明 1.初始化迷宫模块： Inint（）函数用来初始化迷宫，使用二维数组来表示迷宫，假设迷宫是 用一个个封闭的小格子组成的，每个格子的四周是封闭的。首先随机生成入口和 出口的位置。 2.随机化生成迷宫路径模块： 并查集（数据结构）：(1)并查集可以用来表示元素之间的集合关系，即这些元素是 不是属于哪个集合。通俗理解是，若两个元素是属于统一集合，就将这两个元素并在一起。 (2)存储结构上，用树结构模拟。一开始，每个元素自己构成一个集合，所以自己构成一棵树。 然后，若有两个元素并成一个集合，则将这两个元素所在的树，合并成一棵树。具体实现的 话，就是将一棵树的根看成是另一棵树根的新根。(3)并查集的作用是可以统计并判定两个元 素是否属于统一集合。 初始化迷宫模块 随机化生成迷 宫路径模块 广度优先搜索 模块 深度优先搜索模 块 形象化显示迷宫 模块 开始 结束 沈阳航空航天大学课程设计报告 2 利用并查集实现入口和出口的连通：find()函数和 unite()函数，初始化迷宫的每个 元素都是一个独立的集合，随机化选择一个数组元素，再随机选择一个方向，使 其与相邻的元素放入同一集合。直到入口和出口处于同一个集合。 3.深度优先搜索模块： Bfs()函数利用队列从入口开始找到一条路径抵达出口。 4.深度优先搜索模块： Dfs()函数利用递归从入口开始找到一条路径抵达出口。 5.形象化显示迷宫模块： 迷宫数组中任意相邻的元素如果属于同一集合，则之间是连通的，否则不连 通，并标注出入口和出口的位置。 3 使用的数据结构的描述 3.1 数据结构设计数据结构设计 并查集：并查集可以用来表示元素之间的集合关系，即这些元素是不是属于哪个集合。 通俗理解是，若两个元素是属于统一集合，就将这两个元素并在一起。 存储结构上，用树结构模拟。一开始，每个元素自己构成一个集合，所以自己构成一棵树。 然后，若有两个元素并成一个集合，则将这两个元素所在的树，合并成一棵树。具体实现的 话，就是将一棵树的根看成是另一棵树根的新根。 并查集的作用是可以统计并判定两个元素是否属于统一集合。 广度优先搜索：(1)从队列头取出一个结点，检查它按照扩展规则是否能够扩 沈阳航空航天大学课程设计报告 3 展，如果能则产生一个新节点。 (2)检查新生成的结点，看它是否已在队列中存在，如果新节点已在队列中，就放 弃此节点，然后回到第(1)步。否则，加入队尾。 (3)检查新节点是否为目标结点，如果是则搜索成功，程序结束，如果不是，回到 第(1)步，再从队列头取出结点进行扩展 (4)当需要给出解的路径时，则要保存每个节点的来源，也就是它是从哪个结点扩 展来的。 深度优先搜索：初始化所有顶点均未被访问过，选择初始点后，递归调用以 下步骤： (1)访问搜索到的未被访问的邻接点； (2)将此顶点的 visited 数组元素值置 1； (3)搜索该顶点的违背访问的邻接点，若该邻接点存在，则从此邻接点开始进 行同样的访问和搜索。 3.2 数据结构用法说明数据结构用法说明 并查集：首先将所有的迷宫元素处理成独立的集合，fatheri=i;当选择将 两个元素连通时，即将两个元素处于同一集合下，具体做法是将一棵树的根看成 是另一棵树根的新根。 假设元素 i 的树根是 b,元素 j 的树根是 h,则将 fatherb=h;即将两个 元素放在 了同一集合里，也就是两个元素的树根相同。 广度优先搜索：搜索时用到了队列，广度优先搜索的结果是最优的，也就是 从入口到出口的最短的路径，因为要知道具体的路径，所以需要标记每个入队列 的元素的来源，这样就能从出口返回到入口。 深度优先搜索：搜索时用到了栈，递归操作是深度搜索的关键，标记的添加 与删除是非常重要的。我们需要存储遍历的路径，每当我们深入一层递归时，我 们需要将坐标入栈，每当递归回退时，表示这个位置不合适，我们将出栈，最后， 当我们搜索到出口时，将栈输出即为遍历路径。 沈阳航空航天大学课程设计报告 4 4 函数的描述 4.14.1 主要函数设计主要函数设计 1.inint（）函数： 作用：按照规定尺寸申请二维数组表示迷宫，并将每个数组元素设置为独 立的集合，用并查集表示，规定每个元素与四周相邻的元素是不连通的，用 arry. state表示，当为 1 表示连通，0 时表示不连通。 2.void maze()函数： 作用：随机生成迷宫。构造路径从入口到出口是连通的。按并查集来说就 是将入口和出口以及二者间的路径元素都处于同一个集合，也就是有着相同的树 根。 3.void bfs()函数： 作用：广度优先搜索从入口遍历至出口，并记录具体路径。 4.void dfs（）函数： 作用：深度优先搜索从入口遍历至出口，并记录具体路径。 沈阳航空航天大学课程设计报告 5 5.void finalprint()函数： 作用：按照遍历路径扫描二维数组，形象化表示迷宫。 4.2 主要函数流程图 Inint（）： 图图 4.2.14.2.1 初始化迷宫函数流程初始化迷宫函数流程图图 开始 输入迷宫尺 寸 随机选择入口 和出口 申请二维数组， 并将所有数组 元素设置为独 立的集合 将任意两个相邻的 数组元素设置为不 连通 结束 沈阳航空航天大学课程设计报告 6 VoidVoid mazemaze（）：（）： 否 是 图图 4.2.24.2.2 随机生成连通函数流程图随机生成连通函数流程图 开始 入口和出口 是否连通？ 随机选择一 个数组元素 从上述元素的 四周随机选择 一个方向 将这两个元素连通 起来 结束 沈阳航空航天大学课程设计报告 7 Void bfs()函数： 是 否 图图 4.2.34.2.3 广度优先遍历迷宫函数流程图广度优先遍历迷宫函数流程图 开始 将入口坐标入队 列 取队头元素 将与队头元素相 邻的四个方向的 元素入队列，并 记录父节点坐标 判断是否 是出口？ 结束 沈阳航空航天大学课程设计报告 8 Void dfs（）函数： 是 否 是 否 图图 4.2.44.2.4 深度优先遍历迷宫函数流程图深度优先遍历迷宫函数流程图 开始 以迷宫入口作为递归入 口，并依此为初始点 判断初始点的相邻 四个方向是否都查 看完毕？ 判断此点是 否为出口？ 以此点作为递归 的新入口，并标 记 结束 递归回退，返回 上一个初始点 沈阳航空航天大学课程设计报告 9 5 程序测试和运行的结果 5.1 程序测试程序测试 由用户自行规定迷宫的尺寸由用户自行规定迷宫的尺寸 截图截图 5.1.1：迷宫的初始化：迷宫的初始化 沈阳航空航天大学课程设计报告 10 迷宫的随机形成迷宫的随机形成 截图截图 5.1.2 ：迷宫的形成：迷宫的形成 沈阳航空航天大学课程设计报告 11 5.2 运行结果运行结果 迷宫的广度优先搜索迷宫的广度优先搜索 截图截图 5.2.1：迷宫的广度搜索：迷宫的广度搜索 迷宫的深度优先搜索迷宫的深度优先搜索 图图 5.2.2：迷宫的深度优先搜索：迷宫的深度优先搜索 沈阳航空航天大学课程设计报告 12 输出迷宫输出迷宫 图图 5.2.3：输出迷宫：输出迷宫 参考文献 沈阳航空航天大学课程设计报告 13 1 高富平，张楚 . 电子商务法M. 北京：北京大学出版社，2002 2谭浩强著. C 程序设计（ 第三版）. 北京: 清华大学出版社,2005 3数据结构: C 语言版 /严蔚敏,吴伟明编著.北京:清华大学出版社,2007 沈阳航空航天大学课程设计报告 14 附 录（关键部分程序清单） #include #include #include #include struct node int state4;/0123 表示上下左右四扇门的闭合情况，0 表示关闭，1 表示打开 arry5000; struct stu int x,y; int loc; q10000,stack1000,cun,bor1000; int n,m,en,ex,father5000,front,rear,vis1000010000,der42=0,1,0,-1,- 1,0,1,0,mark10001000,top,xian10001000;/将二维数组转化为一维数组，二 维坐标（a,b),转化为一维坐标 a*m+b;一维坐标 x,转化为二维坐标(x/m,x%m),二维 数组的行和列从 0 开始 int find(int x) if(fatherx=x) return x; else fatherx=find(fatherx); void unite(int hx,int hy) int i,j; i=find(hx); j=find(hy); fatheri=j; void inint() for(int i=0;in;i+) for(int j=0;jm;j+) fatheri*m+j=i*m+j; printf(%d ,fatheri*m+j); 沈阳航空航天大学课程设计报告 15 printf(n); for(int k=0;km*n;k+) arryk.state0=arryk.state1=arryk.state2=arryk.state3=0;/所有的门 都是闭合的 void nprint() int i,j; printf( ); for(i=0;im;i+) if(i10) printf(%d ,i); else printf(%d,i); printf(n); printf( ); for(i=0;im;i+) if(i=en) printf( ); else printf( _); printf(n); for( i=0;in;i+) if(i10) printf(%d ,i); else printf(%d,i); printf(|); for( j=0;jm;j+) if(arryi*m+j.state3=1) printf( ); else printf( |); printf(n); 沈阳航空航天大学课程设计报告 16 printf( ); for(j=0;jm;j+) if(i=n-1 else if(arryi*m+j.state1=1) printf( ); else printf( -); printf(n); void maze()/随机生成迷宫 int row,col,num,nrow,ncol; clock_t start_time ; start_time = clock();/计时函数，数据类型是 clock_t(长整型，毫秒)，在 time.h 文件中 syx while(find(en)!=find(n-1)*m+ex)/入口和出口不连通 row=rand()%n;/随机找出一个房间 col=rand()%m; num=rand()%4; switch(num) case 0:/与上相通 nrow=row-1; if(row=0) continue; else if(find(nrow*m+col)!=find(row*m+col)/判断是否连通， 如果连通，说明曾经操作过，否则，相连通 arryrow*m+col.state0=arrynrow*m+col.state1=1;/将两个相邻方格的相对应的 墙拆掉 unite(nrow*m+col,row*m+col); 沈阳航空航天大学课程设计报告 17 break; case 1:/与下相通 nrow=row+1; if(row=n-1) continue; else if(find(nrow*m+col)!=find(row*m+col) arryrow*m+col.state1=arrynrow*m+col.state0=1; unite(nrow*m+col,row*m+col); break; case 2:/与左相通 ncol=col-1; if(col=0) continue; else if(find(row*m+col)!=find(row*m+ncol) arryrow*m+col.state2=arryrow*m+ncol.state3=1; unite(row*m+col,row*m+ncol); break; case 3:/与右相通 ncol=col+1; if(col=m-1) continue; else if(find(row*m+col)!=find(row*m+ncol) 沈阳航空航天大学课程设计报告 18 arryrow*m+col.state3=arryrow*m+ncol.state2=1; unite(row*m+col,row*m+ncol); break; void bfs()/xy 为入口的坐标 int i,j,k,px,py,hx,hy; while(frontrear) px=qfront.x; py=qfront.y; if(px=n-1 for(i=0;i=0 qrear.y=hy; vishxhy=1; qrear.loc=px*m+py; rear+; if(px=hx qrear.y=hy; vishxhy=1; qrear.loc=px*m+py; rear+; 沈阳航空航天大学课程设计报告 19 if(hy=py qrear.y=hy; vishxhy=1; qrear.loc=px*m+py; rear+; if(hy=py qrear.y=hy; vishxhy=1; qrear.loc=px*m+py; rear+; front+; void initmaze() int i,j,k; printf( ); for(i=0;im;i+) if(i10) printf(%d ,i); else printf(%d,i); printf(n); printf( ); for(i=0;im;i+) printf( _); 沈阳航空航天大学课程设计报告 20 printf(n); for( i=0;in;i+) if(i10) printf(%d ,i); else printf(%d,i); printf(|); for( j=0;jm;j+) printf( |); printf(n); printf( ); for(j=0;j=0;t-) printf(%d %d)n,stackt.x,stackt.y); 沈阳航空航天大学课程设计报告 21 void dfs(int px,int py) int i,j,k,hx,hy; cuntop.x=px; cuntop.y=py; top+; if(px=n-1itop;i+) bori.x=cuni.x; bori.y=cuni.y; bori.x=-1; return ; for(i=0;i=0 dfs(hx,hy); markhxhy=0; top-; if(px=hx dfs(hx,hy); markhxhy=0; top-; if(hy=py 沈阳航空航天大学课程设计报告 22 dfs(hx,hy); markhxhy=0; top-; if(hy=py dfs(hx,hy); markhxhy=0; top-; markpxpy=0; void finalprint() int i,j; printf( ); for(i=0;im;i+) if(i10) printf(%d ,i); else printf(%d,i); printf(n); printf( ); for(i=0;im;i+) if(i=en) printf( ); else printf( _); printf(n); for( i=0;in;i+) if(i10) printf(%d ,i); else 沈阳航空航天大学课程设计报告 23 printf(%d,i); printf(|); for( j=0;jm;j+) if(arryi*m+j.state3=1) if(xianij=1) printf(* ); else printf( ); else if(xianij=1) printf(*|); else printf( |); printf(n); printf( ); for(j=0;jm;j+) if(i=n-1 else if(arryi*m+j.state1=1) printf( ); else printf( -); printf(n); int main() int j,i; char ch; srand(int)time(NULL);/srand 初始化随机种子,rand 产生随机数 time(0) clock_t start_time ; start_time = clock();/计时函数，数据类型是 clock_t(长整型，毫秒)，在 time.h 沈阳航空航天大学课程设计报告 24 文件中 syx printf(是否输入迷宫的尺寸:输入请选择 A 否则输入 B,默认值为 50 50n); scanf(%c, if(ch=A) printf(请输入迷宫的尺寸n); scanf(%d%d, if(ch=B) n=50; m=50; inint(); initmaze(); en=rand()%m; ex=rand()%m; arryen.state0=1; arry(n-1)*m+ex.state1=1;/入口和出口的相对应的门被打开 printf(随机选择的入口和出口坐标为:n); p