C语言迷宫程序Word格式.docx
- 文档编号:5313689
- 上传时间:2023-05-04
- 格式:DOCX
- 页数:19
- 大小:109.43KB
C语言迷宫程序Word格式.docx
《C语言迷宫程序Word格式.docx》由会员分享,可在线阅读,更多相关《C语言迷宫程序Word格式.docx(19页珍藏版)》请在冰点文库上搜索。
intlength;
//栈的长度
intstacksize;
//栈的最大长度
}sqstack;
2.产生迷宫的矩阵二维数组
为了使每一个迷宫存在迷宫的边界和两个端口:
入口、出口,设置了一个二维数组,在迷宫的周边定义为1,使得迷宫存在边界,并在(1,1),(x-2,y-2)初定义为0,即定义迷宫的出口,大大减小了无解的情况。
for(i=0;
i<
x;
i++)
for(j=0;
j<
y;
j++)
mg[i][j]=rand()%3;
//产生随机数
i=0;
{
mg[i][j]=1;
//定义边界
mg[j][i]=1;
}
i=y-1;
j++)//定义边界
i=x-1;
mg[1][1]=0;
//定义出口和入口
mg[x-2][y-2]=0;
四.主要函数功能
1.voidinitstack(sqstack*s);
/*初始化栈*/
将栈顶和栈底分别申请一段动态存储空间,将栈分配长度为100的空间,将栈的原始长度定义为2
2.voidstackpush(sqstack*s,int);
/*增加栈顶*/
将栈的动态存储空间增加50,将栈顶指针上移相应高度,特殊情况单独考虑见程序。
3.voidstackpop(sqstack*s);
/*撤销栈顶*/
栈空提示无法删除,其他情况删除栈顶。
4.voidstackinput(sqstack*s);
/*输出栈*/
输出寻找到的一条迷宫路径
5.intmgway(sqstack*s);
/*迷宫路径*/
寻找到可执行的一条迷宫路径
6.voiddestorystack(sqstack*s);
/*撤销栈S*/
将栈内元素清空
7.voidmakemg(sqstack*s);
/*制造迷宫*/
输入迷宫的长宽(2-15),并产生迷宫图
五.算例(生成演算结果)
本程序的运算环境为:
codeblocks
输入界面:
输入错误则重新输入
5*5的迷宫图及其路径:
继续输入错误提示:
重新输入结果:
可以看到每个迷宫都存在“围墙”
六.分析算法
1.空间复杂度
固定空间需求:
25*25的二维迷宫数组
可变空间需求:
初始化栈中申请了100倍int型所占空间大小的动态空间,加入栈顶时额外申请50倍int型所占空间大小
2.时间复杂度
可以通过“程序步”对程序的时间复杂度进行测量,可以引入count计数器进行测量,考虑到其复杂程度,本程序将不采用此方法。
本程序的排错率较高,计算机会改掉没有通路的栈,并随机生成有通路迷宫,提高了程序的执行效率,并给迷宫添加了必要的围墙和出口、入口有助于执行效率的提高。
但对于路径的搜索,栈并没有引入方向指针,在后面,通过flag进行标记来确定栈的路径的寻找的,一定程度上会影响执行效率。
附录:
C语言源程序
#include<
stdio.h>
stdlib.h>
#defineSTACKINCREMENT50
#defineNULL0
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);
voidmakemg(sqstack*s);
sqstacks;
inti,flag1=1,flag2=1,flag3=1;
charch;
srand((unsigned)time(NULL));
while(flag1)
initstack(&
s);
flag2=1;
makemg(&
i=mgway(&
if(i==0)
printf("
此迷宫没有通路\n"
);
else
stackinput(&
destorystack(&
还继续么?
"
fflush(stdin);
scanf("
%c"
&
ch);
while(flag2)
if(ch=='
n'
||ch=='
N'
)
flag1=0;
flag2=0;
elseif(ch=='
y'
Y'
flag1=1;
输入错误请重新输入"
}
voidinitstack(sqstack*s)/*初始化栈*/
s->
top=s->
base=(int*)malloc(STACK_INI_SIZE*sizeof(int));
if(!
base)
exit
(1);
stacksize=STACK_INI_SIZE;
*(s->
base)=0;
top++;
top)=101;
length=2;
voidstackpush(sqstack*s,inti)/*增加栈顶*/
if(s->
length>
=s->
stacksize)
路过"
s->
base=(int*)realloc(s->
base,(STACK_INI_SIZE+STACKINCREMENT)*sizeof(int));
if(!
base+s->
length;
stacksize+=STACKINCREMENT;
stackinput(s);
length==0)
*(s->
base)=i;
length++;
top)=i;
voidstackpop(sqstack*s)/*删除栈顶*/
if(s->
栈空无法删除"
length==1)
top--;
top)=*(s->
base)=NULL;
length=0;
else
top)=NULL;
length--;
voidstackinput(sqstack*s)/*迷宫栈的输出*/
intw,x,y,z,i=0,*p;
p=s->
base;
p++;
迷宫正确路径\n"
while(p!
top)
(%d%d,%d%d)"
x=*p/1000,y=*p/100%10,z=*p%100/10,w=*p%10);
i++;
if(i==7)
\n"
intmgway(sqstack*s)/*迷宫路径*/
intgudge(sqstack*s,int);
/*判断是否能通行*/
inthoming(sqstack*s);
/*退栈后I所对应的方向*/
inti=1,j,k;
while(s->
top!
if(i<
5)
j=gudge(s,i);
if(j==1&
&
k=m*100+n;
stackpush(s,k);
if(m==y-2&
n==x-2)
return
(1);
i=1;
if(m==0&
n==0)
return(0);
elseif(i==4||i==5)
i=homing(s);
stackpop(s);
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))
if(i==1)
if(i==2)
if(i==3)
if(i==4)
intecho(sqstack*s)
inti,*p,*q;
i=m*100+n;
p=s->
top;
q=s->
q++;
p--;
while(p!
=q&
*p!
=i)
p--;
if(*p==i)
inthoming(sqstack*s)/*i退位后所对应的方向*/
inta,b,c,d,*q;
q--;
a=(*q)/100;
b=(*q)%100;
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)
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);
voidmakemg(sqstack*s)/*创建迷宫及输出迷宫图的函数*/
intmgway(sqstack*s);
voidclearstack(sqstack*s);
intflag=1,flag2=1,i,j,k;
while(flag)
请输入迷宫的长宽(长度范围2-15,宽范围2-15)\n"
输入长"
%d"
y);
输入宽"
x);
if(x<
16&
x>
3&
y>
y<
16)
flag=0;
if(flag==0)
自动筛选能通过的迷宫需要一段时间,请耐心等待,如20秒后无法显示出迷宫样本请重试......\n"
flag=1;
while(flag2)
m=1;
n=1;
for(i=0;
k=mgway(s);
if(k==1)
clearstack(s);
printf("
"
%2d"
i);
\n"
↓"
%2d→"
if(mg[i][j]==2)
0"
%d"
mg[i][j]);
voidclearstack(sqstack*s)/*清空栈对于此程序而言*/
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 语言 迷宫 程序
![提示](https://static.bingdoc.com/images/bang_tan.gif)