棧的應(yīng)用舉例：迷宮求解

參考嚴(yán)蔚敏老師的《數(shù)據(jù)結(jié)構(gòu)》棧和隊(duì)列這一章的相關(guān)內(nèi)容完成的

棧的定義與基本操作的實(shí)現(xiàn)

/* 棧的順序存儲(chǔ)表示 */
#define STACK_INIT_SIZE 100
#define STACKINCREMENT  10
typedef struct
{
    ElemType *base;
    ElemType *top;
    int stacksize;
}SqStack;

/* 基本操作函數(shù) 9個(gè) */

Status InitStack(SqStack *S)
{/* 01構(gòu)造一個(gè)空棧 */
    S->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
    if (!S->base)
    {
        printf("存儲(chǔ)分配失敗!: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設(shè)置為空棧 */
    S.top = S.base;
    return OK;
}

Status StackEmpty(SqStack S)
{/* 04查看棧是否為空 */
    return (S.top == S.base) ? TRUE : FALSE;
}

int StackLength(SqStack S)
{/* 05查看棧長(zhǎng)度 */
    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("存儲(chǔ)分配失敗!: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

迷宮求解的算法實(shí)現(xiàn)

typedef struct
{
    int x;  // 行號(hào)
    int y;  // 列號(hào)
} PosType;
typedef struct
{
    int ord;        // 序號(hào)
    PosType seat;   // 坐標(biāo)
     int di;     // 方向 0123代表右下左上，默認(rèn)向右
} ElemType;
#include "c1.h"
#include "cbo3-1.c"

/* 迷宮求解 */

/*
 * 地圖
 * '#'    墻
 * ' '    路
 * 's'    入口
 * 'e'    出口
 * '*'  當(dāng)前位置
 * 'o'  走過(guò)的路
 */
int map[10][10] = {{'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},
                   {'#', ' ', ' ', '#', ' ', ' ', ' ', '#', ' ', '#'},
                   {'#', ' ', ' ', '#', ' ', ' ', ' ', '#', ' ', '#'},
                   {'#', ' ', ' ', ' ', ' ', '#', '#', ' ', ' ', '#'},
                   {'#', ' ', '#', '#', '#', ' ', ' ', ' ', ' ', '#'},
                   {'#', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', '#'},
                   {'#', ' ', '#', ' ', ' ', ' ', '#', ' ', ' ', '#'},
                   {'#', ' ', '#', '#', '#', ' ', '#', '#', ' ', '#'},
                   {'#', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#'},
                   {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'}};


PosType start;      // 入口坐標(biāo)
PosType end;        // 出口坐標(biāo)
SqStack ss;         // 棧
ElemType cur, top;  // 當(dāng)前位置和棧頂位置


PosType direc[4] = {{0, 1},     // 右
                    {1, 0},     // 下
                    {0, -1},    // 左
                    {-1, 0}};    // 上
                    

int step = 0;       // 走的步數(shù)

/**
 * 打印地圖有的
 */
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)
{ /* 設(shè)置腳印1：設(shè)置 0：清除 */
    if (map[pt.x][pt.y]==' ' && op==1)
    { // 只有在通路上設(shè)置腳印
        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位置的下一個(gè)指向 */
    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
    {   // 無(wú)路可走
        return 0;
    }
    return 1;
}

int main()
{
    /* 設(shè)置出口入口坐標(biāo) */
    start.x = 1;
    start.y = 1;
    end.x = 8;
    end.y = 8;

    /* 初始化當(dāng)前位置 */
    cur.ord = 0;
    cur.seat = start;   // 設(shè)定當(dāng)前位置的初值為入口坐標(biāo)
    cur.di = 0;
    InitStack(&ss);
    
    printMap();
    
    int isStep=0;
    do {
        step++;
        if(isStep)
        {
            printf("\n******按回車鍵查看下一步******\n");
            getchar();
            printMap();
            isStep = 0;
        }
        if (pass(cur.seat))
        { // 若當(dāng)前位置是通路
            cur.ord++;
            Push(&ss, cur);          // 將當(dāng)前位置入棧
            setfoot(cur.seat, 1);    // 設(shè)置腳印
            print(cur, "當(dāng)前位置入棧");
            isStep = 1;
            
            GetTop(ss, &top);
            if (isEnd(cur.seat))
            {   // 該位置是出口，則結(jié)束
                printf("pass! game over!\n");
                system("pause");
                
                return 0;
            }
            else
            {
                cur.seat.y++;   // 切換當(dāng)前位置的右方為新的當(dāng)前位置
                printf("當(dāng)前位置向右移");
            }
        }
        else
        {  // 當(dāng)前位置不通
            if (!StackEmpty(ss))
            { // 棧不空
                if (nextDi(top, &cur))
                { // 棧頂位置尚有其它方向，并且設(shè)定新的當(dāng)前位置為順時(shí)針?lè)较蛐D(zhuǎn)的棧頂位置的下一鄰塊
                    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))
                    { // 如果棧不空，則重新測(cè)試新的棧頂位置
                        GetTop(ss, &cur);
                    }
                    else
                    { // 棧為空，無(wú)結(jié)果
                        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, "當(dāng)前位置");
    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

用到的一個(gè)包含文件

/* 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() */
 /* 函數(shù)結(jié)果狀態(tài)代碼 */
 #define TRUE 1
 #define FALSE 0
 #define OK 1
 #define ERROR 0
 #define INFEASIBLE -1
 /* #define OVERFLOW -2 因?yàn)樵趍ath.h中已定義OVERFLOW的值為3,故去掉此行 */
 typedef int Status; /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 */
 typedef int Boolean; /* Boolean是布爾類型,其值是TRUE或FALSE */

c1.h
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 二、棧和隊(duì)列 棧和隊(duì)列都是線性結(jié)構(gòu)，它們是操作受限的線性表，即它們的操作是線性表操作的子集。因此也可以用線性表在某...
    MinoyJet閱讀 505評(píng)論 0贊 1
  • Android 自定義View的各種姿勢(shì)1 Activity的顯示之ViewRootImpl詳解 Activity...
    passiontim閱讀 178,978評(píng)論 25贊 709
  • 本篇將嘗使用canvas + wasm畫一個(gè)迷宮，生成算法主要用到連通集算法，使用wasm主要是為了提升運(yùn)行效率。...
    極樂(lè)君閱讀 3,852評(píng)論 0贊 9
  • 之前在微博 @算法時(shí)空 做了一次電臺(tái)，花了一個(gè)多小時(shí)談了一下Sedgewick和Wayne所著的暢銷書《算法》第4...
    算法時(shí)空閱讀 6,541評(píng)論 1贊 39
  • 我是一粒塵埃，靜靜的躺在鄂爾多斯高原煤海的臂彎，看著很多默默無(wú)聞的煤礦工人辛勤勞作，陪著他們守望在這片礦山，耕作未...
    塵飛揚(yáng)兮閱讀 398評(píng)論 1贊 12

友情鏈接更多精彩內(nèi)容