migong.rar_visual c_数据结构 迷宫

#include<iostream> #include<fstream> #include<stack> #include"labyrinth.h" #define D 4 using namespace std; ///\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ // 函数名：Labyrinth // 功能：迷宫类的构造函数 // 函数参数：无 // 函数返回值：无 Labyrinth::Labyrinth() // 初始化工作很简单，把矩阵的行数和列数设为 0 就行了 { num_x=0; num_y=0; } ///\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ // 函数名：~Labyrinth // 功能：迷宫类的析构函数 // 函数参数：无 // 函数返回值：无 Labyrinth::~Labyrinth() { DeleteLabyrinth(); // 析构函数很简单，就是调用删除迷宫的函数 } ///\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ // 函数名：CreatLabyrinth // 功能：创建一个迷宫 // 函数参数：无 // 函数返回值：无 void Labyrinth::CreatLabyrinth() { int i,j; int ch; // 判断采用哪种方式获取迷宫矩阵 cout<<" 您打算从文件读入迷宫矩阵，还是从键盘输入迷宫矩阵？"<<endl; cout<<" 1. 我要从文件读入迷宫矩阵。"<<endl; cout<<" 2. 我要从键盘输入迷宫矩阵。"<<endl; cout<<" 请选择 1 或 2 : \n "; cin>>ch; if((ch!=1)&&(ch!=2)) cout<<" 输入不合法！"<<endl; else if(ch==1) CreatLabyrinthFF(); // 从文件获取迷宫矩阵 else // 从键盘读入迷宫矩阵 { // 读入迷宫矩阵的行数和列数 cout<<" 我将为您创建一个迷宫。"<<endl; cout<<" 请输入迷宫矩阵的行数: "; cin>>num_x; cout<<" 请输入迷宫矩阵的列数: "; cin>>num_y; // 动态声明二维数组以存放迷宫矩阵 matrix=new int * [num_x+2]; for(i=0;i<num_x+2;i++) matrix[i]=new int [num_y+2]; // 建立迷宫矩阵，在迷宫矩阵外围加了"一堵墙" for(i=0;i<num_x+2;i++) { if((i!=0)&&(i!=num_x+1)) cout<<" 请输入迷宫矩阵第 "<<i<<" 行的值 :\n "; for(j=0;j<num_y+2;j++) { if((i==0)||(i==num_x+1)||(j==0)||(j==num_y+1)) // 迷宫矩阵外墙结点的值为 1 matrix[i][j]=1; else cin>>matrix[i][j]; // 为迷宫矩阵结点赋值 } } } } ///\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ // 函数名：CreatLabyrinthFF // 功能：从文件读入迷宫矩阵 // 函数参数：无 // 函数返回值：无 void Labyrinth::CreatLabyrinthFF() { ifstream infile("in.txt",ios::out); int i,j; // 读入迷宫矩阵的行数和列数 infile>>num_x; infile>>num_y; // 动态声明二维数组以存放迷宫矩阵 matrix=new int * [num_x+2]; for(i=0;i<num_x+2;i++) matrix[i]=new int [num_y+2]; // 建立迷宫矩阵，在迷宫矩阵外围加了"一堵墙" for(i=0;i<num_x+2;i++) { if((i!=0)&&(i!=num_x+1)) for(j=0;j<num_y+2;j++) { if((i==0)||(i==num_x+1)||(j==0)||(j==num_y+1)) matrix[i][j]=1; // 外墙的数据不从文件读入 else infile>>matrix[i][j]; // 从文件读入迷宫矩阵的结点值 } } } ///\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ // 函数名：ShowLabyrinth // 功能：显示迷宫矩阵 // 函数参数：无 // 函数返回值：无 void Labyrinth::ShowLabyrinth() // 超简单，不过就是使用输出二维数组的算法 { int i,j; for(i=1;i<num_x+1;i++) { for(j=1;j<num_y+1;j++) cout<<" "<<matrix[i][j]; cout<<endl; } } ///\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ // 函数名：LabyrinthPath // 功能：求出迷宫路径 // 函数参数：无 // 函数返回值：无 void Labyrinth::LabyrinthPath() { stack < DataType > s; DataType Temp1,Temp2; int x,y,loop; DataType move[D]; // DataType[D] 是表示移动方向的一个结构体数组 int i; for(i=0;i<D;i++) // 表示前进方向的结构体数组 { switch(i) { case D-D: move[i].y=1; move[i].x=0; break; case D-D+1: move[i].y=0; move[i].x=1; break; case D-D+2: move[i].y=-1; move[i].x=0; break; case D-D+3: move[i].y=0; move[i].x=-1; break; } } Temp1.x=1; Temp1.y=1; s.push(Temp1); // 将入口位置压入栈中 matrix[1][1]=-1; // 标志入口位置已经到达过 while(!s.empty()) { Temp2=s.top(); // 取栈顶元素 if((Temp2.x==num_x)&&(Temp2.y==num_y)) // 如果走到出口，就退出循环 break; if(PracticalDirection(Temp2)==0) // 如果当前位置的可行方向为 0 ，则返回前一位置 s.pop(); else { for(loop=0;loop<D;loop++) // 探索当前位置的四个相邻位置 { x=Temp2.x+move[loop].x; y=Temp2.y+move[loop].y; if(matrix[x][y]==0) // 新位置是否可到达 { Temp1.x=x; Temp1.y=y; matrix[x][y]=-1; // 标志该位置已经到达过 s.push(Temp1); break; // 一旦找到当前位置的下一可行位置就不再继续查找 }// if }// for }// else }// while if(s.empty()) cout<<" 这个迷宫没有进得去出不来-_-!\n"; else PrintPathByThree(s); // 输出路径 Restore(); // 恢复迷宫 } ///\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ // 函数名：LabyrinthInstruction // 功能：打印迷宫游戏的操作说明 // 函数参数：无 // 函数返回值：无 void Labyrinth::LabyrinthInstruction() { cout<<" 操作说明 : \n"; cout<<" 1. 迷宫一定要用矩阵的形式表示。\n"; cout<<" 2. 走得通的矩阵单元用 0 表示，走不通的矩阵单元用 1 表示。\n"; cout<<" 2. 迷宫的出口和入口分别在矩阵左上角和右下角。\n"; } ///\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ // 函数名：IsEmpty // 功能：判断迷宫矩阵是否为空 // 函数参数：无 // 函数返回值： // true：表示迷宫矩阵为空 // false: 表示迷宫矩阵非空 bool Labyrinth::IsEmpty() { if((num_x==0)&&(num_y==0)) return true; return false; } ///\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ // 函数名：DeleteLabyrinth // 功能：删除迷宫矩阵 // 函数参数：无 // 函数返回值：无 void Labyrinth::DeleteLabyrinth() { int i; for(i=0;i<num_x;i++) delete [] matrix[i]; // 注意释放动态二维数组空间的写法 delete []matrix; } ///\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ // 函数名：PracticalDirection // 功能：求出给定迷宫结点前后左右的可通行结点个数 // 函数参数：DataType data // 返回值类型：int // 说明：这个函数是私成员，专供 LabyrinthPath 函数调用 int Labyrinth::PracticalDirection( DataType data) { int x,y; int count=0; // count 用来表示当前结点的前方有多少岔路 x=data.x; y=data.y; if(matrix[x][y+1]==0) count++; if(matrix[x+1][y]==0) count++; if(matrix[x][y-1]==0) count++; if(matrix[x-1][y]==0) count++; return count; } ///\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ // 函数名：PrintPathByThree // 功能：使用三元组法表示迷宫路径 // 函数参数：stack < DataType > s // 返回值类型：无 // 说明：这个函数是私成员，专供 LabyrinthPath 函数调用 void Labyrinth::PrintPathByThree( stack < DataType > s) { stack < Three > t; DataType a,b; Three temp; int x,y; // 处理最后一个迷宫路径结点的三元组，该结点在栈顶哦 a=s.top(); s.pop(); temp.x=a.x; temp.y=a.y; temp.z=0; t.push(temp); // 处理其他迷宫路径上的结点 while(!s.empty()) { b=a; a=s.top(); s.pop(); temp.x=a.x; temp.y=a.y; x=a.x-b.x; y=a.y-b.y; if(y==-1) temp.z=1; else if(y==1) temp.z=3