迷宫（2）----细节上的完善

头文件：

        AfxStd.h：

#ifndef AFXSTD_H #define AFXSTD_H #include<stdio.h> #include<stdlib.h> #include<malloc.h> #endif

        Maze.h：

#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; //行下标 int col; //列下标 }PosType; typedef struct { int ord; PosType seat; int di; //方向 1 南 2 西 3 北 4 东 }MElemType; typedef MElemType SElemType; //重命名为栈中元素节点 void loading(MapType maze); //载入地图 bool MazePass(MapType maze, PosType curpos); //判断当前方块是否可通 void FootPrint(MapType maze, PosType curpos); //将当前方块标记为Foot（2） void MarkPrint(MapType maze, PosType curpos); //将当前方块标记为Mark（3） PosType NexPos(PosType curpos, int di); //返回当前方块的相邻方块 bool MazePath(MapType maze, PosType start, PosType end); //判断从start到end是否可达 void PrintMap(MapType maze); //打印该地图 #endif

        SeqStack.h：

#include"Maze.h" #ifndef SEQSTACK_H #define SEQSTACK_H #define STACKSIZE 100 //栈初始元素节点个数 #define Increment 2 //栈扩容倍数 //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); //判断栈是否为满 bool Stack_Resize(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); //返回栈顶元素 bool Pop(SeqStack &st); //元素节点出栈（不带回栈顶元素） #endif // !SEQSTACK_H

源文件：

        AfxStd.cpp

#include"AfxStd.h"

        Maze.cpp：

#include"AfxStd.h" #include"Maze.h" #include"SeqStack.h" // void loading(MapType maze) //载入地图 { int i = 0; FILE *stream; errno_t err = fopen_s(&stream, "maze.txt", "r"); if (err != 0) exit(1); int *ip = (int *)maze; while (!feof(stream)) { char ch = getc(stream); if (ch == '0' || ch == '1') { ip[i++] = ch - '0'; } } fclose(stream); } 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 NexPos(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)    //将方块标记为不可通Mark（3） { maze[curpos.row][curpos.col] = Mark; } bool MazePath(MapType maze, PosType start, PosType end) //判断从start到end是否可达 { bool res = false; PosType curpos = start; int curstep = 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 = NexPos(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 = NexPos(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("-", maze[i][j]); } printf("\n"); } printf("\n"); }

        SeqStack.cpp：

#include"AfxStd.h" #include"SeqStack.h" 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; } 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; } 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 = GetTop(st); Pop(st); return true; } SElemType GetTop(SeqStack &st) //返回栈顶元素 { return st.data[st.top]; } bool Pop(SeqStack &st) //元素出栈（不带回栈顶元素） { if (Stack_Empty(st)) { return false; } st.data[st.top--]; return true; }

        TestMaze.cpp：

#include"AfxStd.h" #include"Maze.h" #include"SeqStack.h" int main() { MapType maze; loading(maze); PosType start = { 1,1 }, end = { 8,8 }; PrintMap(maze); MazePath(maze,start, end); PrintMap(maze); return 0; }

本程序在VS2017下运行通过