武汉纺织大学数学与计算机学院 数据结构课程设计报告 迷宫问题 求解 学生姓名：
学 学 号：
班 班 级：
指导老师：
报告日期：
一、问题描述 以一个 m x n 的长方矩阵表示迷宫，1 和 0 分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出从入口到出口的通路，或者没有通路的结论。
二、需求分析 1、以二维数组 maze[10][10]表示迷宫，数组中以元素 1 表示通路，0 表示障碍，迷宫的大小理论上可以不限制，但现在只提供 10*10 大小迷宫。
2、迷宫的入口和出口需由用户自行设置。
3、以长方形矩阵的形式将迷宫及其通路输出，输出中“#”表示迷宫通路，“1”表示障碍。
4、本程序只求出一条成功的通路。但是只要对函数进行小量的修改，就可以求出其他全部的路径。
5、程序执行命令为：（1）输入迷宫；（2）、求解迷宫；（3）、输出迷宫。
三、概要设计 1 1、设定栈的抽象数据类型定义：
ADT zhan{ 基本操作：
InitStack(SqStack &S)操作结果：构造一个空栈 push（*s，*e）初始条件：栈已经存在 操作结果：将 e 所指向的数据加入到栈 s 中 pop（*s,*e）初始条件：栈已经存在 操作结果：若栈不为空，用 e 返回栈顶元素，并删除栈顶元素 getpop（*s，*e）初始条件：栈已经存在 操作结果：若栈不为空，用 e 返回栈顶元素 stackempty(*s)初始条件：栈已经存在 操作结果：判断栈是否为空。若栈为空，返回 1，否则返回 0 } ADT zhan 2 2、设定迷宫的抽象数据类型定义 ADT migong{ 基本操作：
Status print(MazeType maze)； //显示迷宫 Status Pass(MazeType maze,PosType curpos);//判断当前位置是否可通
Status FootPrint(MazeType &maze,PosType curpos);//标记当前位置已经走过 Status MarkPrint(MazeType &maze,PosType curpos);//标记当前位置不可通 PosType NextP os(PosType curpos,Di rectiveType di);// 进入下一位置 }ADT yanshu 3 3、本程序包括三个模块 a、主程序模块 void main(){ 初始化； 迷宫求解； 迷宫输出； } b、栈模块——实现栈的抽象数据类型 c、迷宫模块——实现迷宫的抽象数据类型 四、流程图
五、、数据 结构 t typedef struct //位置结构 { int row;//行位置 int col;//列位置 }PosType;typedef struct //迷宫类型 { int arr[10][10];}MazeType;typedef struct { int step;//当前位置在路径上的"序号" PosType seat;//当前的坐标位置 DirectiveType di;//往下一个坐标位置的方向 }SElemType;将入口、出口位置传入方法里 判断当前位置是否可通 将元素入栈 是否到达迷宫出口 右边是否存在通路 上边是否存在通路 左边是否存在通路 下边是否存在通路 存储结点入栈 循环结束，无解迷宫 有解迷宫
typedef struct // 栈类型 { SElemType *base;//栈的尾指针 SElemType *top;//栈的头指针 int stacksize;//栈的大小 }SqStack;六、调试结果和分析 a)测试结果 实际程序执行过程如下图所示：
参考文献 [1] 严蔚敏、吴伟民：《数据结构（C 语言版）》[M]，清华大学出版社 2022 年版 [2] 谭浩强：《C 语言设计（第三版）》[M]，清华大学出版社 2022 年版 心得体会 通过这段时间的课程设计，本人对计算机的应用，数据结构的作用以及 C语言的使用都有了更深的了解。尤其是 C 语言的进步让我深刻的感受到任何所学的知识都需要实践，没有实践就无法真正理解这些知识以及掌握它们，使其成为自己的财富。在设计此程序时，刚开始感到比较迷茫，然后一步步分析，试着写出基本的算法，思路渐渐清晰，最后完成程序。当然也遇到不少的问题，也正是因为这些问题引发的思考给我带了收获。
在遇到描写迷宫路径的算法时，我感到有些困难，后来经过一步步分析和借鉴书本上的穷举求解的算法，最后把算法写出来。
这次课程设计让我更加深入了解很多方面的知识，如数组的运用等等。在程序的编写中不要一味的模仿，要自己去摸索，只有带着问题反复实践，才能熟练地掌握和运用。
附录、、源代码 #include
}SElemType;typedef struct { SElemType *base;SElemType *top;int stacksize;}SqStack;//栈的存储 typedef struct { int arr[10][10];}MazeType;//迷宫类型 //---------函数声明 Status InitStack(SqStack &S);Status Pop(SqStack &S,SElemType &e);Status Push(SqStack &S,SElemType e);Status StackEmpty(SqStack S);Status MazePath(MazeType &maze,PosType start,PosType end);Status Pass(MazeType maze,PosType curpos);Status FootPrint(MazeType &maze,PosType curpos);PosType NextPos(PosType curpos,DirectiveType di);Status MarkPrint(MazeType &maze,PosType curpos);Status print(MazeType maze);void main(){
PosType start,end;MazeType a;printf("请输入迷宫数据n");for(int i=0;i<10;i++)//接受输入的迷宫数据 { for(int j=0;j<10;j++){ scanf("%d",&a.arr[i][j]);} } printf("请输入起始位置：行列 ");// 用户自定义起始点与终点 scanf("%d%d",&start.row,&start.col);printf("请输入结束位置：行列 ");scanf("%d%d",&end.row,&end.col);if(MazePath(a,start,end))//寻找路径 print(a);else printf("没有找到路径n");} Status InitStack(SqStack &S){ S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));// 为栈申请存储地址 if(!S.base)
exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;}//end InitStack Status Pop(SqStack &S,SElemType &e){ if(S.top==S.base)return ERROR;e=*(S.top-1);//如果没有这句话就会在原地打转，导致在死胡同堵死 S.top--;return OK;}//end Pop Status Push(SqStack &S,SElemType e){ *S.top=e;S.top++;return OK;}//end Push Status StackEmpty(SqStack S){ if(S.top==S.base)return OK;else
return ERROR;}//end StackEmpty Status MazePath(MazeType &maze,PosType start,PosType end){ PosType curpos;curpos=start;int curstep=1;SElemType e;SqStack S;InitStack(S);do { if(Pass(maze,curpos))//当前位置可以通过，即未曾走过的模块 { e.step=curstep;e.seat=curpos;e.di=1;FootPrint(maze,curpos);//留下足迹 Push(S,e);//加入到路径栈中 if(curpos.col==end.col&&curpos.row==end.row)// 达到终点（出口）return OK;curpos=NextPos(curpos,1);//下一位置是当前位置的东邻 curstep++;//探索下一步 }//end if
else { //当前位置不能通过 if(!StackEmpty(S)){ Pop(S,e);while(e.di==4&&!StackEmpty(S)){ MarkPrint(maze,e.seat);Pop(S,e);// 留下不能通过的标记，并回退一步 }//end while if(e.di<4){ e.di++;// 换一个方向探索 Push(S,e);curpos=NextPos(e.seat,e.di);//设定当前位置是该新方向的相邻快 }//end if }//end if }//end else }while(!StackEmpty(S));//end if printf("nn");for(int i=0;i<10;i++){ for(int j=0;j<10;j++)
{ printf("%d ",maze.arr[i][j]);} printf("n");} return ERROR;}//end MazePath Status Pass(MazeType maze,PosType curpos){ if(maze.arr[curpos.row][curpos.col]==0)//判断当前路径对应数组值是否等于 0，即当前路径是否可通 return OK;else return ERROR;} Status FootPrint(MazeType &maze,PosType curpos){ maze.arr[curpos.row][curpos.col]=2;//为当前路径留下可以通过的标志 return OK;}//end Pass PosType NextPos(PosType curpos,DirectiveType di){ PosType pos = curpos;
switch(di){ case 1:pos.col++;//向东寻找 break;case 2:pos.row++;//向西寻找 break;case 3:pos.col--;//向南寻找 break;case 4:pos.row--;//向北寻找 break;} return pos;}//end NextPos Status MarkPrint(MazeType &maze,PosType curpos){ maze.arr[curpos.row][curpos.col]=3;//为当前路径留下不可通过的标志 return OK;}//end MarkPrint Status print(MazeType maze)//迷宫的输出显示 { int i,j;printf("nn");for(i=0;i<10;i++)
{ for(j=0;j<10;j++){ switch(maze.arr[i][j]){ case 0: printf(" ");break;case 1: printf("1 ");break;case 2: printf("# ");break;case 3: printf(" ");break;}//end swith }//end 内层 for printf("n");}//end 外层 for return OK;}//end print
实验四A星算法求解迷宫问题实验
操作系统实验报告经典生产者—消费者问题
遗传算法求解TSP问题实验报告
有关迷宫作文300字四篇
走迷宫教案（集锦8篇）
