数据结构---利用顺序栈的迷宫问题

/*希望大家多多指正*/

原始迷宫：

输出迷宫：

实现如下：

MazeStructure.h

#define up 0
#define right 1
#define down 2
#define left 3
#define OVERFLOW 0;
#define OK 1;
#define termination -2

typedef struct Point {//迷宫中每一点的位置的信息;
int x;
int y;
int value;  //每一点的值
int d;      //direction

}PointType;

typedef PointType ElemType;

typedef struct {
ElemType *elem;
int top;
int size;
int increment;

} SqStack;

main.cpp

#include <stdlib.h>
#include "MazeStructure.h"


int InitStack_Sq(SqStack &S, int size, int inc) {//初始化空顺序栈
S.elem = (ElemType*)malloc(size * sizeof(ElemType));
if (NULL == S.elem) return OVERFLOW;
S.top = 0;
S.size = size;
S.increment = inc;
return OK;
}


int Push_Sq(SqStack &S, ElemType e) {//元素e压入栈S
ElemType *newbase;
if (S.top >= S.size) {
newbase = (ElemType*)realloc(S.elem, (S.size + S.increment) * sizeof(ElemType));
if (NULL == newbase) return OVERFLOW;
S.elem = newbase;
S.size += S.increment;
}
S.elem[S.top++] = e;
return OK;
}


ElemType Pop_Sq(SqStack &S, ElemType &e) {//栈顶元素出栈，并用e返回
e = S.elem[S.top--];
return e;
}


int StackEmpty_Sq(SqStack S) {//判断栈是否为空，若空则返回true，否则返回false
if (S.top == 0) return true;
else return false;
}


int main() { //主函数
int i, j,top;
Point maze[10][8];
for (j = 0; j < 8; j++){
for (i = 0; i < 10; i++){
maze[i][j].value = 1;
maze[i][j].x = i;
maze[i][j].y = j;
}
}
//人工加载信息
maze[1][1].value = 0; maze[2][1].value = 0; maze[2][2].value = 0; maze[3][2].value = 0; maze[4][2].value = 0; maze[3][3].value = 0; maze[4][3].value = 0;
maze[5][3].value = 0; maze[6][3].value = 0; maze[7][3].value = 0; maze[5][4].value = 0; maze[5][5].value = 0; maze[5][6].value = 0; maze[4][6].value = 0;
maze[6][5].value = 0; maze[7][5].value = 0; maze[8][5].value = 0; maze[8][6].value = 0; maze[1][3].value = 0; maze[1][4].value = 0; maze[1][6].value = 0;
maze[2][5].value = 0; maze[3][5].value = 0; maze[5][1].value = 0;
maze[1][1].d = -1; maze[2][1].d = -1; maze[2][2].d = -1; maze[3][2].d = -1; maze[4][2].d = -1; maze[3][3].d = -1; maze[4][3].d = -1;
maze[5][3].d = -1; maze[6][3].d = -1; maze[7][3].d = -1; maze[5][4].d = -1; maze[5][5].d = -1; maze[5][6].d = -1; maze[4][6].d = -1;
maze[6][5].d = -1; maze[7][5].d = -1; maze[8][5].d = -1; maze[8][6].d = -3; maze[1][3].d = -1; maze[1][4].d = -1; maze[1][6].d = -1;
maze[2][5].d = -1; maze[3][5].d = -1; maze[5][1].d = -1;

SqStack S;
ElemType e;
InitStack_Sq(S,13,5); //第一步，栈初始化
Push_Sq(S, maze[1][1]);  //第二步，将入口点坐标maze[1][1]压入栈
while (!StackEmpty_Sq(S)) { //第三步，若栈不空时循环执行下列操作
top = S.top - 1;
S.elem[top].d++;//下一个方向 d++
e = S.elem[top];
if (e.d == termination) break;   //如果到了终点，条件循环语句结束
if (e.d == up) {
if ((maze[e.x][e.y - 1].value == 0) && ((e.x != S.elem[S.top-2].x) || (e.y-1 != S.elem[S.top - 2].y))) {
Push_Sq(S, maze[e.x][e.y - 1]);
}
}
else if (e.d == right) {
if ((maze[e.x + 1][e.y].value == 0) && ((e.x+1 != S.elem[S.top - 2].x) || (e.y != S.elem[S.top - 2].y))) {
Push_Sq(S, maze[e.x + 1][e.y]);
}
}
else if (e.d == down) {
if ((maze[e.x][e.y + 1].value == 0) && ((e.x != S.elem[S.top - 2].x) || (e.y + 1 != S.elem[S.top - 2].y))) {
Push_Sq(S, maze[e.x][e.y + 1]);
}
}
else if (e.d == left) {
if ((maze[e.x - 1][e.y].value == 0) && ((e.x - 1 != S.elem[S.top - 2].x) || (e.y != S.elem[S.top - 2].y))) {
Push_Sq(S, maze[e.x - 1][e.y]);
}
else{//如果四个方向都不行，就返回上一个记录的位置
Pop_Sq(S, e);
}
}
}
/*以下为输出矩阵步骤*/
int step = 0;
SqStack S1;
InitStack_Sq(S1, 13, 5);
for (j = 0; j < 8; j++) {
for (i = 0; i < 10; i++) {
maze[i][j].value = 1;
maze[i][j].x = i;
maze[i][j].y = j;
}
}
while (!StackEmpty_Sq(S)){
e = S.elem[S.top - 1];
Push_Sq(S1,e);
maze[e.x][e.y].value = 0;
Pop_Sq(S, e);
}
while (!StackEmpty_Sq(S1)){
step++;
e = S1.elem[S1.top - 1];
printf("Step%d: x=%d,y=%d\n",step,e.x,e.y);
Pop_Sq(S1,e);
}
printf("\n输出矩阵如下：\n");
for (j = 0; j < 8; j++) {//打印测试
for (i = 0; i < 10; i++) {
printf("  %d", maze[i][j].value);
}
printf("\n");
}
return OK;
}