注：下面分别是三个文件：栈的定义与声明（头文件）、栈的实现、迷宫问题.
/* 顺序栈表示：类型和界面函数声明 */
enum { MAXNUM = 20 /* 栈中最大元素个数,应根据需要定义 */
};
typedef int DataType; /* 栈中元素类型,应根据需要定义 */
struct SeqStack { /* 顺序栈类型定义 */
int t; /* 栈顶位置指示 */
DataType s[MAXNUM];
};
typedef struct SeqStack SeqSack, *PSeqStack; /* 顺序栈类型和指针类型 */
/*创建一个空栈;为栈结构申请空间,并将栈顶变量赋值为-1*/
PSeqStack createEmptyStack_seq( void );
/*判断pastack所指的栈是否为空栈,当pastack所指的栈为空栈时,则返回1,否则返回0*/
int isEmptyStack_seq( PSeqStack pastack );
/* 在栈中压入一元素x */
void push_seq( PSeqStack pastack, DataType x );
/* 删除栈顶元素 */
void pop_seq( PSeqStack pastack );
/* 当pastack所指的栈不为空栈时,求栈顶元素的值 */
DataType top_seq( PSeqStack pastack );
/* 顺序栈表示：函数定义 */
#include
#include
#include "sstack.h"
/*创建一个空栈;为栈结构申请空间,并将栈顶变量赋值为-1*/
PSeqStack createEmptyStack_seq( void ) {
PSeqStack pastack = (PSeqStack)malloc(sizeof(struct SeqStack));
if (pastack==NULL)
printf("Out of space! \n");
else
pastack->t = -1;
return pastack;
}
/*判断pastack所指的栈是否为空栈,当pastack所指的栈为空栈时,则返回1,否则返回0*/
int isEmptyStack_seq( PSeqStack pastack ) {
return pastack->t == -1;
}
/* 在栈中压入一元素x */
void push_seq( PSeqStack pastack, DataType x ) {
if( pastack->t >= MAXNUM - 1 )
printf( "Stack Overflow! \n" );
else {
pastack->t++;
pastack->s[pastack->t] = x;
}
}
/* 删除栈顶元素 */
void pop_seq( PSeqStack pastack ) {
if (pastack->t == -1 )
printf( "Underflow!\n" );
else
pastack->t--;
}
/* 当pastack所指的栈不为空栈时,求栈顶元素的值 */
DataType top_seq( PSeqStack pastack ) {
return pastack->s[pastack->t];
}
/* 迷宫问题的非递归算法(栈实现)*/
#define MAXNUM 100/* 栈中最大元素个数 */
#define N 11 /*地图的第一维长度*/
#include
#include
typedef struct {
int x;/* 行下标 */
int y;/* 列下标 */
int d;/* 运动方向 */
} DataType;
struct SeqStack { /* 顺序栈类型定义 */
int t; /* 指示栈顶位置 */
DataType s[MAXNUM];
};
typedef struct SeqStack *PSeqStack; /* 顺序栈类型的指针类型 */
PSeqStack pastack; /* pastack是指向顺序栈的一个指针变量 */
PSeqStack createEmptyStack_seq( void ) {
PSeqStack pastack;
pastack = (PSeqStack)malloc(sizeof(struct SeqStack));
if (pastack == NULL)
printf("Out of space! \n");
else
pastack->t = -1;
return pastack;
}
int isEmptyStack_seq( PSeqStack pastack ) {
return pastack->t == -1;
}
/* 在栈中压入一元素x */
void push_seq( PSeqStack pastack, DataType x ) {
if( pastack->t >= MAXNUM - 1 )
printf( "Overflow! \n" );
else {
pastack->t++;
pastack->s[pastack->t] = x;
}
}
/* 删除栈顶元素 */
void pop_seq( PSeqStack pastack ) {
if (pastack->t == -1 )
printf( "Underflow!\n" );
else
pastack->t--;
}
/* 当pastack所指的栈不为空栈时,求栈顶元素的值 */
DataType top_seq( PSeqStack pastack ) {
return (pastack->s[pastack->t]);
}
void pushtostack(PSeqStack st, int x, int y, int d) {
DataType element;
element.x = x;
element.y = y;
element.d = d;
push_seq(st, element);
}
void printpath(PSeqStack st) {
DataType element;
printf("The revers path is:\n"); /* 打印路径上的每一点 */
while(!isEmptyStack_seq(st)) {
element = top_seq(st);
pop_seq(st);
printf("the node is: %d %d \n", element.x, element.y);
}
}
/* 迷宫maze[M][N]中求从入口maze[x1][y1]到出口maze[x2][y2]的一条路径 */
/* 其中 1
