C语言数据结构之迷宫求解问题
更新时间:2020年4月25日 17:25 点击:1801
现在网上各种对于迷宫的求解,版本多的数不胜数。本人小白一枚,贴上自己对迷宫的求解这个小项目,自己写的。望能帮助一些同样有困难的人,毕竟我当时费解了好一会儿时间呢。
首先,先标明对于迷宫求解这个项目,首先我提出自己的思路,利用“穷举求解”的方法(严蔚敏老师数据结构一书中提到,一开始不知方法其名。)其实简单来说就是一条路一条路去试,当然不能随便试,我的方法是按照从入口出发,顺一个方向向前探索,走得通就继续向前走;否则留下标记沿原路退回并换一个方向继续探索,直到所有的路都走完为止。还是用栈的先进后出的结构保存一路的路线。代码用到了栈的顺序实现数组格式的结构(对于栈并没有详细阐述)。
//调用头文件 #ifndef AFXSTD_H #define AFXSTD_H #include<stdio.h> #include<stdlib.h> #include<malloc.h> #include<iostream> using namespace std; // cout; cin;C++的输入输出 #endif
//迷宫的结构体的创建 #ifndef MAZE_H #define MAZE_H #define ROWSIZE 10 //迷宫大小 #define COLSIZE 10 #define Reachable 0 //可以到达的结点 #define Bar 1 //障碍物 #define Foot 2 //足迹 #define Mark 3 //不可通路标记 typedef int MapType[ROWSIZE][COLSIZE]; // 地图类型 typedef struct { int row;// x int col;// y; }PosType; //坐标结构体 typedef struct { int ord; //通道块在道路上的序号 PosType seat; //小人坐标 int di; // 方向 // 1 2 3 4 }MElemType; //试迷宫小人的结构 typedef MElemType SElemType; // 和stack 关联 bool MazePass(MapType maze,PosType curpos); void FootPrint(MapType maze,PosType curpos); //足迹打印 PosType NextPos(PosType curpos,int di); //下一个位置 void MarkPrint(MapType maze,PosType curpos); //打印不可通标记 bool MazePath(MapType maze,PosType start,PosType end); //迷宫解谜核心 void PrintMap(MapType maze); //打印地图 #endif
//栈的结构体 #include"Maze.h" #ifndef SEQSTACK_H #define SEQSTACK_H #define STACKSIZE 100 //typedef int SElemType; struct SeqStack { SElemType *data; int maxsize; int top; }; void Init_Stack(SeqStack &st); void Destroy_Stack(SeqStack &st); void Stack_Clear(SeqStack &st); bool Stack_Empty(SeqStack &st); bool Stack_Full(SeqStack &st); int Stack_Size(SeqStack &st); bool Stack_Push(SeqStack &st,const SElemType &x); bool Stack_Pop(SeqStack &st, SElemType &x); SElemType GetTop(SeqStack &st); void Pop(SeqStack &st); #endif
以上是头文件的创建,和结构体的创建,现在真的深切感到结构体的重要性。结构体创建不好就是自己给自己挖坑,切记切记!!
现在贴出函数的代码,解释我会尽力都写清楚。(栈的问题我后续会重新再仔细阐述的,这次的重点在于迷宫的求解,所以直接贴出栈的详细代码,望谅解。)
//这里是栈的实现代码 #include"AfxStd.h" #include"Stack.h" bool Stack_Resize(SeqStack &st) { SElemType *s = (SElemType*)malloc(sizeof(SElemType)*st.maxsize * 2); if(NULL == s) return false; for(int i = 0;i<= st.top;++i) { s[i] = st.data[i]; } free(st.data); st.data = s; st.maxsize = st.maxsize * 2; return true; } void Init_Stack(SeqStack &st) { st.maxsize = STACKSIZE; st.top = -1; st.data = (SElemType*)malloc(sizeof(SElemType)*st.maxsize); if(NULL == st.data) { exit(0); } } void Destroy_Stack(SeqStack &st) { free(st.data); st.data = NULL; st.maxsize = 0; st.top = -1; } void Stack_Clear(SeqStack &st) { st.top = -1; } bool Stack_Empty(SeqStack &st) { return Stack_Size(st) == 0; } bool Stack_Full(SeqStack &st) { return Stack_Size(st) == st.maxsize; } int Stack_Size(SeqStack &st) { return st.top + 1; } bool Stack_Push(SeqStack &st,const SElemType &x) { if(Stack_Full(st) && ! Stack_Resize(st)) { return false; } st.data[++st.top] = x; return true; } bool Stack_Pop(SeqStack &st, SElemType &x) { if(Stack_Empty(st)) { return false; } x = st.data[st.top--]; return true; }
//调用前面创建的头文件 #include"AfxStd.h" #include"Maze.h" #include"Stack.h" ///////////////////////////////////////////////// bool MazePass(MapType maze,PosType curpos) //判断是否可以通过 { return maze[curpos.row][curpos.col] == Reachable; //判断当前结点是否能通过 } void FootPrint(MapType maze,PosType curpos) //打印足迹 { maze[curpos.row][curpos.col] = Foot; } PosType NextPos(PosType curpos,int di) //对下一个结点方向的判断 { switch(di) { case 1: curpos.row+=1; break;// 1 case 2: curpos.col-=1; break;// 2 case 3: curpos.row-=1; break;// 3 case 4: curpos.col+=1; break;// 4 } return curpos; } void MarkPrint(MapType maze,PosType curpos) //不能通过的结点留下不能通过的标记 { maze[curpos.row][curpos.col] = Mark; } bool MazePath(MapType maze,PosType start,PosType end)//(核心)迷宫解谜 { bool res = false; //定义一个res参数为布尔型 PosType curpos = start; //初始当前位置为入口 int curstep = 1; // 初始探索方向为1 SeqStack st; //路径存储栈 MElemType e; //初始探索小人 Init_Stack(st); //初始化栈 do{ if(MazePass(maze,curpos)) //当前位置可通过,即是未曾走到过的坐标 { FootPrint(maze,curpos); //留下足迹 e.di = 1, e.seat = curpos,e.ord = curstep++; Stack_Push(st,e); //加入路径中 if(curpos.row == end.row && curpos.col == end.col) { res = true; break; } //到达终点 curpos = NextPos(curpos,1); //探索下一位置 } else { if(!Stack_Empty(st)) //当前位置不能通过 { Stack_Pop(st,e); while(e.di == 4 && !Stack_Empty(st)) { MarkPrint(maze,e.seat); Stack_Pop(st,e); // 留下不能通过的标记,并退回一步 } if(e.di < 4) { e.di+=1; // 换下一个方向探索 Stack_Push(st,e); //再次记录路径 curpos = NextPos(e.seat,e.di); // 当前位置设为新方向的相邻块 } } } }while(!Stack_Empty(st)); //当栈空摧毁栈,返回失败参数 Destroy_Stack(st); return res; } void PrintMap(MapType maze) //打印地图 { for(int i = 0;i<ROWSIZE;++i) { for(int j = 0;j<COLSIZE;++j) { printf("%2d",maze[i][j]); } printf("\n"); } printf("\n"); }
以上就是迷宫的详细解释,希望能帮助到大家。后面再添加我的测试文件。
#include"AfxStd.h" #include"Maze.h" int main() { MapType maze ={ //一开始地图的创建 {1,1,1,1,1,1,1,1,1,1}, {1,0,1,1,1,1,1,1,1,1}, {1,0,0,0,0,0,0,0,0,1}, {1,0,0,0,1,1,1,1,0,1}, {1,0,0,0,1,1,1,1,0,1}, {1,0,1,1,1,1,0,0,0,1}, {1,0,1,1,1,1,1,1,1,1}, {1,0,0,0,0,0,0,1,1,1}, {1,0,1,1,1,1,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1}, }; PosType start={1,1},end={8,8}; PrintMap(maze); //打印初始地图 MazePath(maze,start,end); PrintMap(maze); //打印迷宫解法 return 0; }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持猪先飞。
上一篇: C语言实现小学生考试系统
下一篇: C语言实现小型电子词典
相关文章
- 这篇文章主要介绍了如何利用java语言实现经典《复杂迷宫》游戏,文中采用了swing技术进行了界面化处理,感兴趣的小伙伴可以动手试一试...2022-02-01
- 这篇文章主要为大家详细介绍了C语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
- 这篇文章主要介绍了C#数据结构之队列(Quene),结合实例形式较为详细的讲述了队列的功能、原理与C#实现队列的相关技巧,需要的朋友可以参考下...2020-06-25
- free函数是释放之前某一次malloc函数申请的空间,而且只是释放空间,并不改变指针的值。下面我们就来详细探讨下...2020-04-25
- 这篇文章主要介绍了C语言中计算正弦的相关函数总结,包括正弦和双曲线正弦以及反正弦的函数,需要的朋友可以参考下...2020-04-25
详解C语言中的rename()函数和remove()函数的使用方法
这篇文章主要介绍了详解C语言中的rename()函数和remove()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25- 这篇文章主要介绍了C语言中求和、计算平均值、方差和标准差的实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-12-10
- 本篇文章主要讲解C语言 基本语法,这里提供简单的示例和代码来详细讲解C语言的基本语法,开始学习C语言的朋友可以看一下,希望能够给你带来帮助...2021-09-18
- 这篇文章主要介绍了C语言中send()函数和sendto()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25
- 今天小编就为大家分享一篇C语言实现从文件读入一个3*3数组,并计算每行的平均值,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了C语言中memcpy 函数的用法详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了使用C语言操作文件的基本函数整理,包括创建和打开以及关闭文件的操作方法,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C#常用数据结构和算法,这里我们总结了一些知识点,可以帮助大家理解这些概念。...2020-06-25
- 这篇文章主要介绍了C语言中查找字符在字符串中出现的位置的方法,分别是strchr()函数和strrchr()函数的使用,需要的朋友可以参考下...2020-04-25
- 本文将结合实例代码介绍Javascript结合Vue实现对任意迷宫图片的自动寻路,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-06-13
- 很多同学在学习c语言的时候是不是会碰到a++和++a都有甚么作用啊。今天我们就来探讨下...2020-04-25
- 这篇文章主要对C语言中const关键字的用法进行了详细的分析介绍,需要的朋友可以参考下...2020-04-25
- 下面小编就为大家带来一篇C语言实现时间戳转日期的算法(推荐)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-04-25