C 数据结构之迷宫求解

2009级数据结构实验报告实验名称：用栈和队列实现迷宫问题求解学生姓名：桂柯易班级：2009211120班内序号：07学号：09210580日期：2010年11月19日1.实验要求【实验目的】进一步掌握指针、模板类、异常处理的使用；掌握栈的操作的实现方法；掌握队列的操作的实现方法；培养使用栈解决实际问题的能力；培养使用队列解决实际问题的能力。【实验内容】利用栈结构实现迷宫求解问题。迷宫求解问题如下：心理学家把一只老鼠从一个无顶盖的大盒子的入口赶进迷宫，迷宫中设置很多障碍物，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口，测试算法的迷宫如下图所示。2.程序分析2.1存储结构存储结构：队列2.2关键算法分析【设计思想】可以采用回溯法实现该问题的求解。回溯法是一种不断试探及时纠正错误的搜索方法。从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向；若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都搜索到，或找到一条通路，或无路可走又返回到入口点。在求解过程中，为了保证在任何位置上都能沿原路返回，需要一个后进先出的栈来保存从入口到当前位置的路径。考虑到使用栈的实现复杂度，本次实验采用标记法标记已经走过的地方，所以就在求解迷宫通路方面可能不够全面，有时不能得到正确的解法。可以将迷宫定义成一个二维数组，则每个点有8个试探方向，如当前点的坐标是（x,y），与其相邻的8个点的坐标都可根据与该点的相邻方位而得到，规定试探顺序为顺时针方向，将这8个方向的坐标增量放在一个结构数组move[8]中，在move数组中，每个元素由两个域组成：x表示横坐标增量，y表示纵坐标增量。这样会很方便地求出从某点（x,y）按某一方向v（0≤v≤7）到达新点（i,j）的坐标：i=x+move[v].x；j=y+move[v].y。【伪代码】栈初始化；将入口点坐标（x,y）及该点的方向d（设为-1）入栈；当栈不空时循环执行下述操作：3.1（x,y,d）<==栈顶元素出栈；3.2求出下一个要试探的方向d++;3.3沿顺时针试探每一个方向，执行下述操作：3.3.1如果方向d可走，则3.3.1.1将（x,y,d）入栈；3.3.1.2求新点坐标（i,j）；3.3.1.3将新点（i,j）切换为当前点（x,y）；3.3.1.4若（x,y）是终点，则算法结束；否则，重置d=0；3.3.2否则，试探下一个方向d++；【复杂度】（1）手动生成迷宫算法：voidhand_maze(intm,intn){ inti,j; cout<<endl;cout<<"请按行输入迷宫，0表示通路，1表示障碍:"<<endl;for(i=0;i<m;i++)for(j=0;j<n;j++) { cin>>maze[i][j]; }}该算法的时间复杂度为T(N)=O(N2)（2）自动生成迷宫算法：voidautomatic_maze(intm,intn)//自动生成迷宫{ inti,j; cout<<"\n迷宫生成中……\n\n"; system("pause"); for(i=0;i<m;i++) for(j=0;j<n;j++) maze[i][j]=rand()%2;//随机生成0、1maze[0][0]=0;maze[i-1][j-1]=0;//首尾置为0，保证迷宫基本功能的实现}时间复杂性、度上，该算法同于手动生成迷宫算法，为T（N）=O（N2）2.3其他程序源代码：#include<stdlib.h>//rand()函数#include<stdio.h>#include<iostream>usingnamespacestd;#defineN100//定义迷宫数组的上线,为全局变量#defineM100intX;//标记迷宫是否有解的变量intmaze[N+2][M+2];inthead=NULL,tail=NULL;//队列的头尾指针，初始值设为NULLstructpoint//定义迷宫的队列结构体，包含列，行，序号{introw,col,predecessor;}queue[1000];voidstudent_maze()//函数生成书本后面的迷宫{ cout<<"下面将要为您生成书本课后的迷宫，请稍候"<<endl; system("pause");maze[0][0]=0;maze[0][1]=1;maze[0][2]=1;maze[0][3]=1;maze[0][4]=1;maze[0][5]=1;maze[0][6]=1;maze[0][7]=1;maze[0][8]=1;maze[0][9]=1;maze[1][0]=1;maze[1][1]=0;maze[1][2]=0;maze[1][3]=1;maze[1][4]=0;maze[1][5]=0;maze[1][6]=0;maze[1][7]=1;maze[1][8]=0;maze[1][9]=1;maze[2][0]=1;maze[2][1]=0;maze[2][2]=0;maze[2][3]=1;maze[2][4]=0;maze[2][5]=0;maze[2][6]=0;maze[2][7]=1;maze[2][8]=0;maze[2][9]=1;maze[3][0]=1;maze[3][1]=0;maze[3][2]=0;maze[3][3]=0;maze[3][4]=0;maze[3][5]=1;maze[3][6]=1;maze[3][7]=0;maze[3][8]=0;maze[3][9]=1; maze[4][0]=1;maze[4][1]=0;maze[4][2]=1;maze[4][3]=1;maze[4][4]=1;maze[4][5]=0;maze[4][6]=0;maze[4][7]=0;maze[4][8]=0;maze[4][9]=1; maze[5][0]=1;maze[5][1]=0;maze[5][2]=0;maze[5][3]=0;maze[5][4]=1;maze[5][5]=0;maze[5][6]=0;maze[5][7]=0;maze[5][8]=0;maze[5][9]=1; maze[6][0]=1;maze[6][1]=0;maze[6][2]=1;maze[6][3]=0;maze[6][4]=0;maze[6][5]=0;maze[6][6]=1;maze[6][7]=0;maze[6][8]=0;maze[6][9]=1;maze[7][0]=1;maze[7][1]=0;maze[7][2]=1;maze[7][3]=1;maze[7][4]=1;maze[7][5]=0;maze[7][6]=1;maze[7][7]=1;maze[7][8]=0;maze[7][9]=1; maze[8][0]=1;maze[8][1]=0;maze[8][2]=0;maze[8][3]=0;maze[8][4]=0;maze[8][5]=0;maze[8][6]=0;maze[8][7]=0;maze[8][8]=0;maze[8][9]=0; maze[9][0]=1;maze[9][1]=1;maze[9][2]=1;maze[9][3]=1;maze[9][4]=1;maze[9][5]=1;maze[9][6]=1;maze[9][7]=1;maze[9][8]=1;maze[9][9]=0;}voidautomatic_maze(intm,intn)//定义函数可自动生成一个迷宫{ inti,j; cout<<"自动生成迷宫中，请稍候......"<<endl; system("pause"); for(i=0;i<m;i++) for(j=0;j<n;j++) maze[i][j]=rand()%2;//随机生成0、1作为迷宫中一点的标志（通路或障碍） maze[0][0]=0;//将入口和出口强制为0，保证有可能出来迷宫 maze[m-1][n-1]=0;}voidhand_maze(intm,intn)//定义函数手动生成一个迷宫{ inti,j;cout<<"请按行输入迷宫，0表示此处为通路，1表示此处为障碍:"<<endl;for(i=0;i<m;i++)for(j=0;j<n;j++) { cin>>maze[i][j];//需手动输入每一个点的相关信息，比较繁琐，仅供求解已知迷宫形状用 if(maze[i][j]!=0&&maze[i][j]!=1)//当输入的数字不是0或1的时候，需要及时纠错 cout<<"您输入的数字有误，请输入0或1!"<<endl; cin>>maze[i][j]; }}voiddata(intm,intn)//考虑到用户输入数字的随机性，加入异常处理函数，保证能生成一个规则的迷宫{ inti,j; cout<<"根据您先前输入的迷宫范围"<<endl; cout<<"系统将取所输入的前"<<m*n<<"个数生成一个迷宫"<<endl; cout<<"\n数字迷宫生成结果:\n\n"; cout<<"迷宫入口\n";cout<<"↓"; for(i=0;i<m;i++)//组成一个方阵，显示每一点的情况（障碍还是通路） { cout<<"\n"; for(j=0;j<n;j++) { if(maze[i][j]==0)cout<<"0"; if(maze[i][j]==1)cout<<"1"; } } cout<<"→迷宫出口\n";}voidprint_maze(intm,intn)//函数将迷宫输出为可视化界面，加强程序交互性{ inti,j,k; cout<<"\n迷宫图生成结果如下，空心圆代表此处为通路，实心圆代表此处为障碍:\n"; cout<<"迷宫入口\n"<<"↓";//入口指示 cout<<endl; cout<<"★";//生成入口边上的五角星 for(k=0;k<n;k++)//通过一个横排的实心五角星来生成迷宫的上边界 { cout<<"★"; } for(i=0;i<m;i++) { cout<<"\n";//生成左边界 cout<<"★"; for(j=0;j<n;j++) { if(maze[i][j]==0)printf("○");//空心圆代表此处为通路，实心圆代表此处为障碍 if(maze[i][j]==1)printf("●"); } cout<<"★";//生成右边界 } cout<<endl; for(k=0;k<n;k++) { cout<<"★"; } cout<<"★\n";//最后是底部的边界for(i=0;i<n;i++) { cout<<"";}cout<<"↓\n"; for(i=0;i<n-1;i++) { cout<<"";} cout<<"迷宫出口\n";//出口指示}voidresult_maze(intm,intn)//这个函数用来输出迷宫的求解结果{ inti,j; cout<<"以上生成的迷宫通路(用□表示)为：\n\t"; for(i=0;i<m;i++) { cout<<"\n"; for(j=0;j<n;j++) { if(maze[i][j]==0||maze[i][j]==2)//2标记的是队列中已访问过的点 cout<<"○"; if(maze[i][j]==1) cout<<"●"; if(maze[i][j]==3)//3标记的是走出迷宫路径 cout<<"□"; } }}voidenqueue(structpointp)//迷宫中队列入队操作{ queue[tail]=p; tail++;}structpointdequeue()//迷宫中队列出队操作，返回的是结构体变量{ head++; returnqueue[head-1];}boolis_empty()//判断队列是否为空{ returnhead==tail;}voidvisit(introw,intcol,intmaze[102][102])//访问迷宫中的各个位置{ structpointvisit_point={row,col,head-1};//head-1的作用是访问这个点序号之前的点序号 maze[row][col]=2;//将已访问过的点位标记为2，便于以后输出 enqueue(visit_point);//将访问过的位置入队}intpath(intmaze[102][102],intm,intn)//主要函数，用于求解迷宫路径{ X=1;//刚开始声明的变量，初始值定为1 structpointp={0,0,-1};//定义入口节点 if(maze[p.row][p.col]==1)//异常处理，如果入口为1时，迷宫无解{cout<<"很遗憾......此迷宫无解\n\n"; X=0; return0; }maze[p.row][p.col]=2;//入口标记为已访问 enqueue(p);//将p入队列 while(!is_empty())//只在队列不为空的情况下执行此函数，向着迷宫通的位置移动，寻找路线 {p=dequeue();//将p标记为此时访问的位置，如果这个位置已到出口，则表示迷宫有解 if((p.row==m-1)&&(p.col==n-1))//当行和列为出口时结束 break; //以下定义8个走位方向 if((((p.row-1)>=0)&&((p.row-1)<m)&&((p.col+0)<n))&&(maze[p.row-1][p.col+0]==0)) visit(p.row-1,p.col+0,maze);//北 if((((p.row-1)>=0)&&((p.row-1)<m)&&((p.col+1)<n))&&(maze[p.row-1][p.col+1]==0)) visit(p.row-1,p.col+1,maze);//东北 if((((p.row+0)<m)&&((p.col+1)<n))&&(maze[p.row+0][p.col+1]==0)) visit(p.row+0,p.col+1,maze);//东 if((((p.row+1)<m)&&((p.col+1)<n))&&(maze[p.row+1][p.col+1]==0)) visit(p.row+1,p.col+1,maze);//东南 if((((p.row+1)<m)&&((p.col+0)<n))&&(maze[p.row+1][p.col+0]==0)) visit(p.row+1,p.col+0,maze);//南 if((((p.row+1)<m)&&((p.col-1)<n)&&((p.col-1)>=0))&&(maze[p.row+1][p.col-1]==0)) visit(p.row+1,p.col-1,maze);//西南 if((((p.row+0)<m)&&((p.col-1)<n)&&((p.col-1)>=0))&&(maze[p.row+0][p.col-1]==0)) visit(p.row+0,p.col-1,maze);//西 if((((p.row-1)>=0)&&((p.row-1)<m)&&((p.col-1)<n)&&((p.col-1)>=0))&&(maze[p.row-1][p.col-1]==0)) visit(p.row-1,p.col-1,maze);//西北 } if(p.row==m-1&&p.col==n-1)//如果p到达出口点，输出路径 { cout<<"\n恭喜您，此迷宫有解!\n"; cout<<"迷宫路径为：\n";cout<<"出口"<<endl; cout<<""<<"↑"<<endl; printf("(%d,%d)\n",p.row+1,p.col+1); cout<<""<<"↑"<<endl; maze[p.row][p.col]=3;//逆序将路径标记为3，便于以后输出 while(p.predecessor!=-1)//输出迷宫的坐标求解图 { p=queue[p.predecessor]; printf("(%d,%d)\n",p.row+1,p.col+1); cout<<""<<"↑"<<endl; maze[p.row][p.col]=3; } cout<<"入口"<<endl; } else { cout<<endl<<"很遗憾，此迷宫无解！\n\n"; X=0; } return0;}voidmain(){inti,m,n,cycle=0;//初始化各函数变量while(cycle!=(-1))//用cycle标记当前是否继续调试{cout<<"================================================================================\n";cout<<"欢迎进入迷宫求解系统\n"; cout<<endl;cout<<"设计者:桂柯易（09210580，2009211120班）\n";cout<<"================================================================================\n";cout<<"如需手动生成迷宫请按：1\n";cout<<"如需自动生成迷宫请按：2\n"; cout<<"如需求解书后给的迷宫请按：3\n";cout<<"如需退出请按：4\n\n";cout<<"================================================================================\n";cout<<endl;cout<<"请选择你的操作：\n";cin>>i; switch(i)//用switch函数确定对应的操作 { case1: cout<<"\n请输入行数："; cin>>m; cout<<"\n"; cout<<"请输入列数："; cin>>n; while((m<0||m>100)||(n<0||n>100))//异常处理，当输入的行列数不满足要求时，需要重新输入 { cout<<"\n抱歉，你输入的行列数不属于预设范围(0-100,0-100),请重新输入：\n\n"; cout<<"\n请输入行数："; cin>>m; cout<<"\n"; cout<<"请输入列数："; cin>>n; } hand_maze(m,n);//手动输入迷宫 data(m,n);//根据实际情况生成数字迷宫 print_maze(m,n);//画出迷宫图 path(maze,m,n);//迷宫求解 if(X!=0)result_maze(m,n);//当X不为0时，有解，调用输出路径函数 cout<<"\n\n需要继续调试，请按回车键!\n"; getchar(); while(getchar()!='\n');//输入一个操作，当为回车时执行break跳出 break; case2: cout<<"\n请输入行数：";cin>>m; cout<<"\n";cout<<"请输入列数："; cin>>n; while((m<0||m>49)||(n<0||n>49))//异常处理，行列不满足要求时需要重新输入 { cout<<"\n抱歉，你输入的行列数不属于预设范围(0-100,0-100),请重新输入：\n\n"; cout<<"\n请输入行数："; cin>>m; cout<<"\n"; cout<<"请输入列数："; cin>>n; } automatic_maze(m,n);//自动生成迷宫 data(m,n);//生成数字迷宫 print_maze(m,n);//画出迷宫图 path(maze,m,n);//迷宫求解 if(X!=0)result_maze(m,n);//当X不为0时，有解，调用输出路径函数 cout<<"\n\n需要继续调试，请按回车键!\n"; getchar(); while(getchar()!='\n'); break; case3: student_maze();//生成书后迷宫 print_maze(10,10);//画出迷宫图（暂不生成数字迷宫） path(maze,10,10);//迷宫求解 if(X!=0)result_maze(10,10);