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

1、迷宫求解一. 问题描述对迷宫问题的求解过程实际就是从入口开始，一步一步地走到出 口的过程。基本要求：输入一个任意大小的迷宫数据，用递归和非递归两种方法求出 一条走出迷宫的路径，并将路径输出。二. 设计思路在本程序中用两种方法求解迷宫问题-非递归算法和递归算法。对于非递归算法采用回溯的思想，即从入口出发，按某一方向向 前探索，若能走通，并且未走过，则说明某处可以到达，即能到达新 点，否则试探下一方向；若所有的方向均没有通路，或无路可走又返 回到入口点。在求解过程中，为了保证在到达某一点后不能向前继续 行走（无路）时，能正确返回前一点以便继续从下一个方向向前试探, 则需要用一个栈保存所能到达的没一

2、点的下标及该点前进的方向，然 后通过对各个点的进出栈操作来求得迷宫通路。对于递归算法，在当前位置按照一定的策略寻找下个位置，在下 个位置又按照相同的策略寻找下下个位置；直到当前位置就是出口 点，每一步的走法都是这样的。随着一步一步的移动，求解的规模不 断减小；如果起始位置是出口，说明路径找到，算法结束，如果起始 位置的四个方向都走不通，说明迷宫没有路径，算法也结束。另外，为了保证迷宫的每个点都有四个方向可以试探，简化求解 过程，将迷宫四周的值全部设为1,因此将m行n列的迷宫扩建为m+2 行，n+2列，同时用数组来保存迷宫阵列。三. 数据结构设计在迷宫阵列中每个点都有四个方向可以试探，假设当前点

3、的坐 标（x, y）,与其相邻的四个点的坐标都可根据该点的相邻方位 而得到，为了简化问题，方便求出新点的坐标，将从正东开始沿 顺时针进行的这四个方向的坐标增量放在一个结构数组move 4 中，每个元素有两个域组成，其中x为横坐标增量，y为纵坐标增 量，定义如下：typedef structint x,y;item;为到达了某点而无路可走时需返回前一点，再从前一点开始向下 一个方向继续试探。因此，还要将从前一点到本点的方向压入栈中。 栈中的元素由行、列、方向组成，定义如下：typedef structint x,y,d;jdatatype;由于在非递归算法求解迷宫的过程中用到栈，所以需定义栈的类

4、 型，本程序中用的是顺序栈，类型定义如下；typedef structdatatype datamaxsize;int top;jseqstack, *pseqstack;四. 功能函数设计(1 )函数 pseqstack i n i t_seqstack ()此函数实现对栈的初始化工作。(2) 函数 empty_seqstack (pseqstack s)此函数用于判断栈是否为空。(3) 函数 push_seqstack (pseqstack s, datatype x)此函数实现入栈操作。(4) 函数 pop_seqstack (pseqstack s , datatype *x)此函数实

5、现出栈操作。(5) 函数 destory_seqstack (pseqstack *s)此函数执行栈的销毁操作，释放内存空间。(6) 函数 mazepath (int maze n+2, item moved, int xo, int yo)此函数实现对迷宫问题的非递归算法求解。在求解过程中需调 用上面定义的关于栈的一系列函数(栈的初始化，判空，入栈，出栈, 栈的销毁)，进而求得迷宫路径。(7) 函数 path (int maze n+2, item move, int x, int y, int step)此函数实现对迷宫问题的递归算法求解。(8) 函数 pr inway (int maze

6、 n+2, item move)此函数用于在递归算法求解迷宫后输出求解后的结果，即打印迷 宫路径。(9) 函数 copy (int maze n+2, int ms n+2)此函数的作用是复制一下输入的原始迷宫序列，因为本程序是通 过菜单选择求解迷宫的实现方式，将非递归算法和递归算法放在一起 通过菜单选择实现，在调用完一种算法后，为保证调用另一种算法时 原始迷宫序列未改变，所以需调用此函数来原始迷宫序列备份一下。(10) 主函数 ma i n ()定义变量，实现迷宫的输入操作，通过菜单选择求解迷宫路径的 实现方法，调用相关函数。(门)系统功能总体模块(a)栈的初始化(b)判栈空函数return

7、 i;renirnoj(c)入栈returno;s->top+;return i;(d)出栈(e)销毁栈free(es);*s-null;return;(f)非递归算法求解迷宫函数(g)递归算法求解迷宫函数inti;return i;i-0multiplex汁十step-;retiirno;(h)打印递归算法求解迷宫的路径函数intij;printfc找到路矗的?.prints-无法找到路?i-0multiplex汁+multiplex(i)复制原始迷宫阵列函数(j)主函数五. 编码实现#include<stdio.h>#include<stdlib.h>#def

8、ine m 6#define n 8#define maxsize 100typedef structint x,y;item;item move4;typedef structint x,y,d;jdatatype;typedef structdatatype datamaxsize;int top;jseqstack, *pseqstack;pseqstack init_seqstack()/ 栈的初始化pseqstack s; s=(pseqstack)malloc(sizeof(seqstack); 讦(s)s->top=-l;return s;int empty_seqstac

9、k(pseqstack s) 判栈空if (s->top=-l)return 1;elsereturn 0;入栈int push_seqstack (pseqstack s, datatype x) if(s->top=maxsize-l) 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->t

10、op;s->top;return 1;void destory_seqstack(pseqstack *s)销毁栈if(*s)free(*s);件null;return;int mazepath(int mazen+2,item movef,int x0,int yo) 非递归算法求解迷宫 pseqstack s;datatype temp;int x,y,d,i,j；temp.x=x0;temp.y=y0;temp.d=-l;s=init_seqstack();if(!s)printf(n栈初始化失败！ ”);return (0);push_seqstack (s, temp);whi

11、le(! empty_seqstack(s)pop_seqstack(s，&temp);x=temp.x;y=temp.y;d 二 temp.d+1;while(d<4)i=x+movedl.x; j=y+movedl.y; if(mazei|j=o)temp.x=x;temp.y=y;temp.d二d;push_seqstack (s, temp);x=i;y=j；mazexy=-l;if(x=m&&y 二二 n)printf(nn非递归算法求解的迷宫路径为(顺序为从出口到入 口输出)：nh);while(! empty _seqstack(s)pop_seqs

12、tack(s,&temp); printf("(%d %d) <- ",temp.x,temp.y);printf(hnnn");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+;mazex刃二 step;if(x=m&&y=n)return 1;for(i 二 0;iv4;

13、i+)if(mazex+movei-xy+movei.y=0) if(path(maze,move,x+movei .x,y+movei ystep) return 1;step-;mazexy=o;return 0;void print_way(int mazen+2,itein move) 打印递归算法求解迷宫的路径 int i,j；if(path(maze,move, 1,1,1)printf(un找到路径的矩阵形式输出如下：十)； for(i=0;i<m+2;i+)for(j=0;j<n+2;j+)printf(h%d n,mazeij);printf(hnh);print

14、f(nnn);printf(um归算法求解的迷宫路径为(顺序为从入口到出口输出)：n”); for(i=0;ivm+2;i+)for(j=0；jvn+2;j+)if(mazeij>l) printf(n(%d %d)>printf(hnnnm);elseprint”无法找到路径！ nn);void copy(int mazen+2,int msjn+2)复制原始迷宫序列函数for(int i二0;ivm+2;i+)for(int j=0;j<n+2;j+)msij=mazeij;void main()int mazem+2n+21;item move4;int i,j,q；p

15、rintf(n请输入迷宫序列：nh);for(i=0;ivm+2;i+)for(j=0;j<n+2;j+) scanf(n%dh,&mazeij);printf(hnh); move0-x=0;move0.y=l; move 1 .x= 1 ;movel .y=0; move2 .x=0;move2 .y=-1; move3.x=-1 ;move3.y=0; printf(hnh);int mase 1 m+2 n+2;copy(maze,masel);printf(11rffw rjw rjw rjw rjw rjw rjw rjw rjw rjw rjw rjw rjw rj

16、w rjw rjw rjw rjw rjw rjw rjw rjw rjw rjw rjw rjw rjw rjw%、走迷宫/t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /t /tnu)；printf(hnh);printf(hl.非递归形式走迷宫n”); printf(n2.递归形式走迷宫5”)； printf(n3.退出 n”)；printf( * 求解 方 式while(l)printf(hn请选择(选择0退出):

17、”); scanf(n%d&q);switch(q)case 1:mazepath(maze,move, 1,1); break;case 2: print_way(mase 1 .move); break;case 0:exit(o);-x六.运行与测试e：学习c益隔结构上机舞结乜涯亘没汁上枉debug1 keshe2.exe'七总结在这个课程设计中，遇到的主要问题是选择了一种实现方法后，在选择另一种时不会输出结果，但是当我把这两个程序分开调试时都 会出现结果，结果还是正确的，后来经过分析知道原来是调用完一种 方法后，原来输入的迷宫序列可能被改变了，因此，又增加了一个复 制原

18、始迷宫序列的函数，对原始序列进行了保存，然后在调用时就出 现结果了。通过调试这个程序，熟悉了迷宫的两种求法，在调试找错 过程中也学会好多。构造n个城市连接的最小生成树一. 问题描述一个地区的n个城市间的距离网，用prim算法建立最小生成 树，并计算得到的最小生成树的代价。基本要求：1）城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定 义采用课本中给出的定义，若两个城市之间不存在道路，则将相 应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的 最小生成树中包括了哪些城市间的道路，并显示得到的最小生成 树的代价。2）表示城市间距离网的邻接矩阵（要求至少6个城市，10条边）二. 设计思路在

19、本程序中，各个地区之间的距离网可以用邻接矩阵表示，在 进行定义时表示出相应的权值，以便计算最小代价，当权值赋为999 时，表示两城市之间无路径。然后用prim算法建立最小生成树，进 而在建立过程中可以计算得到的最小生成树的代价。三. 数据结构设计首先，在用邻接矩阵存储图时，除了用一个二维数组存储用于 表示顶点间相邻关系的邻接矩阵外，还需要用一个一维数组来存 储顶点信息，另外，还有图的顶点数和边数。故可将其形式描述 如下：typedef structchar vertexsfmaxvertexnum;int arcsmaxvertexnummaxvertexnum;int vertexnum,e

20、dgenum;jmgraph;为实现普利姆算法求最小生成树，需设置一个辅助数组closedge, 里面存放一顶点为与已构造好的部分生成树的顶点间权值最小的顶 点，边为某顶点与已构造好的部分生成树的顶点间的最小权值。定义 形式如下：typedef structint adj vertex;int lowcost; closedgemaxvertexn um;四. 功能函数设计(1 )函数 creatgraph (mgraph *g)此函数用于创建邻接矩阵，用邻接矩阵来存储图，建立各个 城市之间的关系。在建立过程中，给相应的边赋权值，以表示两 城市之间的代价。注：999代表两城市之间无路径。(2)

21、 函数 minispantree_prim (mgraph *g, int u, closedge ciosedge)此函数为普利姆函数，用于求最小生成树，在此过程中求出相应 的权值，及最小生成树权值之和，用于表示连接各城市之间的最小代 价。(3) 主函数main ()定义变量，分别调用相应的函数。(4) 系统功能总体模块(a)创建邻接矩阵creatgraph (mgraph *g)的流程图如下：mttlfiplci(b)构建最小生成树普利姆函数mini spantree_pr im (mgraph *g, intu, closedge c i osedge)流程图如下：i-0clomrdge

22、i adjvertcxerclo>edgeu lowco$r-0;iti卄multlplri(c)主函数ma i n ()流程图如下:mgnphegt五. 编码实现#include<stdio.h>#include<stdlib.h>#define maxvertexnum 30#define infinity 3000typedef structchar vertexsmax vertexnum;int arcs max vertexnum max vertexnum; int vertexnum,edgenum;jmgraph; typedef structi

23、nt adj vertex;int lowcost;closedgemaxvertexnum;void creatgraph(mgraph *g)int i,j,k,n;printf("i#输入顶点数和边数：”)；scanf("%d %dm，&(g->vertexnum),&(g->edgenum); printf(,nh);for(i=0;i<g->vertexnum;i+)printf("i#输入第d 个顶点字符信息(共d 个)：h,i+l,g->vertexnum); scanf(h%cn,&(g->

24、;vertexsfi);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("nh);printtf请输入边vvi,vj>对应的顶点序号(共d个)：n,g->edgenum); scanf("%d %d”,&i,&j);printf(u请输入此边的权值：”)；scanf(h%dm,&am

25、p;n);g->arcsij=n;g->arcsji=n;printf(,nh);printf("图已成功创建!n”);printf(',nn); 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)closedge i .adj vertex=u;closedge i jo wcost=g->arcs u i;closedgeu.lowcost=0;fdr(i=o;i&

26、lt;g->vertexnum-1 ;i+)w=infinity;for(j=0;j<g->vertexnum;j+)if(closedgejowcost!=0 && closedgejowcost<w)w=closedgej.lowcost;k=j；closedgek.lowcost=0;for(j=0;j<g->vertexnum;j+) if(g->arcskjl<closedgejjowcost)closedgej.adjvertex=k;closedgefj .lowcost=g->arcsk fj ;for(i=

27、0;i<g->vertexnum;i+)if(i!=u)printf(n输出构建的最小牛成树为：");printf("%d->%d,%dn",i,closedgeij.adj vertex,g->arcsiclosedgei.adjvertex); count+=g>arcs i c 1 osedge i . adj vertex;printf(hnh);printf(”此最小生成树的代价为:%du,count); printf(,nh);void main()mgraph *g;int u;closedge closedge;g=(mgraph*)malloc(sizeof(mgraph);creatgraph(g);printf(h输入构造最小生成树的出发顶点：”); scanf(”d",&u);printf(hnh);minispantree_prim(g,u,closedge);printf(h