數(shù)據(jù)結(jié)構(gòu)迷宮問題.doc

/base.h/- 公用的常量和類型 -#include#include #include #include /函數(shù)結(jié)果狀態(tài)代碼#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status; /函數(shù)的返回值typedef int DirectiveType; /下一個通道方向#define RANGE 100 /迷宮大小/2。/stack.h#define STACK_INIT_SIZE 100#define STACKINCREMENT 10/- 棧的順序存儲實(shí)現(xiàn) -typedef struct. int row; int col;PosType;typedef struct. int step; /當(dāng)前位置在路徑上的序號 PosType seat; /當(dāng)前的坐標(biāo)位置 DirectiveType di; /往下一個坐標(biāo)位置的方向SElemType;typedef struct. SElemType *base; SElemType *top; int stacksize;SqStack;/- 棧的基本操作的算法實(shí)現(xiàn) -Status InitStack(SqStack &s). s.base = (SElemType * ) malloc(STACK_INIT_SIZE * sizeof(SElemType); if(!s.base) exit(OVERFLOW); s.top=s.base; s.stacksize=STACK_INIT_SIZE; return OK;Status GetTop(SqStack s, SElemType &e ). if( s.top = s.base) return ERROR; e = *(s.top-1); return OK;Status Push(SqStack &s, SElemType e). if(s.top-s.base = s.stacksize). /棧滿，追加存儲空間 s.base = (SElemType *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(SElemType); if(!s.base) exit(OVERFLOW);s.top = s.base + s.stacksize; s.stacksize += STACKINCREMENT; *s.top+ = e; return OK;Status Pop(SqStack &s, SElemType &e). if(s.top=s.base)return ERROR; e = * -s.top; return OK;int StackEmpty(SqStack s). return s.base = s.top;Status ClearStack(SqStack &s). s.top = s.base; return OK;/3。/maze.h/- 迷宮程序 -/*/* 迷宮問題算法: 從入口出發(fā),順著某一個方向進(jìn)行探索,若能走通,則繼續(xù)前進(jìn);否則沿著原路退回,換一個方向繼續(xù)探索,直至出口位置,求得一條通路,假如所有可能的通路都探索到而未能達(dá)到出口,則所設(shè)定的迷宮沒有通路. 說明:可通: 未增走到過的通道快. */#define ROW 9 /迷宮的行數(shù)#define COL 8 /迷宮的列數(shù)typedef struct. int m,n; int arrRANGERANGE;MazeType; /迷宮類型Status InitMaze(MazeType &maze, int aCOL, int row, int col). /按照用戶輸入的row行和col列的二維數(shù)組(0/1) /設(shè)置迷宮maze的初值,包括加上邊緣一圈的值 for(int i=1;i=row;i+). for(int j=1;j=col;j+). maze.arrij = ai-1j-1; /加上圍墻 for(int j=0;j=col+1;j+). maze.arr0j = maze.arrrow+1j=1; for(i=0;i=row+1;i+). maze.arri0 = maze.arricol+1=1; maze.m = row, maze.n = col; return OK;Status Pass(MazeType maze,PosType curpos). /判斷當(dāng)前節(jié)點(diǎn)是否通過 return maze.arrcurpos.rowcurpos.col = 0;Status FootPrint(MazeType &maze,PosType curpos). /留下足跡 maze.arrcurpos.rowcurpos.col=*; return OK;Status MarkPrint(MazeType &maze,PosType curpos). /留下不能通過的標(biāo)記 maze.arrcurpos.rowcurpos.col=; return OK;SElemType CreateSElem(int step, PosType pos, int di). SElemType e; e.step = step; e.seat = pos; e.di = di; return e;PosType NextPos(PosType curpos, DirectiveType di). /返回當(dāng)前節(jié)點(diǎn)的下一節(jié)點(diǎn) PosType pos = curpos; switch(di) . case 1: /東 pos.col+; break; case 2: /南 pos.row+; break; case 3: /西 pos.col-; break; case 4: /北 pos.row-; break; return pos;Status PosEquare(PosType pos1, PosType pos2). /判斷兩節(jié)點(diǎn)是否相等 return pos1.row=pos2.row & pos1.col=pos2.col ;void PrintMaze(MazeType maze,int row,int col). /打印迷宮信息 for(int i=1;i=row;i+). for(int j=1;j=col;j+). switch(maze.arrij) . case 0: printf( ); break; case *: printf(* ); break; case : printf( ); break; case 1: printf(# ); break; printf( ); Status MazePath(MazeType &maze,PosType start, PosType end). /求解迷宮maze中,從入口start到出口end的一條路徑 /若存在,返回TRUE,否則返回FALSE SqStack s;SElemType e; InitStack(s); PosType curpos = start; int curstep = 1; /探索第一部 do. if( Pass(maze,curpos) ). /如果當(dāng)前位置可以通過,即是未曾走到的通道塊 FootPrint(maze,curpos); /留下足跡 e = CreateSElem(curstep,curpos,1); /創(chuàng)建元素 Push(s,e); if( PosEquare(curpos,end) ) return TRUE; curpos =NextPos(curpos,1); /獲得下一節(jié)點(diǎn):當(dāng)前位置的東鄰 curstep+; /探索下一步 else. /當(dāng)前位置不能通過 if(!StackEmpty(s). Pop(s,e); while(e.di=4 & !StackEmpty(s) ). MarkPrint(maze,e.seat); Pop(s,e);curstep-; /留下不能通過的標(biāo)記,并退回一步 if(e.di4). e.di+; Push(s,e); /換一個方向探索 curpos = NextPos(e.seat,e.di); /求下一個節(jié)點(diǎn) while(!StackEmpty(s); return FALSE;/test.cpp#include base.h#include stack.h#include maze.h/*/* 測試 */void main(). int aROWCOL; printf(enter the mazes data: ); for(int i=0;iROW;i+) . for(int j=0; jCOL;j+) . scanf(%d,&aij); PosType