《数据结构》上机实验报告—利用栈实现迷宫求解

.福州大学数计学院数据结构上机实验报告专业和班级：信息计算科学与应用数学6班学号姓名成绩实验名称栈、队列实验内容利用栈实现迷宫求解实验目的和要求【实验目的】应用栈结构来解决应用问题，加深对栈结构特点的认识和应用。【基本要求】首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如:对于下列数据的迷宫，输出的一条通路为;(1,1,1),(1,2,2),(2,2,2),(3,2,3),(3,1,2),.问题描述和主要步骤【问题描述】以一个mn的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论【程序设计】#include #include #include #define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2#define INIT_SIZE 100 /存储空间初始分配量#define INCREMENT 10 /存储空间分配增量#define MAXLEN 10/迷宫包括外墙最大行列数目typedef int Status;typedef struct /迷宫中r行c列的位置 int r; int c;PostType;typedef struct int ord; /当前位置在路径上的序号 PostType seat;/当前坐标 int di; /往下一坐标的方向SElemType; /栈元素类型typedef struct SElemType* base;/栈基址,构造前销毁后为空 SElemType* top;/栈顶 int stackSize; /栈容量Stack; /栈类型Status InitStack(Stack &S) /构造空栈s S.base=(SElemType*)malloc(INIT_SIZE *sizeof(SElemType); if(!S.base) exit(OVERFLOW);/存储分配失败 S.top=S.base; S.stackSize=INIT_SIZE; return OK;/InitStackStatus StackEmpty(Stack S) /若s为空返回TRUE,否则返回FALSE if(S.top=S.base) return TRUE; return FALSE;/StackEmptyStatus Push(Stack &S,SElemType e)/插入元素e为新的栈顶元素 if(S.top-S.base =S.stackSize)/栈满，加空间 S.base=(SElemType *)realloc(S.base,(S.stackSize+INCREMENT)*sizeof(SElemType); if(!S.base) exit(OVERFLOW); /存储分配失败 S.top=S.base+S.stackSize; S.stackSize+=INCREMENT; *S.top+=e; return OK;/pushStatus Pop(Stack &S,SElemType &e)/若栈不空删除栈/顶元素用e返回并返回OK，否则返回ERROR if(S.top=S.base) return ERROR; e=*-S.top; return OK;/PopStatus DestroyStack(Stack &S)/销毁栈S, free(S.base); S.top=S.base; return OK;/DestroyStacktypedef struct int r; int c; int adrMAXLENMAXLEN;/可取0,1,2,3MazeType; /迷宫类型Status InitMaze(MazeType &maze)/初始化迷宫若成功返回TRUE,否则返回FALSE int i,j; maze.r=9,maze.c=8; /迷宫行和列数 for(i=0;i=maze.c+1;i+)/迷宫行外墙 maze.adr0i=1; maze.adrmaze.r+1i=1; /for for(i=0;i=maze.r+1;i+)/迷宫列外墙 maze.adri0=1; maze.adrimaze.c+1=1; for(i=1;i=maze.r;i+) for(j=1;j=maze.c;j+) maze.adrij=0;/初始化迷宫maze.adr17=maze.adr13=maze.adr23=1;maze.adr27=maze.adr35=maze.adr36=maze.adr38=1;maze.adr42=maze.adr43=maze.adr44=maze.adr47=1;maze.adr54=maze.adr62=maze.adr66=maze.adr68=1;maze.adr72=maze.adr73=maze.adr74=maze.adr75=maze.adr78=1;maze.adr81=maze.adr82=maze.adr86=maze.adr88=maze.adr91=maze.adr92=1; return OK;/InitMaze Status Pass(MazeType maze,PostType curpos)/当前位置可通则返回TURE,否则返回FALSE if(maze.adrcurpos.rcurpos.c=0)/可通 return TRUE; else return FALSE;/PassStatus FootPrint(MazeType &maze,PostType curpos)/若走过并且可通返回TRUE,否则返回FALSE在返回之前销毁栈S maze.adrcurpos.rcurpos.c=2;/2表示可通 return OK;/FootPrintPostType NextPos(PostType &curpos,int i)/指示并返回下一位置的坐标 PostType cpos; cpos=curpos; switch(i) /1.2.3.4分别表示东,南,西,北方向 case 1 : cpos.c+=1; break; case 2 : cpos.r+=1; break; case 3 : cpos.c-=1; break; case 4 : cpos.r-=1; break; default: exit(ERROR); return cpos;/NextposStatus MarkPrint(MazeType &maze,PostType curpos)/曾走过但不是通路标记并返回OK maze.adrcurpos.rcurpos.c=3;/3表示曾走过但不通 return OK;/MarkPrintStatus MazePath(MazeType &maze,PostType start,PostType end,Stack &Path) /若迷宫maze存在从入口start到end的通道则求得一条存放在栈中并返回TRUE,否则返回FALSE Stack S; PostType curpos; int curstep;/当前序号 SElemType e; InitStack(S); InitStack(Path); curpos=start; /设置当前位置为入口位置 curstep=1; /探索第一步 do if(Pass(maze,curpos)/当前位置可以通过,即是未曾走到过的通道 FootPrint(maze,curpos);/留下足迹 e.ord=curstep; e.seat=curpos; e.di=1; Push(S,e); /加入路径 if(curpos.r=end.r& curpos.c=end.c) do Pop(S,e); Push(Path,e); while(!StackEmpty(S);return TRUE; /到达出口 else curpos=NextPos(curpos,1);/下一位置是当前位置的东邻 curstep+; /探索下一步 /else /if else /当前位置不通 if(!StackEmpty(S) Pop(S,e); while(e.di=4& !StackEmpty(S) MarkPrint(maze,e.seat); Pop(S,e); /留下不能通过的标记,并退一步 /while if(e.di 4) e.di+;/换下一个方向探索 Push(S,e); curpos=NextPos(e.seat,e.di);/设定当前位置是该新方向上的相邻 /if /if /else while(!StackEmpty(S); if(!DestroyStack(S)/销毁失败 exit(OVERFLOW); else return FALSE;/MazePathvoid PrintMaze(MazeType &maze)/将标记路径信息的迷宫输出到终端(包括外墙) int i,j; printf(n显示路径(2是路)nn); printf( ); for(i=1;i=maze.c;i+)/打印列数名 printf(%4d,i); printf(nn); for(i=1;i=maze.r;i+) printf(%2d,i);/打印行名 for(j=1;jmaze.r | start.cmaze.c) printf(n超过了数组的大小n); continue; while(start.rmaze.r | start.cmaze.c); do /输入迷宫出口坐标 printf(n输入迷宫出口坐标:);/(9,8) scanf(%d,%d,&end.r,&end.c); if(end.rmaze.r | end.cmaze.c) printf(n超过了数组的大小n); continue; while(end.rmaze.r | end.cmaze.c); if(!MazePath(maze,start,end,Path)/迷宫求解 printf(n无路可走!n); else PrintMaze(maze);/打印路径 doPop(Path,e);printf(-(%d,%d,%d)n,e.seat.r,e.seat.c,e.di);while(!StackEmpty(Path); printf(n继续?(y/n): ); scanf(%s,&cmd); w