数据结构迷宫求解.doc

《数据结构迷宫求解.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实训报告实训题目：迷宫问题学院：计算机科学与信息学院专业：计算机科学与技术专业班级：学号：学生姓名：指导教师：2012年6月29日一、实训目的及要求数据结构是计算机课程的一门重要的基础课，它的教学要求大致有三个重要方面：其一就是让学生学会分析研究计算机加工的数据对象的特性，以便为数据选择适当的物理结构和逻辑结构；其二，根据结构，选择适当的算法，并初步掌握算法的时间分析和空间分析；其三，学习复杂的程序设计。本综合实训利用VisualStudio2008集成编程环境为实践工具，通过上机实践培养学生分析具体问题、解决实际问题的能力，训

2、练和培养学生的数据抽象能力和程序设计的能力。数据结构是一门实践性较强的课程，以养学生的数据抽象能力和程序设计的能力为目的。在实训时应注重培养学生的实际操作能力。本综合实训安排了20学时的实验课时，完成4次上机作业。具体要求如下：1.学习和理解每个实训题目的基本理论和方法；2.掌握每个实验的实现步骤和关键技术；3.准备好实验所需要的资源和文档；4.上机实现程序，得到通过调试的正确程序。5.根据每个实验的不同要求，完成实验报告的word文档。二、实训环境WindowsXPVisualStudio2010三、实训内容迷宫求解:(1)迷

3、宫的提供：A、可由运行过程中，用户自己输入迷宫B、在文件或者程序中存储多个迷宫结构，运行时随机抽取C、在文件或者程序中存储多个迷宫结构，运行时可以随机抽取。用户也可以选择添加迷宫，增加文件或者程序中的迷宫库。(2)设计算法完成迷宫问题的求解；图形显示迷宫的过程，并将最后结果输出。一旦发现没有出口，程序显示无出口四、算法描述及实训步骤本项目要实现两个主要功能：迷宫设计和求解附加一些其他功能搜索算法流程图如下所示：五、总结及心得体会这个课题主要体现了栈和队列的应用，要对队列有很好的理解，入队出队的应用，还有就是对节点的存储，这样才能

4、实现下一步六、实训结果七、源代码：#include"stdlib.h"#include"stdio.h"#defineN39#defineM39intX;intmaze[N+2][M+2];structpoint{introw,col,predecessor;}queue[512];inthead=0,tail=0;voidshoudong_maze(intm,intn){inti,j;printf("");printf("请按行输入迷宫，0表示通路，1表示障碍:");for(i=0;i

5、0;j

6、{printf("");for(j=0;j

7、

8、maze[i][j]==2)printf("□?");i

9、f(maze[i][j]==1)printf("■?");if(maze[i][j]==3)printf("☆?");}}}voidenqueue(structpointp){queue[tail]=p;tail++;}structpointdequeue(){head++;returnqueue[head-1];}intis_empty(){returnhead==tail;}voidvisit(introw,intcol,intmaze[41][41]){structpointvisit_point={row,col,hea

10、d-1};maze[row][col]=2;enqueue(visit_point);}intmgpath(intmaze[41][41],intm,intn){X=1;structpointp={0,0,-1};if(maze[p.row][p.col]==1