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");}

#include"AfxStd.h"#include"Maze.h" int main(){ MapType maze ={      //一开始地图的创建 {1,1,1,1,1,1,1,1,1,1}, {1,0,1,1,1,1,1,1,1,1}, {1,0,0,0,0,0,0,0,0,1}, {1,0,0,0,1,1,1,1,0,1}, {1,0,0,0,1,1,1,1,0,1}, {1,0,1,1,1,1,0,0,0,1}, {1,0,1,1,1,1,1,1,1,1}, {1,0,0,0,0,0,0,1,1,1}, {1,0,1,1,1,1,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1}, }; PosType start={1,1},end={8,8}; PrintMap(maze);      //打印初始地图 MazePath(maze,start,end); PrintMap(maze);      //打印迷宫解法 return 0;}