数据结构与算法大作业:走迷宫程序(实验报告) | 您所在的位置:网站首页 › 大数据大作业实验报告 › 数据结构与算法大作业:走迷宫程序(实验报告) |
好家伙,本篇为应付老师的实验报告,有需要的拿去抄吧
思路讲解在上一篇: 数据结构与算法大作业:走迷宫程序(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=0&&newx=0&&newynext; int i=0,j=0; printf("第%d条路径为:\n",flag); for(i=0;ix+1,s->y+1); s=s->next; cont++; } printf("(%d,%d)",s->x+1,s->y+1); cont++; if(cont(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=0&&newx=0&&newynext; int i=0,j=0; printf("第%d条路径为:\n",flag); for(i=0;inext){ //将栈中的元素输出为直观路径 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(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
|
CopyRight 2018-2019 实验室设备网 版权所有 |