菜鸟的高手情结——数据结构之走迷宫.数据结构习题哦

本文主要是介绍菜鸟的高手情结——数据结构之走迷宫.数据结构习题哦，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这几天，我睡不着，课也不想上。就是因为数据结构的作业，一道迷宫问题。只要是上过数据结构的一订会遇到这道题。我原以为这么经典的题目网上一定会有完美的答案。搜了好久也没见完美。有是有人谈，但都只给一大段代码，看不懂啊！为了证明我不是弱智我翘了选修课

终于搞定它。水平有限，这只是初步代码。废话少说直接代码：

//main.cpp

#include<iostream>
#include<string>
#include "stack.h"
#include "maze.h"

bool MatchPath(maze ma,stack &pathstack,point in,point out);

int main()
{
//输入地图名称，初始化
std::cout<<"请输入地图名称，确保地图文件位置存放正确\n";
char mapname[25];
std::cin>>mapname;
maze ma;
if(!ma.InitMaze(mapname))
{std::cout<<"地图的名称有问题或地图文件内里的数据有问题，请检查\n";
return 0;}
//入口坐标
ma.PrintMaze();
std::cout<<"请输入入口坐标\n";
int ix,iy;
std::cin>>ix>>iy;
std::cout<<"请输入出口坐标\n";
int ox,oy;
std::cin>>ox>>oy;
//检查坐标输入是否合理
if(ix<0||ix>=ma.i||ox<0||ox>=ma.j)
{std::cout<<"坐标输入错误!";return 0;}

//查找路径
std::cout<<"路径查找中...\n";

point in,out;
in.x=ix;in.y=iy;
out.x=ox;out.y=oy;
stack path;
//匹配的关键算法
stack path2;
if(MatchPath(ma,path,in,out))
{
std::cout<<"结果如下：\n";
//因为栈中保存的路径是倒叙的，现在将这个栈中的元素压入另一个栈，就是正序了，
//在此过程中我们将地图中国的找到通路路径标记为*，方便输出时查看

while(!path.Isempty()){
  point tem;
  path.pop_back(tem);
  ma.MarkPath(tem.x,tem.y,'*');
  path2.push_back(tem);
}
//输出地图,路径已用*表示
ma.PrintMaze();
}
else std::cout<<"该迷宫无出路！\n";
//输出栈中的路径
path2.traversing();
return 0;

}
bool MatchPath(maze ma,stack &path,point start,point out)
{

point p=start;
path.push_back(p);
ma.MarkPath(p.x,p.y,'@');             //走过的路一@标示
int j=ma.j;
while(p.x!=out.x||p.y!=out.y){
  if(ma.point[(p.x)*j+p.y]=='@')
    ma.MarkPath(p.x,p.y,'#');
  else ma.MarkPath(p.x,p.y,'@');
// char c=getchar();

// if(c=='p')ma.PrintMaze();
  int dir=4;
  if(ma.point[(p.x+1)*j+p.y]=='#')dir-=1;
  if(ma.point[(p.x)*j+p.y+1]=='#')dir-=1;
  if(ma.point[(p.x-1)*j+p.y]=='#')dir-=1;
  if(ma.point[(p.x)*j+p.y-1]=='#')dir-=1;
     if(1==dir)
  {
   ma.MarkPath(p.x,p.y,'#');
   point tem;
   path.pop_back(tem);
   if(path.Isempty())return 0;//栈中已无元素，已无退路，失败
   p.x=path.top->num.x;
   p.y=path.top->num.y;
   ma.MarkPath(p.x,p.y,'#');
   continue;
  }
  if(0==dir)return 0;            //失败了，无路可走
  if(ma.point[(p.x+1)*j+p.y]!='#')   //向下走
  {
   p.x+=1;
   path.push_back(p);
  }
  else if(ma.point[(p.x)*j+p.y+1]!='#')        //向右走
  {
   p.y+=1;
   path.push_back(p);
     }

  else if(ma.point[(p.x-1)*j+p.y]!='#')        //向上走
  {
   p.x-=1;
   path.push_back(p);
  }
  else if(ma.point[(p.x)*j+p.y-1]!='#')         //向左走
  {
   p.y-=1;
   path.push_back(p);
  }
  else;
}
return true;
}

//maze.h

#include<fstream.h>
class maze{
public:
char *point;
int i,j;
bool InitMaze(char mapname[]);//初始化
void MarkPath(int x,int y,char c); //更改迷宫状态
void PrintMaze();//打印迷宫

};
bool maze::InitMaze(char mapname[])//接受一个地图文件
{
int r,w;
ifstream fileInput(mapname);
if(fileInput.is_open()){
  fileInput>>r>>w;
  i=r+2;j=w+2;
  point=new char[i*j];
  char *p=point;

  for(int k=0,num;k<i*j;k++)
  {
   fileInput>>num;
   if(num==0)*p=' ';
   else if(num==1)*p='#';
   else return false;
   p++;
  }
  fileInput.close();
}
else return false;
return true;
}
void maze::MarkPath(int x,int y,char c)
{
point[x*j+y]=c;
}
void maze::PrintMaze()
{
for(int x=0;x<i;x++)
{
  for(int y=0;y<j;y++)
   std::cout<<point[x*j+y]<<" ";
  std::cout<<"\n";
}
}
//stack.h

typedef struct{
int x;
int y;
}point;
typedef struct Node{
point num;
struct Node *pNext;
}Node;
class stack{
public:
Node node;
Node*top;
stack();
void push_back(point a);            //入栈
void pop_back(point &e);            //出栈
bool Isempty();                     //判断是否为空
void traversing();                  //遍历
};
stack::stack()
{
top=NULL;
}
void stack::push_back(point a)
{
Node*p;
p=new Node;
p->num.x=a.x;
p->num.y=a.y;
p->pNext=top;
top=p;
}
void stack::pop_back(point &e)
{
Node*p=top;
e.x=top->num.x;
e.y=top->num.y;
top=top->pNext;
delete p;
}
bool stack::Isempty()
{
return top==NULL;
}
void stack::traversing()
{
Node*p=top;
while(p){
  std::cout<<"("<<p->num.x<<", "<<p->num.y<<") \n";
  p=p->pNext;
}
}