實(shí)驗(yàn)二 棧的應(yīng)用迷宮求解

1、一、實(shí)驗(yàn)?zāi)康?. 掌握棧的順序存儲結(jié)構(gòu)的存儲特點(diǎn)與操作特點(diǎn)。2. 掌握棧的存儲表示與基本操作的實(shí)現(xiàn)方法。3. 熟悉棧的基本應(yīng)用。4. 了解抽象數(shù)據(jù)類型的定義、表示與實(shí)現(xiàn)的含義。二、實(shí)驗(yàn)內(nèi)容編寫程序，進(jìn)行調(diào)試，寫出調(diào)試正確的源代碼，給出測試結(jié)果。在棧存儲結(jié)構(gòu)下，完成如下操作：迷宮求解（1）源代碼：1.h#define true 1#define false 0#define ok 1#define error 0#define infeasible -1#define overflow -2#define STACK_INIT_SIZE 30#define STACKINCREMENT 10ty

2、pedef int status;typedef structint i; int j;postype;typedef structint ord; postype seat; int di;selemtype;typedef structselemtype * base;selemtype *top;int stacksize;sqstack;sqstack s;typedef int mazetype55;mazetype maze;status initstack(sqstack &s);status push(sqstack &s,selemtype e); statu

3、s pop(sqstack &s,selemtype &e); status stackempty(sqstack s);status pass(postype curpos);postype nextpos (postype curpos,int di); status footprint(postype curpos); status markprint(postype curpos);#include<stdio.h>#include<stdlib.h>#include"1.h"status initstack(sqstack

4、&s)status push(sqstack &s,selemtype e)if(s.top-s.base>=s.stacksize) s.base=(selemtype 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;*)realloc(s.base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(sel

5、emtype);status pop(sqstack &s,selemtype &e)if(s.top=s.base) return error; s.top-; e=*s.top; return ok; if(!s.base) exit(overflow); s.top=s.base+s.stacksize; s.stacksize+=STACKINCREMENT; *s.top=e; s.top+; return ok;status stackempty(sqstack s)if(s.top=s.base) return true;else return false;sta

6、tus pass(postype curpos)if(curpos.i<1|curpos.i>10)|(curpos.j<1|curpos.j>10) return false;if(mazecurpos.icurpos.j=0) return true;else return false;postype nextpos (postype curpos,int di)status mazepath (mazetype maze,postype start,postype end) switch(di) return curpos; case 1:curpos.j+;br

7、eak; case 2:curpos.i+;break; case 3:curpos.j-;break; case 4:curpos.i-;break;initstack(s); postype curpos=start;/設(shè)當(dāng)前位置為入口位置 selemtype e;int curstep=1;/探索第一步do if(pass(curpos)/當(dāng)前位置可以通過，既是未曾走過的通道塊 else /當(dāng)前位置不能通過 if(!stackempty(s) pop(s,e); while(e.di=4&&!stackempty(s) markprint(e.seat); footpri

8、nt(curpos);/留下足跡 /e=(curstep,curpos,1); e.ord=curstep; e.seat=curpos; e.di=1; push(s,e);/加入路徑 /if(curpos=end) if(curpos.i=end.i)&&(curpos.j=end.j) return true;/到達(dá)終點(diǎn) curpos=nextpos(curpos,1);/下一位置是當(dāng)前位置的東鄰 curstep+;/探索下一步 pop(s,e);/留下不能通過的標(biāo)記，并退回一步 if(e.di<4) e.di+; push(s,e);/換下一個(gè)方向探索 curpo

9、s=nextpos(e.seat,e.di);/設(shè)定當(dāng)前位置是新方向上的相鄰塊status footprint(postype curpos)status markprint(postype curpos)void main() int i,j;postype start; postype end; start.i=1; mazecurpos.icurpos.j=3; return ok; mazecurpos.icurpos.j=2; return ok; while(!stackempty(s); return false;start.j=1; end.i=3; end.j=3; printf("請輸入迷宮內(nèi)容：n"); for(i=0;i<5;i+) for(j=0;j<5;j+) scanf("%d",&mazeij); if( mazepath(maze,start,end) for(i=0;i<5;