我叫邢依姗
范文一：设计迷宫
设计迷宫》是一节设计. 应用课。
1、 尝试用各种工具材料，通过看看、想想、画画等方法进行设计制作，体验了设计迷宫活
动的乐趣，形成设计意识。
2、 教师采用游戏导入，充分激发学生的学习兴趣，运用多媒体演示对学生进行从认识迷宫
到分析迷宫再到设计迷宫的指导，在构思主题时，教师放手让学生构思创作，注重学生自我经验的构建。
3、 在整个指导过程中，谈话法、演示法占主导地位。演示采用多媒体演示与教师手绘演示
同时存在，让学生清楚地了解设计步骤与方法。技法介绍时，“双线笔”的介绍与运用成了一个技法亮点，学生乐于体验，把自己的想法融入其中，可见老师经验丰富。
4、运用大量的图片资料，充分开拓学生视野，让学生了解迷宫的产生、由来，了解迷宫的文化和历史以及造型特点，让美术课堂从单纯的技能与知识学习到文化层面的学习。
5、学习的学习方式建立在自主性、探究性和合作性基础之上，设计迷宫不是单纯的吸收课本上现成的结论，而是在老师的指导下，学生亲自参与丰富的思维活动，通过发现问题、认识问题、分析问题、解决问题的认识规律，引导学生自主获取知识与技能，在探究式的学习中清楚地了解迷宫认识并掌握其特点，验证探究的结果，尝试设计迷宫的方法与步骤。
6、培养了学生的观察能力。如：认识迷宫的特点时，准备大量图片让学生欣赏观察，并进行比较找到迷宫的共同特征，培养和提高了学生的观察能力。
7、开发与挖掘学生的创造思维。在创作选择主题时，准备一些图片，让学生充分的想象主题故事情境，开发学生的思维。包括在路线设置上，在障碍物、环境背景的设计上，引导学生开发思维，大胆创造和想象，体现了学生的自主性与自由性。
《设计迷宫》
是一节轻松、愉悦、自主、探究、体验、和谐的课堂。
是一节学的有趣、有用的课堂。
是一节注重自由性和注重功能性的课堂。
充分的体现了新课程的理念，恰当地体现了设计. 应用课的特色。
范文二：迷宫设计
目录
第一节 课程设计的题目及目的 ........................... 1
第二节 课程设计内容和要求 ............................ 1
2.1设计内容 ........................................... 1
2.2设计要求 ........................................... 2
第三节 课程设计方案及分析 ............................ 2
3.1问题分析 ........................................... 2
3.1.1 迷宫的建立 ..................................... 2
3.1.2 迷宫的存储 ..................................... 2
3.1.3 迷宫路径的搜索 .................................. 3
3.1.4 流程图 ......................................... 3
3.2 概要设计 ........................................... 5
3.3 详细设计 ........................................... 5
第四节 源程序 .......................................... 6
第五节 测试结果 ........................................ 10
5.1 错误输入 .......................................... 10
5.2正确路径 .......................................... 10
第六节 课程设计总结 ................................. 11
第七节 参考文献 ........................................ 11
第一节 课程设计的题目及目的
这次课程设计，我们的题目是迷宫求解。迷宫求解是数据结构中的经典问题，我期望达到的目的有四个：
1) 巩固书本知识，对书上的知识能更透彻地了解。
通过自己设计程序积累调试数据结构的经验，培养我们的编程能力。巩
固我们所学的数据结构知识，消化课堂所讲解的内容。也是对所学知识的
一次整理，将原本在我们脑中比较混乱的课程设计重新梳理。
2) 通过课程设计能够更好的掌握迷宫求解中的设计思路为以后灵活运用奠定
基础。
3) 能够独立的完成简单程序的设计以及完成一份较为满意的程序设计报告
第二节 课程设计内容和要求 2.1设计内容
迷宫问题是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无
顶大盒子的门放入，在盒子中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口走到出口，而不走错一步。老鼠经过多次试验最终学会走通迷宫的路线。设计一个计算机程序对任意设定的矩形迷宫, 求出一条从入口到出口的通路，或得出没有通路的结果。
2.2设计要求
（1） 建立一个大小为m×m的任意迷宫（迷宫数据可由用户输入或由程序自动生
成），并在屏幕上显示出来
（2） 在屏幕上输出迷宫和通路
第三节 课程设计方案及分析
3.1问题分析
3.1.1 迷宫的建立
迷宫中存在通路和障碍，为了方便迷宫的创建，可用0表示通路，用1表示障碍，#表示墙壁，这样迷宫就可以用0、1矩阵来描述，
3.1.2 迷宫的存储
迷宫是一个矩形区域，可以使用二维数组表示迷宫，这样迷宫的每一个位置都可 以用其行列号来唯一指定，但是二维数组不能动态定义其大小，我们可以考虑先 定义一个较大的二维数组maze[M+2][M+2],然后用它的前m 行m 列来存放元素，即可得到一个m×m的二维数组，这样(0,0)表示迷宫入口位置，(m-1,m-1)表示迷宫出口位置。
3.1.3 迷宫路径的搜索
首先从迷宫的入口开始，如果该位置就是迷宫出口，则已经找到了一条路径，搜 索工作结束。否则搜索其上、下、左、右位置是否是障碍，若不是障碍，就移动到该位置，然后再从该位置开始搜索通往出口的路径；若是障碍就选择另一个相邻的位置，并从它开始搜索路径。为防止搜索重复出现，则将已搜索过的位置用函数进行判断和标记，同时保留搜索痕迹，在考虑进入下一个位置搜索之前，将当前位置保存在一个队列中，如果所有相邻的非障碍位置均被搜索过，且未找到通往出口的路径，则表明不存在从入口到出口的路径。这实现的是广度优先遍历的算法如果找到路径，则最短路径。
3.1.4 流程图
3.2 概要设计
1. ①构建一个二维数组maze[M+2][M+2]用于存储迷宫矩阵
②自动或手动生成迷宫，即为二维数组maze[M+2][M+2]赋值
③构建一个队列用于存储迷宫路径
④建立迷宫节点, 用于存储迷宫中每个节点的访问情况
⑤实现搜索算法
⑥屏幕上显示操作菜单
2.本程序包含12个函数：
(1)主函数 main()
(2)Status InitStack(); //创建一个空栈S
(3)Status Push(); //插入新元素a
(4)Status Pop();//删除栈顶元素，a 返回其值
(5)Status StackEmpty();//检查是否空栈
(6)Status MazePath(); //找通路
(7)void Initmaze(); //初始化迷宫
(8)void printmaze(); //显示迷宫
(9)Status Pass();/判断当前位置是否可通
(10)void Markfoot(); //标记当前位置不可通
(11)PosType NextPos(); //进入下一位置
(12)void printpath(); //显示通路
3.3 详细设计
程序设计的基本思想，原理和算法描述：
此算法最大的优点是支持图形化输入与输出，观察效果好
迷宫求解问题主要运用了堆栈的性质
第四节 源程序
#define M2 12 /*M2*N2为实际使用迷宫数组的大小*/
#define N2 11
#define MAXLEN M2 /*栈的长度*/
#define True 1
#define False 0
# include “stdio.h”
#include int M=M2-2, N=N2-2; /*M*N为迷宫的大小*/ typedef struct /*定义栈元素的类型*/ { int x,y,dir; }elemtype; typedef struct /* 定义顺序栈*/ {elemtype stack[MAXLEN]; int top; }sqstktp; struct moved /*定义方向位移数组的元素类型对于存储坐标增量的方向位移数组move*/ { int dx,dy; }; void inimaze(int maze[][N2]) /*初始化迷宫*/ { int i,j,num; for(i=1;i<> {for(j=1;j<> {num=(800*(i+j)+1500) %327; /*根据M 和N 值产生迷宫*/ if((num<150)&&(i!=m ||="" j!=""> maze[i][j]=1; else maze[i][j]=0; printf(“%3d”, maze[i][j]); /*显示迷宫*/ } printf(“\n”); } printf(“\n”); for(i=0,j=0;i<=m+1;i++)> maze[i][j]=1; for(i=0,j=N+1;i<> maze[i][j]=1; for(i=0,j=0;j<> maze[i][j]=1; for(i=M+1,j=0;j<> maze[i][j]=1; } /*inimaze*/ void inimove(struct moved move[]) /*初始化方向位移数组*/ { /* 依次为东E ，东南SE ，南S ，西南SW ，西W ，西北NW ，北N ，东北NE*/. move[0].dx=0; move[0].dy=1; move[1].dx=1; move[1].dy=1; move[2].dx=1; move[2].dy=0; move[3].dx=1; move[3].dy=-1; move[4].dx=0; move[4].dy=-1; move[5].dx=-1; move[5].dy= -1; move[6].dx=-1; move[6].dy=0; move[7].dx=-1; move[7].dy=1; } void inistack(sqstktp *s) /*初始化栈*/ { s->top= -1; } int push(sqstktp *s,elemtype x) /*数据元素x 入指针s 所指的栈*/ { if(s->top==MAXLEN-1) /*栈满，返回False */ return(False); else { s->stack[++s->top]=x; /*栈不满，执行入栈操作 */ return(True); } } elemtype pop(sqstktp *s) /*栈顶元素出栈*/ { elemtype elem; if (s->top<0)> {elem.x = Null; elem.y = Null; elem.dir = Null; return(elem); } else { s->top- - ; retrun(s->stack[s->top+1]); /*如果栈不空，返回栈顶元素值*/ } } void path(int maze[][N2],struct moved move[],sqstktp *s) /*寻找迷宫中的一条通路*/ {int i, j, dir, x, y, f; elemtype elem; i=1; j=1; dir=0; maze[1][1] = -1; /*设[1][1]为入口处*/ do { x=i+move[dir].dx; /*求下一步可行的到达点的坐标*/ y=j+move[dir].dy; if(maze[x][y]= =0) {elem.x = i; elem.y = j; elem.dir = dir; f=push(s, elem); /*如果可行，将此点数据入栈*/ if(f = =False) /*如果入栈操作返回假，说明栈容量不够*/ printf(栈长度太短\n); i=x; j=y; dir=0; maze[x][y]= -1; /*走过的位置设为-1 */ } else if(dir<7)> dir++; else {elem = pop(s); /*8个方向都不可行，就转到下一个方向*/ if(elem.x!=Null) {i=elem.x; j=elem.y; dir=elem.dir+1;} } }while(!((s->top= = -1)&&(dir>=7)|| (x= =M)&&(y= =N)&&(maze[x][y]= = -1))); /*循环，直到入口处或出口处为止*/ if (s->top= =-1) /*如果是入口处，则迷宫无通路*/ printf(“此迷宫无通路\n”); else { elem.x = x; elem.y = y; elem.dir = dir; /*将最后出口处的坐标压入栈中*/ f= push(s,elem); printf(“迷宫通路是：\n”); i= 0; while (i<=s->top) {printf(“%d, %d”, s ->stack[i].x , s->stack[i].y ); /*显示迷宫通路*/ if (i!=s->top) printf(“-->”); if((i+1)%4= =0) printf(“\n”); i++; } printf(“\n”); } } void draw(int maze[][N2], sqstktp *s) /*在迷宫中绘制出通路*/ { int i, j; elemtype elem; for(i =1; i<=m; i++)=""> for(j =1;j<=n;> if (maze[i][j]= = -1) maze[i][j]= = 0; while (s->top> -1) /*根据栈中元素的坐标，将通路的各个点的值改为-1*/ {elem = pop(s); i = elem.x; j = elem.y; maze[i][j]= = 8; } for(i =1; i<=m;> {for(j =1;j<=n;> printf(“%3d”, maze[i][j]); printf(“\n”); } printf(“\n”); } void main() {sqstktp *s; int maze[M2][N2]; struct moved move[8]; inimaze(maze); s=(sqstktp *p)malloc(sizeof(sqstktp)); inistack(s); inimove(move); path(maze, move, s); draw(maze,s); } 第五节 测试结果 5.1 错误输入 5.2正确路径 第六节 课程设计总结 通过这段时间的课程设计，本人对软件专业的应用，数据结构的作用以及C 语言的使用都有了更深的了解。尤其是C 语言的进步让我深刻的感受到任何所学的知识都需要实践，没有实践就无法真正理解这些知识以及掌握它们，使其成为自己的财富。 在实际的上机操作过程中，不仅是让我们了解数据结构的理论知识，更重要的是培养解决实际问题的能力，所以相信通过此次实习可以提高我们分析设计能力和编程能力，为后续课程的学习及实践打下良好的基础。 时间过得真快，大学生活不知不觉就走过了三年，三年的大学学习和课程实践阶段的提高，使我们本身知识得到提高的同时，也增强了我们对未来工作的信心，我们相信自己未来三年的学习更使我们有能力胜任将来的工作。 第七节 参考文献 1. 谭浩强 2. 严蔚敏 <数据结构（c 语言版）="">>[M]. 北京：清华大学出版社 3. 王华 , 叶爱亮 等 . 4. 钱新贤 ,程兆炜等 . 如何设计光电式烟雾报警器 — 烟雾光学迷宫 任何物体闷烧或燃烧时,都会产生大量的颗粒,漂浮在空气中。 我们使用一束特定强度的光,照射这些微颗粒,产生大量的反射光, 通过采集这些反射回来的光强,来测量漂浮颗粒在局部空气中的密 度,判定其发生火灾。 我们总是希望接收到的光都是颗粒反射回来的光,而不是外界的 干扰光,因此我们需要设计一个迷宫,隔离外部的干扰光。目前在市 面上我们可以看到各式各样的迷宫,如图 1所示。在这些迷宫中,我 们总能发现很多共同之处和不同之处。 图 1 随着我们生活水平的不断提高, 对产品的性能要求也越来越苛刻, 如扩大使用温度范围、增加应用场合、延长电池使用寿命、增加探测 火种和改善人机交换功能等。 我们也看到世界各国消防法规不断的更 新,测试要求也越来越高。如德国、美国等。 设计一款性能优异、价格低廉的烟雾光学迷宫(以下简称迷宫) , 成了我们思考的重点。一个完整的迷宫包括三个部件:红外发射管、 红外接收管和迷宫塑料件。我们可以通过隔离值、气阻值、解析度、 底噪值、准确度和温漂值等参数来衡量一个迷宫的性能。 隔离值,主要衡量迷宫结构的优异性,以百分比 K 来表示。测量 方式:使用特定波长和强度的点光源,立体 360旋转照射迷宫,测量 接收区的光强。计算公式:K=(1- Sr / Si) * 100% /A; Si 为照射光 的强度, Sr 为接收区的光强, A 为距离单位。 气阻值,主要衡量迷宫的进气特性,以响应时间 t 来表示。测量 方式:在无对流的局部空气中,均匀的分布一定密度的烟雾颗粒,响 应值以接收区的光强达到该烟雾密度值所需要的时间。单位 t 秒每 A 密度。 解析度,主要衡量迷宫能测量最小烟雾颗粒的密度值,以光强 l 来表示。测量方式:在一定气流的局部空气中,均匀的分布一定密度 的烟雾颗粒,测量接收区的光强。单位 mW 每 A 密度的 B 颗粒。 底噪值, 主要衡量迷宫的结构对检测的红外光所产生干扰光的量, 以百分比 K 来表示。测量方式:红外发射管以一定强度照射,测量 接收区的光强。 计算公式:K=Sr / Si* 100%; Si 为红外发射管的光强, Sr 为接收区的光强。 准确度,主要衡量迷宫对测量烟雾颗粒密度的准确性,以相应消 防法规规定的检测设备的检测区域为基准, 是一个相对量, 以百分比 K 表示。检测区域越大,对不均匀分布的烟雾颗粒影响越小,准确度 越高。 温漂值,主要衡量迷宫的解析度和底噪在不同温度的变化值,以 温度 23℃±2为基准,是一个相对量,以百分比 K 表示。 根据不同的产品,我们往往需要设计不同大小的迷宫。如系统式 报警器,绝大多数都采用大迷宫,而家用型的,大都采用小迷宫。一 般,迷宫越大,其性能也越好。设计迷宫的内部结构是我们最大的工 作量。 一、为了控制和降低底噪,设计光的路径,使红外光按照路径进 行反射传播。如图 2简单所示。 图 2 二、为了增加准确度和解析度,排布光的路径,使光路径均匀的 分布在检测区域内。如图 3简单所示。 图 3 三、为了增加隔离能力、减少气阻,在检测区域周围,采用特定 形状的挡片来反射外部干扰光, 但要避免发生衍射。 保持相邻挡片之 间的距离,增加气流量。如图 4简单所示。 图 4 经过以上的步骤,初步完成一个迷宫。在设计中,我们还要考虑 其它参数,如波长、可视角、光强、温度特性、暗电流、短路电流、 夹角(发射管和接收管的角度) 、材料的特性和吸收率(对光的吸收) 等参数,来提升整个迷宫的性能,但有几个性能参数是相对的,所以 要根据硬件电路、产品的应用场合和结构,来权衡迷宫的某些性能。 作者:Tom 2014-3-30 《设计迷宫》教学设计 教学目标 1、了解迷宫相关知识，学习运用线条表现。 2、能够大胆地运用线条、颜色画迷宫，提高用线和色的表现能力。 3、通过迷宫造型游戏的活动，体验快乐。 教学重难点 重点：运用多种造型方法表现出一个立体的迷宫。 难点：收集多种材料，掌握不同材料的运用表现方法。 课前准备 教师：世界各地迷宫图片资料，黄花镇迷宫资料等。 学生：通过书籍和网络查看各种设计的迷宫，纸笔等绘画工具。 教学过程 一、游戏导入 1、学生分组比赛走迷宫。 比赛条件： （1）、时间5分钟； （2）、记住迷宫的主题、造型、颜色和材料； （3）、记录走迷宫过程（情景、起点、路径、障碍物、终点）； 2、你走迷宫顺利吗？当遇到障碍物怎么办？ 请小组成员举手回答。 二、欣赏迷宫 教师带领学生欣赏分析教材上迷宫图。 欣赏《黄花镇迷宫》，让学生可以根据要点说一说，教师及时给予补充。（学生通过走迷宫游戏，已经了解设计迷宫的要点。） 黄花镇迷宫主题是：八月十五中秋之夜，皇帝在此举行灯火晚会，宫女们手执用黄绸扎制的荷花灯走迷阵，先到中心圆亭者，便可得到赏赐。造型特点：仿法国巴黎的凡尔赛迷宫。材料是：石亭，砖墙，花园。颜色是：根据季节变化。黄花镇虽然从入口到中心亭的直径距离不过30多米，但因遍筑矮墙，周围植矮松，所以此阵易进难出。 三、学生课堂作业 学生可以按照自己设计思路进行迷宫设计，教师巡视指导。 四、课外拓展延伸 在本课学习活动后，教师继续让学生多欣赏一些世界著名的迷宫。学生欣赏的图片多了，思路就更加开阔了。 （一）设计题目：迷宫 （二）需求分析： 任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷 宫的路径，并将路径输出； 要求：在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法； （三）概要设计： 在迷宫设计中，由于不能使用递归则可以借助栈来实现在迷宫中的前进和后退。同时在还需要设计迷宫的大小、迷宫的出入口、根据输入的入口来寻找迷宫的出口，并把路径输出来。 在这个编程中由于不知道所走路劲步数，所以采用了链式栈实现每一步的移动，若找到出路则前进否则返回下一步改变方向来实现相关的移动，所以栈在其间起到了工具作用。 在设计迷宫大小和出入口时，采用的是根据操作者实现的，但迷宫的具体路障和通道是随机实现的。 当然，重点是如何从出口来找出口。 求迷宫的一条通路的伪码如下： 设当前初始位置为出口： do{ 若当前位置可通，则{ 将该位置插入到栈顶；//纳入路径 若该位置为出口位置。则结束当前程序；/求得的路径放在栈中 否则切换当前位置的东临位置（即向右）为新的当前的位置； } 否则{ 若栈不为空且栈顶元素尚有其他位置未被探索，则设定新的当前位置为沿着顺时针旋转得到的栈顶位置的下一个临快； 若栈不为空且栈顶位置的四周均不通 { 则删去栈顶元素；//后退一步，从路径中删去该通块 若栈不空，则重新测试新的栈顶位置，直到找到一个可通的相邻块或出栈至栈空； } }//否则 }while(栈不为空) 本程序的模块 主程序从main()函数中进行，包括输入迷宫的大小等信息，然后调用迷宫模块，在迷宫模块中也调用了栈的模块。 栈模块——实现栈抽象数据类型 迷宫模块——实现迷宫抽象数据类型 各模块之间的关系如下： 主程序模块 栈模块 （四）详细设计 1．坐标的位置类型： typedef struct { int r; int c; }PosType; 2.迷宫类型： typedef struct{ int Col,Row;//迷宫的大小 int arr[Rangle][Rangle]; //0表示障碍，1表示是可走的通道，-1表示外界的围墙 //2表示已经走过， 3表示已经知道其不能通过 }MazeType; void InitMaze(MazeType &M,int col,int row) { //按照用户的输入的行数row和列数col列的二维数组（元素值为1或0） //设置迷宫的错初值，加上边缘的一圈的值 } void PrintMaze(MazeType M) { //根据已经进行二维数组的标记值来输出迷宫（或者其通路） } bool Pass(MazeType M,PosType pos) {//求解迷宫M中，从Start到end的一条路径 //若存在则返回true，否则返回false Stack S; InitStack(S); PosType curpos=start;//设置当前坐标为入口位置； int curstep=1; //当前的步数 bool Find=false; //是否找到出口 ElemType e; do{ if(Pass(M,curpos))//如果当前位置可以通过（不是障碍物且未曾留下足迹） { FootPrint(M,curpos);//在当前位置标记为2 e.step=1; e.seat=curpos; e.di=1;//初始化为向东临位置移动（即向右） Push(S,e);//将已经周的的放入栈中 if(curpos.c==end.c&&curpos.r==end.r)//如果找到了出口则终止，并返回true { Find=true; return Find; } else{//在其东临位置上移动，当前步数加一 curpos=NextPos(curpos,1); curstep++; } } else{//当前位置不能通过 if(!StackEmpty(S)){ Pop(S,e);//将已经走过的最近位置弹出，数据保存在e中 while(e.di==4&&!(StackEmpty(S))){//当方向改变一周后仍不能找到可通过的 MarkPrint(M,e.seat);//留下不能通过的标记 Pop(S,e);//删除站定元素 curstep--; 路径 }//while if(e.di } curpos = NextPos(e.seat,e.di); //求下一个节点 }//if }//if }//else }while(!StackEmpty(S)&&!Find); //(!StackEmpty(S)&&!Find);//当栈不为空且没有找到出口 return false;//没有找到出口则返回false 从入口口到出口的查找的流程图 （五）调试分析、测试结果 （1）由于是不确定的步骤，采用的是易于操作的链式栈，这样就不免了时间和空间的浪费。 （2）对于设计迷宫，可能会觉得会很繁琐，刚开始也是自己设计迷宫图，但由于是随机设定迷宫的大小这就需要利用随机数来设计一个迷宫图。而利用%运算则可以解决这个问题，因为在设置迷宫数组时，1就代表通道，而0就是障碍，随意一个随机数%2得到的就是0或者1就可以自由设计迷宫了。 （3）来利用到进出栈时为计算进出栈的情况，特设定了curstep来调试程序的执行。 那下面就介绍一下设计的迷宫界面情况： （六）设计心得体会 在知识方面,在设计迷宫时需要用到一些基本的如栈的相关信息，来解决不能使用递归的问题，递归在使用过程中虽然简介但不易理解通过栈的使用来加强我们对递归的使用。 在对问题的理解上我们通过对相关知识的理解和认识，来解决一些实际问题。 （七）附录 Stack.h #include #include typedef struct { int r; int c; }PosType; typedef struct{ int step; //当前位置在路径上的序号 PosType seat; //当前位置的坐标 int di; //往下一坐标的方向 }ElemType; typedef struct NodeType{ ElemType data; NodeType *next; }*NodeLink; typedef struct{ NodeLink top;//指向栈顶 int size; }Stack; ////////////栈的基本操作 void InitStack(Stack &S){ //初始化栈，设S为空栈 } int LengthStack(Stack S){return S.size;} bool StackEmpty(Stack S) { S.size=0; ///cout if(S.size==0)return true; else return false; } bool Push(Stack &S,ElemType e) { //若分配空间成功，则在S的栈顶插入新的栈顶元素e，并返回true } NodeType *p; if((p=(NodeType *)malloc(sizeof(NodeType)))==NULL) return false; p->data=e; p->next=S.top; S.top=p; S.size++; return true; bool Pop(Stack &S,ElemType &e){ //若栈不空，将栈S的栈顶元素删除并由e带回其值，且返回true NodeType *p=S.top; if(p==NULL) { cout return false; } e=p->data; S.size--; S.top=p->next; free(p); return true; } bool StackTraveser(Stack S) { } NodeType *p; p=S.top; if(p==NULL) { return false; } while(!p){ coutdata.dinext; } return true; 主程序 #include #include #include #include "stack.h" #include /***************************************************************迷宫的相关信息*************/ #define Rangle 100 typedef struct{ int Col,Row;// int arr[Rangle][Rangle]; //0表示障碍，1表示是可走的通道，-1表示外界的围墙 //2表示已经走过， 3表示已经知道其不能通过 }MazeType; void InitMaze(MazeType &M,int col,int row) { //按照用户的输入的行数row和列数col列的二维数组（元素值为1或0） //设置迷宫的错初值，加上边缘的一圈的值 M.Col=col; M.Row=row; int i; //根据随机产生数进行初始化这个二维数组 for(i=1;i M.arr[0][i]=-1; M.arr[M.Row+1][i]=-1; } for(i=0;i M.arr[i][0]=-1; M.arr[i][M.Col+1]=-1; for(int j=1;j //srand(time(0)); int n=rand()%101+100; M.arr[i][j]=n%2;//得到的值是1或者0，即恰好是路或是通道 //围墙的标记 for(i=0;i } } void PrintMaze(MazeType M) { //根据已经进行二维数组的标记值来输出迷宫（或者其通路） int i,j; for(i = 0; i if(M.arr[i][j] == 0) cout else if(M.arr[i][j] ==-1) cout cout else cout bool Pass(MazeType M,PosType pos) {//若在迷宫M中，当前位置pos不是障碍物0，不是围墙-1，以前没有经过2且不是不可通过3 则可以通过，并返回true if(M.arr[pos.r][pos.c]!=0&&M.arr[pos.r][pos.c]!=-1&&M.arr[pos.r][pos.c]!=2&&M.arr[pos.r][pos.c]!=2&&M.arr[pos.r][pos.c]!=3) return true; } void FootPrint(MazeType &M,PosType pos) {//在迷宫中的pos的位置留下足迹，证明已经经过这个位置 } void MarkPrint(MazeType &M,PosType pos){ //在迷宫的pos位置，留下不能通过的标记 M.arr[pos.r][pos.c]=3; } PosType NextPos(PosType CurPos, int Dir) { else return false; M.arr[pos.r][pos.c]=2; //根据不同的方向来进行移动 PosType ReturnPos; switch (Dir) { case 1://向右 ReturnPos.r=CurPos.r; ReturnPos.c=CurPos.c+1; break; case 2://向下 ReturnPos.r=CurPos.r+1; ReturnPos.c=CurPos.c; break; case 3://向左 ReturnPos.r=CurPos.r; ReturnPos.c=CurPos.c-1; break; case 4://向上 ReturnPos.r=CurPos.r-1; ReturnPos.c=CurPos.c; break; } return ReturnPos; } bool MazePath(MazeType &M,PosType start,PosType end) { //求解迷宫M中，从Start到end的一条路径 //若存在则返回true，否则返回false Stack S; InitStack(S); PosType curpos=start;//设置当前坐标为入口位置； int curstep=1; //当前的步数 bool Find=false; //是否找到出口 ElemType e; do{ if(Pass(M,curpos))//如果当前位置可以通过（不是障碍物且未曾留下足迹） { FootPrint(M,curpos);//在当前位置标记为2 e.step=1; e.seat=curpos; e.di=1;//初始化为向东临位置移动（即向右） Push(S,e);//将已经周的的放入栈中 if(curpos.c==end.c&&curpos.r==end.r)//如果找到了出口则终止，并返回true { Find=true; return Find; } else{//在其东临位置上移动，当前步数加一 curpos=NextPos(curpos,1); curstep++; } } else{//当前位置不能通过 if(!StackEmpty(S)){ Pop(S,e);//将已经走过的最近位置弹出，数据保存在e中 while(e.di==4&&!(StackEmpty(S))){//当方向改变一周后仍不能找到可通过的 MarkPrint(M,e.seat);//留下不能通过的标记 Pop(S,e);//删除站定元素 路径 curstep--; }//while if(e.di } void main() { PosType start,end; MazeType M; int col,row; loop: cout cin>>row; cout>col; InitMaze(M,col,row); cout>start.r>>start.c; cout>end.r>>end.c; if(start.r>M.Row||start.c>M.Col||start.r==0||start.c==0||end.r>M.Row||end.c>M.Col||end.r==0||end.c==0) { //查看输入数据的准确性 cout } else if(MazePath(M,start,end)) { //若找到了相关路径则输出路径信息 PrintMaze(M); } else } cout>ch; if(ch=='y'||ch=='Y') goto loop; else if (ch=='n'||ch=='N') return ;范文三：如何设计光电式烟雾报警器-烟雾光学迷宫
范文四：《设计迷宫》教学设计
范文五：迷宫程序设计
