C语言数据结构之迷宫求解问题分享！

现在网上各种对于迷宫的求解，版本多的数不胜数。本人小白一枚，贴上自己对迷宫的求解这个小项目，自己写的。望能帮助一些同样有困难的人，毕竟我当时费解了好一会儿时间呢。

首先，先标明对于迷宫求解这个项目，首先我提出自己的思路，利用“穷举求解”的方法（严蔚敏老师数据结构一书中提到，一开始不知方法其名。）其实简单来说就是一条路一条路去试，当然不能随便试，我的方法是按照从入口出发，顺一个方向向前探索，走得通就继续向前走；否则留下标记沿原路退回并换一个方向继续探索，直到所有的路都走完为止。还是用栈的先进后出的结构保存一路的路线。代码用到了栈的顺序实现数组格式的结构（对于栈并没有详细阐述）。

  //调用头文件  #ifndef AFXSTD_H  #define AFXSTD_H      #include<stdio.h>  #include<stdlib.h>  #include<malloc.h>  #include<iostream>  using namespace std;   // cout; cin;C++的输入输出  #endif

  //迷宫的结构体的创建  #ifndef MAZE_H  #define MAZE_H     #define ROWSIZE 10 //迷宫大小  #define COLSIZE 10  #define Reachable 0 //可以到达的结点  #define Bar  1 //障碍物  #define Foot 2 //足迹  #define Mark 3 //不可通路标记  typedef int MapType[ROWSIZE][COLSIZE]; // 地图类型      typedef struct   {   int row;// x   int col;// y;  }PosType;   //坐标结构体     typedef struct  {   int ord;  //通道块在道路上的序号   PosType seat; //小人坐标   int di; // 方向 // 1 2 3 4  }MElemType; //试迷宫小人的结构     typedef MElemType SElemType; // 和stack 关联           bool MazePass(MapType maze,PosType curpos);  void FootPrint(MapType maze,PosType curpos); //足迹打印  PosType NextPos(PosType curpos,int di);  //下一个位置  void MarkPrint(MapType maze,PosType curpos);  //打印不可通标记  bool MazePath(MapType maze,PosType start,PosType end); //迷宫解谜核心  void PrintMap(MapType maze);    //打印地图        #endif

  //栈的结构体  #include"Maze.h"  #ifndef SEQSTACK_H  #define SEQSTACK_H  #define STACKSIZE 100     //typedef int SElemType;     struct SeqStack  {   SElemType *data;   int maxsize;   int top;  };     void Init_Stack(SeqStack &st);  void Destroy_Stack(SeqStack &st);  void Stack_Clear(SeqStack &st);  bool Stack_Empty(SeqStack &st);  bool Stack_Full(SeqStack &st);  int Stack_Size(SeqStack &st);  bool Stack_Push(SeqStack &st,const SElemType &x);  bool Stack_Pop(SeqStack &st, SElemType &x);     SElemType GetTop(SeqStack &st);  void Pop(SeqStack &st);     #endif

以上是头文件的创建，和结构体的创建，现在真的深切感到结构体的重要性。结构体创建不好就是自己给自己挖坑，切记切记！！

现在贴出函数的代码，解释我会尽力都写清楚。（栈的问题我后续会重新再仔细阐述的，这次的重点在于迷宫的求解，所以直接贴出栈的详细代码，望谅解。）

  //这里是栈的实现代码  #include"AfxStd.h"  #include"Stack.h"     bool Stack_Resize(SeqStack &st)  {   SElemType *s = (SElemType*)malloc(sizeof(SElemType)*st.maxsize * 2);   if(NULL == s) return false;   for(int i = 0;i<= st.top;++i)   {   s[i] = st.data[i];   }   free(st.data);   st.data = s;   st.maxsize = st.maxsize * 2;   return true;  }  void Init_Stack(SeqStack &st)  {   st.maxsize = STACKSIZE;   st.top = -1;   st.data = (SElemType*)malloc(sizeof(SElemType)*st.maxsize);   if(NULL == st.data)   {   exit(0);   }  }  void Destroy_Stack(SeqStack &st)  {   free(st.data);   st.data = NULL;   st.maxsize = 0;   st.top = -1;  }     void Stack_Clear(SeqStack &st)  {   st.top = -1;  }  bool Stack_Empty(SeqStack &st)  {   return Stack_Size(st) == 0;  }  bool Stack_Full(SeqStack &st)  {   return Stack_Size(st) == st.maxsize;  }     int Stack_Size(SeqStack &st)  {   return st.top + 1;  }     bool Stack_Push(SeqStack &st,const SElemType &x)  {   if(Stack_Full(st) && ! Stack_Resize(st))   {   return false;   }   st.data[++st.top] = x;   return true;  }  bool Stack_Pop(SeqStack &st, SElemType &x)  {   if(Stack_Empty(st))   {   return false;   }   x = st.data[st.top--];   return true;  }  

  //调用前面创建的头文件  #include"AfxStd.h"  #include"Maze.h"  #include"Stack.h"        /////////////////////////////////////////////////     bool MazePass(MapType maze,PosType curpos) //判断是否可以通过  {   return maze[curpos.row][curpos.col] == Reachable; //判断当前结点是否能通过  }  void FootPrint(MapType maze,PosType curpos) //打印足迹   {   maze[curpos.row][curpos.col] = Foot;   }  PosType NextPos(PosType curpos,int di)  //对下一个结点方向的判断  {   switch(di)   {   case 1: curpos.row+=1; break;// 1   case 2: curpos.col-=1; break;// 2   case 3: curpos.row-=1; break;// 3   case 4: curpos.col+=1; break;// 4   }   return curpos;  }  void MarkPrint(MapType maze,PosType curpos)  //不能通过的结点留下不能通过的标记  {   maze[curpos.row][curpos.col] = Mark;  }     bool MazePath(MapType maze,PosType start,PosType end)//（核心）迷宫解谜  {   bool res = false;    //定义一个res参数为布尔型   PosType curpos = start;   //初始当前位置为入口   int curstep = 1;    // 初始探索方向为1   SeqStack st;     //路径存储栈   MElemType e;     //初始探索小人   Init_Stack(st);     //初始化栈   do{   if(MazePass(maze,curpos))   //当前位置可通过，即是未曾走到过的坐标   {   FootPrint(maze,curpos);  //留下足迹   e.di = 1, e.seat = curpos,e.ord = curstep++;   Stack_Push(st,e);   //加入路径中   if(curpos.row == end.row && curpos.col == end.col)   {   res = true;   break;   }    //到达终点   curpos = NextPos(curpos,1); //探索下一位置   }   else   {   if(!Stack_Empty(st))  //当前位置不能通过   {   Stack_Pop(st,e);   while(e.di == 4 && !Stack_Empty(st))   {   MarkPrint(maze,e.seat);    Stack_Pop(st,e);  // 留下不能通过的标记，并退回一步   }   if(e.di < 4)   {   e.di+=1;   // 换下一个方向探索   Stack_Push(st,e);  //再次记录路径   curpos = NextPos(e.seat,e.di); // 当前位置设为新方向的相邻块   }   }   }   }while(!Stack_Empty(st)); //当栈空摧毁栈，返回失败参数   Destroy_Stack(st);     return res;  }  void PrintMap(MapType maze)  //打印地图  {   for(int i = 0;i<ROWSIZE;++i)   {   for(int j = 0;j<COLSIZE;++j)   {   printf("%2d",maze[i][j]);   }   printf("n");   }   printf("n");  }  

• 1
• 2
• 下一页