好家伙,本篇为应付老师的实验报告,有需要的拿去抄吧
思路讲解在上一篇:
数据结构与算法大作业：走迷宫程序（C,代码以及思路）
一、作业目的
1、 掌握用数据结构的知识进行程序设计。
2、 应用所学的数据结构完成一个具有一定实际意义的应用程序的设计、编码、调试，锻炼实践动手能力，提高编程水平。
二、作业内容
走迷宫程序
问题描述：
以一个 m * n 的长方阵表示迷宫， 0和1分别表示迷宫的通路和障碍。 设计一个程序， 对任意设定的迷宫， 求出一条从入口到出口的通路， 或得出没有通路的结论。
基本要求：
（1） 实现一个以链表做存储的栈类型， 然后编写一个求解迷宫的非递归程序。 求的通路以三元组（i， j， d） 的形式输出， 其中：（i， j） 指示迷宫中的一个坐标， d 表示走到下一坐标的方向。 如： 对于下列数据的迷宫， 输出一条通路：
（1， 1， 1），（1， 2， 2），
（2， 2，
2），（3， 2， 3），（3， 1， 2） ……。
（2） 编写递归形式的算法， 求得迷宫中所有可能的道路；
扩展功能要求：
以方阵形式输出迷宫及其到道路
测试数据： 迷宫的测试数据如下： 左上角（1， 1） 为入口， 右下角（8， 9） 为出口。
三、大作业设计思路与实现
（一）设计背景
迷宫是一个十分经典且有趣的游戏，借着本次大作业的机会，在锻炼自身编程水平的同时还原这一经典游戏。在未确定路径是进次尝试最终找到通路。
(二)、解决方案设计
1、系统操作需求
本程序使用windows 10 操作系统下，程序在 Devc++或Visual C++中运行的。
2、开发环境需求
硬件环境
笔记本电脑，运行时所需内存：1G
软件环境
操作系统：windows 10
3.功能介绍
（1）迷宫游戏是非常经典的游戏，在该题中设计随机生成一个迷宫和手动输入迷宫2种程序，并求解迷宫。
（2）在程序中，随机迷宫用了随机函数，对方向的随机挖去路径；手动迷宫是通过自己给出迷宫进行输入并给出所有路径。
（3）在求解这两中迷宫是个有些不同。在随机迷宫中，我们让程序自己运行，当入口给定时，会让程序自己跑动，迷宫的路径和出口是随机的，这时只有一条路径；而手动输入迷宫时，如果一个通道其四面都有通道时，这时就会形成一个回路，其基本是一样的，就是多了一个来回而已。
（4）用图形进行展示，其迷宫大小可以调试。
(5)在多条路径的情况下，程序会自动生成最短的路径
(三)、程序概要设计
1.各种功能完成的详细情况已经实现以一个 m * n 的长方阵表示迷宫， 0和1分别表示迷宫的通路和障碍。 设计一个程序， 对任意设定的迷宫， 求出一条从入口到出口的通路， 或得出没有通路的结论。
2. 实现一个以链表做存储的栈类型， 然后编写一个求解迷宫的非递归程序。 求的通路以三元组（i， j， d） 的形式输出， 其中：（i， j） 指示迷宫中的一个坐标， d 表示走到下一坐标的方向。 如： 对于下列数据的迷宫， 输出一条通路：
（1， 1， 1），（1， 2， 2），
（2， 2，
2），（3， 2， 3），（3， 1， 2） ……。
3. 编写递归形式的算法， 求得迷宫中所有可能的道路；
(四)、系统用例设计和流程图
系统流程图：
a) 程序详细设计：各种功能的实现方法描述、关键代码分析
问题分析:迷宫求解
这种迷宫求解的问题非常适合使用搜索来求解
此处我们使用深度优先搜索算法去求出迷宫的解,当一条支路完成时,我们将整条完整的路径输出
关键代码分析
1.栈的几种基本操作:
//栈中存位置以及遍历时所走的方向，打印时可以显示出来
typedef struct Node{
int x;
int y;
// int dir; //-1为左上右下对应 '\' 0为上下对应'|' 1为左右对应'——' 2为左下右上对应'/'
struct Node *next;
}Node;
typedef Node* Stack; //定义数据结构栈 Stack
//-----------创建一个空栈--------------
Stack creakEmptyStack(){
Stack p;
p=(Stack)malloc(sizeof(Node)); //申请一个空间
if(p){
p->next=NULL;
return p;
}
}
//------------将元素压入栈----------------
void push(int x,int y,Stack s){
Stack p;
p=(Stack)malloc(sizeof(Node));
if(p){ //如果申请空间成功则用头插法将元素压入
p->x=x;
p->y=y;
if(!s->next) p->next=NULL; //如果此时栈里还没有任何元素，则p此时为第一个结点
else p->next=s->next; //否则将p插入头结点之后
s->next=p;
}
else{
printf("No space!\n");
}
}
//-------------检测栈是否为空--------------
int isEmpty(Stack s){ //为空则返回1，不为空返回0
if(s->next==NULL) return 1;
else return 0;
}
//--------------将元素弹出栈----------------
void pop(Stack s){
Stack p;
p=s->next;
if(p->next){
s->next=p->next;
free(p);
}
else return;
}
//------------取栈顶元素------------------
Node top(Stack s){
Node t;
//判断是否为空，若不为空则返回
t=*(s->next);
return t;
}
解释:此处我们使用栈来储存我们迷宫的解,上述代码定义了一系列的
2.核心算法:
此处我们使用深度优先搜索去求出迷宫的解\
代码如下
//-----------遍历迷宫寻找路径(dfs)------------
void mazePath(int x,int y,int endx,int endy,int n,int m,Stack s){
int newx,newy,i;
Node t;
for(i=0;i<4;i++){
newx=x+direction[i][0];
newy=y+direction[i][1];
if(newx>=0&&newx<n&&newy>=0&&newy<m&&maze[newx][newy]==0){ //下一个路能走
push(newx,newy,s);
maze[newx][newy]=2;
if(newx==endx&&newy==endy){//走到出口
flag++;
printPath(s,n,m);
maze[newx][newy]=0;
pop(s);
}
else{
mazePath(newx,newy,endx,endy,n,m,s); //开始递归
}
}
// else if(!isEmpty(s)) pop(s);
}
maze[x][y]=0; //遍历完四个方向之后回溯前将自己赋为空
pop(s);
}
解释如下:
在该方法中,xy代表的是当前坐标的xy轴,newx,newy代表的是下一坐标点的xy轴坐标,
随后我们对坐标进行判断,
2.1.若下一坐标点为1,则进行下一个方向的寻找
2.2.若下一个坐标为0且不越界
则将下一坐标推入栈,并将该点标记为已走(即标记为2)
再次进行判断
2.2.1. 如果下一坐标为出口
打印整个路径
2.2.2.下一坐标不为出口
递归
流程图如下:
3.打印迷宫路径
//-------------打印迷宫路径-----------------
void printPath(Stack s,int n,int m){
int cont =0; //计算路径长度
s=s->next;
int i=0,j=0;
printf("第%d条路径为：\n",flag);
for(i=0;i<n;i++){ //按图形输出
for(j=0;j<m;j++){
if(maze[i][j]==2) printf("* ");
else printf("%d ",maze[i][j]);
}
printf("\n");
}
while(s->next){ //将栈中的元素输出为直观路径
printf("(%d,%d)->",s->x+1,s->y+1);
s=s->next;
cont++;
}
printf("(%d,%d)",s->x+1,s->y+1);
cont++;
if(cont<MIN) MIN=cont;
printf("\n");
printf("路径长度为：%d\n\n",cont);
}
解释:将栈中的路径输出
b) 使用情况：展示各种功能的运行情况
样例一:手动输入迷宫正常使用程序：
首先输入迷宫的行数和列数
随后输入迷宫的各行各列
其中0代表路，1代表墙
随后程序会显示迷宫的大致样式
并给出迷宫道路的解
输入样例:
3 3
1
0 0 0
1 0 0
1 1 0
1 1 3 3
输出:
生成的迷宫如下：
0 0 0
1 0 0
1 1 0
请输入起点及终点：
第1条路径为：
* * *
1 0 *
1 1 *
(3,3)->(2,3)->(1,3)->(1,2)
路径长度为：4
第2条路径为：
* * 0
1 * *
1 1 *
(3,3)->(2,3)->(2,2)->(1,2)
路径长度为：4
样例二:随机生成迷宫
输入:
2 2
0
2 1 2 2
输出:
第1条路径为：
1 1
* *
(2,2)
路径长度为：1
最短路径长度为:1
c) 总结：分析程序的优点和不足、开发时遇到的困难及解决的问题、总结。
开发时遇到的问题:算法不会用,栈的操作总是出错,随后去找百度搜索,翻书,找到解决问题的方法
作为一名初学者，我对深度优先搜索算法的使用进行了研究，并通过实践掌握了它的一些使用心得。深度优先搜索算法可以解决很多问题，如最短路径、迷宫问题、图着色问题等，因此学会使用深度优先搜索算法是非常有益的。
首先，我认为理解深度优先搜索算法的核心思想是非常重要的。深
在使用广度优先算法解决问题时，我发现栈的使用非常重要。
最后，我深刻认识到广度优先搜索算法的局限性。尽管广度优先搜索算法可以解决很多问题，但有些问题并不适用于该算法。例如，当搜索的节点数量非常大时，算法的时间和空间复杂度会变得非常高。因此，在使用广度优先搜索算法解决问题时，需要注意算法的局限性，并选择最适合当前问题的算法。
总之，通过对广度优先搜索算法的研究和实践，我认为理解其核心思想、正确选择数据结构、考虑时间和空间限制、深入了解其局限性等方面都是非常重要的。广度优先算法可以解决很多问题，但在实践过程中可能会遇到各种问题。如果我们能够在使用广度优先搜索算法时思考这些问题，并做出正确的决策，那么我们就能够更好地应用广度优先搜索算法，解决更多更复杂的问题。
关于本次的迷宫问题,我认为深度优先搜索是非常好的算法
d) 参考文献。
[1]严蔚敏.数据结构C语言版[M].清华大学出版社，2007.
[2] 啊哈磊, 《啊哈!算法》, 人民邮电出版社,2014
[3]百度百科 https://baike.baidu.com/
[4] 栈——栈的定义及基本操作（初始化、判空、进栈、出栈、遍历栈、销毁栈等）-CSDN博客，https://blog.csdn.net/weixin_44162361/article/details/115868909
[5]BFS(广度优先搜索)：层序遍历和最短路径 - 灿影之晶 - 博客园 (cnblogs.com)，https://www.cnblogs.com/sbb-first-blog/p/13259728.html
[6] 深度优先搜索（DFS）算法详解 (biancheng.net), http://data.biancheng.net/view/325.html
一、作业目的
1、掌握用数据结构的知识进行程序设计。
2、应用所学的数据结构完成一个具有一定实际意义的应用程序的设计、编码、调试，锻炼实践动手能力，提高编程水平。
二、作业内容
走迷宫程序
问题描述：
以一个 m * n 的长方阵表示迷宫， 0和1分别表示迷宫的通路和障碍。 设计一个程序， 对任意设定的迷宫， 求出一条从入口到出口的通路， 或得出没有通路的结论。
基本要求：
（1） 实现一个以链表做存储的栈类型， 然后编写一个求解迷宫的非递归程序。 求的通路以三元组（i， j， d） 的形式输出， 其中：（i， j） 指示迷宫中的一个坐标， d 表示走到下一坐标的方向。 如： 对于下列数据的迷宫， 输出一条通路：
（1， 1， 1），（1， 2， 2），
（2， 2，
2），（3， 2， 3），（3， 1， 2） ……。
（2） 编写递归形式的算法， 求得迷宫中所有可能的道路；
扩展功能要求：
以方阵形式输出迷宫及其到道路
测试数据：迷宫的测试数据如下：左上角（1， 1）为入口，右下角（8， 9）为出口。
三、大作业设计思路与实现
（一）设计背景
迷宫是一个十分经典且有趣的游戏，借着本次大作业的机会，在锻炼自身编程水平的同时还原这一经典游戏。在未确定路径是进次尝试最终找到通路。
(二)、解决方案设计
1、系统操作需求
本程序使用windows 10 操作系统下，程序在 Devc++或Visual C++中运行的。
2、开发环境需求
硬件环境
笔记本电脑，运行时所需内存：1G
软件环境
操作系统：windows 10
3.功能介绍
（1）迷宫游戏是非常经典的游戏，在该题中设计随机生成一个迷宫和手动输入迷宫2种程序，并求解迷宫。
（2）在程序中，随机迷宫用了随机函数，对方向的随机挖去路径；手动迷宫是通过自己给出迷宫进行输入并给出所有路径。
（3）在求解这两中迷宫是个有些不同。在随机迷宫中，我们让程序自己运行，当入口给定时，会让程序自己跑动，迷宫的路径和出口是随机的，这时只有一条路径；而手动输入迷宫时，如果一个通道其四面都有通道时，这时就会形成一个回路，其基本是一样的，就是多了一个来回而已。
（4）用图形进行展示，其迷宫大小可以调试。
(5)在多条路径的情况下，程序会自动生成最短的路径
(三)、程序概要设计
1.各种功能完成的详细情况已经实现以一个 m * n 的长方阵表示迷宫， 0和1分别表示迷宫的通路和障碍。 设计一个程序， 对任意设定的迷宫， 求出一条从入口到出口的通路， 或得出没有通路的结论。
2.实现一个以链表做存储的栈类型， 然后编写一个求解迷宫的非递归程序。 求的通路以三元组（i， j， d） 的形式输出， 其中：（i， j） 指示迷宫中的一个坐标， d 表示走到下一坐标的方向。 如： 对于下列数据的迷宫， 输出一条通路：
（1， 1， 1），（1， 2， 2），
（2， 2，
2），（3， 2， 3），（3， 1， 2） ……。
3.编写递归形式的算法， 求得迷宫中所有可能的道路；
(四)、系统用例设计和流程图
系统流程图：
a) 程序详细设计：各种功能的实现方法描述、关键代码分析
问题分析:迷宫求解
这种迷宫求解的问题非常适合使用搜索来求解
此处我们使用深度优先搜索算法去求出迷宫的解,当一条支路完成时,我们将整条完整的路径输出
关键代码分析
1.栈的几种基本操作:
//栈中存位置以及遍历时所走的方向，打印时可以显示出来
typedef struct Node{
int x;
int y;
// int dir; //-1为左上右下对应 '\' 0为上下对应'|' 1为左右对应'——' 2为左下右上对应'/'
struct Node *next;
}Node;
typedef Node* Stack; //定义数据结构栈 Stack
//-----------创建一个空栈--------------
Stack creakEmptyStack(){
Stack p;
p=(Stack)malloc(sizeof(Node)); //申请一个空间
if(p){
p->next=NULL;
return p;
}
}
//------------将元素压入栈----------------
void push(int x,int y,Stack s){
Stack p;
p=(Stack)malloc(sizeof(Node));
if(p){ //如果申请空间成功则用头插法将元素压入
p->x=x;
p->y=y;
if(!s->next) p->next=NULL; //如果此时栈里还没有任何元素，则p此时为第一个结点
else p->next=s->next; //否则将p插入头结点之后
s->next=p;
}
else{
printf("No space!\n");
}
}
//-------------检测栈是否为空--------------
int isEmpty(Stack s){ //为空则返回1，不为空返回0
if(s->next==NULL) return 1;
else return 0;
}
//--------------将元素弹出栈----------------
void pop(Stack s){
Stack p;
p=s->next;
if(p->next){
s->next=p->next;
free(p);
}
else return;
}
//------------取栈顶元素------------------
Node top(Stack s){
Node t;
//判断是否为空，若不为空则返回
t=*(s->next);
return t;
}
解释:此处我们使用栈来储存我们迷宫的解,上述代码定义了一系列的
2.核心算法:
此处我们使用深度优先搜索去求出迷宫的解\
代码如下
//-----------遍历迷宫寻找路径(dfs)------------
void mazePath(int x,int y,int endx,int endy,int n,int m,Stack s){
int newx,newy,i;
Node t;
for(i=0;i<4;i++){
newx=x+direction[i][0];
newy=y+direction[i][1];
if(newx>=0&&newx<n&&newy>=0&&newy<m&&maze[newx][newy]==0){ //下一个路能走
push(newx,newy,s);
maze[newx][newy]=2;
if(newx==endx&&newy==endy){//走到出口
flag++;
printPath(s,n,m);
maze[newx][newy]=0;
pop(s);
}
else{
mazePath(newx,newy,endx,endy,n,m,s); //开始递归
}
}
// else if(!isEmpty(s)) pop(s);
}
maze[x][y]=0; //遍历完四个方向之后回溯前将自己赋为空
pop(s);
}
解释如下:
在该方法中,xy代表的是当前坐标的xy轴,newx,newy代表的是下一坐标点的xy轴坐标,
随后我们对坐标进行判断,
2.1.若下一坐标点为1,则进行下一个方向的寻找
2.2.若下一个坐标为0且不越界
则将下一坐标推入栈,并将该点标记为已走(即标记为2)
再次进行判断
2.2.1. 如果下一坐标为出口
打印整个路径
2.2.2.下一坐标不为出口
递归
流程图如下:
3.打印迷宫路径
//-------------打印迷宫路径-----------------
void printPath(Stack s,int n,int m){
int cont =0; //计算路径长度
s=s->next;
int i=0,j=0;
printf("第%d条路径为：\n",flag);
for(i=0;i<n;i++){ //按图形输出
for(j=0;j<m;j++){
if(maze[i][j]==2) printf("* ");
else printf("%d ",maze[i][j]);
}
printf("\n");
}
while(s->next){ //将栈中的元素输出为直观路径
printf("(%d,%d)->",s->x+1,s->y+1);
s=s->next;
cont++;
}
printf("(%d,%d)",s->x+1,s->y+1);
cont++;
if(cont<MIN) MIN=cont;
printf("\n");
printf("路径长度为：%d\n\n",cont);
}
解释:将栈中的路径输出
b) 使用情况：展示各种功能的运行情况
样例一:手动输入迷宫正常使用程序：
首先输入迷宫的行数和列数
随后输入迷宫的各行各列
其中0代表路，1代表墙
随后程序会显示迷宫的大致样式
并给出迷宫道路的解
输入样例:
3 3
1
0 0 0
1 0 0
1 1 0
1 1 3 3
输出:
生成的迷宫如下：
0 0 0
1 0 0
1 1 0
请输入起点及终点：
第1条路径为：
* * *
1 0 *
1 1 *
(3,3)->(2,3)->(1,3)->(1,2)
路径长度为：4
第2条路径为：
* * 0
1 * *
1 1 *
(3,3)->(2,3)->(2,2)->(1,2)
路径长度为：4
样例二:随机生成迷宫
输入:
2 2
0
2 1 2 2
输出:
第1条路径为：
1 1
* *
(2,2)
路径长度为：1
最短路径长度为:1
c) 总结：分析程序的优点和不足、开发时遇到的困难及解决的问题、总结。
开发时遇到的问题:算法不会用,栈的操作总是出错,随后去找百度搜索,翻书,找到解决问题的方法
作为一名初学者，我对深度优先搜索算法的使用进行了研究，并通过实践掌握了它的一些使用心得。深度优先搜索算法可以解决很多问题，如最短路径、迷宫问题、图着色问题等，因此学会使用深度优先搜索算法是非常有益的。
首先，我认为理解深度优先搜索算法的核心思想是非常重要的。深
在使用广度优先算法解决问题时，我发现栈的使用非常重要。
最后，我深刻认识到广度优先搜索算法的局限性。尽管广度优先搜索算法可以解决很多问题，但有些问题并不适用于该算法。例如，当搜索的节点数量非常大时，算法的时间和空间复杂度会变得非常高。因此，在使用广度优先搜索算法解决问题时，需要注意算法的局限性，并选择最适合当前问题的算法。
总之，通过对广度优先搜索算法的研究和实践，我认为理解其核心思想、正确选择数据结构、考虑时间和空间限制、深入了解其局限性等方面都是非常重要的。广度优先算法可以解决很多问题，但在实践过程中可能会遇到各种问题。如果我们能够在使用广度优先搜索算法时思考这些问题，并做出正确的决策，那么我们就能够更好地应用广度优先搜索算法，解决更多更复杂的问题。
关于本次的迷宫问题,我认为深度优先搜索是非常好的算法
d) 参考文献。
[1]严蔚敏.数据结构C语言版[M].清华大学出版社，2007.
[3]百度百科 https://baike.baidu.com/
[4] 栈——栈的定义及基本操作（初始化、判空、进栈、出栈、遍历栈、销毁栈等）-CSDN博客，https://blog.csdn.net/weixin_44162361/article/details/115868909
[5]BFS(广度优先搜索)：层序遍历和最短路径 - 灿影之晶 - 博客园 (cnblogs.com)，https://www.cnblogs.com/sbb-first-blog/p/13259728.html
[6] 深度优先搜索（DFS）算法详解 (biancheng.net),http://data.biancheng.net/view/325.html