数据结构--迷宫问题求解

1安徽大学计算机实验教学中心学号专业计算机科学与技术姓名实验日期2017.6.20教师签字成绩实验报告【实验名称】迷宫问题的求解【实验目的】（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。（3）用递归和非递归两种方式完成迷宫问题的求解。【实验原理】迷宫问题通常是用“穷举求解”方法解决，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前走；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没2安徽大学计算机实验教学中心有通路。栈是一个后进先出的结构，可以用来保存从入口到当前位置的路径。【实验内容】1需求分析1.基本要求：（1）首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出。其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如，对于教材第50页图3.4所示的迷宫，输出一条通路为：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），…（2）编写递归形式的算法，求得迷宫中所有可能的通路。（3）以方阵形式输出迷宫及其通路。（4）按照题意要求独立进行设计，设计结束后按要求写出设计报告。2.输入输出的要求：(i)求得的通路以三元组（i，j，d）的形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一个坐标的方向。（ii）输出迷宫示意图3.程序所能达到的功能：3安徽大学计算机实验教学中心(i)实现一个以链表作存储结构的栈类型，以非递归算法求出通路(ii)以一个递归算法，对任意输入的迷宫矩阵求出所有通路。2概要设计1.①构建一个二维数组maze[M][N]用于存储迷宫矩阵②手动生成迷宫，即为二维数组maze[M][N]赋值③构建一个栈用于存储迷宫路径④建立迷宫节点用于存储迷宫中每个节点的访问情况；非递归本程序包含6个函数：(1)主函数main()(2)生成迷宫create_maze()(4)打印迷宫print_maze()(5)搜索迷宫路径并用三元组输出路径mgpath()(6)用图来输出路径print_tu();递归本程序包含3个函数：（1）主函数main();（2）打印迷宫printmaze()；（3）搜索迷宫路径pass(intx,inty)；3.详细设计1.非递归4安徽大学计算机实验教学中心起点和终点的结构类型typedefstruct{inth;intl;}T;栈节点类型typedefstructcell{introw;intcol;intdir;}TCell;1.生成迷宫voidcreat_maze(inta,intb){定义i,j为循环变量for(ia)for(jb)输入maze[i][j]的值}2.打印迷宫voidprint_maze(intm,intn){用i,j循环变量，将maze[i][j]输出}3.搜索迷宫路径5安徽大学计算机实验教学中心voidmazepath(intmaze[][],Ts,Te)//参数传递迷宫和起点与终点{TCellS[N1*N2];top=0;//建立栈S[top].row=s.h;S[top].col=s.l;S[top].dir=-1;//起点入栈while(top=0)//判栈是否空{i,j为当前访问点的位置if(i,j是终点坐标)用循环输出栈里的元素；else将(i,j),即访问点入栈，然后向四周寻找是否有通路，若有通路，将原访问点标记（赋值-1），选一条通路作为新访问点，入栈。若没有通路，回溯，将栈顶元素出栈作为访问点，继续寻找通路。}4.生成路线图Print_tu()6安徽大学计算机实验教学中心{i,j为循环变量for(ia)for(jb){if(maze[i][j]==1);print（“#”）//#表示墙elseif(maze[i][j]==0)print（“”）elseprint(“+”)//+表示路径}2.递归voidprintmaze(){用i,j循环变量，将maze[i][j]输出}voidpass(intx,inty){将访问点标记maze[x][y]=-1；if(x,y是终点坐标)调用printmaze()输出栈里的元素；if(x,y的左边是通路)7安徽大学计算机实验教学中心递归调用pass（x,y-1）；if(x,y的右边是通路)递归调用pass（x,y+1）；if(x,y的上边是通路)递归调用pass（x-1,y）；if(x,y的下边是通路)递归调用pass（x+1,y）；}4.测试与分析8安徽大学计算机实验教学中心【小结或讨论】这次的项目，加强了我动手、思考和解决问题的能力。巩固和加深了9安徽大学计算机实验教学中心对数据结构的理解，提高综合运用本课程所学知识的能力培养了我查阅参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。附页源程序非递归#includestdio.h#includestdlib.h#defineN110#defineN210intmaze[N1][N2];//迷宫数组typedefstruct{//起点终点坐标inth;intl;}T;10安徽大学计算机实验教学中心typedefstructcell{introw;intcol;intdir;}TCell;//栈的元素结构TCellS[N1*N2];//栈voidcreat_maze(inta,intb)//建立迷宫{inti,j;for(i=0;ia;i++)for(j=0;jb;j++)scanf(%d,&maze[i][j]);}voidprint_maze(inta,intb)//打印迷宫{inti,j;11安徽大学计算机实验教学中心for(i=0;ia;i++){for(j=0;jb;j++)printf(%d,maze[i][j]);printf(\n);}}voidprint_tu(inta,intb)//打印迷宫路径图{inti,j;for(i=0;ia;i++){for(j=0;ja;j++){if(maze[i][j]==1)printf(#);elseif(maze[i][j]==0)12安徽大学计算机实验教学中心printf();elseprintf(+);}printf(\n);}}voidmazepath(intmaze[N1][N2],Ts,Te)//搜索路径{inttop=0;inti,j,k,find,di;S[top].row=s.h;S[top].col=s.l;S[top].dir=-1;maze[s.h][s.l]=-1;while(top=0){i=S[top].row;13安徽大学计算机实验教学中心j=S[top].col;di=S[top].dir;if(i==e.h&&j==e.l){printf(输出迷宫路径三元组：\n);for(k=0;k=top;k++)printf(%d%d%d\n,S[k].row,S[k].col,S[k].dir);return;}find=0;while(find==0&&di4){di++;switch(di){case0:{i=S[top].row-1;j=S[top].col;break;14安徽大学计算机实验教学中心}case1:{i=S[top].row;j=S[top].col+1;break;}case2:{i=S[top].row+1;j=S[top].col;break;}case3:{i=S[top].row;j=S[top].col-1;break;}}if(maze[i][j]==0)find=1;}if(find==1){S[top].dir=di;top++;S[top].row=i;S[top].col=j;15安徽大学计算机实验教学中心maze[i][j]=-1;}else{maze[S[top].row][S[top].col]=0;top--;}}printf(没有路径\n);}intmain()//主函数{inta,b;Ts,e;printf(输入迷宫的行数与列数：\n);scanf(%d,%d,&a,&b);printf(输入迷宫数据:\n);16安徽大学计算机实验教学中心creat_maze(a,b);printf(输出迷宫：\n);print_maze(a,b);printf(输入起点与终点：\n);scanf(%d,%d,&s.h,&s.l);scanf(%d,%d,&e.h,&e.l);mazepath(maze,s,e);printf(输出迷宫图和路线:\n);print_tu(a,b);}递归#includestdio.h#includestdlib.hintmaze[9][9]={1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,1,1,0,1,1,0,1,1,0,1,17安徽大学计算机实验教学中心1,0,1,0,0,1,0,0,1,1,0,1,0,1,0,1,0,1,1,0,0,0,0,0,1,0,1,1,1,0,1,1,0,1,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1};voidprintmaze(){inti,j;for(i=0;i9;i++){for(j=0;j9;j++){if(maze[i][j]==1)printf(#);elseif(maze[i][j]==-1)printf(+);18安徽大学计算机实验教学中心elseprintf();}printf(\n);}}voidpass(intx,inty){maze[x][y]=-1;if(x==7&&y==7){printf(输出路径\n);printmaze();}if(maze[x][y+1]==0)pass(x,y+1);if(maze[x+1][y]==0)pass(x+1,y);if(maze[x-1][y]==0)19安徽大学计算机实验教学中心pass(x-1,y);if(maze[x][y-1]==0)pass(x,y-1);maze[x][y]=0;}intmain(){intinx=1,iny=1;printf(迷宫图是：\n);printmaze();pass(inx,iny);}