数据结构实验二 迷宫递归

北京邮电大学信息与通信工程学院第1页北京邮电大学电信工程学院第1页数据结构实验报告实验名称：实验二——栈与队列学生姓名：大学霸班级：xxxxxxxxxx班内序号：19学号：xxxxxxxxxx日期：2012年11月17日1．实验要求a.实验目的通过选择下面五个题目之一进行实现，掌握如下内容：进一步掌握指针、模板类、异常处理的使用掌握栈的操作的实现方法掌握队列的操作的实现方法学习使用栈解决实际问题的能力学习使用队列解决实际问题的能力b.实验内容利用栈结构实现迷宫求解问题。迷宫求解问题如下：心理学家把一只老鼠从一个无顶盖的大盒子的入口赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口，测试算法的迷宫如下图所示。2.程序分析本程序的功能是用递归的方法找到所有走出迷宫的路径，并将路径输出，同时在这些路径中找出最优解。首先，读取后台预定的迷宫TXT地图（实际上是10×10的数字矩阵，0代表空地，3代表墙，可以很直观地修改）,把数据赋给arr二维数组，内容不发生改变。然后，将这个迷宫地图输出，判断迷宫是否有完整通路，如果能走出便进行下一步，如果不能，提示错误迷宫有完整通路，可使用回溯的方法，即从入口出发，顺着某一个方向进行探索，若能走通，则此步进栈，继续往前进；否则沿着原路返回，换另一个方向探索，直至出口位置，求得一条通路……重复上述步骤，找出所有可能的路径，统计每一步在程序的最后，将每一种路径的长度进行比较，找出最短的一个或多个路径2.1存储结构定义结点的结构体structPoint{ intX; intY;};进行前进后退等操作时即是对X、Y值的改变，同时也代表二维数组元素的行数、列数迷宫图的数据用二维数组来存储，用0表示空地可以前进，用3表示墙走不通arr1arr2…………arrn-1arrn当执行寻找路径时，从一个节点到下一个结点系统会自动调用栈2.2关键算法分析关键算法1.找出迷宫走法回溯法，利用递归穷举可能解每走一步：[1]如果当前位置=出口，把完整路径输出，结束[2]否则：[2.1]假设当前位置为路径；[2.2]如果东面未走过：向东走一步[2.3]如果南面未走过：向南走一步[2.4]如果西面未走过：向西走一步[2.5]如果北面未走过：向北走一步[3]设置当前位置走不通，回溯，并将此位置标记2.读取迷宫图[1]进行循环体[1.1]输入要读取的迷宫图maze[1.2]如果存在跳出循环，下一环节[1.3]如果不存在显示错误输入的迷宫图有误，重新上面的步骤[2]定义文件流对象fin[3]根据maze选择打开不同的迷宫图TXT文件，建立关联[4]判断文件是否能打开[4.1]如果能打开，逐行提取数字，赋给二维数组arr，关闭文件[4.2]如果不能打开，提示错误3.打印还未走过的迷宫图[1]从第一行到第十行循环[2]从第一列到第十列循环[2.1]此节点如果为墙，打印“■”[2.2]其他为空地，打印空格4.判断是否能走通[1]从最后一行倒序循环[1.1]如果找到不是墙的元素，返回能走通[2]从最后一列倒序循环[2.1]如果找到不是墙的元素，返回能走通[3]返回不能走通5.打印走通后的迷宫图[1]将路径计数器k置0[2]从第一行到第十行循环[2.1]从第一列到第十列循环[2.1.1]此节点如果为墙，打印“■”[2.1.2]此节点如果为路径，打印“*”，k加1[2.1.3]此节点如果未走过，打印空格[3]将k存到向量PathLength（专门比较路径长度）打印一共走了k步6.找出最优解[1]定义最短路径数组ShortestPath假设最短路径长度ShortestLength为向量PathLength的第一个元素值[2]在向量PathLength里进行循环[2.1]如果PathLength里某个元素值小于最短路径长度ShortestLength[2.2]将最小路径长度ShortestLength等于这个元素值[3]在向量PathLength里进行循环[3.1]如果PathLength里某个元素值等于最短路径长度ShortestLength[3.2]将这个元素的下标存入最短路径数组ShortestPath[4]打印最短路径数组ShortestPath里的所有元素，即为最优解[5]打印最短路径长度ShortestLength代码详尽分析1.找出迷宫走法每走一步：[1]如果当前位置=出口，把完整路径输出，结束[2]否则：[2.1]假设当前位置为路径；[2.2]如果东面未走过：向东走一步[2.3]如果南面未走过：向南走一步[2.4]如果西面未走过：向西走一步[2.5]如果北面未走过：向北走一步[3]设置当前位置走不通，回溯，并将此位置标记C++实现voidnext(intarr[][10],Pointcur){[1] if(cur.X==9||cur.Y==9)//如果走出迷宫 {cout<<"第"<<++Path<<"种路径：\n";PrintPath(arr); arr[cur.X][cur.Y]=0;} //打印完整路径[2] else {[2.1] arr[cur.X][cur.Y]=2;//假设当前位置为路径[2.2] if(arr[cur.X+1][cur.Y]==0) { Pointt=cur; t.X++; next(arr,t);//向右 }[2.3] if(arr[cur.X][cur.Y+1]==0) { Pointt=cur; t.Y++; next(arr,t);//向下 }[2.4] if(arr[cur.X-1][cur.Y]==0) { Pointt=cur; t.X--; next(arr,t);//向左 }[2.5] if(arr[cur.X][cur.Y-1]==0) { Pointt=cur; t.Y--; next(arr,t);//向上 }[3] arr[cur.X][cur.Y]=1;//标记此处走不通 } arr[cur.X][cur.Y]=0;}2.读取迷宫图[1]进行循环体[1.1]输入要读取的迷宫图maze[1.2]如果存在跳出循环，下一环节[1.3]如果不存在显示错误输入的迷宫图有误，重新上面的步骤[2]定义文件流对象fin[3]根据maze选择打开不同的迷宫图TXT文件，建立关联[4]判断文件是否能打开[4.1]如果能打开，逐行提取数字，赋给二维数组arr，关闭文件[4.2]如果不能打开，提示错误C++实现[1]do{ cout<<"请选择迷宫(1~5):";[1.1] cin>>maze;//输入要读取的迷宫图maze[1.2] if(maze>=1&&maze<=5)break;//如果存在跳出循环，下一环节[1.3] elsecout<<"无此迷宫！"<<endl<<endl;}//如果不存在显示错误 while(1);[2] ifstreamfin;//定义文件流对象fin[3] switch(maze)//根据maze选择打开不同的迷宫图TXT文件，建立关联 { case1: fin.open("maze1.txt"); break; case2: fin.open("maze2.txt"); break; case3: fin.open("maze3.txt"); break; case4: fin.open("maze4.txt"); break; case5: fin.open("maze5.txt"); break; default: break; }//输出迷宫[4] if(fin.is_open())//判断文件是否能打开 { cout<<"迷宫载入中"<<endl;[4.1] for(inti=0;i<10;i++) { for(intj=0;j<10;j++) { fin>>arr[i][j];//逐行提取数字，赋给二维数组arr } } fin.close(); PrintMaze(arr);}else[4.2]cout<<"迷宫不能打开！"<<endl;//提示错误3.打印还未走过的迷宫图[1]从第一行到第十行循环[2]从第一列到第十列循环[2.1]此节点如果为墙，打印“■”[2.2]其他为空地，打印空格C++实现voidPrintMaze(intarr[][10]){[1] for(inti=0;i<10;i++) {[2] for(intj=0;j<10;j++) {[2.1] if(arr[i][j]==3)cout<<"■";//此节点如果为墙，打印“■”[2.2] elsecout<<"";//其他为空地，打印空格 } cout<<endl; } cout<<endl;}4.判断是否能走通[1]从最后一行倒序循环[1.1]如果找到不是墙的元素，返回能走通[2]从最后一列倒序循环[2.1]如果找到不是墙的元素，返回能走通[3]返回不能走通C++实现boolIsThrough(intarr[][10]){[1] for(inti=8;i>=1;i--) {[1.1] if(arr[9][i]==0)returntrue;//如果找到不是墙的元素，返回能走通 }[2] for(inti=8;i>=1;i--) {[2.1] if(arr[i][9]==0)returntrue;//如果找到不是墙的元素，返回能走通 }[3] returnfalse;}5.打印走通后的迷宫图[1]将路径计数器k置0[2]从第一行到第十行循环[2.1]从第一列到第十列循环[2.1.1]此节点如果为墙，打印“■”[2.1.2]此节点如果为路径，打印“*”，k加1[2.1.3]此节点如果未走过，打印空格[3]将k存到向量PathLength（专门比较路径长度）[4]打印“一共走了k步”C++实现voidPrintPath(intarr[][10]){[1] intk=0;[2] for(inti=0;i<10;i++)//行循环 {[2.1] for(intj=0;j<10;j++)//列循环 {[2.1.1] if(arr[i][j]==3)cout<<"■";//此节点如果为墙，打印“■”[2.1.2] elseif(arr[i][j]==2){cout<<"*";k++;}//此节点如果为路径，打印“*”，k加1[2.1.3] elsecout<<"";//此节点如果未走过，打印空格 } cout<<endl; }[3] PathLength.push_back(k);//插入路径长度向量[4] cout<<"一共走了"<<k<<"步";//打印步数 cout<<endl;}6.找出最优解[1]定义最短路径数组ShortestPath假设最短路径长度ShortestLength为向量PathLength的第一个元素值[2]在向量PathLength里进行循环[2.1]如果PathLength里某个元素值小于最短路径长度ShortestLength[2.1.1]将最小路径长度ShortestLength等于这个元素值[3]在向量PathLength里进行循环[3.1]如果PathLength里某个元素值等于最短路径长度ShortestLength[3.1.1]将这个元素的下标存入最短路径数组ShortestPath[4]打印最短路径数组ShortestPath里的所有元素，即为最优解[5]打印最短路径长度ShortestLengthC++实现voidPrintShortest(){[1] intShortestPath[50]={0}; intShortestLength=PathLength[0]; ShortestPath[0]=1;[2] for(unsignedi=1;i<PathLength.size();i++) {[2.1] if(PathLength[i]<ShortestLength) {[2.1.1] ShortestLength=PathLength[i]; } } intk=0;[3] for(unsignedi=0;i<PathLength.size();i++) {[3.1] if(PathLength[i]==ShortestLength)[3.1.1]ShortestPath[k++]=i+1; }cout<<"最短路径为：";[4] for(inti=0;i<50;i++) if(ShortestPath[i])cout<<ShortestPath[i]<<""; cout<<endl;[5] cout<<"共走了"<<ShortestLength<<"步"<<endl; }2.3其他我在调试程序时，已经预写了几个迷宫地图文件maze1.txt、maze2.txt……保存在工程文件夹下。类似的，其他开发者可以编写新的地图，加以改进、创新3.程序运行结果3.1测试主函数流程图开始开始用户输入迷宫是否存在打开迷宫图迷宫是否能打开打印迷宫图迷宫是否能走通