数据结构上机实验报告-迷宫求解
//////////By Lea//////////////
////////2010210501////////////
#include<stdio.h>
#include<stdlib.h>
/*数据定义*/
typedef enum { ERROR, OK } Status;
typedef struct
{
int row; //row表示"行"号
int line; //line表示"列"号
}PosType; //位置的元素类型
typedef struct
{
int ord; //该通道在路径上的"序号"
PosType seat; //通道块在迷宫中的"坐标位置"
int di; //从此通道走向下以通道块的"方向"
}SElemType; //栈的元素类型
typedef struct
{
SElemType * base;
SElemType * top;
int stacksize;
}SqStack;
/*函数原型说明*/
Status InitStack(SqStack &S); //创建一个空栈S
Status Push(SqStack &S,SElemType &a); //插入新元素a
Status Pop(SqStack &S,SElemType &a); //删除栈顶元素，a返回其值
Status StackEmpty(SqStack S); //检查是否空栈
Status MazePath(int maze[12][12],SqStack &S, PosType start, PosType end); //找通路
void Initmaze(int maze[12][12],int x,int y); //初始化迷宫
void printmaze(int maze[12][12],int x,int y); //显示迷宫
Status Pass(int maze[12][12],PosType CurPos); //判断当前位置是否可通
void Markfoot(int maze[12][12], PosType CurPos); //标记当前位置不可通
PosType NextPos(PosType CurPos, int Dir); //进入下一位置
void printpath(int maze[12][12],SqStack S,int x,int y,PosType start,PosType end); //显示通路
/*主函数*/
void main (void)
{
PosType start,end;
int t=0;
SqStack S;
int maze[12][12];
do{
if(t!=0)
printf("\n");
for(int i=0;i<20;i++)
{
printf("* ");
}
if(t==0)
{
printf("\n*\t欢迎来到迷宫世界\t * \n");
printf("*\t 1.设置迷宫\t\t * \n");
}
else
{
printf("\n* 请继续选择：\t\t\t * \n");
printf("*\t 1.设置迷宫\t\t * \n");
}
printf("*\t 2.设置迷宫路径\t\t * \n");
printf("*\t 3.输出迷宫通路路径\t * \n");
printf("*\t 4.结束\t\t\t *\n");
t++;
for(int j=0;j<20;j++)
{
printf("* ");
}
printf("\n");
int s;
printf("请选择：");
scanf("%d",&s);
int aa; int x,y;
switch(s)
{
case 1://1.初始化迷宫
aa=1;
printf("迷宫设置：请输入\n"); //设置迷宫大小
do
{
printf("行X(x<10)=");
scanf("%d",&x);
printf("列Y(y<10)=");
scanf("%d",&y);
if(x<1 || x>10||y<1 || y>10)
{
printf("输入错误!\n");
}
}while(x<1 || x>10||y<1 || y>10);
Initmaze(maze,x,y); //初始化迷宫
printmaze(maze,x,y); //显示所创建的迷宫
break;
case 2://寻找迷宫路径
if(aa==1)
{
aa=2; //设置入口和出口
do{
printf("输入入口行坐标:");scanf("%d",&start.row);
if(start.row>x)
printf("输入错误!\n");
}while(start.row>x);
do{
printf("输入入口列坐标:");scanf("%d",&start.line);
if(start.line>y)
printf("输入错误!\n");
}while(start.line>y);
do{
printf("输入出口行坐标:");scanf("%d",&end.row);
if(end.row>x)
printf("输入错误!\n");
}while(end.row>x);
do{
printf("输入出口列坐标:");scanf("%d",&end.line);
if(end.line>y)
printf("输入错误!\n");
}while(end.line>y);
}
else
printf("请先初始化迷宫！\n");
printf("\n所设置入口坐标为(%d,%d),出口坐标为(%d,%d).\n",start.row,start.line,end.row,end.line);
break;
case 3://输出此迷宫通路路径
if(aa==2)
{
aa=3;
if(MazePath(maze,S,start,end)) //若有通路，显示通路
printpath(maze,S,x,y,start,end);
else
printf("\n抱歉，找不到通路!\n\n");
}
else
printf("请先初始化迷宫并寻找路径！\n");
break;
case 4:exit(0);
break;
default:
exit(0);
}
}while(1);
}
/*若迷宫maze中从入口 start到出口 end的通道，则求得一条存放在栈中 */
Status MazePath(int maze[12][12],SqStack &S, PosType start, PosType end)
{
PosType curpos;
int curstep;
SElemType e;
InitStack(S);
curpos = start; // 设定"当前位置"为"入口位置
curstep = 1; // 探索第一步
do {
if (Pass(maze,curpos)) // 当前位置可通过，即是未曾走到过的通道块
{
Markfoot(maze,curpos); // 留下足迹
e.di =1;
e.ord = curstep;
e.seat= curpos;
Push(S,e); // 加入路径
if (curpos.row==end.row && curpos.line==end.line)
return OK; // 到达终点（出口）
curpos = NextPos(curpos, 1); // 下一位置是当前位置的东邻
curstep++; // 探索下一步
}
else // 当前位置不能通过
{
if (!StackEmpty(S))
{
Pop(S,e);
while (e.di==4 && !StackEmpty(S))
{
Markfoot(maze,e.seat); // 留下不能通过的标记，并退回一步
Pop(S,e);
}
if (e.di<4)
{
e.di++; // 换下一个方向探索
Push(S, e);
curpos = NextPos(e.seat, e.di); // 当前位置设为新方向的相邻块
}
}
}
} while (!StackEmpty(S));
return ERROR;
}
/*初始化迷宫 时间复杂度：n^2*/
void Initmaze(int maze[12][12],int x,int y)
{
char select;
do{
printf("创建方式 A:自动生成 B:手动创建\n");
label: scanf("%c",&select);
if(select=='a'||select=='A') //自动生成
{
for(int i=1;i<x+1;i++)
{
for(int j=1;j<y+1;j++)
maze[i][j]=rand()%2;
}
break;
}
else if(select=='b'||select=='B') //手动设置
{
printf("按行输入%d*%d数据,0代表可通,1代表不可通(每行以Enter结束):\n",x,y);
for(int i=1;i<x+1;i++)
{
for(int j=1;j<y+1;j++)
scanf("%d",&maze[i][j]);
maze[i][y+1]=1;
}
for(i=0;i<x+2;i++)maze[x+1][i]=1;
break;
}
else if(select=='\n')goto label; //排除Enter键的影响
else
if(select!='b'||select!='B'||select!='a'||select!='A')
printf("输入错误!\n");
}while(select!='b'||select!='B'||select!='a'||select!='A');
}
/*显示迷宫 时间复杂度：n^2*/
void printmaze(int maze[12][12],int x,int y)
{
printf("\n\n");
printf("显示所建的迷宫(#表示墙):\n");
printf("%c ",'#');
printf("%c ",'y');
for(int j=1;j<y+1;j++)
printf("%d ",j);
printf("%c ",'#');
printf("\nx ");
for(int i=1;i<y+3;i++)
printf("%c ",'#');
printf("\n");
for(i=1;i<x+1;i++)
{
if(i<x+1)
printf("%d ",i);
else
printf("%c ",'#');
printf("%c ",'#');
for(int j=1;j<y+1;j++)
{
printf("%d ",maze[i][j]);
}
printf("%c",'#');
printf("\n");
}
for(i=0;i<y+3;i++)printf("%c ",'#');printf("\n");
}
/*输出路径 时间复杂度：n^2*/
void printpath(int maze[12][12],SqStack S,int x,int y,PosType start,PosType end)
{
printf("\n\n\001通路路径:\n");
SElemType * p=S.base;
while(p!=S.top)
{
maze[p->seat.row][p->seat.line]=2; //标记为路径中的点
p++;
}
printf("\001路径图为：\n");
printf("%c ",'#');
printf("%c ",'y');
for(int j=1;j<y+1;j++)
printf("%d ",j);
printf("%c ",'#');
printf("\nx ");
for(int m=1;m<y+3;m++)
printf("%c ",'#');
printf("\n");
for(int i=1;i<x+1;i++)
{
if(i<x+1)
printf("%d ",i);
else
printf("%c ",'#');
printf("%c ",'#');
for(int j=1;j<y+1;j++)
{
if(maze[i][j]==2)
{if(i==start.row&&j==start.line||i==end.row&&j==end.line){
if(i==start.row&&j==start.line)
printf("i ");
if(i==end.row&&j==end.line)
printf("o ");}
else
printf("%c ",' ');}
else
printf("%c ",'#');
}
printf("%c ",'#');
printf("\n");
}
for(i=0;i<y+3;i++)
printf("%c ",'#');
printf("\n\n");
printf("\001路径线路为：\n");
SqStack M;
InitStack(M);
SElemType a;
while (!StackEmpty(S))
{
Pop(S,a);
Push(M,a);
}
while (!StackEmpty(M))
{
Pop(M,a);
printf("(%d,%d)",a.seat.row,a.seat.line);
}
printf("\n");
printf("路径输出成功！\n");
}
/* 判断当前位置是否可通*/
Status Pass(int maze[12][12],PosType CurPos)
{
if(maze[CurPos.row][CurPos.line]==0)
return OK; // 如果当前位置是可以通过，返回1
else
return ERROR; // 其它情况返回0
}
/* 标记当前位置不可通*/
void Markfoot(int maze[12][12],PosType CurPos)
{
maze[CurPos.row][CurPos.line]=1;
}
/*进入下一位置*/
PosType NextPos(PosType CurPos, int Dir)
{
PosType ReturnPos;
switch (Dir)
{
case 1:
ReturnPos.row=CurPos.row;
ReturnPos.line=CurPos.line+1;
break;
case 2:
ReturnPos.row=CurPos.row+1;
ReturnPos.line=CurPos.line;
break;
case 3:
ReturnPos.row=CurPos.row;
ReturnPos.line=CurPos.line-1;
break;
case 4:
ReturnPos.row=CurPos.row-1;
ReturnPos.line=CurPos.line;
break;
}
return ReturnPos;
}
/*创建一个空栈S*/
Status InitStack(SqStack &S)
{
S.base=(SElemType *)malloc(100*sizeof(SElemType));
if(!S.base)return ERROR;
S.top=S.base;
S.stacksize=100;
return OK;
}
/*插入新元素a*/
Status Push(SqStack &S,SElemType &a)
{
*S.top++=a;
return OK;
}
/* 删除栈顶元素，a返回其值*/
Status Pop(SqStack &S,SElemType &a)
{
if(S.top==S.base)return ERROR;
a=*--S.top;
return OK;
}
/*检查是否空栈*/
Status StackEmpty(SqStack S)
{
if(S.top==S.base)return OK;
return ERROR;
}
-
数据结构上机实验报告
实验一线性表的基本操作实验目的学习掌握线性表的顺序存储结构链式存储结构的设计与操作对顺序表建立插入删除的基本操作对单链表建立插入删…
-
数据结构上机实验答案
数据结构实验指导书答案实验一1请编写函数intfunintaintb函数的功能是判断两个指针a和b所指存储单元的值的符号是否相同若…
-
数据结构上机实验报告
空间数据结构基础上机实验报告20xx姓名班级地信121学号07122857环境与测绘学院级实验报告1C面向对象程序设计范例1二维坐…
-
数据结构第一次上机实验报告
数据结构第一次上机实验报告线性表实验要求1实现顺序表结构的创建插入删除查找等操作2利用上述顺序表操作实现如下程序建立两个顺序表表示…
-
数据结构上机实验报告
计算机科学与技术学院数据结构教程实验报告20xx20xx学年第2学期学生姓名学生专业学生班级学生学号20xx65实验报告一设计人员…
-
数据结构和算法设计实验报告
数据结构与算法分析实验报告班级指导老师学生组长数据结构与算法设计课程设计组号设计主题数据结构与算法设计实验指导老师组长学号组员学号…
-
数据结构-迷宫-实验报告与代码
一需求分析本程序是利用非递归的方法求出一条走出迷宫的路径并将路径输出首先由用户输入一组二维数组来组成迷宫确认后程序自动运行当迷宫有…
-
数据结构之迷宫求解实验报告武汉大学
数据结构实验报告迷宫求解问题实验上机环境DevC二程序设计相关信息1实验题目迷宫求解问题问题描述实验题35改进314节中的求解迷宫…
-
数据结构试验报告-迷宫问题
实验报告：迷宫问题题目：编写一个求解迷宫通路的程序一、需求分析：1)采用二维数组maze[M][N]来表示迷宫，其中：maze[0…
-
迷宫求解数据结构课程设计报告
数据结构课程设计题目学院专业班级学生姓名指导教师数据结构课程设计目录第一部分引言3第二部分课程设计报告3第一章课程设计目的3第二章…
-
C++迷宫问题实验报告
数据结构集中上机试验报告学院计算机科学与技术专业计算机科学与技术学号00000000班级6姓名20xx01027题目编制一个求解迷…