参考严蔚敏老师的《数据结构》栈和队列这一章的相关内容完成的

栈的定义与基本操作的实现

/* 栈的顺序存储表示 */
#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