迷宫 数据结构.doc

实验报告题目：设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。一、 需求分析1. 以二维数组mazeNN表示迷宫，数组中以元素值0表示通路，1表示障碍，限定迷宫大小N迷宫模块-栈模块三 详细设计1. 坐标位置类型typedef struct PosType /定义坐标int x; /当前横坐标int y; /当前纵坐标PosType;2.迷宫类型int Maze;/迷宫存放在一个数字型数组中int MazePath(int mazeNN,PosType start,PosType end,LinkStack &stack,int n1,int n2)/求解迷宫maze中，从入口Start到出口end的一条路径stack=NULL;SElemType e;PosType curpos;InitStack(stack);/初始化stackcurpos.x=start.x; /设定当前位置为入口位置curpos.y=start.y;int curstep=1; /探索第一步doif(Pass(curpos,maze,n1,n2)=1)/当前位置可通FootPrint(curpos,maze); /留下足迹e.ord=curstep;e.seat.x=curpos.x;e.seat.y=curpos.y;e.di=1;Push(stack,e); /加入路径，入栈if(curpos.x=end.x&curpos.y=end.y) /到达出口位置return 1;elseNextPos(curpos,1); /探索下一步curstep+;/ifelse /当前位置不能通过if(!StackEmpty(stack)Pop(stack,e);while(e.di=4&!StackEmpty(stack)MarkPrint(e.seat,maze);/留下不能通过的标记，并退回一步Pop(stack,e);/whileif(e.di4) /换下一个方向探索e.di+;Push(stack,e);NextPos(e.seat,e.di); /设当前位置是该新方向上的相邻块，1代表向右，2代表向下，3代表向左，4代表向上。 curpos.x=e.seat.x;curpos.y=e.seat.y;while(!StackEmpty(stack);return 0;void InitMaze(int MazeNN,int r,int c) /初始化迷宫 printf(请输入迷宫(以0表示可走,1表示有障碍)：n);/按照用户要求输入一二维数组来表示迷宫for(int i=0;ir;i+)for(int j=0;jnext=NULL;return 1;void DestroyStack(LinkStack &S)LinkStack q;if(S!=NULL)while(S-next!=NULL) /如果栈非空，则释放空间q=S-next;if (S-next-next!=NULL)S-next=S-next-next;elseS-next=NULL;free(q);free(S);S=NULL;void ClearStack(LinkStack &S)LinkStack q;if(S!=NULL)while(S-next!=NULL) /如果栈非空，则释放空间q=S-next;if (S-next-next!=NULL)S-next=S-next-next;elseS-next=NULL;free(q);int StackEmpty(LinkStack S)if (S!=NULL) /判断栈是否存在if (S-next=NULL)return 1;return 0;int StackLength(LinkStack S)int m=0;LinkStack q=S;if (S!=NULL) /判断栈是否存在if (q-next!=NULL)/判断栈是否为空while (q-next!=NULL)+m;q=q-next;return m;return 0; int GetTop(LinkStack S,SElemType &e)LinkStack q=S;if (S!=NULL) /判断栈是否存在if (q-next!=NULL)/判断栈是否为空while (q-next!=NULL)q=q-next;e=q-SItem;return 1;return 0; /如果不能得到数据元素，则返回0(false)int Push(LinkStack &S,SElemType e)LinkStack q=S;LinkStack m=(LinkStack)malloc(sizeof(SNode); /通过malloc函数分配空间if (S!=NULL)while (q-next!=NULL)q=q-next;m-SItem=e;m-next=NULL;q-next=m;return 0;int Pop(LinkStack &S,SElemType &e)LinkStack q=S;if (S!=NULL)if (q-next!=NULL) /若栈不是空的while (q-next-next!=NULL)q=q-next;e=q-next-SItem;q-next=NULL;return 1;return 0;int StackTraverse(LinkStack S)/依次输出从栈底到栈顶的每个元素if (S!=NULL)LinkStack q=S;if (q-next!=NULL) /若栈不是空的printf(n依次输出从栈底到栈顶的每个元素为：n);while (q-next!=NULL)q=q-next;printf(%d ,q-SItem);printf(n);return 1;return 0;3. 求解迷宫路径的代码int MazePath(int mazeNN,PosType start,PosType end,LinkStack &stack,int n1,int n2)/求解迷宫maze中，从入口Start到出口end的一条路径stack=NULL;SElemType e;PosType curpos;InitStack(stack);/初始化stackcurpos.x=start.x; /设定当前位置为入口位置curpos.y=start.y;int curstep=1; /探索第一步if(Pass(curpos,maze,n1,n2)!=1)/判断初始方块是否是障碍物return 0;elsedoif(Pass(curpos,maze,n1,n2)=1)/当前位置可通FootPrint(curpos,maze); /留下足迹e.ord=curstep;e.seat.x=curpos.x;e.seat.y=curpos.y;e.di=1;Push(stack,e); /加入路径，入栈if(curpos.x=end.x&curpos.y=end.y) /到达出口位置return 1;elseNextPos(curpos,1); /探索下一步curstep+;/ifelse /当前位置不能通过if(!StackEmpty(stack)Pop(stack,e);while(e.di=4&!StackEmpty(stack)MarkPrint(e.seat,maze);/留下不能通过的标记，并退回一步Pop(stack,e);/whileif(e.di4) /换下一个方向探索e.di+;Push(stack,e);NextPos(e.seat,e.di); /设当前位置是该新方向上的相邻块curpos.x=e.seat.x;curpos.y=e.seat.y;while(!StackEmpty(stack);return 0;4. 主函数和其他函数的代码void main()int m,n;int mazeNN=0;LinkStack S;PosType start,end;int cmd;for(int i;i+)printf(n-n);printf( 1.创建迷宫:n);printf( 2.退出 n);printf(-n);printf(请输入选择：n);scanf(%d,&cmd);switch(cmd)case 1:printf(请输入迷宫的行数和列数:n);scanf(%d%d,&m,&n);InitMaze(maze,m,n); /迷宫初始化printf(请输入起点坐标:n);scanf(%d%d,&start.x,&start.y);start.x-;start.y-;printf(请输入出口坐标:n);scanf(%d%d,&end.x,&end.y);end.x-;end.y-;printf(迷宫为n);PrintMaze(maze,m,n);/输出初始迷宫if(MazePath(maze,start,end,S,m,n)printf(走出迷宫的路径为:n);StackTraverse(S);elseprintf(此迷宫无通路！n);printf(此时路径在迷宫中(用2标记表示可通路径，用3表示死胡同)显示为：n);PrintMaze(maze,m,n);/输出改变状态的迷宫break;case 2:exit(0);break;default:exit(0);break;DestroyStack(S);int Pass(PosType seat,int mazeNN,int n1,int n2) /检查当前通道块是否可通 if(mazeseat.xseat.y=0&seat.x=0&seat.y=0)return 1;else return 0; int FootPrint(PosType curpos,int mazeNN) mazecurpos.xcurpos.y=2; return 1;void NextPos(PosType &curpos,int i) /转换至下一个位置 if(i=1) curpos.y+; else if(i=2) curpos.x+; else if(i=3) curpos.y-; else if(i=4) curpos.x-;int MarkPrint(PosType curpos,int mazeNN) /标记此处不能走 mazecurpos.xcurpos.y+; return 1;5. 函数的调用关系图反映了演示程序的层次结构二、 调试分析1. 此次作业有一个核心算法，就是求迷宫的路径，在调试过程中一开始没有及时更新当前位置导致死循环，后来在判断该方块是否在当前路径上出错，在调试起点位置为障碍物时出现了错误，因此还要再加入判断初始方块是否为障碍物才能进行下面的操作，另外就是一些语法小错误。2. StackTravers在调试过程中可以插入在MazeParh中，以察看求解迷宫过程走的路径是否正确。3. 本题中三个主要算法：InitMaze,MazePath和PrintMaze时间复杂度均