迷宫程序张小强.docx
《迷宫程序张小强.docx》由会员分享，可在线阅读，更多相关《迷宫程序张小强.docx（19页珍藏版）》请在冰点文库上搜索。
迷宫程序张小强
实验报告
实验课程名称数据结构
实验项目名称迷宫程序
年级2112级
专业math
学生姓名
张小强
理学院
实验时间：
3014年9月20日
学生实验室守则
一、按教学安排准时到实验室上实验课，不得迟到、早退和旷课。
二、进入实验室必须遵守实验室的各项规章制度，保持室内安静、整洁，不准在室内打闹、喧哗、吸烟、吃食物、随地吐痰、乱扔杂物，不准做与实验内容无关的事，非实验用品一律不准带进实验室。
三、实验前必须做好预习（或按要求写好预习报告），未做预习者不准参加实验。
四、实验必须服从教师的安排和指导，认真按规程操作，未经教师允许不得擅自动用仪器设备，特别是与本实验无关的仪器设备和设施，如擅自动用或违反操作规程造成损坏，应按规定赔偿，严重者给予纪律处分。
五、实验中要节约水、电、气及其它消耗材料。
六、细心观察、如实记录实验现象和结果，不得抄袭或随意更改原始记录和数据，不得擅离操作岗位和干扰他人实验。
七、使用易燃、易爆、腐蚀性、有毒有害物品或接触带电设备进行实验，应特别注意规范操作，注意防护；若发生意外，要保持冷静，并及时向指导教师和管理人员报告，不得自行处理。
仪器设备发生故障和损坏，应立即停止实验，并主动向指导教师报告，不得自行拆卸查看和拼装。
八、实验完毕，应清理好实验仪器设备并放回原位，清扫好实验现场，经指导教师检查认可并将实验记录交指导教师检查签字后方可离去。
九、无故不参加实验者，应写出检查，提出申请并缴纳相应的实验费及材料消耗费，经批准后，方可补做。
十、自选实验，应事先预约，拟订出实验方案，经实验室主任同意后，在指导教师或实验技术人员的指导下进行。
十一、实验室内一切物品未经允许严禁带出室外，确需带出，必须经过批准并办理手续。
1、设计题目：
迷宫
2、需求分析：
任务：
可以任意生成一个迷宫，通过运用到栈来求出一条走出迷宫的路径，并将路径输出。
3、概要设计：
在迷宫设计中，我们可以借助栈来实现在迷宫中的前进和后退。
同时，还需要设计迷宫的大小、迷宫的出入口、根据输入的入口来寻找迷宫的出口，并把路径给表示出来。
在这个设计中由于不知道所走路径的步数，所以采用了链式栈实现每一步的移动若找到出路则前进，否则返回下一步改变方向来实现对应的移动，所以栈在其间起到了工具的作用。
在设计迷宫大小和出入口时，采用的是根据操作者实现的，但迷宫的具体路障与通道是随机实现的。
当然，重点是如何从入口找到出口。
求迷宫的一条通路的伪码如下：
设当前初始位置为出口：
do{
若当前位置可通，则{
将该位置插入到栈顶；//纳入路径
若该位置为出口位置。
则结束当前程序；/求得的路径放在栈中
否则切换当前位置的东临位置（即向右）为新的当前的位置；
}
否则{
若栈不为空且栈顶元素尚有其他位置未被探索，则设定新的当前位置为沿着顺时针旋转得到的栈顶位置的下一个临快；}
若栈不为空且栈顶位置的四周均不通
{
则删去栈顶元素；//后退一步，从路径中删去该通块
若栈不空，则重新测试新的栈顶位置，直到找到一个可通的相邻块或出栈至栈空；
}
}
程序模块
主程序从main（）函数中进行，包括输入迷宫的大小等信息，然后调用迷宫模块，在迷宫模块中也调用栈的模块。
栈模块---实现栈抽象数据类型
迷宫模块---实现迷宫抽象数据类型
各模块之间的关系如下：
主程序模块
迷宫模块
栈模块
4、算法流程图
五、对应程序：
#include
#include
#defineSTACK_INI_SIZE100
#defineSTACKINCREMENT50
#defineNULL0
typedefstruct
{
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"）;
else
stackinput（&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）;
}
else
i=1;
}
else
{
if（m==0&&n==0）
return（0）;
elseif（i==4||i==5）
{
i=homing（s）;
stackpop（s）;
i++;
}
else
i++;
}
}
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（"自动筛选能通过的迷宫需要一段时间,请耐心等待,如15秒后无法显示出迷宫样本请重试......\n"）;
}
flag=1;
while（flag2）
{
m=1;
n=1;
for（i=0;ifor（j=0;jmg[i][j]=rand（）%3;
i=0;
for（j=0;j{
mg[i][j]=1;
mg[j][i]=1;
}
i=y-1;
for（j=0;jmg[j][i]=1;
i=x-1;
for（j=0;jmg[i][j]=1;
mg[1][1]=0;
mg[x-2][y-2]=0;
k=mgway（s）;
if（k==1）
flag2=0;
else
clearstack（s）;
}
printf（""）;
for（i=0;iprintf（"%2d",i）;
printf（"\n"）;
printf（""）;
for（i=0;iprintf（"↓"）;
printf（"\n"）;
for（i=0;i{
printf（"%2d→",i）;
for（j=0;j{
if（mg[i][j]==2）
printf（"0"）;
else
printf（"%d",mg[i][j]）;
}
printf（"\n"）;
}
}
/*********************************************/
voidclearstack（sqstack*s）/*清空栈对于此程序而言*/
{
s->top=s->base;
*（s->base）=0;
s->top++;
*（s->top）=101;
s->top++;
s->length=2;
}
程序运行结果：
迷宫正确路径坐标：
（1，1）、（1，2）、（1，3）、（1，4）、（2、4）、（3，4）（3，3）、
（4，3）、（5，3）、（5，4）、（6，4）、（7，4）、（7，5）、（7，6）、（7，7）
即：
升级会员 