数据结构课程设计迷宫求解.docx

迷宫求解一问题描述对迷宫问题的求解过程实际就是从入口开始，一步一步地走到出 口的过程。 基本要求：输入一个任意大小的迷宫数据，用递归和非递归两种方法求出 一条走出迷宫的路径，并将路径输出。二设计思路在本程序中用两种方法求解迷宫问题 - 非递归算法和递归算法。 对于非递归算法采用回溯的思想，即从入口出发，按某一方向向 前探索，若能走通，并且未走过，则说明某处可以到达，即能到达新 点，否则试探下一方向；若所有的方向均没有通路，或无路可走又返 回到入口点。在求解过程中， 为了保证在到达某一点后不能向前继续 行走（无路）时，能正确返回前一点以便继续从下一个方向向前试探， 则需要用一个栈保存所能到达的没一点的下标及该点前进的方向， 然 后通过对各个点的进出栈操作来求得迷宫通路。对于递归算法，在当前位置按照一定的策略寻找下个位置，在下 个位置又按照相同的策略寻找下下个位置； 直到当前位置就是出口 点，每一步的走法都是这样的。随着一步一步的移动，求解的规模不 断减小；如果起始位置是出口，说明路径找到，算法结束，如果起始 位置的四个方向都走不通，说明迷宫没有路径，算法也结束。另外，为了保证迷宫的每个点都有四个方向可以试探，简化求解过程，将迷宫四周的值全部设为 1，因此将 m行 n 列的迷宫扩建为 m+2行， n+2列，同时用数组来保存迷宫阵列。 三数据结构设计在迷宫阵列中每个点都有四个方向可以试探，假设当前点的坐 标（ x，y），与其相邻的四个点的坐标都可根据该点的相邻方位 而得到，为了简化问题，方便求出新点的坐标，将从正东开始沿 顺时针进行的这四个方向的坐标增量放在一个结构数组 move4 中，每个元素有两个域组成，其中 x 为横坐标增量， y 为纵坐标增 量，定义如下：typedef structint x,y;item;为到达了某点而无路可走时需返回前一点，再从前一点开始向下 一个方向继续试探。因此，还要将从前一点到本点的方向压入栈中。 栈中的元素由行、列、方向组成，定义如下： typedef structint x,y,d;DataType;由于在非递归算法求解迷宫的过程中用到栈，所以需定义栈的类 型，本程序中用的是顺序栈，类型定义如下 ;typedef structDataType dataMAXSIZE;int top;SeqStack, *PSeqStack;四功能函数设计（ 1）函数 PSeqStack Init_SeqStack（） 此函数实现对栈的初始化工作。（ 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） 此函数实现对迷宫问题的非递归算法求解。在求解过程中需调 用上面定义的关于栈的一系列函数 （栈的初始化， 判空，入栈，出栈， 栈的销毁），进而求得迷宫路径。（ 7）函数 path（int mazen+2,item move,int x,int y,intstep） 此函数实现对迷宫问题的递归算法求解。（ 8）函数 print_way（int mazen+2,item move） 此函数用于在递归算法求解迷宫后输出求解后的结果， 即打印迷 宫路径。（ 9）函数 copy（int mazen+2,int msn+2）此函数的作用是复制一下输入的原始迷宫序列，因为本程序是通 过菜单选择求解迷宫的实现方式， 将非递归算法和递归算法放在一起 通过菜单选择实现， 在调用完一种算法后， 为保证调用另一种算法时 原始迷宫序列未改变，所以需调用此函数来原始迷宫序列备份一下。 （ 10）主函数 main（）定义变量，实现迷宫的输入操作，通过菜单选择求解迷宫路径的 实现方法，调用相关函数。（11）系统功能总体模块（a）栈的初始化b）判栈空函数c）入栈d）出栈e）销毁栈f ）非递归算法求解迷宫函数g）递归算法求解迷宫函数h)打印递归算法求解迷宫的路径函数i ) 复制原始迷宫阵列函数報国州()五编码实现#include<stdio.h>#include<stdlib.h>#define m 6#define n 8#define MAXSIZE 100typedef structint x,y;item;item move4;typedef structint x,y,d;DataType;typedef structDataType 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 1;elsereturn 0;/入栈int Push_SeqStack (PSeqStack S, DataType x)if (S->top=MAXSIZE-1)return 0; /栈满不能入栈 elseS->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) /销毁栈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 ,&temp); x=temp.x; y=temp.y;d=temp.d+1;while(d<4)i=x+moved.x;j=y+moved.y;if(mazeij=0)temp.x=x;temp.y=y;temp.d=d;Push_SeqStack (S, temp);x=i;y=j;mazexy=-1;if(x=m&&y=n)printf("n 非递归算法求解的迷宫路径为 (顺序为从出口到入 口输出)：n");while(!Empty_SeqStack(S)Pop_SeqStack(S,&temp);printf("(%d %d) <- ",temp.x,temp.y);printf("nnn");Destory_Seqstack(&S);return 1;elsed=0;elsed+;Destory_Seqstack(&S);return 0;int path(int mazen+2,item move,int x,int y,int step) /递归算法求解迷宫 int i;step+; mazexy=step;if(x=m&&y=n)return 1;for(i=0;i<4;i+) if(mazex+movei.xy+movei.y=0) if(path(maze,move,x+movei.x,y+movei.y,step) return 1;step-;mazexy=0;return 0;void print_way(int mazen+2,item move) / 打印递归算法求解迷宫的路径 int i,j;if(path(maze,move,1,1,1)printf("n 找到路径的矩阵形式输出如下： n");for(i=0;i<m+2;i+)for(j=0;j<n+2;j+) printf("%d ",mazeij);printf("n");printf("n");printf(" 递归算法求解的迷宫路径为(顺序为从入口到出口输出) ：n"); for(i=0;i<m+2;i+)for(j=0;j<n+2;j+) if(mazeij>1) printf("(%d %d) -> ",i,j);printf("nnn");elseprintf(" 无法找到路径！ n");void copy(int mazen+2,int msn+2)/复制原始迷宫序列函数for(int i=0;i<m+2;i+)for(int j=0;j<n+2;j+) msij=mazeij;void main()int mazem+2n+2;item move4;int i,j,Q;printf(" 请输入迷宫序列： n"); for(i=0;i<m+2;i+)for(j=0;j<n+2;j+) scanf("%d",&mazeij); printf("n"); move0.x=0;move0.y=1; move1.x=1;move1.y=0; move2.x=0;move2.y=-1; move3.x=-1;move3.y=0; printf("n");int mase1m+2n+2;copy(maze,mase1);printf("走迷宫*n");printf("n");printf("1. 非递归形式走迷宫 n");printf("2. 递归形式走迷宫 n");printf("3. 退出 n");printf("求解方式*n");while(1);printf("n 请选择 (选择 0 退出 )： scanf("%d",&Q);switch(Q)case 1:mazepath(maze,move,1,1); break;case 2:print_way(mase1,move);break;case 0:exit(0);六运行与测试七总结在这个课程设计中，遇到的主要问题是选择了一种实现方法后，在选择另一种时不会输出结果， 但是当我把这两个程序分开调试时都 会出现结果，结果还是正确的， 后来经过分析知道原来是调用完一种 方法后，原来输入的迷宫序列可能被改变了，因此，又增加了一个 复 制原始迷宫序列的函数， 对原始序列进行了保存， 然后在调用时就出 现结果了。通过调试这个程序，熟悉了迷宫的两种求法，在调试找错 过程中也学会好多。构造 n 个城市连接的最小生成树一问题描述一个地区的 n 个城市间的距离网，用 Prim 算法建立最小生成 树，并计算得到的最小生成树的代价。基本要求：1） 城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定 义采用课本中给出的定义，若两个城市之间不存在道路，则将相 应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的 最小生成树中包括了哪些城市间的道路，并显示得到的最小生成 树的代价。2）表示城市间距离网的邻接矩阵 （要求至少 6个城市， 10条边） 二设计思路在本程序中，各个地区之间的距离网可以用邻接矩阵表示，在 进行定义时表示出相应的权值，以便计算最小代价，当权值赋为 999 时，表示两城市之间无路径。 然后用 Prim 算法建立最小生成树，进 而在建立过程中可以计算得到的最小生成树的代价。三数据结构设计首先，在用邻接矩阵存储图时，除了用一个二维数组存储用于 表示顶点间相邻关系的邻接矩阵外，还需要用一个一维数组来存 储顶点信息，另外，还有图的顶点数和边数。故可将其形式描述 如下：typedef structchar vertexsMaxVertexNum;int arcsMaxVertexNumMaxVertexNum;int vertexNum,edgeNum;MGraph;为实现普利姆算法求最小生成树，需设置一个辅助数组Closedge，里面存放一顶点为与已构造好的部分生成树的顶点间权值最小的顶 点，边为某顶点与已构造好的部分生成树的顶点间的最小权值。 定义 形式如下：typedef structint adjvertex;int lowcost;ClosEdgeMaxVertexNum;四功能函数设计( 1)函数 CreatGraph(MGraph *G)此函数用于创建邻接矩阵，用邻接矩阵来存储图，建立各个 城市之间的关系。在建立过程中，给相应的边赋权值，以表示两 城市之间的代价。注： 999 代表两城市之间无路径。( 2)函数 MiniSpanTree_PRIM(MGraph* G,int u,ClosEdge closedge)此函数为普利姆函数， 用于求最小生成树， 在此过程中求出相应的权值， 及最小生成树权值之和， 用于表示连接各城市之间的最小代 价。（ 3）主函数 main（）定义变量，分别调用相应的函数。（4）系统功能总体模块（ a）创建邻接矩阵 CreatGraph（MGraph *G） 的流程图如下：( b)构建最小生成树普利姆函数 MiniSpanTree_PRIM(MGraph* G,int u,ClosEdge closedge) 流程图如下 :c)主函数 main() 流程图如下：五编码实现#include<stdio.h>#include<stdlib.h>#define MaxVertexNum 30#define INFINITY 3000 typedef struct char vertexsMaxVertexNum;int arcsMaxVertexNumMaxVertexNum; int vertexNum,edgeNum;MGraph;typedef structint adjvertex;int lowcost;ClosEdgeMaxVertexNum;void CreatGraph(MGraph *G)int i,j,k,n;printf(" 请输入顶点数和边数： ");scanf("%d %d",&(G->vertexNum),&(G->edgeNum);printf("n");for(i=0;i<G->vertexNum;i+)printf("请输入第 %d个顶点字符信息 (共%d 个)：",i+1,G->vertexNum); scanf("%c",&(G->vertexsi);getchar();for(i=0;i<G->vertexNum;i+)for(j=0;j<G->vertexNum;j+)if(i=j)G->arcsij=0;elseG->arcsij=999;for(k=0;k<(G->edgeNum);k+)printf("n");printf("请输入边<Vi,Vj> 对应的顶点序号 (共%d个)：",G->edgeNum); scanf("%d %d",&i,&j);printf(" 请输入此边的权值： ");scanf("%d",&n);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;i<G->vertexNum;i+)if(i!=u)closedgei.adjvertex=u;closedgei.lowcost=G->arcsui;closedgeu.lowcost=0;for(i=0;i<G->vertexNum-1;i+)w=INFINITY;for(j=0;j<G->vertexNum;j+)if(closedgej.lowcost!=0 && closedgej.lowcost<w)w=closedgej.lowcost;k=j;closedgek.lowcost=0;for(j=0;j<G->vertexNum;j+) if(G->arcskj<closedgej.lowcost)closedgej.adjvertex=k; closedgej.lowcost=G->arcskj;for(i=0;i<G->vertexNum;i+)if(i!=u)printf(" 输出构建的最小生成树为： ");printf("%d->%d,%dn",i,closedgei.adjvertex,G->arcsiclosedgei.adjvertex);count+=G->arcsiclosedgei.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",&u);printf("n");MiniSpanTree_PRIM(G,u,closedge);printf("n");六运行与测试七总结本程序相对来说不太难，但在调试过程中也遇到很多错误，其中 也包括很多低级错误，还有内存溢出问题，不出现结果问题，通过在 猜测出问题的地方加写 printf 输出提示，然后查找原因，发现了好 多问题。最后找到原因，加以改正。通过这次的课程设计，使我加深 了对相关知识点的理解掌握， 同时在设计调试过程中， 也发现了好多 的不足之处， 对学过的好多知识点都掌握的不够牢固， 所以在用起来 时经常会出错， 还有许多因为粗心带来的问题， 虽然在这次课程设计 花费了好长时间，但总的来说，收获还是挺大的。