《数据结构课程设计_迷宫求解》由会员分享，可在线阅读，更多相关《数据结构课程设计_迷宫求解（21页珍藏版）》请在金锄头文库上搜索。
1、迷宫求解一 问 题 描 述对迷宫问题的求解过程实际就是从入口开始，一步一步地走到出口的过程。基 本 要 求 ：输 入 一 个 任 意 大 小 的 迷 宫 数 据 ， 用 递 归 和 非 递 归 两 种 方 法 求 出一 条 走 出 迷 宫 的 路 径 ， 并 将 路 径 输 出 。二设计思路在本程序中用两种方法求解迷宫问题-非递归算法和递归算法。对于非递归算法采用回溯的思想，即从入口出发，按某一方向向前探索，若能走通，并且未走过，则说明某处可以到达，即能到达新点，否则试探下一方向；若所有的方向均没有通路，或无路可走又返回到入口点。在求解过程中，为了保证在到达某一点后不能向前继续行走（无路）时，
2、能正确返回前一点以便继续从下一个方向向前试探，则需要用一个栈保存所能到达的没一点的下标及该点前进的方向，然后通过对各个点的进出栈操作来求得迷宫通路。对于递归算法，在当前位置按照一定的策略寻找下个位置，在下个位置又按照相同的策略寻找下下个位置；直到当前位置就是出口点，每一步的走法都是这样的。随着一步一步的移动，求解的规模不断减小；如果起始位置是出口，说明路径找到，算法结束，如果起始位置的四个方向都走不通，说明迷宫没有路径，算法也结束。另外，为了保证迷宫的每个点都有四个方向可以试探，简化求解过程，将迷宫四周的值全部设为 1，因此将 m 行 n 列的迷宫扩建为m+2 行，n+2 列，同时用数组来保存
3、迷宫阵列。三 数 据 结 构 设 计在 迷 宫 阵 列 中 每 个 点 都 有 四 个 方 向 可 以 试 探 ， 假 设 当 前 点 的 坐标 （ x， y） ， 与 其 相 邻 的 四 个 点 的 坐 标 都 可 根 据 该 点 的 相 邻 方 位而 得 到 ， 为 了 简 化 问 题 ， 方 便 求 出 新 点 的 坐 标 ， 将 从 正 东 开 始 沿 顺时 针 进 行 的 这 四 个 方 向 的 坐 标 增 量 放 在 一 个 结 构 数 组 move4中 ，每 个 元 素 有 两 个 域 组 成 ， 其 中 x 为 横 坐 标 增 量 ， y 为 纵 坐 标 增 量 ，定 义 如
4、下 ：typedef struct int x,y;item;为到达了某点而无路可走时需返回前一点，再从前一点开始向下一个方向继续试探。因此，还要将从前一点到本点的方向压入栈中。栈中的元素由行、列、方向组成，定义如下：typedef struct int x,y,d;DataType;由于在非递归算法求解迷宫的过程中用到栈，所以需定义栈的类型，本程序中用的是顺序栈，类型定义如下;typedef struct DataType dataMAXSIZE;int top;SeqStack, *PSeqStack;四 功 能 函 数 设 计（ 1） 函 数 PSeqStack Init_SeqStac
5、k()此函数实现对栈的初始化工作。（ 2） 函 数 Empty_SeqStack(PSeqStack S)此函数用于判断栈是否为空。（ 3） 函 数 Push_SeqStack (PSeqStack S, DataType x)此函数实现入栈操作。（ 4） 函 数 Pop_SeqStack(PSeqStack S ,DataType *x)此函数实现出栈操作。（ 5） 函 数 Destory_Seqstack(PSeqStack *S)此函数执行栈的销毁操作，释放内存空间。（ 6） 函 数 mazepath(int mazen+2,item move,int x0,int y0)此函数实现对迷
6、宫问题的非递归算法求解。在求解过程中需调用上面定义的关于栈的一系列函数（栈的初始化，判空，入栈，出栈，栈的销毁） ，进而求得迷宫路径。（ 7） 函 数 path(int mazen+2,item move,int x,int y,int step)此函数实现对迷宫问题的递归算法求解。（ 8） 函 数 print_way(int mazen+2,item move)此函数用于在递归算法求解迷宫后输出求解后的结果，即打印迷宫路径。（ 9） 函 数 copy(int mazen+2,int msn+2)此函数的作用是复制一下输入的原始迷宫序列，因为本程序是通过菜单选择求解迷宫的实现方式，将非递归算法
7、和递归算法放在一起通过菜单选择实现，在调用完一种算法后，为保证调用另一种算法时原始迷宫序列未改变，所以需调用此函数来原始迷宫序列备份一下。（ 10） 主 函 数 main()定义变量，实现迷宫的输入操作，通过菜单选择求解迷宫路径的实现方法，调用相关函数。（11）系统功能总体模块（a）栈的初始化（b）判栈空函数（c）入栈（d）出栈（e）销毁栈（f）非递归算法求解迷宫函数（g）递归算法求解迷宫函数（h）打印递归算法求解迷宫的路径函数（i） 复制原始迷宫阵列函数（j）主函数五编码实现#include#include#define m 6#define n 8#define MAXSIZE 100ty
8、pedef struct int x,y;item;item move4;typedef struct int x,y,d;DataType;typedef struct DataType dataMAXSIZE;int top;SeqStack, *PSeqStack;PSeqStack Init_SeqStack() /栈的初始化 PSeqStack S;S=(PSeqStack)malloc(sizeof(SeqStack);if (S)S-top=-1;return S;int Empty_SeqStack(PSeqStack S) /判栈空 if (S-top=-1) return
9、1;else return 0;int Push_SeqStack (PSeqStack S, DataType x) /入栈 if (S-top=MAXSIZE-1)return 0; /栈满不能入栈else S-top+;S-dataS-top=x;return 1;int Pop_SeqStack(PSeqStack S ,DataType *x) /出栈 if (Empty_SeqStack ( S ) )return 0; /栈空不能出栈 else *x=S-dataS-top;S-top-;return 1; void Destory_Seqstack(PSeqStack *S)
10、/销毁栈if(*S)free(*S);*S=NULL;return;int mazepath(int mazen+2,item move,int x0,int y0) /非递归算法求解迷宫PSeqStack S;DataType temp;int x,y,d,i,j;temp.x=x0; temp.y=y0;temp.d=-1;S=Init_SeqStack();if(!S)printf(栈初始化失败！);return (0);Push_SeqStack (S, temp);while(!Empty_SeqStack(S)Pop_SeqStack(S ,x=temp.x;y=temp.y;d=
11、temp.d+1;while(d1)printf(%d %d) - ,i,j);printf(nn.n);elseprintf(无法找到路径！n);void copy(int mazen+2,int msn+2) /复制原始迷宫序列函数for(int i=0;i#include#define MaxVertexNum 30#define INFINITY 3000typedef structchar vertexsMaxVertexNum;int arcsMaxVertexNumMaxVertexNum;int vertexNum,edgeNum;MGraph;typedef structin
12、t adjvertex;int lowcost;ClosEdgeMaxVertexNum;void CreatGraph(MGraph *G)int i,j,k,n;printf(请输入顶点数和边数：);scanf(%d %d,printf(n);for(i=0;ivertexNum;i+)printf(请输入第%d 个顶点字符信息(共%d 个)：,i+1,G-vertexNum);scanf(%c,getchar();for(i=0;ivertexNum;i+)for(j=0;jvertexNum;j+)if(i=j)G-arcsij=0;elseG-arcsij=999;for(k=0;k
13、edgeNum);k+)printf(n);printf(请输入边对应的顶点序号(共%d 个)：,G-edgeNum);scanf(%d %d,printf(请输入此边的权值：);scanf(%d,G-arcsij=n;G-arcsji=n;printf(n);printf(图已成功创建!n);printf(n);void MiniSpanTree_PRIM(MGraph *G,int u,ClosEdge closedge)int i,j,w,k;int count=0;for(i=0;ivertexNum;i+)if(i!=u)closedgei.adjvertex=u;closedgei
14、.lowcost=G-arcsui;closedgeu.lowcost=0;for(i=0;ivertexNum-1;i+)w=INFINITY;for(j=0;jvertexNum;j+)if(closedgej.lowcost!=0 & closedgej.lowcostvertexNum;j+)if(G-arcskjarcskj;for(i=0;ivertexNum;i+)if(i!=u)printf(输出构建的最小生成树为：);printf(%d-%d,%dn,i,closedgei.adjvertex,G-arcsiclosedgei.adjvertex);count+=G-arcs
15、iclosedgei.adjvertex;printf(n);printf(此最小生成树的代价为：%d,count);printf(n);void main()MGraph *G;int u;ClosEdge closedge;G=(MGraph*)malloc(sizeof(MGraph);CreatGraph(G);printf(输入构造最小生成树的出发顶点：);scanf(%d,printf(n);MiniSpanTree_PRIM(G,u,closedge);printf(n);六运行与测试七总结本程序相对来说不太难，但在调试过程中也遇到很多错误，其中也包括很多低级错误，还有内存溢出问题，
