return ERROR; if (maze->a[curpos.y][curpos.x]==' ') return OK; else return ERROR; }

int FootPrint(MazeType *maze,PosType curpos) //留下足迹 { maze->a[curpos.y][curpos.x]='*'; return OK; }

int MarkPrint(MazeType *maze,PosType curpos) //留下不能通过的标记 { maze->a[curpos.y][curpos.x]='@'; return OK; }

PosType NextPos(PosType curpos,int di) //返回当前位置的下一位置 { PosType pos=curpos; switch(di) { case 1: //右东 pos.x++; break;

case 2: //下南 pos.y++; break; case 3: //左西 pos.x--; break;

case 4: //上北 pos.y--; break; } return pos; }

//若迷宫有解，则求得一条存放在栈中（从栈底到栈顶），并返回OK，否则返回ERROR int MazePath(MazeType *maze,PosType start,PosType end) { PosType curpos; SqStack *S=(SqStack *)malloc(sizeof(SqStack)); InitStack(S); SElemType *e; e=(SElemType *)malloc(sizeof(SElemType));

curpos=start; //设定当前位置为入口位置 int curstep = 1; //探索第一步 do { if(Pass(maze,curpos)) //当前位置可通过 { FootPrint(maze,curpos); e->ord=curstep; e->seat=curpos; e->di=1; Push(S,e); if(curpos.x==end.x&&curpos.y==end.y) return (OK); curpos=NextPos(curpos,1); curstep++; } else { if(!StackEmpty(S)) { Pop(S,e);

while(e->di==4&&!StackEmpty(S)) //栈不空但栈顶位置四周均不通 { MarkPrint(maze,e->seat); Pop(S,e); }

if(e->di<4) //栈不空且栈顶位置四周有其他位置未探索 { e->di++; Push(S,e); curpos=e->seat; curpos=NextPos(curpos,e->di); } } } } while(!StackEmpty(S)); return ERROR; }

void PrintMaze(MazeType *maze) //打印迷宫 { int i,j,k,n; int c[999],d[999]; for(i=0,k=0;i<=maze->hang;i++) {

for(j=0;j<=maze->lie;j++) { printf(\ if(maze->a[i][j]=='*') { c[k]=i; d[k]=j; k++; } } printf(\ } n=k; for(k=0;k

int main() { int zmg; char ch; printf(\ 数据结构课程设计--迷宫问题求解 printf(\ |----------------------------------------|\\n\ printf(\ | printf(\ | printf(\ | printf(\ | printf(\ | XXXX XXXXXXXXXXXXXX printf(\ | XXXXXXX printf(\ |----------------------------------------|\\n\ getchar(); do { system(\ fflush(stdin); MazeType *maze=(MazeType *)malloc(sizeof(MazeType)); printf(\请输入迷宫的列数（不含外墙时）:\ scanf(\ printf(\请输入迷宫的行数（不含外墙时）:\ scanf(\ generatemaze(maze); printf(\随机创建迷宫\\n\

\\n\\n\ |\\n\ |\\n\ |\\n\ |\\n\ |\\n\ //设置迷宫的长宽不含外墙 |\\n\ }

PrintMaze(maze); getchar(); getchar();

PosType start,end; start.x=1;start.y=1;

end.x=maze->lie-1;end.y=maze->hang-1; zmg=MazePath(maze,start,end); if(zmg) {

printf(\此迷宫通路为\\n\ PrintMaze(maze); } else

printf(\此迷宫无通路\\n\ //getchar(); printf(\再次尝试？（Y/N）?\ scanf(\}

while(ch=='Y'||ch=='y'); return 0;

四、 调试分析

1. 本程序界面设计合理，以空格为通路，感叹号！为障碍，笑脸为起始点，*为行走路线，心形为出口

设计精巧，便于用户使用。

2. 获得用户输入时一步一步的提示用户输入，具有很强的实用性。

3. 本实习作业采用数据抽象的程序设计方法，使得设计思路清晰，实现时调试顺利。

五、 用户守则

1.本程序的运行环境为windows操作系统，可执行文件为：a.exe 2.为了界面更加友好特将背景颜色设计为黑色，字体为白色。 3.进入演示程序后即显示文本形式的用户界面：

按回车键，即可进行迷宫求解

六、 测试结果

七、 附录（源代码）

#include #include #include #include #include