C语言迷宫程序

《C语言迷宫程序》由会员分享，可在线阅读，更多相关《C语言迷宫程序（12页珍藏版）》请在装配图网上搜索。

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

2、通过。现假设耗子从 左上角1,1进入迷宫，编写算法，寻求一条从右下角 m,n出去的路径。下图是一个迷宫的 示意图：算法基本思想迷宫问题是栈应用的一个典型例子。求解过程可采用回溯法。回溯法是一种不断试探且 及时纠正错误的搜索方法。从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向；若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。在求解过程中，为了保证在到达某一点后不能向前继续行走（无路）时，能正确返回前 一点以便继续从下一个方向向前试探， 则需要用一个栈保存所

3、能够到达的每一点的下标及从 该点前进的方向，栈中保存的就是一条迷宫的通路。为了确保程序能够终止，调整时，必须保证曾被放弃过的填数序列不被再次试验，即要 求按某种有序模型生成填数序列。 给解的候选者设定一个被检验的顺序， 按这个顺序逐一生 成候选者并检验。三 主要数据结构1. 方阵栈：#define STACK_INI_SIZE 100typedef structint *top;/ 指向栈的顶端域int *base;/ 指向栈的低端域int length;/ 栈的长度int stacksize;/ 栈的最大长度sqstack;2产生迷宫的矩阵二维数组为了使每一个迷宫存在迷宫的边界和两个端口：入

4、口、出口， 设置了一个二维数组，在迷宫 的周边定义为 1使得迷宫存在边界，并在(1,1) , (x-2,y-2)初定义为0，即定义迷宫的出 口，大大减小了无解的情况。for(i=0;ix;i+)for(j=0;jy;j+)mgij=rand()%3;/ 产生随机数i=0;for(j=0;jy;j+)mgij=1;/ 定义边界mgji=1;i=y-1;for(j=0;jx;j+)/ 定义边界mgji=1;i=x-1;for(j=0;jy;j+)mgij=1;mg11=0;/ 定义出口和入口mgx-2y-2=0;四 主要函数功能1. void initstack(sqstack *s);/* 初始

5、化栈 */100的空间，将栈的原始长将栈顶和栈底分别申请一段动态存储空间，将栈分配长度为 度定义为22. void stackpush(sqstack *s,int);/*增加栈顶 */将栈的动态存储空间增加50,将栈顶指针上移相应高度，特殊情况单独考虑见程序。3. void stackpop(sqstack *s);/*撤销栈顶 */ 栈空提示无法删除，其他情况删除栈顶。4. void stackinput(sqstack *s);/*输出栈 */输出寻找到的一条迷宫路径5. int mgway(sqstack *s);/*迷宫路径 */ 寻找到可执行的一条迷宫路径6. void desto

6、rystack(sqstack *s);/*撤销栈 S*/将栈内元素清空7. void makemg(sqstack *s);/*制造迷宫 */ 输入迷宫的长宽(2-15),并产生迷宫图五.算例(生成演算结果)本程序的运算环境为：codeblocks 输入界面：输入错误则重新输入|巨11 i0 10 18 1Q12345678 910111213匸:Wse巧弹rvthonyXDesla1 i 1l_f 1 8 32- 1 8 33- 1 1 14*1 1111迷莒正确尼ldlrUl)kil,02JS2(!l2( 02,93 ) C03,03还盘也续么丁 竄入错误请重新输人重新输入结果:呼秒后无

7、袪显示岀迷宫样本请畫试0-1 1111 1-1 0 0 0 12- 1 01093- 1 01104- 1 110 35- 1 B Q B 161 0 0 0 1 7F 10 0 38 -1 0 1Q19 -1 0 0 0 010- 1 10 1311- 1 0 0 0 012-1 0109 1111医宫正确路径111111111 009011001 00H116101 10100011 01818101 191006001 10300001 80B1188S1 016111011 009000001 01100001 00900101B010611Q1 111111111kR4,m y fi

8、7,0?,10X0?,11?10.11X10,12X11,12X12么？.可以看到每个迷宫都存在“围墙”六 分析算法1. 空间复杂度固定空间需求： 25*25 的二维迷宫数组 可变空间需求：初始化栈中申请了 100 倍 int 型所占空间大小的动态空间，加入栈顶时 额外申请 50倍 int 型所占空间大小2. 时间复杂度可以通过“程序步”对程序的时间复杂度进行测量，可以引入 count 计数器进行测量， 考虑到其复杂程度，本程序将不采用此方法。本程序的排错率较高，计算机会改掉没有 通路的栈，并随机生成有通路迷宫，提高了程序的执行效率，并给迷宫添加了必要的围 墙和出口、入口有助于执行效率的提高。

9、但对于路径的搜索，栈并没有引入方向指针， 在后面，通过 flag 进行标记来确定栈的路径的寻找的，一定程度上会影响执行效率。附录： C 语言源程序#include #include#define STACK_INI_SIZE 100#define STACKINCREMENT 50#define NULL 0typedef structint *top;int *base;int length;int stacksize;sqstack;int mg2525;int m=1,n=1,x,y; /*/ main()void initstack(sqstack *s);/* 初始化栈 */ voi

10、d stackpush(sqstack *s,int);/* 增加栈顶 */ void stackpop(sqstack *s);/* 撤销栈顶 */ void stackinput(sqstack *s);/* 输出栈 */ int mgway(sqstack *s);/* 迷宫路径 */ void destorystack(sqstack *s);/*撤销栈 S*/ void makemg(sqstack *s);/*制造迷宫 */ sqstack s;int i,flag1=1,flag2=1,flag3=1;char ch; srand(unsigned)time(NULL);whil

11、e(flag1)initstack(&s);flag2=1;makemg(&s); i=mgway(&s);if(i=0)printf( 此迷宫没有通路 n);elsestackinput(&s); destorystack(&s);printf( 还继续么 ?);fflush(stdin); scanf(%c,&ch);while(flag2)if(ch=n|ch=N)flag1=0;flag2=0;else if(ch=y|ch=Y)flag1=1;flag2=0;elseprintf( 输入错误请重新输入 );fflush(stdin);scanf(%c,&ch);/*/void ini

12、tstack(sqstack *s)/* 初始化栈 */s-top=s-base=(int *)malloc(STACK_INI_SIZE*sizeof(int); if(!s-base)exit(1);s-stacksize=STACK_INI_SIZE;*(s-base)=0;s-top+;*(s-top)=101;s-top+;s-length=2;/*/void stackpush(sqstack *s,int i)/* 增加栈顶 */ if(s-length=s-stacksize)printf( 路过 );s-base=(int *)realloc(s-base,(STACK_IN

13、I_SIZE+STACKINCREMENT)*sizeof(int); if(!s-base)exit(1);s-top=s-base+s-length;s-stacksize+=STACKINCREMENT; stackinput(s);if(s-length=0)*(s-base)=i;s-top+;s-length+;else*(s-top)=i;s-top+;s-length+;/*/void stackpop(sqstack *s)/* 删除栈顶 */if(s-length=0)printf( 栈空 无法删除 );if(s-length=1)s-top-;*(s-top)=*(s-b

14、ase)=NULL;s-length=0;elses-top-;*(s-top)=NULL;s-length-;/*/void stackinput(sqstack *s)/* 迷宫栈的输出 */int w,x,y,z,i=0,*p; p=s-base;p+;printf( 迷宫正确路径 n);while(p!=s-top) printf(%d%d,%d%d),x=*p/1000,y=*p/100%10,z=*p%100/10,w=*p%10);p+;i+;if(i=7) printf(n); i=0;/*/int mgway(sqstack *s)/* 迷宫路径 */int gudge(sq

15、stack *s,int);/* 判断是否能通行 */ int homing(sqstack *s);/* 退栈后 I 所对应的方向 */ int i=1,j,k;while(s-top!=s-base)if(i5) j=gudge(s,i);if(j=1&itop; q=s-base; q+;p-;while(p!=q&*p!=i)p-;if(*p=i) return(0);elsereturn(1);/*/int homing(sqstack *s)/*i 退位后所对应的方向 */int a,b,c,d,*q;q=s-top;q-;a=(*q)/100;b=(*q)%100;q-;c=(*

16、q)/100;d=(*q)%100;m=(*q)/100;n=(*q)%100; if(a=c)if(d-b=1)return(3);else if(d-b=-1)return(1);else if(b=d)if(c-a=1)return(4);else if(c-a=-1)return(2);return(0);void destorystack(sqstack *s) if(*(s-base)!=NULL) free(s-base);s-length=0;/*/void makemg(sqstack *s)/* 创建迷宫及输出迷宫图的函数 */ int mgway(sqstack *s);

17、void clearstack(sqstack *s);int flag=1,flag2=1,i,j,k;char ch;while(flag)printf( 请输入迷宫的长宽 (长度范围 2-15,宽范围 2-15)n);printf( 输入长 );fflush(stdin);scanf(%d,&y);printf( 输入宽 );fflush(stdin);scanf(%d,&x);if(x3&y3&y16)flag=0;if(flag=0)printf( 自动筛选能通过的迷宫需要一段时间,请耐心等待 ,如 20秒后无法显示出迷宫样本请重试 . .n);flag=1;while(flag2)

18、m=1;n=1;for(i=0;ix;i+)for(j=0;jy;j+)mgij=rand()%3;i=0;for(j=0;jy;j+)mgij=1;mgji=1;i=y-1;for(j=0;jx;j+)mgji=1;i=x-1;for(j=0;jy;j+)mgij=1;mg11=0;mgx-2y-2=0;k=mgway(s);if(k=1)flag2=0;elseclearstack(s);printf( );for(i=0;iy;i+)printf(%2d,i);printf(n );for(i=0;iy;i+)printf( J ”)；printf(n);for(i=0；ix；i+)printf(%2d”,i);for(j=0；jtop=s-base;*(s-base)=0;s-top+;*(s-top)=101;s-top+;s-length=2;此文档可自行编辑修改，如有侵权请告知删除，感谢您的支持，我们会努力把内容做得更 好