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

数据结构课程设计迷宫求解学院：湖北工业大学计算机学院教师：沈华老师班级：12网络工程1班学号：1210322118姓名：饶进阳时间：2013年12月22日目录问题描述.........................................................2思路解析.........................................................3程序流程.........................................................4核心代码.........................................................5源程序代码........................................................6程序运行实例.....................................................12课设总结.........................................................141迷宫求解问题描述：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；要求：在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；比如这是一个迷宫电脑找出的出路2思路设定当前位置的初值为入口位置：do｛若当前位置可通，则｛将当前位置插入栈顶；}若该位置是出口位置，则结束；否则切换当前位置的东邻块为新的当前位置；否则｛若栈不空且栈顶位置还有其他方向未被探索，则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块；}若{栈不空但栈顶位置的四周均不可通，则删去栈顶位置；}若{栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空；｝｝while(栈不空)｛栈空说明没有路径存在｝PS：类似动态求解方法3程序流程第一次用visio做程序框图，所以只把程序的大概流程画出来了。4核心代码//栈相关操作intinitlStack(Stack*S)intpushStack(StackS,coordinatee)intpopStack(StackS,coordinate*e)intgetTop(StackS,coordinate*e)voidshow(StackS)//创建一个迷宫intcreatMaze(Maze*m)//打印出一个迷宫voidshowMaze(Maze*m)//求当前结点的下一个通路coordinatepassNext(Maze*m,inti,intj)//求迷宫路径intsolveMaze(Maze*m,StackS)//模拟出路径voidshowRoad(Mazem,StackS)5程序源码：#includestdio.h#includestdlib.h#defineMAX100#defineSIZEsizeof(Node)//****************************//栈typedefstruct{intx;//行inty;//列}coordinate;//坐标typedefstructnode{coordinatedata;structnode*next;}Node,*Stack;//栈的相关操作//栈初始化//带头结点的链栈intinitlStack(Stack*S){(*S)=(Node*)malloc(SIZE);if((*S)==NULL){return1;}(*S)-next=NULL;return0;}//入栈intpushStack(StackS,coordinatee){Node*p;p=(Node*)malloc(SIZE);p-data.x=e.x;p-data.y=e.y;p-next=S-next;S-next=p;return0;}//出栈intpopStack(StackS,coordinate*e){Node*p;if(S-next==NULL){printf(\nStackisempty!\n);return2;}e-x=S-next-data.x;e-y=S-next-data.y;p=S-next;S-next=p-next;free(p);return0;}//读取栈顶intgetTop(StackS,coordinate*e){e-x=S-next-data.x;e-y=S-next-data.y;return0;}//显示voidshow(StackS){Node*p;p=S-next;while(p!=NULL){printf(%d%d-,p-data.x,p-data.y);p=p-next;}printf(start\n);}//***************************//***************************//迷宫typedefstruct{introw;intcol;intarr[MAX][MAX];}Maze;//创建一个迷宫intcreatMaze(Maze*m){inti,j;printf(\npleaseinputMaze'srowandcol:\n);scanf(%d%d,&(m-row),&(m-col));printf(\npleaseinputtheMaze'smessage:(0isok),(1isno)\n);for(i=0;i=MAX-1;i++){for(j=0;j=MAX-1;j++){m-arr[i][j]=1;}}for(i=1;i=m-row;i++){for(j=1;j=m-col;j++){scanf(%d,&(m-arr[i][j]));}}return0;}//显示迷宫信息voidshowMaze(Maze*m){inti,j;printf(\ntheMazeyouhavainput:\n);for(i=1;i=m-row;i++){for(j=1;j=m-col;j++){printf(%d,m-arr[i][j]);}printf(\n);}printf(\nlikethis:\n);for(i=1;i=m-row;i++){for(j=1;j=m-col;j++){if(m-arr[i][j]!=0){printf(■);}else{printf(□);}}printf(\n);}}//求当前结点的下个通路//顺时针找coordinatepassNext(Maze*m,inti,intj){coordinatek;if(m-arr[i][j+1]==0){//东k.x=i;k.y=j+1;returnk;}if(m-arr[i+1][j]==0){//南k.x=i+1;k.y=j;returnk;}if(m-arr[i][j-1]==0){//西k.x=i;k.y=j-1;returnk;}if(m-arr[i-1][j]==0){//北k.x=i-1;k.y=j;returnk;}else{//不存在k.x=-1;k.y=-1;returnk;}}//求解迷宫intsolveMaze(Maze*m,StackS){inti,j;intboolean;coordinatea;i=1;j=1;do{if(m-arr[i][j]==0){a.x=i;a.y=j;m-arr[i][j]=2;pushStack(S,a);if(i==m-row&&j==m-col){return0;}}a=passNext(m,i,j);if(a.x!=-1){i=a.x;j=a.y;continue;}elseif(a.x==-1){boolean=popStack(S,&a);if(2==boolean){return0;}getTop(S,&a);i=a.x;j=a.y;}}while(S-next!=NULL);return0;}//模拟出路径voidshowRoad(Mazem,StackS){coordinatee;inti,j;if(S-next==NULL){printf(\nSorry!youcan'tgoouttheMaze!\n);}while(S-next!=NULL){popStack(S,&e);m.arr[e.x][e.y]=-1;}for(i=1;i=m.row;i++){for(j=1;j=m.col;j++){if(m.arr[i][j]=0){printf(■);}else{printf(□);}}printf(\n);}}//***************************//主函数intmain(){Mazem;StackS;printf(※欢迎玩耍迷宫求解游戏※\n);initlStack(&S);creatMaze(&m);showMaze(&m);solveMaze(&m,S);printf(\ntherootishere:\n);show(S);showRoad(m,S);return0;}程序运行结果：第一步：输入迷宫行列大小第二步：输入迷宫信息第四步：程序会自动求出路径课设总结敬爱的沈华老师您好，感谢您这半年对我们的教诲，说实话，很喜欢上您的课，您上课的风采深深的吸引了我，每次上您的课，我都听得特别认真。好吧，言归正传，谈谈这次课程设计的感想。首先看到这道题的时候，真心没多少思路，我抱着试一试的态度，去网上搜索相关的算法。网上资源蛮多的，刚开始就搜索到了，严蔚敏老师的相关算法讲解视频，虽然她讲的是思想（就是他并没有源程序的实现），但是足够让我理解了基本算法流程。其实先开始都不知道怎么下笔，但是我还是想着从基本栈开始写吧，慢慢写着，程序大概思想框架就成型了，最后在实现求解迷宫路径的时候，着手用笔在草稿纸上面模拟，然后才敲到编译器中，最好几经调试，终于得到了想要的结果。做完这次课设后，深刻的体会到一些道理，在信息时代，解决问题的最好方法是运用现代的信息资源。并且在实际中，开始没思路的事，慢慢完成小部分，那么你的总体思维会渐渐地成型。做事做人，平心气和的干，总会得到成功！