迷宫问题说明书

1、目目 录录摘摘 要要.1前前 言言.2正正 文文.31.采用类C语言定义相关的数据类型.32.各模块的伪码算法.33.函数的调用关系图.54.调试分析.55.测试结果.66.源程序（带注释）.9总总 结结.16参考文献参考文献.17致致 谢谢.18附件附件 部分部分源源程序代码程序代码.191摘摘 要要迷宫问题的求解是一个很好的在栈或者队列等方面的应用问题，本次设计是以栈去实现的。问题的求解主要是给定一个入口坐标和出口坐标时求出一条从入口到出口的路径，如果不存在或存在要做出相应的判断，存在时打印其路径，并做动态演示。 关键字：栈，栈的存储结构，出栈与入栈2前前 言言由于计算机解迷宫时，通常用的

2、是群举的方法，即从入口出发，顺某一方向搜索。若能走通，则继续往前走；否则沿原路退回，换一个方向再继续搜直至所有可能的通路都搜索完为止。为了保证在任何位置上都能沿原路返回，这就需要一个后进先出的结构来存储起位置，所以用到了栈的概念。在问题的求解过程中，用到了对栈的定义、栈的初始化、栈的空间的申情、栈的销毁等有关栈的知识。 通过这次课程设计可让我们更深一步的了解栈的概念。在解决问题的过程中初步懂的如何去选择合适的方法去处理问题，提高解决问题的效率。3正正 文文1.1. 采用类采用类 c c 语言定义相关的数据类型语言定义相关的数据类型(1) void enqueue(struct point p)

3、 queuetail=p; tail+; (2) struct point dequeue(void) head+; return queuehead-1; 2.2. 各模块的伪码算法各模块的伪码算法(1)void zidong_maze(int m,int n) /自动生成迷宫问题 system(cls); int i,j;4 printf(自动生成迷宫n); printf(loadingn); system (pause); /暂停 for(i=0;im;i+) for(j=0;jn;j+) mazeij=rand()%2; (2)void print_maze(int m,int n)

4、int i,j; for(i=0;in;i+) /*迷宫外围设置封闭*/ mazei0=1; mazein-1=1; maze0i=1; mazen-1i=1; for(i=0;im;i+) printf(n); for(j=0;j50|n50) 6 printf(n); printf(:n); scanf(%d,&m); printf(:n); scanf(%d,&n);b、算法的时间复杂度和空间复杂度空间复杂度：4.27kb；时间复杂度：O(n)；5.5. 测试结果测试结果a欢迎界面：输入行，列：7选择界面：8运行结果：96.6. 源程序（带注释）源程序（带注释）#incl

5、udeiostream#includestdlib.husing namespace std;#define N 50#define M 50int mazeN+2M+2;struct point int row, col, predecessor; queue512;int head=0, tail=0;void zidong_maze(int m,int n) /自动生成迷宫问题 system(cls); int i,j; printf(自动生成迷宫n); printf(loadingn); system (pause); /暂停 for(i=0;im;i+) for(j=0;jn;j+)

6、 mazeij=rand()%2; /0、1 随机数产生，生成迷宫 void print_maze(int m,int n) int i,j; for(i=0;in;i+) /*迷宫外围设置封闭*/ mazei0=1; mazein-1=1; maze0i=1;10 mazen-1i=1; for(i=0;im;i+) printf(n); for(j=0;jn;j+) printf(%d,mazeij);void build_maze(int m,int n) system(cls); printf(生成结果n); printf(迷宫入口n); printf(); print_maze(m,

7、n); printf(迷宫出口n);void result_maze(int m,int n) /迷宫生成图形 int i,j; printf(迷宫生成图形如下所示: n); for(i=0;im;i+) printf(n); for(j=0;jn;j+) if(mazeij=0) printf( ); if(mazeij=1) printf(); 11void enqueue(struct point p) queuetail=p; tail+;struct point dequeue(void) head+; return queuehead-1; int is_empty(void) r

8、eturn head=tail; void visit(int row,int col,int maze5252) struct point visit_point=row,col,head-1; mazerowcol=2; enqueue(visit_point); int mgpath(int maze5252,int m,int n) struct point p=0,0,-1; if(mazep.rowp.col=1) printf(此迷宫无解nn);return 0;mazep.rowp.col=2;enqueue(p);while (!is_empty() p=dequeue();

9、 if (p.row=m-1&p.col=n-1) /goal break;12 if(p.col+1n&mazep.rowp.col+1=0) /right visit(p.row,p.col+1,maze); if(p.row+1=0&mazep.rowp.col-1=0) /left visit(p.row,p.col-1,maze); if(p.row-1=0&mazep.row-1p.col=0) /up visit(p.row-1,p.col,maze); print_maze(m,n); printf(n-n);if(p.row=m-1&p

10、.col=n-1) printf(迷宫路径为:n); printf(%d,%d)n,p.row, p.col); mazep.rowp.col=3; while(p.predecessor !=-1) p=queuep.predecessor; printf(%d,%d)n,p.row,p.col); mazep.rowp.col=3; else printf(此迷宫无解!n); return 0;void menu() int m,n; /控制迷宫的行数和列数 int cycle; /循环控制 int choice; /选择13 printf(n);printf(*欢迎进入用户界面*n);

11、printf(n); while(cycle!=-1) printf(请输入行数：n); scanf(%d,&m); printf(请输入列数:n); scanf(%d,&n); while(m50|n50) printf(n); printf(:n); scanf(%d,&m); printf(:n); scanf(%d,&n); if(m=50&n50|n50) printf(行列数超出预设范围，请重新输入n); printf(请输入行数n); scanf(%d,&m); printf(请输入列数n); scanf(%d,&n); m

12、gpath(maze,m,n); /寻找迷宫路由 result_maze(m,n); /打印出迷宫图形及路径 printf(n 是否重新输入迷宫，如果不继续，按-1 退出n); scanf(%d,&cycle);void main()15 system(color f5); /系统函数 menu();16总总 结结在这三周的数据结构课程设计中,我的题目是:迷宫问题,这三周课程设计中,通过该题目的设计过程,我加深了对栈的逻辑结构,存储结构及入栈出栈过程的理解,对栈的基本运算的实现有所掌握,对课本中所学的各种数据结构进一步理解和掌握,学会了如何把学到的知识用于解决实际问题,锻炼了自己动手的

13、能力。一个人要完成所有的工作是非常困难和耗时的。在以后的学习中我会更加注意各个方面的能力的协调发展。在课程设计时遇到了很多的问题，在老师的帮助，和对各种资料的查阅中，将问题解决，培养了我自主动手，独立研究的能力，为今后在学习工作中能更好的发展打下了坚实的基础。三周的课程设计很短暂，但其间的内容是很充实的，在其中我学习到了很多平时书本中无法学到的东西，积累了经验，锻炼了自己分析问题，解决问题的能力，并学会了如何将所学的各课知识融会，组织，来配合学习，三周中我收益很大，学到很多。17参考文献参考文献1 严蔚敏，吴伟民. 数据结构（C 语言版） .清华大学出版社.2 严蔚敏，吴伟民.数据结构题集（C

14、 语言版） .清华大学出版社.3 DATA STRUCTURE WITH C+.William Ford，William Tcpp.清华大学出版社（影印版）.4 谭浩强.C 语言程序设计.清华大学出版社.18致致 谢谢首先感谢我的指导老师王旭阳老师，她在我的课程设计过程中提出了指导性的方案和架构，并指引我阅读相关的资料和书籍，使我在不熟悉的领域中仍能迅速掌握新的技术。感谢我的数据结构老师王旭阳老师和张永老师以及 C 语言老师王连相老师在以往的基础课学习中为我打下良好的基础，这是我这次课程设计能够顺利完成的前提。我的同学在设计完成后对程序的测试，没有他们，也许就难以发现一些潜在的错误，在此一并表

15、示感谢。19附件附件 部分源程序代码部分源程序代码#includeiostream#includestdlib.husing namespace std;#define N 50#define M 50int mazeN+2M+2;struct point int row, col, predecessor; queue512;int head=0, tail=0;void zidong_maze(int m,int n) /自动生成迷宫问题 system(cls); int i,j; printf(自动生成迷宫n); printf(loadingn); system (pause); /暂停

16、 for(i=0;im;i+) for(j=0;jn;j+) mazeij=rand()%2; /0、1 随机数产生，生成迷宫 void print_maze(int m,int n) int i,j; for(i=0;in;i+) /*迷宫外围设置封闭*/ mazei0=1; mazein-1=1; maze0i=1;20 mazen-1i=1; for(i=0;im;i+) printf(n); for(j=0;jn;j+) printf(%d,mazeij);void result_maze(int m,int n) /迷宫生成图形 int i,j; printf(迷宫生成图形如下所示:

17、 n);void enqueue(struct point p) queuetail=p; tail+;struct point dequeue(void) head+; return queuehead-1; int is_empty(void) return head=tail; void visit(int row,int col,int maze5252) struct point visit_point=row,col,head-1; mazerowcol=2; enqueue(visit_point); int mgpath(int maze5252,int m,int n) st

18、ruct point p=0,0,-1;21 if(mazep.rowp.col=1) printf(此迷宫无解nn);return 0;mazep.rowp.col=2;enqueue(p);while (!is_empty() p=dequeue(); if (p.row=m-1&p.col=n-1) /goal break; if(p.col+1n&mazep.rowp.col+1=0) /right visit(p.row,p.col+1,maze); if(p.row+1=0&mazep.rowp.col-1=0) /left visit(p.row,p.col-1,maze); if(p.row-1=0&mazep.row-1p.col=0) /up visit(p.row-1,p.col,maze); print