数据结构迷宫求解new

1、数据结构上机实验报告 实验二：栈和队列 学生姓名：蒋映喆 学生学号：201086250124 学生院系：城南学院 学生班级：计算机1001班 程序清单： #include#include#include#includetypedef int Status;#define OK 1#define ERROR 0#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef structint row;int line;PosType;typedef structint ord;PosType seat;int di;SelemType;ty

2、pedef structSelemType *base;SelemType *top;int stacksize;SqStack;Status InitStack (SqStack &S)S.base = (SelemType *)malloc(STACK_INIT_SIZE * sizeof(SelemType);if(!S.base)exit(-2);S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;Status Push(SqStack &S,SelemType e)if(S.top - S.base = S.stacksize

3、)S.base = (SelemType *)realloc(S.base,(S.stacksize + STACKINCREMENT)*sizeof(SelemType);if(!S.base)exit(-2);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 0;e = *-S.top;return OK;Status StackEmpty(SqStack S)

4、if(S.top = S.base)return OK;elsereturn ERROR;void InitMaze(int maze1111)srand(int)time(NULL);for(int i = 0;i10;i+)maze0i = 0;for(i = 1; i9; i+)mazei0 = 1;for(int j = 1;j9;j+)mazeij = rand()%2;mazei9 = 1;for(i = 0;i10;i+)maze9i = 1;void OutputmazeFirst(int maze1111)printf(nn);printf(所建迷宫为（#为外墙）：nn);f

5、or(int i = 0;i10;i+)printf(# );printf(n);for(i=1;i9;i+)printf(# );for(int j = 1;j9;j+)printf(%d ,mazeij);printf(# );printf(n);for(i = 0;iseat.rowp-seat.line = 2;p+;for(int i = 0;i10;i+)printf(# );printf(n);for(i=1;i9;i+)printf(# );for(int j = 1;j9;j+)if(mazeij = 2)printf(* );elseprintf( );printf(# )

6、;printf(n);for(i = 0;i10;i+)printf(# );printf(n);Status Pass( int maze1111,PosType CurPos) if (mazeCurPos.rowCurPos.line=0) return OK; elsereturn ERROR; void MarkFoot( int maze1111,PosType CurPos)mazeCurPos.rowCurPos.line=1;PosType NextPos(PosType CurPos, int Dir) PosType ReturnPos; switch (Dir) cas

7、e 1: ReturnPos.row=CurPos.row; ReturnPos.line=CurPos.line+1; break; case 2: ReturnPos.row=CurPos.row+1; ReturnPos.line=CurPos.line; break; case 3: ReturnPos.row=CurPos.row; ReturnPos.line=CurPos.line-1; break; case 4: ReturnPos.row=CurPos.row-1; ReturnPos.line=CurPos.line; break; return ReturnPos;St

8、atus MazePath(int maze1111,SqStack &S, PosType start, PosType end) / 若迷宫maze中从入口 start到出口 end的通道，则求得一条存放在栈中 / （从栈底到栈顶），并返回TRUE；否则返回FALSE PosType curpos; int curstep; SelemType e; InitStack(S); curpos = start; / 设定当前位置为入口位置 curstep = 1; / 探索第一步 do if (Pass(maze,curpos) / 当前位置可通过，即是未曾走到过的通道块 MarkFoot(

9、maze,curpos); / 留下足迹 e.di =1; e.ord = curstep; e.seat= curpos; Push(S,e); / 加入路径 if (curpos.row = end.row & curpos.line=end.line) return OK; / 到达终点（出口） curpos = NextPos(curpos, 1); / 下一位置是当前位置的东邻 curstep+; / 探索下一步 else / 当前位置不能通过 if (!StackEmpty(S) Pop(S,e); while (e.di=4 & !StackEmpty(S) MarkFoot(m

10、aze,e.seat); Pop(S,e); / 留下不能通过的标记，并退回一步 / while if (e.di4) e.di+; Push(S, e); / 换下一个方向探索 curpos = NextPos(e.seat, e.di); / 当前位置设为新方向的相邻块 while (!StackEmpty(S) ); return 0; int main()SqStack S;int maze1111;printf(创建一个正方形迷宫，大小为10 X 10：n);InitMaze(maze);OutputmazeFirst(maze);PosType start,end;printf(n请输入入口坐标(行，列)：);scanf(%d,&start.row);scanf(%d,&start.line);printf(n请输入出口坐标(行，