迷宫问题
迷宫问题一直是计算机工作者感兴趣的问题，因为它可以展现栈的巧妙应用，
这里将利用栈开发一个走迷宫程序，虽然在发现正确路径前，程序要尝试许多
错误路径，但是，一旦发现，就能够重新走出迷宫，而不会再去尝试任何错误路径。
迷宫问题求解
计算机中可以用如图所示的方块图表示迷宫。图中空白方块为通道，蓝色方块为墙
迷宫的储存可以使用二维数组，其中“0”代表墙值，“1”代表通路。由于迷宫被表示为
二维数组，所以，在任何时刻，迷宫中的位置都可以用行，列坐标来描述。
在迷宫中的某一个位置进行移动的可能方向如图所示
值得注意的是，并不是每一个位置都有四个邻居。如果[row][col]在边界上那么邻居的
个数就少于4个，甚至只有2个。为了避免边界条件的检查，在迷宫周围加上一圈边界。这样，
一个m*n的迷宫就需要一个(m+2)*(n+2)的数组。入口位置在[1][1],而出口位置在[m][n]。
另一个简化问题的策略是，用数值direc 预先定义出“可能的移动方向”数字0-3表示4个
可能的移动方向，对每个方向都指出其垂直和水平的偏移量。
求迷宫中一条径的算法的基本思想是：
若当前位置“可通“，则纳入”当前路径”，并继续朝“下一个位置探索”，即切换“下一位置”为
“当前位置”，如此反复直到出口；
若当前位置“不可通”则应顺着“来向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；
若该通道块的四周4个方块均“不可通”，则应从“当前路径”上删除该通道块。假设以栈
S记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。由此，
“纳入路径”的操作即为“当前位置压入”，“从当前路径上删除前一块通道块”的操作即为“弹出”。
需要说明的是，所谓的当前位置可通，指的是未曾走到过的通道块，即要求该方块位置S记录“当前路径”，
则栈顶中存放的是“当前路径上最后一个通道块”。由此，“纳入路径”的操作即为“当前位置压入”，
“从当前路径上删除前一块通道块”的操作即为“弹出”。不仅是通道块，而且不在当前路径上(否则路径不是简单路径)，
也不是曾经纳入过路径的通道块(否则只能在死胡同内转圈)。
sqstack.h
1 #pragma once 2 #include <stdio.h> 3 #include <stdlib.h> 4 #define STACK_INIT_SIZE 100//储存空间初始分配量 5 #define STACKINCREMENT 10//存储空间分配增量 6 #define OK 1 7 #define ERROR 0 8 typedef struct { 9 int x; //行值 10 int y; //列值 11 }PosType; //迷宫坐标位置类型 12 typedef struct 13 { 14 int ord; //序号 15 int di; //方向 16 PosType seat; //位置 17 18 } StackType; //栈元素类型 19 20 typedef struct { 21 StackType *base; //在构造之前和销毁之后，base的值为NULL 22 StackType *top; //栈顶指针 23 int stacksize; //当前已分配的存储空间，以元素为单位 24 25 }SqStack; //顺序栈 26 27 //栈的初始化 28 int InitStack(SqStack *p) { 29 30 31 p->base = (StackType*)malloc(STACK_INIT_SIZE * sizeof(StackType)); 32 if (p->base == NULL) return ERROR; //内存分配失败 33 p->top = p->base; //栈顶与栈底相同表示一个空栈 34 p->stacksize = STACK_INIT_SIZE; 35 return OK; 36 37 } 38 //判断栈是否为空 39 int EmptyStack(SqStack *p) { 40 //若为空栈 则返回OK，否则返回ERROR 41 if (p->top == p->base) return OK; 42 else return ERROR; 43 } 44 //顺序栈的压入 45 int Push(SqStack *p, StackType e) { 46 //插入元素e为新的栈顶元素 47 if ((p->top - p->base) >= p->stacksize) //栈满，追加储存空间 48 { 49 p->base = (StackType*)realloc(p->base, (p->stacksize + STACKINCREMENT) * sizeof(StackType)); 50 if (p->base == NULL) return ERROR;// 储存空间分配失败 51 p->top = p->base + p->stacksize; 52 p->stacksize += STACKINCREMENT; 53 } 54 *(p->top) = e; 55 (p->top)++; 56 return OK; 57 } 58 // 顺序栈的弹出 59 int Pop(SqStack *p, StackType *e) { 60 //若栈不空，则删除p的栈顶元素，用e返回其值 61 if (p->top == p->base) return ERROR; 62 --(p->top); 63 *e = *(p->top); 64 return OK; 65 66 67 } 68 //将顺序栈置空 栈还是存在的，栈中的元素也存在， 69 //如果有栈中元素的地址任然能调用 70 int ClearStack(SqStack *p) { 71 p->top = p->base; 72 return OK; 73 } 74 //顺序栈的销毁 75 int Des