基于栈的C语言迷宫问题与实现一．问题描述多年以来，迷宫问题一直是令人感兴趣的题目。实验心理学家训练老鼠在迷宫中寻找食物。许多神秘主义小说家也曾经把英国乡村花园迷宫作为谋杀现场。于是，老鼠过迷宫问题就此产生，这是一个很有趣的计算机问题，主要利用“栈”是老鼠通过尝试的办法从入口穿过迷宫走到出口。迷宫只有两个门，一个叫做入口，另一个叫做出口。把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。求解迷宫问题，即找出从入口到出口的路径。一个迷宫可用上图所示方阵[m,n]
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示，0表示能通过，1表示不能通过。现假设耗子从左上角[1,1]进入迷宫，编写算法，寻求一条从右下角[m,n]出去的路径。下图是一个迷宫的示意图：入口出口迷宫示意图二．算法基本思想迷宫问题是栈应用的一个典型例子。求解过程可采用回溯法。回溯法是一种不断试探且及时纠正错误的搜索方法。从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向;若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。在求解过程中，为了保证在到达某一点后不能向前继续行走（无路）时，能正确返回前可编辑范本一点以便继续从下一个方向向前试探，则需要用一个栈保存所能够到达的每一点的下标及从该点前进的方向，栈中保存的就是一条迷宫的通路。为了确保程序能够终止，调整时，必须保证曾被放弃过的填数序列不被再次试验，即要求按某种有序模型生成填数序列。给解的候选者设定一个被检验的顺序，按这个顺序逐一生成候选者并检验。三．主要数据结构方阵栈：#defineSTACK_INI_SIZE100typedefstruct{int*top;//指向栈的顶端域int*base;//指向栈的低端域intlength;//栈的长度intstacksize;//栈的最大长度}sqstack;2．产生迷宫的矩阵二维数组为了使每一个迷宫存在迷宫的边界和两个端口：入口、出口，设置了一个二维数组，在迷宫的周边定义为1，使得迷宫存在边界，并在（1,1），（x-2,y-2）初定义为0，即定义迷宫的出口，大大减小了无解的情况。for(i=0;i
#include#defineSTACK_INI_SIZE100#defineSTACKINCREMENT50#defineNULL0typedefstruct{int*top;int*base;intlength;intstacksize;}sqstack;intmg[25][25];intm=1,n=1,x,y;/*********************************************/main(){voidinitstack(sqstack*s);/*初始化栈*/voidstackpush(sqstack*s,int);/*增加栈顶*/voidstackpop(sqstack*s);/*撤销栈顶*/voidstackinput(sqstack*s);/*输出栈*/intmgway(sqstack*s);/*迷宫路径*/voiddestorystack(sqstack*s);/*撤销栈S*/voidmakemg(sqstack*s);/*制造迷宫*/sqstacks;inti,flag1=1,flag2=1,flag3=1;charch;srand((unsigned)time(NULL));while(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;}elseif(ch=='y'||ch=='Y'){flag1=1;flag2=0;}else{printf("输入错误请重新输入");fflush(stdin);scanf("%c",&ch);}}}}/*********************************************/voidinitstack(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;}/*********************************************/voidstackpush(sqstack*s,inti)/*增加栈顶*/{if(s->length>=s->stacksize){printf("路过");s->base=(int*)realloc(s->base,(STACK_INI_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++;}}/*********************************************/voidstackpop(sqstack*s)/*删除栈顶*/{if(s->length==0)printf("栈空无法删除");if(s->length==1){s->top--;*(s->top)=*(s->base)=NULL;s->length=0;}else{s->top--;*(s->top)=NULL;s->length--;}}/*********************************************/voidstackinput(sqstack*s)/*迷宫栈的输出*/{intw,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;}}}/*********************************************/intmgway(sqstack*s)/*迷宫路径*/{intgudge(sqstack*s,int);/*判断是否能通行*/inthoming(sqstack*s);/*退栈后I所对应的方向*/inti=1,j,k;while(s->top!=s->base){if(i<5)j=gudge(s,i);if(j==1&&i<5){k=m*100+n;stackpush(s,k);if(m==y-2&&n==x-2){return(1);}elsei=1;}else{if(m==0&&n==0)return(0);elseif(i==4||i==5){i=homing(s);stackpop(s);i++;}elsei++;}可编辑范本}return(0);}/*********************************************/intgudge(sqstack*s,inti)/*退栈后i所对应的方向*/{intecho(sqstack*s);if(i==1)n++;if(i==2)m++;if(i==3)n--;if(i==4)m--;if((mg[m][n]==0||mg[m][n]==2)&&echo(s))return(1);else{if(i==1)n--;if(i==2)m--;if(i==3)n++;if(i==4)m++;return(0);}}/*********************************************/intecho(sqstack*s){inti,*p,*q;i=m*100+n;p=s->top;q=s->base;q++;p--;while(p!=q&&*p!=i)p--;if(*p==i)return(0);else可编辑范本return(1);}/*********************************************/inthoming(sqstack*s)/*i退位后所对应的方向*/{inta,b,c,d,*q;q=s->top;q--;a=(*q)/100;b=(*q)%100;q--;c=(*q)/100;d=(*q)%100;m=(*q)/100;n=(*q)%100;if(a==c){if(d-b==1)return(3);elseif(d-b==-1)return(1);}elseif(b==d){if(c-a==1)return(4);elseif(c-a==-1)return(2);}return(0);}voiddestorystack(sqstack*s){if(*(s->base)!=NULL)free(s->base);s->length=0;}/*********************************************/voidmakemg(sqstack*s)/*创建迷宫及输出迷宫图的函数*/{intmgway(sqstack*s);voidclearstack(sqstack*s);intflag=1,flag2=1,i,j,k;charch;可编辑范本while(flag){printf("请输入迷宫的长宽(长度范围2-15,宽范围2-15)\n");printf("输入长");fflush(stdin);scanf("%d",&y);printf("输入宽");fflush(stdin);scanf("%d",&x);if(x<16&&x>3&&y>3&&y<16)flag=0;if(flag==0)printf("自动筛选能通过的迷宫需要一段时间,请耐心等待,如20秒后无法显示出迷宫样本请重试......\n");}flag=1;while(flag2){m=1;n=1;for(i=0;itop=s->base;*(s->base)=0;s->top++;*(s->top)=101;s->top++;s->length=2;}[此文档可自行编辑修改，如有侵权请告知删除，感谢您的支持，我们会努力把内容做得更好]可编辑范本
浙公网安备 33021202002483