2023年迷宫实验报告.pdf

《2023年迷宫实验报告.pdf》由会员分享，可在线阅读，更多相关《2023年迷宫实验报告.pdf（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、一、实 验 内 容 3、迷 宫 问 题。假 设 迷 宫 由 m行 n 列 构 成，有 一 个 出 口 和 一 个 入 口，入 口 坐 标 为(1,1),出 口 坐 标 为(m,n),试 设 计 并 验 证 以 下 算 法：找 出 一 条 从 入 口 通 往 出 口 的 途 径，或 报 告 一 个“无 法 通 过”的 信 息。(1)用 C语 言 实 现 顺 序 存 储 队 列 上 的 基 本 操 作，然 后 运 用 该 队 列 的 基 本 操 作 找 出 迷 宫 的 一 条 最 短 途 径。(2)设 计 一 个 二 维 数 组 MAZE m+2 n+2 表 达 迷 宫，数 组 元 素 为 0 表

2、 达 该 位 置 可 以 通 过，数 组 元 素 为 1 表 达 该 位 置 不 可 以 通 行。MAZE11,MAZEm n 分 别 为 迷 宫 的 入 口 和 出 口。(3)输 入 迷 宫 的 大 小 m 行 和 n 歹！I,动 态 生 成 二 维 数 组；由 随 机 数 产 生 0 或 1,建 立 迷 宫,注 意 m*n的 迷 宫 需 要 进 行 扩 展，扩 展 部 分 的 元 素 设 立 为 1,相 称 于 在 迷 宫 周 边 布 上 一 圈 不 准 通 过 的 墙。(4)规 定 输 出 模 拟 迷 宫 的 二 维 数 组;若 存 在 最 短 途 径，则 有 出 口 回 溯 到 入 口

3、(出 队 列 并 运 用 栈 实 现)，再 打 印 从 入 口 到 出 口 的 这 条 途 径，例 如(1,1),.(i,j).(m,n);若 没 有 途 径，则 打 印“N o p a t h”。(5)迷 宫 的 任 一 位 置(i,j)上 均 有 八 个 可 移 动 的 方 向，用 二 维 数 组 D irec tio n存 放 八 个 方 向 的 位 置 偏 移 量。Di re c t i on82=0,1,1,1,0,-1,-1,-1,1-1,0,/；(6)为 避 免 出 现 原 地 踏 步 的 情 况 需 要 标 志 已 经 通 过 的 位 置，采 用 一 个 标 志 数 组 M A

4、RK m+2 n+2,初 值 均 为 0,在 寻 找 途 径 的 过 程 中，若 通 过 了 位 置(i,j)，则 将 M ARKilj置 为 1。(7)为 了 记 录 查 找 过 程 中 到 达 位 置(i,j)及 初 次 到 达(i,j)的 前 一 位 置(i _pre,j_pre),需 要 记 住 前 一 位 置(i_p r e,j_ p r e)在 队 列 中 的 序 号 p r e,即 队 列 中 数 据 元 素 应 当 是 一 个 三 元 组(i,j,pre),（8）搜 索 过 程 简 朴 下：将 入 口 M A ZE 1 作 为 第 一 个 出 发 点，依 次 在 八 个 方 向

5、 上 搜 索 可 通 行 的 位 置,将 可 通 行 位 置（i,j,pre）入 队，形 成 第 一 层 新 的 出 发 点，然 后 依 次 出 队，即 对 第 一 层 中 各 个 位 置 分 别 搜 索 它 所 在 八 个 方 向 上 的 可 通 行 位 置，形 成 第 二 层 新 的 出 发 点，,如 此 进 行 下 去，直 至 达 成 出 口 M AZE mln或 者 迷 宫 所 有 位 置 都 搜 索 完 毕 为 止。二、实 验 过 程 及 结 果 一、需 求 分 析 1、用 栈 的 基 本 操 作 完 毕 迷 宫 问 题 的 求 解，其 中 栈 的 基 本 操 作 作 为 一 个 独

6、 立 的 模 块 存 在。2、以 二 维 数 组 M m+2 n+2 表 达 迷 宫,M E i j 表 达 迷 宫 中 相 应（i,j）位 置 的 通 行 状 态（0：表 达 可 以 通 行，1：表 达 有 墙，不 可 通 行），完 毕 迷 宫 的 抽 象 数 据 类 型，涉 及 出 口、入 口 位 置 等。3、用 户 从 屏 幕 上 输 入 迷 宫，从 键 盘 输 入 迷 宫 的 大 小，即 迷 宫 的 长 和 宽（由 于 控 制 台 大 小 限 制，输 入 的 长 宽 需 在 5 0 以 下），完 毕 相 应 迷 宫 的 初 始 化。根 据 键 盘 输 入 的 迷 宫 规 格 随 机 生

7、 成 大 小 相 同 的 迷 宫，产 生 方 块 的 地 方 为 墙，无 方 块 的 地 方 可 通 过，如 下 例 所 示：如 下 所 示:习 软 件、Microsoft Visual S tudio D ebug3H t5i.ePlease input the length and width of the MAZE：length 0length：12width 0width：12迷 宫 入 口：H,i 一 用#表 示 迷 宫 出 口：112,121一 同*表 小4、程 序 完 毕 对 迷 宫 途 径 的 搜 索，为 了 更 好 地 显 示 出 求 解 结 果，假 如 存 在 途 径，则

8、以 长 方 形 形 式 将 迷 宫 打 印 出 来，而 不 是 只 按 步 输 出 坐 标，也 便 于 检 查 途 径 的 对 的 性，用 特 定 符 号 标 出 迷 宫 的 物 理 状 态，其 中 字 符 表 达 出 口 和 入 口，标 记 出 可 行 的 途 径；假 如 程 序 完 毕 搜 索 后 没 有 找 到 通 路，则 提 醒 用 户“NoPath!”。如 图 所 示：5、程 序 执 行 的 命 令:创 建 初 始 化 迷 宫；搜 索 迷 宫;输 出 搜 索 到 的 最 短 途 径。二、概 要 设 计(按 照 题 目 规 定 应 当 用 队 列 实 现 途 径 的 存 储，但 操 作

9、 过 程 中 碰 到 很 多 困 难 未 能 解 决，故 选 择 栈 的 操 作 来 实 现 途 径 的 存 储)1、迷 宫 的 抽 象 数 据 类 型 定 义：ADT Maze数 据 对 象：D：=a i j,S t a r t,end 卜 2 0=ai j 20,S tart,e n d e(i,j)|0WiWm+2,0WjWn+2,m,n20 数 据 关 系：R=le n g th,width length=|ai-1,aij G D i=1,m+2,j=1,n+2o w i d t h=|aij a i j-1 e D)基 本 操 作：SetMaze(&M)初 始 条 件：M 已 经

10、定 义，M的 下 属 单 元 二 维 数 组 M.M a ze r ow+2 d+2 已 存 在,M.s t ar t,M.e n d 也 已 作 为 下 属 存 储 单 元 存 在 操 作 结 果:构 成 数 据 迷 宫，用 数 值 标 记 迷 宫 的 物 理 状 态，以 0 表 达 通 路，以 1表 达 障 碍,由 终 端 读 取 迷 宫 空 间 大 小，各 点 处 的 具 体 物 理 状 态 及 Start和 E nd点 位 置，完 毕 迷 宫 构 建 Pa s s(M,CurPos)初 始 条 件:已 知 目 前 迷 宫 状 态 及 当 前 位 置 操 作 结 果:完 毕 相 应 的

11、搜 索 任 务，假 如 可 行,则 返 回 1Ne x tP o s(CurPos,d i r e ct i onr)操 作 结 果：返 回 Cu r PO S位 置 在 方 向 d i r e c tio n 上 的 下 一 位 置 Sam e S e a t(Pat h,r o w,col)操 作 结 果：若(row,c o l)位 置 是 途 径 Pa t h 中 的 一 个 点,则 返 回 TRUEPrintMaze(M)初 始 条 件:迷 宫 M 已 存 在 操 作 结 果：输 出 字 符 标 示 的 迷 宫 Ma z e Pat h(M,&P a t h)初 始 条 件:迷 宫 M

12、 已 存 在 操 作 结 果：搜 索 迷 宫，用 palh返 回 搜 索 所 得 途 径。如 不 存 在，返 回 0PrintP a th(M,Path)初 始 条 件：迷 宫 M已 存 在 操 作 结 果：迷 宫 M 存 在 可 行 途 径 则 将 迷 宫 M 及 相 应 最 短 途 径 一 起 打 印 输 出 AD T MAZE；3.本 程 序 模 块 结 构(1)主 函 数 模 块 v o id ma i n()初 始 化 迷 宫 和 栈；创 建 迷 宫：输 出 迷 宫；搜 索 途 径；输 出 途 径；)栈 模 块 一 一 实 现 栈 抽 象 数 据 类 型；迷 宫 模 块 一 一 实

13、现 迷 宫 抽 象 数 据 类 型；各 模 块 之 间 的 调 用 关 系 如 下：主 程 序 模 块 迷 宫 模 块 栈 模 块 三、具 体 设 计 1、基 本 数 据 类 型 操 作 栈 模 块 t ype d e f s t ructi n t or d er;e P o s i t i o n s e a t;“nt di r e ct i o n;SEI e m iy p e;/步 数、方 向 及 位 置/栈 定 义 typ e def struct lnodeS E lemTy p e*b a se;S E lemType*top;设 两 指 针 便 于 判 断 栈 是 否 为 空

14、 in t st a c ks i z e;/栈 当 前 可 使 用 的 最 大 容 量 S q St a ck;参 数 设 立：#def i ne STACKJNIT_SIZE 1 00#define STACKINCR ENT 10/.-基 本 操 作 的 算 法 描 述 一-一 一 St a tu s In i tS t ack(S q S t a ck&s)/构 造 一 个 空 栈 S.b a se=(Selem T y p e)mal 1 oc(STACKJNI T _S IZ E*S izeOf(Selem Type)；i f(!S上 a s e)e x i t(OVERLOW)；

15、/存 储 分 派 失 败 S.top=S.b ase；S.s t a c ksize=ST A C K JN IT _ SIZ E；return o k;)Status S ta c kE m p t y(S q s t a c k&S)/若 S 为 空 返 回 T R U E,否 则 返 回 FALSEreturn S.base=S,t o p;)St a tu s G e tT o p(SqS t a c k&S,Se 1 emtype&e)/栈 不 空，用 e 返 回 s 的 栈 顶 元 素 及 O K,否 则 返 回 ERRORif(S.t o p=S.base)re t urn E

16、R R O R;e=*(S.t o p-1)；r e t u rn o k;S t a tus P ush(Sqstac k&S,Selem T y pe&e)/插 入 元 素 e 为 新 的 栈 顶 元 素 if(S.t o p-S.base=S.s t a c ksize)/栈 满 追 加 存 储 空 间 S.b ase=(S e lemType)r e a lloc(S.base,(S.sta c k s i z e+STAC KICREMENT)S i zeof(S elem t ype);i f(!S.ba s e)e x i t(OVER F LOW)存 储 分 派 失 败 S.t

17、 op=S.bas e+S.s t acks i ze;/拟 定 新 的 栈 顶 指 针 S.stacks i z e+=S T ACKINCREMENT;/已 分 派 空 间 增 长)*S.top+=*e；r e t u r n ok；)Stat u s P o p(Sq s t ack&s,Se 1 emType&e)/若 栈 不 变，则 删 除 栈 顶 元 素，用 e 返 回 其 值 及 o k,否 则 falsei f(S.t o p=o=S.b a s e)r e tu r n E RRO R;*e=*-S.t o p；/顶 指 针 减 小，用 e 返 回 其 数 据 re t ur

18、n o k；)迷 宫 模 块：迷 宫 的 数 据 类 型#define M A X LEN G TH 5 0/迷 宫 的 最 大 长 度#d e f ine MAXWIDTH 50/屏 幕 宽 度，迷 宫 的 最 大 宽 度 元 素 类 型 typedef int Status;t y p edef st r u ctint row；i nt c o 1；Po s ition;。/位 置 坐 标 迷 宫 定 义 t y p e def i n t El e mType;t y p ed e f s t ruct MAZ E ElemT y pe M aze MAX LENGTHM AX W I

19、DTH；。/迷 宫 的 物 理 状 态 描 述 int lengt h,width；/迷 宫 的 大 小 oPosition start,end；/开 始 与 结 束 位 置 与 栈 的 单 元 类 型 相 同 JMAZE;/“迷 宫”型 数 据 迷 宫 模 块 中 的 基 本 操 作 St a t u s s e maz e(MAZE&M)Pr i ntf(aP 1 ease i nput t he lengt h a n d wi d th of t he MA Z E);s a n f(a rlen g th,w i dth”);for(k=0；k Maze 0 k=1;。f o r(j

20、=0;jM a ze|jj 0for(j=0;j 1 ength+2;j+)。M 一 Maze皿 w id t h+1=1；for(k=0;k V w id th+2;k+)。oM-M azelength+l k=1；。/设 立 迷 宫 围 墙 4 o r(j=1;j=l e n gt h;j+)。(f o r(k=1;k M a z e j k=r a n d()%2;。/随 机 生 成 迷 宫 M-1 e ngth=le n gt h;M width=w i d t h；M-st a rt.r o w=1；M-s t a rt.col=1；M-e n d.r ow=M-1 e n gth;

21、M e n d.col=M-w i d t h;。M-MazeM s ta r t.rowM-st a r t.co 1=M-MazeM end.rowM-end.c ol=0；入 口 和 出 口 设 立*/)v o i d PrintMaze(MAZE M)打 印 出 迷 宫，涉 及 边 界 p r i n l f(迷 宫 入 口:l,l 一 用#表 达 n”)；pr i ntf(迷 宫 出 口:%d,%d 1 用#表 达 n”,M.1 ength,M.w i dth);for(r o w=0;rowM.leng t h+2;r o w+)ofo r(c ol=0；co 1 M.width+

22、2；co 1+)if(ro w=1&col=1)|(row=M.length&col=M.w i d t h)o p r i n t f f#入 口 和 出 口 用#表 达 8?e 1 see M p r i n tf(u%c 0,M.Mazer o wc o 1);)p r i n tf(H n M);/用 字 符 型 打 印 输 出(i,j)状 态)S t a t u s P a ss(M AZE M,Po s it i on CurPos)/判 断 迷 宫 中 当 前 位 置 C u r P o s上 能 否 通 过/假 如 通 过 返 回 1i f(M.MazeC u rP o s.r

23、 owJCurPo s.col=0)r e t u r n 1;假 如 当 前 位 置 是 可 以 通 过，返 回 1e 1 se r e tu r n 0;/其 它 情 况 返 回 0)Positi o n NextPo s(P o si t ion CurPos,i nt d i r ecti o n)返 回 当 前 位 置 在 direc t i o n 方 向 上 的 下 一 位 置 R e t u r nPos.r ow=C u rP o s.r ow+D i re c ti o nfd i r e c t ion-1 0;Retur n Pos.col=C urPos.c o 1+

24、D irectio n dir e c tio n 11;re t u r n Retur n Pos;)Status S ameSeat(SqSt a c k Pa t h,int row,i n t col)/位 置(ro w,c o l)在 途 径 中 时 返 回 TRUEowhi 1 e(pPat h.t o p)if(P a th.ba s enum.s eat.ro w=r ow&P a t h.ba s en u m.sea t.col=c o 1)/途 径 某 一 步 所 在 的 位 置 return T R U E;。g n u m+；p+；6return F ALSE；)S

25、tatus Maz e P a t h(M A Z E M,S q Stac k*S)。/若 迷 宫 maz e 中 从 入 口 star t 到 出 口 e n d的 通 道，则 求 得 一 条 存 放 在 栈 中/(从 栈 底 到 栈 顶)，并 返 回 SUCCESS；否 则 返 回 FA I Lc u rpos=M.st a rt；/设 定”当 前 位 置“为“入 口 位 置”cur s te p=l;/探 索 第 一 步 第 一 次 查 找 途 径，设 立 5 个 方 向(不 远 离!终 点 的 五 个 方 向)，若 找 到 则 返 回 SUCCESS讨 o o i f(P a s s

26、(M,c urpos)/当 前 位 置 可 通 过，即 是 未 曾 走 到 过 的 通 道 块。M.Ma z ec u rpos.row curpo s.col-,；/留 下 足 迹。e.di r e c tio n=1;。e.order=c ur s te p;e.s e a t=c u rpos；。P u sh(S,&e);/加 入 途 径 if(cu r pos.ro w=M.end.r ow&curp o s.c o 1=M.end.col)。/到 达 终 点(出 口)。re t u r n SU C C E SS;0 c u r pos=N e x t Pos(cu r pos,l)

27、；/下 一 位 置 在 当 前 位 置 的 右 下 方 curst e p+；/探 索 下 一 步。e l s e 当 前 位 置 不 能 通 过。i f(!St a ckEm p t y(S)。P op(S,&e);o o w h i l e(e.direct i o n=5&!Stack Empt y(S)。M.Maz e cur p os.rowc u rpo s.c o l-；标 记 不 能 通 过。Pop(S,&e)；/留 下 不 能 通 过 的 标 记，并 退 回 一 步 go/whilei f(e.d irect i on5)g e.dire c t ion+;。GetTop(S

28、,&te);川。i f(e.d irection=5&t e.dire c tion=2)8。P o p(S,&e);e.d irect i o n+;0)。Pus h(S,&e);/换 下 一 个 方 向 探 索。cu r p o s=NextP o s(e.seat,e.d i r ecti o n);/当 前 位 置 设 为 新 方 向 的 相 邻 块。/if。/i f/e Isewhile(!S t a ckEmpty(S);cu rp o s=M.st a r t；/设 定”当 前 位 置 为“入 口 位 置”照 urstep=1;探 索 第 一 步/假 如 第 一 次 查 找 无

29、结 果 则 再 进 行 一 次 八 个 方 向 的 查 找,检 查 是 否 存 在 第 一 次 查 找 不 到 的 特 殊 情 况 0 d o if(P a ss(M,c u rp o s)/当 前 位 置 可 通 过，即 是 未 曾 走 到 过 的 通 道 块 g0。deb邻 066eo oM.Maze L c urpos.row L c urp o s.co 1=,；/留 下 足 迹 e.dire c ti o n=1;o e.o r de r=curs t e p;e.sea t=c ur p o s;Push(S,&e);/加 入 途 径 if(c u rpos.row=M.end.r

30、ow&curp o s.c o l=M.e n d.co 1)/到 达 终 点(出 口)/P rintPat h(ma z e,S);。/输 出 途 径 retur n SUCCES S;c u r p os=N e xtPos(c u r p o sj)；/下 一 位 置 是 当 前 位 置 的 东 c ur s te p+;/探 索 下 一 步)el s e/当 前 位 置 不 能 通 过 if(!St a c kEmpty(S)Pop(S,&e);。whi 1 e(e.dir e c tion=8&!Sta c k Empty(S)。M.M a z ecurpos.row c u rpo

31、 s.c o l-；标 记 不 能 通 过 Pop(S,&e);/留 下 不 能 通 过 的 标 记，并 退 回 一 步。/while。i f(e.d i r ect i on8)e.dir e c t ion+;g Ge t Top(S,&t e);。if(e.di r ect i on=4&t e.di r ect i on=2)00 Pop(S,&e)；。e.d ire c tio n+;d 0 IP u sh(S,&e)；/换 下 一 个 方 向 探 索。c u r p os=Nex t Pos(e.seat,e.dire c tion);/当 前 位 置 设 为 新 方 向 的 相

32、邻 块。/if。/if/els e while(!Stack E mpty(S);6 r e t urn F A I L;/MazePat hv o i d P r intPath(M A Z E M,SqSta c k Pat h)/将 迷 宫 及 途 径 一 起 打 印 i f(Sta c kEmpty(&Path)叩 rinlf(”No P a th!n);/途 径 栈 为 空，则 提 醒 无 途 径。e x it(OVERFLOW)；)p r i n t f(H n T h e P a t h:nn);f or(r o w=0;r o wM.1 e ngth+2;r ow+)for(c

33、 o 1=0;c ol);00num+;叩+；Odd|。吒 1 s e。pri n tf(n%c,M.M a z erow c ol);)opr i ntf(n)；)主 函 数 算 法：v o id main()oMAZE M；q St a ck p a t h;InitS t ac k(&pa t h)；SetM a z e(&M);P r i n t Maze(M);MazePat h(M,&p a t h);Pr i n t P a t h(M,path)；)2.函 数 的 调 用 关 系 反 映 了 本 演 示 程 序 的 层 次 结 构 main 1丁 佐 桂 港 方 迷 宫 德 海

34、I n itStack Ma z e P ath PrintPa t h Pri n tM a z e P a ss Se t M azeSame S eat Ne x t PosPush G e t T op PopStackEm p ty四、调 试 分 析 1、开 始 没 有 将 s tart.e n d 设 立 为 M A Z E 型 数 据 的 下 属 单 元，使 得 各 个 迷 宫 操 作 的 函 数 参 数 十 分 散 杂，调 试 时 各 参 数 关 系 不 易 把 握。2、另 行 设 立 PrintPa t h 函 数，使 得 终 端 输 出 更 加 和 谐，并 巧 妙 地 将

35、迷 宫 以 特 殊、明 朗 的 字 符 输 出，效 果 更 好。3、开 始 出 栈 入 栈 的 条 件 没 有 控 制 好，导 致 输 出 时 不 是 完 整 途 径，甚 至 犯 错。4、选 择 方 向 时 有 一 定 策 略，开 始 选 择 时 按 照 顺 时 针 依 次 读 取 方 向，发 现 太 耗 时 且 效 果 不 好,容 易 出 现 不 必 要 的 弯 折 走 法，后 来 通 过 控 制 方 向 顺 序，即 第 一 方 向 为 东 南 方，然 后 再 东 方、南 方，选 取 越 靠 近 出 口 的 方 向 为 优 先 方 向，由 于 这 样 的 话 搜 索 途 径 时 自 然 会

36、本 着 途 径 最 短 的 原 则 向 出 口 处 行 进，那 么 找 到 的 途 径 自 然 是 最 短 途 径（之 一）。5、由 于 八 个 方 向 的 特 殊 性，根 据 方 向 的 顺 序 及 索 途 径 时 仍 会 出 现 多 走 的 情 况，比 如 先 往 东 再 往 西 南，其 实 是 可 以 直 接 往 南 的，因 此 为 了 避 免 这 种 情 况，在 入 栈 时 还 要 先 进 行 这 种 情 况 的 判 断，如 是 这 种 情 况 则 出 栈 将 前 一 位 置 方 向 改 变 再 入 栈。6、为 了 便 于 找 到 最 短 途 径，起 初 只 使 用 了 靠 近 出 口

37、 处 的 五 个 方 向,但 是 发 现 有 特 殊 情 况 存 在 时 由 于 不 能 想 远 离 出 口 的 方 向 行 进 而 找 不 到 途 径，因 此 在 搜 索 途 径 时 进 行 了 两 次 搜 索，第 一 次 使 用 五 个 靠 进 出 口 的 方 向 搜 索，找 到 途 径 时 则 返 回 SU C C E S S,若 未 搜 索 到 则 再 进 行 一 次 八 个 方 向 的 搜 索，即 为 了 防 止 漏 掉 特 殊 情 况,找 届 时 则 返 回 SUC CESS,由 于 第 一 搜 索 无 结 果 若 第 二 次 搜 索 到 途 径 也 只 能 是 特 殊 情 况，故

38、 也 应 当 是 最 短 途 径（之一）。7、最 大 的 问 题 是 并 没 有 按 照 题 目 规 定 来 做,由 于 题 目 中 规 定 用 队 列 来 存 储 途 径，通 过 实 验 发 现 有 很 多 问 题 难 以 解 决，故 选 择 了 只 用 栈 的 方 法 来 实 现。五、用 户 说 明 1.本 程 序 的 运 营 环 境 为 win d ow s 7（6 4 位）操 作 系 统，执 行 文 献 为 数 据 结 构 迷 宫.ex e;2.进 入 演 示 程 序 后,即 显 示 对 话 形 式 的 提 醒 操 作 过 程，1、提 出 输 入 迷 宫 的 大 小 2、按 enter

39、键 输 出 随 机 生 成 的 迷 宫 3、按 en t e r 键 开 始 搜 索 途 径 搜 索 结 果：The P a t h：输 出 迷 宫 及 途 径 或 者 输 出 No Path!3.提 醒 输 入 迷 宫 大 小 后，用 户 输 入 所 要 解 决 迷 宫 的 长 r。w,宽 col；4.提 醒 输 入 迷 宫 后，用 户 将 迷 宫 输 入,0代 表 可 行，1代 表 障 碍；5.按 任 意 键 开 始 后,程 序 自 动 进 行 对 所 建 迷 宫 的 搜 索，并 将 搜 索 结 果；6.按 任 意 键 退 出 程 序。六、测 试 结 果 1、无 途 径:习 软 件 Mic

40、rosoft Visual S tudio Debug S Q 迷 宫.Please input the length andlength 0length：12width 0width：12修 宫 入 口：H,l 一 用 Jt表 示 族 宫 出 口：H 2,12 一 同 年 小 width of the MAZE：n Q Q Q3 03 Q j Q Path?Q Q3 Q Q Q Q Q Press any0QQ00000QQ0QQQQQto continue2、找 到 最 短 途 径:Please input the length and vi id th of the MAZE：lengt

41、h 0length：15idth 0width：16圈 宫 入 口:t i a 一 用*表 示 修 宫 出 口：115,16 一 用 建 不 Q Q Q Q 0 0 0 0 0 Q 0 0 0 Q 0 0 0 0 0 0 0 13Q Q nQ Q QKzQQQXXQQQ Q Q0 QQ 0 Q Q Q Qto continueQQQy0 0 0 Q 00 0 00 QQ0 Q Qnya七、附 录（源 代 码 及 注 释）#incl u de t ime.h#includ e s t di o.h#in c lude stdlib.h,#i n c 1 u d e uco n io.h#de f

42、 i ne NULL 0#d efin e T R U E 1#d e f ine FA L S E 0#d e f i ne SUCCESS 1#define FA I L 0#d e f i ne OK 1#de f ine ERROR 0#d efine OVERFLOW-1#d efineIN F E A S I BL E-2#de f ine M AXLENGTH 50#d e fin e MAX WIDTH 50#define ST A C K _ IN I T _SIZE 100#d e f in e STACKINCRENT 10/元 素 类 型 typed e f int S

43、 t at u s;typedef struc t oint ro w;i nt col；Po s iti o n；位 置 坐 标 ty p ed e f st r uc t i n t o r d e r;oPositio n s eat；i nt direc t i o n;SElemType;/步 数、方 向 及 位 置 栈 定 义 t y p e d e f s t ruct Inode S ElemT y pe*b a s e;SElemT ype*to p;/设 两 指 针 便 于 判 断 栈 是 否 为 空 in t st a ck s ize;栈 当 前 可 使 用 的 最 大

44、 容 量 SqStac k;/迷 宫 定 义 t y pe d ef i nt ElemTy p e;t ypedef s tr u ct MAZEE 1 e mType M a z eM AXLENGT H MAXW I D T H;o i n t le n g th,width；0Pos i tion s t a r t,en d；M A Z E；迷 宫 大 小 及 出 入 口 位 置/栈 操 作 函 数 声 明 Status I ni t S t a ck(SqStack*S);/初 始 化 Statu s S t ackEmpty(SqSt a ck*S)；/判 空 S t a t u

45、 s GetTop(S q St a ck*s,SElem T ype*e)；取 栈 顶 元 素 Sta t u s Push(SqSta c k*S,S E lemType*e);/入 栈 S t atus P o p(SqStack*s,SE 1 emTy p e*e)；/出 栈/迷 宫 操 作 函 数 说 明void Se t Ma z e(MAZE*M);。/*设 立 迷 宫，随 机 生 成*/void P rintM a ze(MAZE M);。/*输 出 迷 宫*/St a t u s Pas s(MA Z E M,Posi t i o n Cur P os)；判 断 当 前 位

46、置 是 否 可 通 Po s i t ion Nex t Po s(Po s ition C u rPo s,i nt direc t ion r);下 一 位 置 S t atus Sam eS e at(S qStack Path,int row,in t c o l);/找 到 迷 宫 中 可 行 途 径 的 各 个 位 置 Status Maz e Path(MA ZE M,S qSt a ck*P a t h);/搜 索 迷 宫 途 径 v o id Pr i ntP a th(MAZE M,SqStack Path);/若 迷 宫 M 存 在 可 行 途 径 则 将 该 途 径 在

47、 迷 宫 中 输 出/主 函 数 v o id main()oMAZEM;S q Stack p a th；“n i t St a c k(&path);oSetM a ze(&M);PrintMaz e(M);0M a zePa t h(M,&p at h);3 P rintPath(M,p ath);)迷 宫 操 作 void SetMaze(MAZE*M)“n t 1 e ngth,w i d t h,j,k;opr i ntf(Plea s e inp u t t h e 1 eng t h a n d w idth of the MAZE：nle n gt h(0length=5 0

48、):)；scanf(u%d”,&1 e n g th);叩 r i n tf(w i dth(0 w i d th=50):H)；oscanf(0%d,&w idth);sr a n d(un s ign e d)tim e(NU LL)；for(k=0;kMazeOJk=1;。f or(j=0;j M a zej 0=l;f or(j=0;j M aze j wi d t h+l=1;for(k=0；k Maze 1 engt h+1 k=1;“/设 立 迷 宫 围 墙 6for(j=1;j=length;j+)。fo r(k=l;k M az e j k=r a n d()%2;。随 机

49、生 成 迷 宫)Mlength=length;M-wi d th=w i dth；oM-s t ar t,row=1;M-s t a rt.col=l;M-end.r o w=M-length;oM-e n d.c o 1=M-wid t h;M-Maze M-start,r owM-start.c o 1=M M a zeM-en d.r ow M e nd.col=0；/入 口 和 出 口 设 立*/)vo i d P r intMaz e(M AZE M)in t row,c o l;叩 rin tf(迷 宫 入 口:1,1 用#表 达 n)；printf(迷 宫 出 口:1%4%打 一

50、-用#表 达 广 4.怕 1111,4.width);ofor(row=0;rowM.len g th+2;r o w+)。f or(col=0;colM.wid t h+2；co 1+)。if(row=l&c o l=l)|(row=M.1 e n gth&c o l=M.w i d t h)p rin t f(入 口 和 出 口 用#表 达。吒 I s e。3 p r intf(u%c M.M az e r o w c o l);0)printf(Mnn)；)St a tu s Pa s s(MAZE M,Po s itio n Cur P o s)if(M.Ma z e Cur P os