数据结构课程设计--迷宫问题

《数据结构课程设计--迷宫问题》由会员分享，可在线阅读，更多相关《数据结构课程设计--迷宫问题（20页珍藏版）》请在毕设资料网上搜索。

1、 数据结构数据结构 -课程设计报告课程设计报告 数据结构课程设计 1 一、一、 设计题目设计题目 迷宫问题 二、二、 需求分析需求分析 1.选题理由 迷宫求解是数据结构课程的一个经典问题，迷宫问题要求寻找一条从入口到出口的 路径。通常用的是“穷举求解”的方法。为了保证在任何位置上都能原路退回，显然需 要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求解迷宫通路的算 法中要应用“栈”的思想。对于栈的内容在整个学期的学习中我也有了一定的了解，所 以选择了迷宫这一经典问题作为本次课设的内容。 2.基本原理分析 迷宫问题通常是用“穷举求解”方法解决，即从入口出发，顺着某一个方向进行探 索，

2、若能走通，则继续往前走；否则沿着原路退回，换一个方向继续探索，直至出口位 置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没 有通路。栈是一个后进先出的结构，可以用来保存从入口到当前位置的路径。 以二维数组存储迷宫数据， 通常设定入口点的下标为 （1， 1） ， 出口点的下标为 （n,n） 。 为处理方便起见，在迷宫的四周加一圈障碍。对于迷宫任何一个位置，均约定东、南、 西、北四个方向可通。 3.功能要求 （ 1 ） 以 一 个 二 维 数 组 Mazem+2n+2 表 示 迷 宫 ， 其 中 ： Maze0j 和 Mazem+1j(0next=NULL; S.sta

3、cksize=0; return OK; /进栈 Status Push(SqStack p=(NodeType*)malloc(sizeof(NodeType); p-data=e; p-next=S.top; S.top=p; S.stacksize+; return OK; /判断是否为栈空 Status StackEmpty(SqStack S) if(S.top-next=NULL) return OK; return ERROR; 数据结构课程设计 11 /出栈 Status Pop(SqStack if(StackEmpty(S) return ERROR; p=S.top; e

4、=p-data; S.top=S.top-next; S.stacksize-; free(p); return OK; /销毁栈 Status DestroyStack(SqStack while(S.top!=NULL) p=S.top; S.top=S.top-next; free(p); /一个一个删除 if(S.top=NULL) return OK; else return ERROR; /曾走过但不是通路标记并返回 OK 数据结构课程设计 12 Status MarkPrint(MazeType /“表示曾走过但不通 return OK; /曾走过而且是通路标记并返回 OK St

5、atus FootPrint(MazeType /“*“表示可通 return OK; /选择下一步的方向 PosType NextPos(PosType 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; return cpos; 数据结构课程设计 13 /判断当前位置是否可通 Status Pass(MazeType else retur

6、n FALSE; /创建迷宫 /按照用户输入的二维数组（0 或 1） ，设置迷宫 maze 的初值，包括加上边缘一圈的 值 void InitMaze(MazeType maze.c=col; for(int i=0;icnum)m+;n=1; a2mn=datai; n+; i+; fclose(fp); InitMaze(maze, a2, rnum, cnum); printf(“n 迷宫建立完成！ ！n“); break; case m: printf(“n 请输入迷宫入口的坐标，以空格为间隔:-“); scanf(“%d %d“, printf(“n 请输入迷宫出口的坐标，以空格为间隔:-“); scanf(“%d %d“, 数据结构课程设计 19 MazePath(maze, start, end); break; case p: if(fo