基于栈的C语言迷宫问题与实现精品资料.docx

《基于栈的C语言迷宫问题与实现精品资料.docx》由会员分享，可在线阅读，更多相关《基于栈的C语言迷宫问题与实现精品资料.docx（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构与算法实验报告基于栈的C语言迷宫问题与实现一 问题描述多年以来，迷宫问题一直是令人感兴趣的题目。实验心理学家训练老鼠在迷宫中寻找食物。许多神秘主义小说家也曾经把英国乡村花园迷宫作为谋杀现场。于是，老鼠过迷宫问题就此产生，这是一个很有趣的计算机问题，主要利用 “栈”是老鼠通过尝试的办法从入口穿过迷宫走到出口。迷宫只有两个门，一个叫做入口，另一个叫做出口。把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。求解迷宫问题，即找出从入口到出口的路径。一个迷宫可用上图所示方阵m,n表示

2、，0表示能通过，1 表示不能通过。现假设耗子从左上角1,1进入迷宫，编写算法，寻求一条从右下角m,n 出去的路径。下图是一个迷宫的示意图：迷宫示意图二 算法基本思想迷宫求解问题是栈的一个典型应用。基本算法思想是：在某个点上，按照一定的顺序（在本程序中顺序为上、右、下、左）对周围的墙、路进行判断（在本程序中分别用1、0）代替，若周围某个位置为0，则移动到该点上，再进行下一次判断；若周围的位置都为1（即没有通路），则一步步原路返回并判断有无其他通路，然后再次进行相同的判断，直到走到终点为止，或者确认没有任何通路后终止程序。要实现上述算法，需要用到栈的思想。栈里面压的是走过的路径，若遇到死路，则将该

3、位置（在栈的顶层）弹出，再进行下一次判断；若遇到通路，则将该位置压栈并进行下一次判断。如此反复循环，直到程序结束。此时，若迷宫有通路，则栈中存储的是迷宫通路坐标的倒序排列，再把所有坐标顺序打印后，即可得到正确的迷宫通路。三 程序具体部分的说明1. 迷宫的生成根据题目的要求，迷宫的大小是自定义输入的。所以在程序中用malloc申请动态二维数组。数组中的元素为随机生成的0、1。数组周围一圈的元素全部定义为1，以表示边界。2. 栈的C语言实现为了实现栈的功能，即清空、压栈、弹出、返回栈顶元素，在程序中编写了相应的函数。MakeNULL 清空栈Push 将横、纵坐标压栈Topx 返回栈顶存储的横坐标T

4、opy 返回栈顶存储的纵坐标Pop 弹出栈顶元素3. 具体的判断算法当位置坐标（程序中为X Y）移到某一位置时，将这个位置的值赋值为1并压栈，以说明该点已经走过。接着依次判断该点的上、右、下、左是否为0，若有一方为0，则移动到该位置上，进行下次判断；若为周围位置全部是1，则将该点压栈后不断弹出，每次弹出时判断栈顶元素（即走过的路）周围有无其他通路。如果有的话，则选择该方向继续走下去；如果栈已经为空仍然没有找到出路，则迷宫没有出口程序结束。当X Y走到出口坐标时，程序判断部分结束。栈里面存储的是每个走过的点的坐标，将这些横纵坐标分别存储在两个数组中，最后将数组中的坐标元素倒序输出，即得到了完整的

5、路径。四 程序源代码及注释 / Maze.cpp : 定义控制台应用程序的入口点。/#include stdafx.h#include#include#include#include #includetypedef int Elementtype;struct nodeElementtype val1;Elementtype val2; node *next;/定义结构体typedef node *MAZE;void MakeNull(MAZE &S);void Push(Elementtype x,Elementtype y, MAZE S);void Pop(MAZE S);Element

6、type Topx(MAZE S);Elementtype Topy(MAZE S);/申明函数int _tmain(int argc, _TCHAR* argv)int *p,*q,*x1,*y1,i,j,k,n1,n2,m1,m2,l,w,max;int x,y;int a,b,c,d; printf(输入迷宫长度及宽度l和wn); scanf(%d %d,&l,&w);getchar();n1=w+2;n2=l+2;/为迷宫加上边界max=n1*n2; p=(int*)malloc(n1*sizeof(int); for(i=0;in1;i+) pi=(int *)malloc(n2*s

7、izeof(int);/生成二维动态数组 srand(time(NULL);x1=(int*)malloc(max*sizeof(int);/生成动态数组用于存储路径y1=(int *)malloc(max*sizeof(int);/生成动态数组用于存储路径 for(i=0;imax;i+) x1i=0;for(i=0;imax;i+) y1i=0;/先将存储路径的数组元素全赋值为0 for(i=0;in1;i+) for(j=0;jn2;j+) if(i=0 | j=0) pij=1; else if(i=n1-1 | j=n2-1) pij=1; else pij=rand()%2+0;

8、/生成二维1 0随机数组p11=0;pn1-2n2-2=0;/定义迷宫的入口及出口 printf(生成的迷宫如下（代表墙0代表路）：n); for(i=0;in1;i+) for(j=0;j=0;) if(x1i!=0 & (x1i!=x1i-1 | y1i!=y1i-1) printf( ,x1i,y1i); i-; else if(x1i!=0 & (x1i=x1i-1 & y1i=y1i-1) printf( ,x1i,y1i); i=i-2; else i-;/倒序打印数组得到顺序出路坐标printf(,n1-2,n2-2);/打印出口坐标 getchar();return 0;voi

9、d MakeNull(MAZE &S) /清空栈的函数S = new node;S-next = NULL;void Push(Elementtype x,Elementtype y, MAZE S)/压栈函数MAZE stk;stk = new node;stk-val1 = x;stk-val2 = y;stk-next = S-next;S-next = stk;void Pop(MAZE S)/弹出函数MAZE stk;if(S-next)stk = S-next;S-next = stk-next;delete stk;Elementtype Topx(MAZE S)/返回横坐标函数

10、if(S-next)return(S-next-val1);elsereturn NULL;Elementtype Topy(MAZE S)/返回纵坐标函数if(S-next)return(S-next-val2);elsereturn NULL;五 程序运行结果运行程序后，首先输入迷宫的长度和宽度假设迷宫是8*8的（也可以为其他大小）。输入后若没有出路，则显示“There is no way out”,程序结束。输入后若迷宫有出路，则显示Success再次按下回车键，则打印出迷宫路径程序结束六 程序运行结果自评该程序运用栈的思想，成功解决了迷宫问题。下面对上述运行结果进行简要分析：当迷宫没有

11、出路时，系统首先走到2,2点弹出，发现2,1点下方为出路，然后继续向下走。但是走到5,1点时发现周围再次为死路，只能不停弹出，同时检测周围有无出路。当弹出到1,1，点时，发现迷宫没有出路，程序结束。当迷宫有出路时，系统按照既定规则移动，在3,5点时并未直接向下走向4,5点，而是按照判断顺序向右移动。当走到1,8点时发现为死路，则不停弹出并且检测周围有无出路。弹出到3,5时发现4,5可以走，则继续走下去，直到走到终点，程序结束。在调试程序时，对栈顶元素进行观测，当程序分步执行时，可以清楚地看到栈里面元素的变化，从而分析出程序完成了的压栈、弹出的步骤。在编写与调试程序的过程中，我遇到了很多问题。其

12、中最主要的有动态数组的生成、对栈的概念的理解与栈的实现、具体算法的判断标准与循环结束条件等等。通过加设断点、分步执行程序、观测变量值等方法，不断对程序进行改进，直到最终成型。在这过程中，我对C语言的使用有了进一步的熟悉，对栈的思想有了更深入的了解。附录资料:不需要的可以自行删除bat文件的基本应用bat是dos下的批处理文件 .cmd是nt内核命令行环境的另一种批处理文件 从更广义的角度来看，unix的shell脚本以及其它操作系统甚至应用程序中由外壳进行解释执行的文本，都具有与批处理文件十分相似的作用，而且同样是由专用解释器以行为单位解释执行，这种文本形式更通用的称谓是脚本语言。所以从某个程

13、度分析，batch, unix shell, awk, basic, perl 等脚本语言都是一样的，只不过应用的范围和解释的平台各有不同而已。甚至有些应用程序仍然沿用批处理这一称呼，而其内容和扩展名与dos的批处理却又完全不同。 = 首先批处理文件是一个文本文件，这个文件的每一行都是一条DOS命令（大部分时候就好象我们在DOS提示符下执行的命令行一样），你可以使用DOS下的Edit或者Windows的记事本(notepad)等任何文本文件编辑工具创建和修改批处理文件。 = 注 = 批处理文件中完全可以使用非dos命令，甚至可以使用不具有可执行特性的普通数据性文件，这缘于windows系统这个

14、新型解释平台的涉入，使得批处理的应用越来越边缘化。所以我们讨论的批处理应该限定在dos环境或者命令行环境中，否则很多观念和设定都需要做比较大的变动。 = 其次，批处理文件是一种简单的程序，可以通过条件语句(if)和流程控制语句(goto)来控制命令运行的流程，在批处理中也可以使用循环语句(for)来循环执行一条命令。当然，批处理文件的编程能力与C语言等编程语句比起来是十分有限的，也是十分不规范的。批处理的程序语句就是一条条的DOS命令（包括内部命令和外部命令），而批处理的能力主要取决于你所使用的命令。 = 注 = 批处理文件(batch file)也可以称之为批处理程序(batch progr

15、am)，这一点与编译型语言有所不同，就c语言来说，扩展名为c或者cpp的文件可以称之为c语言文件或者c语言源代码，但只有编译连接后的exe文件才可以称之为c语言程序。因为批处理文件本身既具有文本的可读性，又具有程序的可执行性，这些称谓的界限是比较模糊的。 = 第三，每个编写好的批处理文件都相当于一个DOS的外部命令，你可以把它所在的目录放到你的DOS搜索路径(path)中来使得它可以在任意位置运行。一个良好的习惯是在硬盘上建立一个bat或者batch目录（例如C:BATCH），然后将所有你编写的批处理文件放到该目录中，这样只要在path中设置上c:batch，你就可以在任意位置运行所有你编写的

16、批处理程序。 = 注 = 纯以dos系统而言，可执行程序大约可以细分为五类，依照执行优先级由高到低排列分别是：DOSKEY宏命令（预先驻留内存），COMMAND.COM中的内部命令（根据内存的环境随时进驻内存），以com为扩展名的可执行程序（由 直接载入内存），以exe位扩展名的可执行程序（由 重定位后载入内存），以bat位扩展名的批处理程序（由 解释分析，根据其内容按优先级顺序调用第2，3，4，5种可执行程序，分析一行，执行一行，文件本身不载入内存） = 第四，在DOS和Win9x/Me系统下，C:盘根目录下的AUTOEXEC.BAT批处理文件是自动运行批处理文件，每次系统启动时会自动运行该

17、文件，你可以将系统每次启动时都要运行的命令放入该文件中，例如设置搜索路径，调入鼠标驱动和磁盘缓存，设置系统环境变量等。下面是一个运行于Windows 98下的autoexec.bat的示例： ECHO OFF PATH C:WINDOWS;C:WINDOWSCOMMAND;C:UCDOS;C:DOSTools; C:SYSTOOLS;C:WINTOOLS;C:BATCH LH SMARTDRV.EXE /X LH DOSKEY.COM /insert LH CTMOUSE.EXE SET TEMP=D:TEMP SET TMP=D:TEMP = 注 = AUTOEXEC.BAT为DOS系统的自

18、动运行批处理文件，由COMMAND.COM启动时解释执行； 而在Win9x环境中，不仅增加支持了 DOSSTART.BAT, WINSTART.BAT 等许多其它自动运行的批处理文件，对AUTOEXEC.BAT 也增加了 .DOS .W40 .BAK .OLD .PWS 等许多变体以适应复杂的环境和多变的需求。 = willsort 编注 = 以下关于命令的分类，有很多值得推敲的地方。常用命令中的本不是命令，而dir、copy等也很常用的命令却没有列入, 而特殊命令中所有命令对我来说都是常用命令。建议将批处理所引用的命令分为内部命令、外部命令、第三方程序三类。而内部命令和外部命令中别有一类是专

19、用于或常用于批处理中的命令可称之为批处理命令。 以下摘录MS-DOS 6.22 帮助文档中关于批处理命令的文字，当然，其中有些概念和定义已经有些落后了。 批处理命令 批处理文件或批处理程序是一个包含若干MS-DOS命令的正文文件，扩展名为.BAT。当在命令提示符下敲入批处理程序的名称时，MS-DOS成组执行此批处理程序中的命令。 任何在命令提示符下可使用的命令都可用在批处理程序中。此外，下面MS-DOS命令是专门在批处理程序中使用的。 = 常用命令 echo、call、pause、rem(小技巧：用:代替rem)是批处理文件最常用的几个命令，我们就从他们开始学起。 = 注 = 首先, 不是一个

20、命令, 而是DOS 批处理的一个特殊标记符, 仅用于屏蔽命令行回显. 下面是DOS命令行或批处理中可能会见到的一些特殊标记符: CR(0D) 命令行结束符 Escape(1B) ANSI转义字符引导符 Space(20) 常用的参数界定符 Tab(09) ; = 不常用的参数界定符 + COPY命令文件连接符 * ? 文件通配符 字符串界定符 | 命令管道符 文件重定向符 命令行回显屏蔽符 / 参数开关引导符 : 批处理标签引导符 % 批处理变量引导符 其次, : 确实可以起到rem 的注释作用, 而且更简洁有效; 但有两点需要注意: 第一, 除了 : 之外, 任何以 :开头的字符行, 在批处

21、理中都被视作标号, 而直接忽略其后的所有内容, 只是为了与正常的标号相区别, 建议使用 goto 所无法识别的标号, 即在 :后紧跟一个非字母数字的一个特殊符号. 第二, 与rem 不同的是, :后的字符行在执行时不会回显, 无论是否用echo on打开命令行回显状态, 因为命令解释器不认为他是一个有效的命令行, 就此点来看, rem 在某些场合下将比 : 更为适用; 另外, rem 可以用于 config.sys 文件中. = echo 表示显示此命令后的字符 echo off 表示在此语句后所有运行的命令都不显示命令行本身 与echo off相象，但它是加在每个命令行的最前面，表示运行时不

22、显示这一行的命令行（只能影响当前行）。 call 调用另一个批处理文件（如果不用call而直接调用别的批处理文件，那么执行完那个批处理文件后将无法返回当前文件并执行当前文件的后续命令）。 pause 运行此句会暂停批处理的执行并在屏幕上显示Press any key to continue.的提示，等待用户按任意键后继续 rem 表示此命令后的字符为解释行（注释），不执行，只是给自己今后参考用的（相当于程序中的注释）。 = 注 = 此处的描述较为混乱, 不如直接引用个命令的命令行帮助更为条理 - ECHO 当程序运行时，显示或隐藏批处理程序中的正文。也可用于允许或禁止命令的回显。 在运行批处理

23、程序时，MS-DOS一般在屏幕上显示（回显）批处理程序中的命令。 使用ECHO命令可关闭此功能。 语法 ECHO ON|OFF 若要用echo命令显示一条命令，可用下述语法： echo message 参数 ON|OFF 指定是否允许命令的回显。若要显示当前的ECHO的设置，可使用不带参数的ECHO 命令。 message 指定让MS-DOS在屏幕上显示的正文。 - CALL 从一个批处理程序中调用另一个批处理程序，而不会引起第一个批处理的中止。 语法 CALL drive:pathfilename batch-parameters 参数 drive:pathfilename 指定要调用的批处

24、理程序的名字及其存放处。文件名必须用.BAT作扩展名。 batch-parameters 指定批处理程序所需的命令行信息。 - PAUSE 暂停批处理程序的执行并显示一条消息，提示用户按任意键继续执行。只能在批处 理程序中使用该命令。 语法 PAUSE REM 在批处理文件或CONFIG.SYS中加入注解。也可用REM命令来屏蔽命令（在CONFIG.SYS 中也可以用分号 ; 代替REM命令，但在批处理文件中则不能替代）。 语法 REM string 参数 string 指定要屏蔽的命令或要包含的注解。 = 例1：用edit编辑a.bat文件，输入下列内容后存盘为c:a.bat，执行该批处理文

25、件后可实现：将根目录中所有文件写入 a.txt中，启动UCDOS，进入WPS等功能。 批处理文件的内容为: 命令注释： echo off 不显示后续命令行及当前命令行 dir c:*.* a.txt 将c盘文件列表写入a.txt call c:ucdosucdos.bat 调用ucdos echo 你好 显示你好 pause 暂停,等待按键继续 rem 准备运行wps 注释：准备运行wps cd ucdos 进入ucdos目录 wps 运行wps 批处理文件的参数 批处理文件还可以像C语言的函数一样使用参数（相当于DOS命令的命令行参数），这需要用到一个参数表示符%。 %1-9表示参数，参数是

26、指在运行批处理文件时在文件名后加的以空格（或者Tab）分隔的字符串。变量可以从%0到%9，%0表示批处理命令本身，其它参数字符串用%1到%9顺序表示。 例2：C:根目录下有一批处理文件名为f.bat，内容为： echo off format %1 如果执行C:f a: 那么在执行f.bat时，%1就表示a:，这样format %1就相当于format a:，于是上面的命令运行时实际执行的是format a: 例3：C:根目录下一批处理文件名为t.bat，内容为: echo off type %1 type %2 那么运行C:t a.txt b.txt %1 : 表示a.txt %2 : 表示b

27、.txt 于是上面的命令将顺序地显示a.txt和b.txt文件的内容。 = 注 = 参数在批处理中也作为变量处理, 所以同样使用百分号作为引导符, 其后跟0-9中的一个数字构成参数引用符. 引用符和参数之间 (例如上文中的 %1 与 a: ) 的关系类似于变量指针与变量值的关系. 当我们要引用第十一个或更多个参数时, 就必须移动DOS 的参数起始指针. shift 命令正充当了这个移动指针的角色, 它将参数的起始指针移动到下一个参数, 类似C 语言中的指针操作. 图示如下: 初始状态, cmd 为命令名, 可以用 %0 引用 cmd arg1 arg2 arg3 arg4 arg5 arg6

28、arg7 arg8 arg9 arg10 | | | | | | | | | | %0 %1 %2 %3 %4 %5 %6 %7 %8 %9 经过1次shift后, cmd 将无法被引用 cmd arg1 arg2 arg3 arg4 arg5 arg6 arg7 arg8 arg9 arg10 | | | | | | | | | | %0 %1 %2 %3 %4 %5 %6 %7 %8 %9 经过2次shift后, arg1也被废弃, %9指向为空, 没有引用意义 cmd arg1 arg2 arg3 arg4 arg5 arg6 arg7 arg8 arg9 arg10 | | | | |

29、 | | | | %0 %1 %2 %3 %4 %5 %6 %7 %8 遗憾的是, win9x 和DOS下均不支持 shift 的逆操作. 只有在 nt 内核命令行环境下, shift 才支持 /n 参数, 可以以第一参数为基准返复移动起始指针. = 特殊命令 if goto choice for是批处理文件中比较高级的命令，如果这几个你用得很熟练，你就是批处理文件的专家啦。 一、if 是条件语句，用来判断是否符合规定的条件，从而决定执行不同的命令。 有三种格式: 1、if not 参数 = 字符串 待执行的命令 参数如果等于(not表示不等，下同)指定的字符串，则条件成立，运行命令，否则运行

30、下一句。 例：if %1=a format a: = if 的命令行帮助中关于此点的描述为: IF NOT string1=string2 command 在此有以下几点需要注意: 1. 包含字符串的双引号不是语法所必须的, 而只是习惯上使用的一种防空字符 2. string1 未必是参数, 它也可以是环境变量, 循环变量以及其他字符串常量或变量 3. command 不是语法所必须的, string2 后跟一个空格就可以构成一个有效的命令行 = 2、if not exist 路径文件名 待执行的命令 如果有指定的文件，则条件成立，运行命令，否则运行下一句。 如: if exist c:con

31、fig.sys type c:config.sys 表示如果存在c:config.sys文件，则显示它的内容。 * 注 * 也可以使用以下的用法: if exist command device 是指DOS系统中已加载的设备, 在win98下通常有: AUX, PRN, CON, NUL COM1, COM2, COM3, COM4 LPT1, LPT2, LPT3, LPT4 XMSXXXX0, EMMXXXX0 A: B: C: ., CLOCK$, CONFIG$, DblBuff$, IFS$HLP$ 具体的内容会因硬软件环境的不同而略有差异, 使用这些设备名称时, 需要保证以下三点:

32、 1. 该设备确实存在(由软件虚拟的设备除外) 2. 该设备驱动程序已加载(aux, prn等标准设备由系统缺省定义) 3. 该设备已准备好(主要是指a: b: ., com1., lpt1.等) 可通过命令 mem/d | find device /i 来检阅你的系统中所加载的设备 另外, 在DOS系统中, 设备也被认为是一种特殊的文件, 而文件也可以称作字符设备; 因为设备(device)与文件都是使用句柄(handle)来管理的, 句柄就是名字, 类似于文件名, 只不过句柄不是应用于磁盘管理, 而是应用于内存管理而已, 所谓设备加载也即指在内存中为其分配可引用的句柄. = 3、if er

33、rorlevel 待执行的命令 很多DOS程序在运行结束后会返回一个数字值用来表示程序运行的结果(或者状态)，通过if errorlevel命令可以判断程序的返回值，根据不同的返回值来决定执行不同的命令(返回值必须按照从大到小的顺序排列)。如果返回值等于指定的数字，则条件成立，运行命令，否则运行下一句。 如if errorlevel 2 goto x2 = 注 = 返回值从大到小的顺序排列不是必须的, 而只是执行命令为 goto 时的习惯用法, 当使用 set 作为执行命令时, 通常会从小到大顺序排列, 比如需将返回码置入环境变量, 就需使用以下的顺序形式: if errorlevel 1 s

34、et el=1 if errorlevel 2 set el=2 if errorlevel 3 set el=3 if errorlevel 4 set el=4 if errorlevel 5 set el=5 . 当然, 也可以使用以下循环来替代, 原理是一致的: for %e in (1 2 3 4 5 6 7 8.) do if errorlevel %e set el=%e 更高效简洁的用法, 可以参考我写的另一篇关于获取 errorlevel 的文章 出现此种现象的原因是, if errorlevel 比较返回码的判断条件并非等于, 而是大于等于. 由于 goto 的跳转特性,

35、由小到大排序会导致在较小的返回码处就跳出; 而由于 set命令的 重复 赋值特性, 由大到小排序会导致较小的返回码 覆盖 较大的返回码. 另外, 虽然 if errorlevel= command 也是有效的命令行, 但也只是 解释命令行时将 = 作为命令行切分符而忽略掉罢了 = 二、goto 批处理文件运行到这里将跳到goto所指定的标号(标号即label，标号用:后跟标准字符串来定义)处，goto语句一般与if配合使用，根据不同的条件来执行不同的命令组。 如: goto end :end echo this is the end 标号用:字符串来定义，标号所在行不被执行。 = willsort 编注 label 常被译为 标签 , 但是这并不具有广泛的约定性. goto 与 : 联用可实现执行中途的跳转, 再结合 if 可实现执行过程的条件分支, 多个 if 即可实现命令的分组, 类似 C 中 switch case 结构或者 Basic 中的 select case 结构, 大规模且结构化的命令分组即可实现高级语言中的函数功能. 以下是批处理和C/Basic在语法结构上的对照: Batch