参考严蔚敏老师的《数据结构》栈和队列这一章的相关内容完成的
栈的定义与基本操作的实现
/* 栈的顺序存储表示 */
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct
{
ElemType *base;
ElemType *top;
int stacksize;
}SqStack;
/* 基本操作函数 9个 */
Status InitStack(SqStack *S)
{/* 01构造一个空栈 */
S->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
if (!S->base)
{
printf("存储分配失败!:InitStack()\n");
exit(OVERFLOW);
}
S->top = S->base;
S->stacksize = STACK_INIT_SIZE;
return OK;
}
Status DestroyStack(SqStack *S)
{/* 02销毁栈S */
free(S->base);
free(S->top);
S->base = NULL;
S->top = NULL;
S->stacksize = 0;
return OK;
}
Status ClearStack(SqStack S)
{/* 03把S设置为空栈 */
S.top = S.base;
return OK;
}
Status StackEmpty(SqStack S)
{/* 04查看栈是否为空 */
return (S.top == S.base) ? TRUE : FALSE;
}
int StackLength(SqStack S)
{/* 05查看栈长度 */
return (S.top-S.base)/sizeof(ElemType);
}
Status GetTop(SqStack S, ElemType *e)
{/* 06获取栈顶元素 */
if (StackEmpty(S))
{
return FALSE;
}
else
{
*e = *(S.top-1);
}
}
Status Push(SqStack *S, ElemType e)
{/* 07入栈 */
if (StackLength(*S)==S->stacksize)
{
ElemType *newbase;
newbase = (ElemType *)realloc(S, (S->stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!newbase)
{
printf("存储分配失败!:Push()\n");
exit(OVERFLOW);
}
S->base = newbase;
S->stacksize += STACKINCREMENT;
}
*(S->top) = e;
S->top++;
return OK;
}
Status Pop(SqStack *S, ElemType *e)
{/* 08出栈 */
if (StackEmpty(*S))
{
return FALSE;
}
else
{
*e = *(--S->top);
}
return OK;
}
Status StackTraverse(SqStack S, Status (* visit)(ElemType e))
{/* 09遍历栈中元素 */
while (S.top != S.base)
{
visit(*(--S.top));
}
printf("\n");
return OK;
}
cbo3-1.c
迷宫求解的算法实现
typedef struct
{
int x; // 行号
int y; // 列号
} PosType;
typedef struct
{
int ord; // 序号
PosType seat; // 坐标
int di; // 方向 0123代表右下左上，默认向右
} ElemType;
#include "c1.h"
#include "cbo3-1.c"
/* 迷宫求解 */
/*
* 地图
* '#' 墙
* ' ' 路
* 's' 入口
* 'e' 出口
* '*' 当前位置
* 'o' 走过的路
*/
int map[10][10] = {{'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},
{'#', ' ', ' ', '#', ' ', ' ', ' ', '#', ' ', '#'},
{'#', ' ', ' ', '#', ' ', ' ', ' ', '#', ' ', '#'},
{'#', ' ', ' ', ' ', ' ', '#', '#', ' ', ' ', '#'},
{'#', ' ', '#', '#', '#', ' ', ' ', ' ', ' ', '#'},
{'#', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', '#'},
{'#', ' ', '#', ' ', ' ', ' ', '#', ' ', ' ', '#'},
{'#', ' ', '#', '#', '#', ' ', '#', '#', ' ', '#'},
{'#', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#'},
{'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'}};
PosType start; // 入口坐标
PosType end; // 出口坐标
SqStack ss; // 栈
ElemType cur, top; // 当前位置和栈顶位置
PosType direc[4] = {{0, 1}, // 右
{1, 0}, // 下
{0, -1}, // 左
{-1, 0}}; // 上
int step = 0; // 走的步数
/**
* 打印地图有的
*/
void printMap();
int pass(PosType pt)
{ /* 判断该位置是否是通路 1:通路， 0:不是通路*/
return map[pt.x][pt.y] == ' ' ? 1 : 0;
}
int isEnd(PosType pt)
{ /* 判断该位置是否是出口 1:是 0:不是 */
int re = 0;
if(pt.x == end.x && pt.y == end.y) {
re = 1;
}
return re;
}
void print(ElemType e, char *s)
{ /* 打印栈元素 */
printf("%s [e.ord:%d, e.seat(%d, %d), e.di:%d]\n", s, e.ord, e.seat.x, e.seat.y, e.di);
}
void setfoot(PosType pt, int op)
{ /* 设置脚印1：设置 0：清除 */
if (map[pt.x][pt.y]==' ' && op==1)
{ // 只有在通路上设置脚印
map[pt.x][pt.y] = 'o';
}
else if (map[pt.x][pt.y]=='o' && op==0)
{ // 清除脚印
map[pt.x][pt.y] = ' ';
}
}
int nextDi(ElemType e, ElemType *next)
{ /* next是e位置的下一个指向 */
if (e.di<3)
{
next->di = 0;
next->seat = e.seat;
next->seat.x += direc[e.di+1].x;
next->seat.y += direc[e.di+1].y;
}
else
{ // 无路可走
return 0;
}
return 1;
}
int main()
{
/* 设置出口入口坐标 */
start.x = 1;
start.y = 1;
end.x = 8;
end.y = 8;
/* 初始化当前位置 */
cur.ord = 0;
cur.seat = start; // 设定当前位置的初值为入口坐标
cur.di = 0;
InitStack(&ss);
printMap();
int isStep=0;
do {
step++;
if(isStep)
{
printf("\n******按回车键查看下一步******\n");
getchar();
printMap();
isStep = 0;
}
if (pass(cur.seat))
{ // 若当前位置是通路
cur.ord++;
Push(&ss, cur); // 将当前位置入栈
setfoot(cur.seat, 1); // 设置脚印
print(cur, "当前位置入栈");
isStep = 1;
GetTop(ss, &top);
if (isEnd(cur.seat))
{ // 该位置是出口，则结束
printf("pass! game over!\n");
system("pause");
return 0;
}
else
{
cur.seat.y++; // 切换当前位置的右方为新的当前位置
printf("当前位置向右移");
}
}
else
{ // 当前位置不通
if (!StackEmpty(ss))
{ // 栈不空
if (nextDi(top, &cur))
{ // 栈顶位置尚有其它方向，并且设定新的当前位置为顺时针方向旋转的栈顶位置的下一邻块
Pop(&ss, &top);
top.di++;
Push(&ss, top); // 修改栈顶元素的di
printf("修改栈顶位置的di");
}
else
{ // 栈顶位置的四周都不通
Pop(&ss, &top); // 删除栈顶位置
setfoot(top.seat, 0); // 清除脚印
print(top, "栈顶位置出栈");
isStep = 1;
GetTop(ss, &top);
if(!StackEmpty(ss))
{ // 如果栈不空，则重新测试新的栈顶位置
GetTop(ss, &cur);
}
else
{ // 栈为空，无结果
printf("no way\n");
break;
}
}
}
}
} while (!StackEmpty(ss));
system("pause");
return 0;
}
int visit(ElemType e) {
printf("[ord:%d\t seat:(%d, %d) di:%d]\n", e.ord, e.seat.x, e.seat.y, e.di);
}
void printMap()
{
printf("step = %d\n", step);
print(cur, "当前位置");
if(!StackEmpty(ss))
{
print(top, "栈顶位置");
StackTraverse(ss, visit);
}
int i, j; // i代表行，j代表列
for (i=0; i<10; i++)
{
for (j=0; j<10; j++)
{
/*
if (cur.seat.x==i && cur.seat.y==j)
{
printf("%c ", '*');
}
else if (start.x==i && start.y==j)
{
printf("%c ", 's');
}
else if (end.x==i && end.y==j)
{
printf("%c ", 'e');
}
else
{
printf("%c ", map[i][j]);
}*/
printf("%c ", map[i][j]);
}
printf("\n");
}
printf("\n");
}
main3-3.c
用到的一个包含文件
/* c1.h (程序名) */
#include<string.h>
#include<ctype.h>
#include<malloc.h> /* malloc()等 */
#include<limits.h> /* INT_MAX等 */
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#include<stdlib.h> /* atoi() */
#include<io.h> /* eof() */
#include<math.h> /* floor(),ceil(),abs() */
#include<process.h> /* exit() */
/* 函数结果状态代码 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
/* #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 */
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */
c1.h
