迷宫实验报告————————————————————————————————作者：————————————————————————————————日期：一、实验内容3、迷宫问题。
假设迷宫由m行ｎ列构成，有一个出口和一个入口,入口坐标为(1，1)，出口坐标为(m,n）,试设计并验证以下算法：找出一条从入口通往出口的路径，或报告一个“无法通过”的信息。
（1)用C语言实现顺序存储队列上的基本操作，然后利用该队列的基本操作找出迷宫的一条最短路径。
(2)设计一个二维数组MAZE［m+２]［ｎ+２]表示迷宫，数组元素为0表示该位置可以通过,数组元素为1表示该位置不可以通行。
MAZE［１][1］、ＭAZE[m][n]分别为迷宫的入口和出口。
(３）输入迷宫的大小ｍ行和n列,动态生成二维数组;由随机数产生0或1,建立迷宫,注意ｍ＊n的迷宫需要进行扩展,扩展部分的元素设置为1，相当于在迷宫周围布上一圈不准通过的墙。
(4）要求输出模拟迷宫的二维数组;若存在最短路径，则有出口回溯到入口(出队列并利用栈实现),再打印从入口到出口的这条路径,例如（１,1），...．..,（i,ｊ)，......,(m，n)；若没有路径,则打印“No patｈ”。
(5）迷宫的任一位置(i,j)上均有八个可移动的方向,用二维数组Ｄireｃtｉon存放八个方向的位置偏移量。
Dｉrｅction[8]［２］={{0,１},{1,1},｛0，－1}，{-1，－1},｛1，-1｝，{1,0},{-１,0},{－1,１}}；（6）为避免出现原地踏步的情况需要标志已经通过的位置,采用一个标志数组MARＫ[m＋２][ｎ+2］,初值均为0,在寻找路径的过程中，若通过了位置（i，j），则将MARＫ[ｉ］[ｊ］置为1。
（7）为了记录查找过程中到达位置(i,j)及首次到达（i,ｊ）的前一位置（i_pre,j＿pre）,需要记住前一位置（i_pｒe,j＿ｐre）在队列中的序号pｒe,即队列中数据元素应该是一个三元组(i，j,prｅ）。
（8）搜索过程简单下：将入口MＡＺE[１][1]作为第一个出发点，依次在八个方向上搜索可通行的位置,将可通行位置(i，j,pre）入队,形成第一层新的出发点，然后依次出队，即对第一层中各个位置分别搜索它所在八个方向上的可通行位置,形成第二层新的出发点,.．．,如此进行下去,直至达到出口ＭAZE［m］［n]或者迷宫所有位置都搜索完毕为止。
二、实验过程及结果一、需求分析１、用栈的基本操作完成迷宫问题的求解，其中栈的基本操作作为一个独立的模块存在。
2、以二维数组M[m+2][n+2]表示迷宫，Ｍ[i]［j] 表示迷宫中相应(i,j)位置的通行状态(0：表示可以通行，1：表示有墙,不可通行),完成迷宫的抽象数据类型，包括出口、入口位置等。
３、用户从屏幕上输入迷宫，从键盘输入迷宫的大小，即迷宫的长和宽(由于控制台大小限制，输入的长宽需在5０以下）,完成对应迷宫的初始化。
根据键盘输入的迷宫规格随机生成大小相同的迷宫，产生方块的地方为墙，无方块的地方可通过,如下例所示:如下所示:4、程序完成对迷宫路径的搜索,为了更好地显示出求解结果，如果存在路径，则以长方形形式将迷宫打印出来,而不是只按步输出坐标，也便于检查路径的正确性,用特定符号标出迷宫的物理状态,其中字符“＃”表示出口和入口，“<”标记出可行的路径；如果程序完成搜索后没有找到通路，则提示用户“NoＰath！”。
如图所示:５、程序执行的命令:⑴创建初始化迷宫;⑵搜索迷宫；⑶输出搜索到的最短路径。
二、概要设计(按照题目要求应该用队列实现路径的存储，但操作过程中遇到很多困难未能解决，故选择栈的操作来实现路径的存储)1、迷宫的抽象数据类型定义:ADT Maze{数据对象:D：={aij,Sｔart,end|－20<=aｉj<20,Ｓtart,eｎｄ∈{(i，j)|０≤i≤m+2,0≤ｊ≤ｎ+２,m,ｎ≥0｝｝数据关系：R=｛leｎgtｈ，ｗidth｝ﻩﻩlengtｈ＝｛<ai－１j,aij>|ai－1,aij∈D i=１,…,ｍ+２,j=1，…,n+2}wiｄｔｈ={<aij-1,ａij>|aijaｉj-１∈D}基本操作:SeｔMａze(＆M)初始条件:Ｍ已经定义,Ｍ的下属单元二维数组M.Ｍａze[row＋2][d+２]已存在,M.ｓｔａrt，M．ｅnｄ也已作为下属存储单元存在操作结果：构成数据迷宫，用数值标识迷宫的物理状态，以0表示通路，以１表示障碍，由终端读取迷宫空间大小,各点处的具体物理状态及Start和End点位置，完成迷宫构建Ｐasｓ(Ｍ, CurPｏs）初始条件：已知目前迷宫状态及当前位置操作结果：完成相应的搜索任务，如果可行，则返回１NextPos(ＣｕｒPos,dｉrectionr)操作结果:返回CurＰOS位置在方向ｄｉrectioｎ上的下一位置SameSeat(Path,rｏw,cｏl)操作结果:若(row,col）位置是路径Ｐath中的一个点,则返回TRＵＥＰrintＭaze（Ｍ)初始条件：迷宫M已存在操作结果：输出字符标示的迷宫MazｅPａth(M,&Ｐath)初始条件：迷宫Ｍ已存在操作结果：搜索迷宫，用path返回搜索所得路径。
如不存在,返回０PriｎtPａth(M,Ｐath)初始条件：迷宫M已存在操作结果：迷宫M存在可行路径则将迷宫M及相应最短路径一起打印输出}AＤT MAZE；⒊本程序模块结构⑴主函数模块voidｍain(){初始化迷宫和栈;创建迷宫；输出迷宫;搜索路径;输出路径;｝⑵栈模块——实现栈抽象数据类型;⑶迷宫模块——实现迷宫抽象数据类型；各模块之间的调用关系如下：ﻩ主程序模块迷宫模块栈模块三、详细设计１、基本数据类型操作⑴栈模块① tｙｐｅdef struｃt{inｔｏrder；Poｓiｔioｎｓeat;ﻩint ｄirection；}SＥleｍType;//步数、方向及位置//栈定义②ｔyｐedeｆsｔｒuct ｌnode{ﻩSEｌemＴype *basｅ；ﻩSEｌemType*toｐ;/／设两指针便于判断栈是否为空ﻩiｎｔstａcksizｅ；//栈当前可使用的最大容量}SqStack；③参数设置：#deｆine SＴACK_INIＴ_SIZE 100＃defｉｎe STＡCKIＮCRENＴ1０/／----－－--－-基本操作的算法描述-－--－－-－----－-－-－－-－Stａtus InitStacｋ(SqＳtack &s){ //构造一个空栈S.ｂase=(SelemType )malｌoc(STＡＣK_INIT_SIＺＥ*SｉzeOｆ(SelemTｙpｅ）);if(!S.base)exiｔ(OVERLOW）; /／存储分配失败S．top=Ｓ.base;S.stackｓiｚe=ＳTACK_ＩNIT_SIZE；rｅtuｒn ok;}SｔａtuｓStackＥmｐty(Ｓｑstacｋ&S)｛／/ 若S为空返回ＴRUＥ，否则返回ＦＡLＳEreｔuｒｎS.base=＝S.top;}StatuｓGeｔTop(SqＳtaｃk ＆S,Ｓelemtｙpe ＆e){/／栈不空,用e返回s的栈顶元素及OK，否则返回ERＲOＲif(Ｓ.tｏp=＝S．bａsｅ）returｎEＲＲOR；e＝*（Ｓ.ｔop-１);ｒｅturｎok;}StatuｓPuｓh(Ｓqsｔａｃk &S,SeleｍTyｐe &e){ ／／插入元素ｅ为新的栈顶元素ｉf(S.toｐ-S．bａse>=S.ｓtacksiｚｅ)｛／／栈满追加存储空间Ｓ.ｂaｓe=(SelemＴype)ｒｅalloc(S．ｂａse,(S.stacksize+STＡCＫＩＣＲEMＥNT）Sizeof(Ｓeｌeｍtｙpe)）;iｆ（!S.base) eｘit(OVERFLOW）／/ 存储分配失败S.top=S．basｅ+S.sｔacksize; ／/确定新的栈顶指针S.stacksｉze＋=ＳTACKINCRＥＭEＮT;// 已分配空间增加｝*S.top++＝*e;return ｏｋ;}Statｕs Ｐoｐ(Sｑｓｔack &s,SｅlemTｙｐe&e){/／若栈不变,则删除栈顶元素,用e返回其值及ok,否则falｓｅif(S.toｐ=o=S.baｓｅ)ｒetｕｒｎＥRROR;*e=*－-S.top; // 顶指针减小,用e返回其数据returｎｏk；}⑵迷宫模块：①迷宫的数据类型#ｄefｉneＭAＸLENＧＴH ５0 /／迷宫的最大长度#definｅＭAＸWIDTＨ５0 /／屏幕宽度，迷宫的最大宽度//元素类型ｔyｐedeｆｉnｔＳｔatus;typedef strｕct{ﻩｉｎｔroｗ;int ｃol;}Ｐosiｔiｏｎ; //位置坐标//迷宫定义typｅdef iｎt ＥlemTｙpｅ;typedef struct MAZＥ{ElemType Ｍaze[MＡXＬENＧTH][MAＸＷＩDTH］; // 迷宫的物理状态描述ﻩiｎｔleｎｇth,wiｄtｈ;ﻩ／/迷宫的大小ﻩPoｓｉtｉｏn start,ｅnd；ﻩ//开始与结束位置与栈的单元类型相同}MAZE;ﻩ／/“迷宫”型数据②迷宫模块中的基本操作Statｕs semaｚe(MＡＺE &Ｍ)｛Printｆ（“Pleaｓe inｐut ｔhe leｎgｔh aｎｄwｉdtｈof the MAZＥ”);sａｎf(“rlength,ｗiｄth”);for（k=0;k＜ｗidth＋2；ｋ++)ﻩﻩＭ－>Maze[0][k］=1;ﻩfｏr（j＝0；j<ｌength＋２;ｊ＋+)ﻩﻩM-＞Maze[j］[0]=1;ﻩfoｒ(j=0;j＜ｌenｇth+2;j++)ﻩﻩM->Maｚe[j][widｔh+1]=1;fｏr(k＝0;k<wｉｄtｈ+２；k++)ﻩﻩM－＞Maze[length+１][k]=1; //设置迷宫围墙for(ｊ＝1;j<＝lｅnｇtｈ；ｊ++){ﻩｆor(ｋ=1；k<=ｗｉｄth;k++）M->Maｚｅ[j][k]=raｎd(）%2;ﻩ／／随机生成迷宫ﻩ}Ｍ->lｅnｇｔh＝length;ﻩM->ｗidth＝wiｄth;M->starｔ．row=1;M－＞start．coｌ=1;M->end.ｒｏｗ=M－>ｌengtｈ;Ｍ->end.col=Ｍ->ｗｉdth;ﻩﻩM->Maze[M->starｔ．row][Ｍ－>stａｒt.ｃoｌ］＝M－>Mａze[Ｍ-＞eｎｄ.row][M->ｅnd.col]=0;//入口和出口设置*/｝void ＰriｎtMaze(MＡZE M)｛／/ 打印出迷宫,包括边界printf（"迷宫入口:［1，1]--用#表示\n")；ﻩprｉntf(＂迷宫出口:[％d,%d］-－用＃表示＼n",Ｍ.lenｇth，M.ｗidｔh);ﻩfor(rｏw＝0;row＜M.length＋２;row＋+){ﻩﻩfor(col=0;coｌ<M．wｉdth+２;col＋+)｛ﻩﻩﻩiｆ((row==1&&col＝＝１)||(ｒoｗ＝=M．length&&cｏl=＝M.width)）printf（＂＃＂); //入口和出口用＃表示ｅlｓｅﻩprinｔf（＂%c"，M.Maze[row]［cｏl]);}ﻩｐrｉntｆ("\ｎ＂);}// 用字符型打印输出（i,j）状态}Status Paｓs（MＡZE Ｍ，ＰoｓitioｎＣurＰｏs)｛/／判断迷宫中当前位置CuｒPｏs上能否通过// 如果通过返回1if(Ｍ.Mａzｅ［CurPos.rｏw][CurPｏs．ｃol]==0)reｔurn１；// 如果当前位置是可以通过，返回1elｓe rｅturn 0; // 其它情况返回０}Posｉｔion NextPｏｓ(Ｐosiｔｉon CuｒＰoｓ, int ｄiｒectioｎ）{//返回当前位置在ｄireｃtion方向上的下一位置ﻩRetuｒｎPos.rｏw=ＣurPｏs.row+Diｒection［direｃtiｏn-1][0］;ReturnPｏｓ.coｌ＝CurPos.ｃoｌ＋Direcｔioｎ［dｉｒecｔion-1][１];return RｅtuｒｎPｏｓ;}Ｓtａｔｕs SameSeaｔ(SqSｔaｃk Path,int roｗ,int col)｛//位置（ｒｏｗ，col)在路径中时返回TRUＥﻩwhｉle（p<Pａｔｈ.tｏp)｛ﻩﻩｉf(Path.basｅ[num].ｓｅat.row＝=row＆&Path.baｓｅ[ｎum]．seat.col==ｃol)//路径某一步所在的位置ﻩｒetｕrn ＴＲUE；num++;ﻩp++；ﻩ}reｔurn FALＳE;}Staｔｕs ＭazePath（ＭAＺE M,SqSｔaｃk *S){// 若迷宫ｍaze中从入口ｓtart到出口eｎd的通道,则求得一条存放在栈中// （从栈底到栈顶），并返回ＳUCCEＳS；否则返回ＦAILcurpos=M.start; ／/ 设定"当前位置"为"入口位置"curstep=1; /／探索第一步//第一次查找路径,设置5个方向（不远离!终点的五个方向)，若找到则返回SUC ＣESSﻩdo｛if(Pass(M,ｃｕrpos))｛// 当前位置可通过，即是未曾走到过的通道块ﻩﻩM.Ｍaｚe[cuｒpos.rｏｗ][curpos．col]=＇'; // 留下足迹ﻩe．ｄirectiｏn=1;ﻩe．oｒder=cuｒstep；ﻩﻩ e.seａt=cｕrpos;Ｐuｓｈ(S,&e）；// 加入路径if(ｃuｒpos.rｏw=＝M.ｅnd．row&&ｃｕｒpos．ｃol==Ｍ.end.col）{ ﻩﻩ/／到达终点(出口)ﻩreturn SUCＣEＳS；ﻩ}ﻩcurｐos=NeｘtPos（cｕrpoｓ，１);/／下一位置在当前位置的右下方ﻩｃursteｐ++; ／／探索下一步}ﻩｅｌsｅ{// 当前位置不能通过ﻩiｆ(!StackEmpty(S）){ﻩﻩPop(S，&e）;ﻩﻩwhile(e.ｄirecｔiｏn=＝5&&!ＳｔaｃkEｍpty(Ｓ)）{ﻩﻩM.Maze[ｃｕrｐos.row][ｃuｒpos.col]='＇; //标记不能通过Pｏp(Ｓ,&e）; ／／留下不能通过的标记，并退回一步ﻩ｝// whiｌeﻩiｆ(e.dirｅcｔion<5){ﻩ e.ｄirection++;ﻩﻩＧetTｏp（S,&tｅ);ﻩif(ｅ.diｒectiｏｎ＝＝5&&ｔe．ｄｉrection==2）{ﻩﻩPｏp(S，&e);ﻩﻩ e.dｉreｃtｉｏｎ+＋;ﻩ}ﻩﻩﻩﻩPush(S，＆e）; ／/换下一个方向探索ﻩﻩcurpｏs=NexｔPｏs(e．seaｔ，e.diｒeｃtiｏn); /／当前位置设为新方向的相邻块ﻩﻩﻩ} ／／ifﻩ} //ifﻩ｝／/ｅlse}ｗhiｌｅ(！SｔaｃkEmpty(S));ﻩcｕｒpos=M.ｓtａrt; // 设定＂当前位置＂为＂入口位置"curｓtｅp=１; ／/ 探索第一步ﻩ/／如果第一次查找无结果则再进行一次八个方向的查找，检查是否存在第一次查找不到的特殊情况ﻩｄo{ﻩif(Pass（M,ｃｕrpos)){ // 当前位置可通过，即是未曾走到过的通道块ﻩﻩM．Ｍaze[cｕrpos.row][ｃｕrpｏｓ.cｏｌ]='';／/留下足迹ﻩｅ．direｃｔｉoｎ=１;ﻩ e.oｒder=cursｔep；ﻩﻩ e.sｅａt＝curｐos；ﻩPuｓh(Ｓ,&e);//加入路径if(ｃurpos.rｏw＝=M．ｅnd.rｏw＆＆curｐoｓ.coｌ=＝Ｍ.ｅnd.coｌ)｛ﻩ／/ 到达终点(出口）ﻩﻩ//PriｎｔＰａth(mａze,S); //输出路径ﻩﻩrｅtuｒn ＳUCCESＳ;｝ﻩﻩcurpｏs=ＮeｘｔＰos(cｕrｐｏs,1); ／／下一位置是当前位置的东邻ﻩcｕrstep++；／/ 探索下一步}ﻩelsｅ{ //当前位置不能通过ﻩﻩif(!SｔackEｍpty（Ｓ)）{Pｏｐ（S，&ｅ）;ﻩｗｈile(e.ｄirｅcｔion==8&&!StackEmpty(S）){ﻩﻩM.Mａze[curpos.rｏw][ｃurｐos．coｌ]=＇'；ﻩ/／标记不能通过ﻩﻩPop(Ｓ,＆e);// 留下不能通过的标记,并退回一步ﻩ} // whileﻩif(e.ｄirｅctｉon<８){ﻩﻩ e.direｃtion＋＋;ﻩGetTop(S,&ｔe)；ﻩﻩﻩiｆ(ｅ.ｄｉrectｉon＝=４&&ｔe．dｉrectｉｏｎ＝=2)｛ﻩﻩﻩﻩPop（S,&e)；ﻩﻩ e.direｃtｉｏｎ＋+;ﻩ｝ﻩﻩﻩﻩPush(S，&e); /／换下一个方向探索ﻩｃｕrpos＝NｅｘtＰoｓ（e.seａt,e.ｄｉrｅｃtion)；// 当前位置设为新方向的相邻块ﻩﻩ｝／/if｝／／if} // eｌｓe}ｗhile(!StａcｋEmpｔy（S));ﻩｒetuｒn FAIL；｝/／MazeＰathvoｉd PrinｔPａｔh（MAZＥM，SqＳtacｋPath){// 将迷宫及路径一起打印ｉf(StａcｋＥmpty(&Paｔh）){ﻩﻩpｒiｎtf（"NｏＰath！＼n"）;／／路径栈为空，则提示无路径ﻩexit(ＯVERFLＯW);}ﻩprintf("＼ｎＴｈe Path:\n")；for(ｒow=０；roｗ＜M.lｅngth＋2；rｏw++){ｆor（col＝0；coｌ<M.widtｈ＋2;ｃoｌ++）{ﻩiｆ(SamｅＳeａt(Pａｔh,ｒｏw,ｃoｌ)){ﻩﻩif((row＝=1＆&coｌ=＝1）||（rｏｗ==M.ｌength&&coｌ=＝Ｍ．wiｄtｈ)) ﻩﻩﻩﻩprｉntf("# ");ﻩﻩｅlｓｅﻩﻩﻩpｒintf(＂>")；ﻩﻩnum++；ﻩp++;ﻩﻩﻩ｝ﻩﻩelseﻩﻩprintｆ("%c ",M.Maｚe[roｗ][col]);ﻩ}ﻩﻩｐrintf("\n"）;ﻩ}}⑶ 主函数算法:void m ａｉｎ()｛ﻩMA ＺＥ Ｍ;Sq Ｓtack path ；ﻩInit Ｓta ｃk(&p ａth);SetMaz ｅ（＆M)；ﻩPr ｉｎtMaze （M);Maze Ｐath(Ｍ,&path);Prin ｔＰat ｈ(Ｍ，p ａth);}⒉ 函数的调用关系反映了本演示程序的层次结构 ma ｉｎInit Ｓｔac ｋ Ｍaz ｅＰa ｔh P ｒintP ａth Ｐri ｎtMaze Pass ＳｅtMaze Sa ｍeSe ａｔ N ｅx ｔP ｏsﻩ……Push G ｅtTop P ｏp StackEmp ｔｙ四、调试分析1、开始没有将Ｍ[n ］[m].ｓta ｒt.end 设置为MAZ Ｅ 型数据的下属单元,使得各个迷宫操作的函数参数十分散杂,调试时各参数关系不易把握。