数据结构课程设计迷宫问题limengyu.doc

课 程 设 计 报 告 课程名称 数据结构课?程设计 课题名称 迷宫问题 专 业 计算机科学?与技术 班 级 计科4班 学 号 20130?26674? 姓 名 李梦宇 指导教师 　　 2012年? 6月 9日 一、设计内容与?设计要求 1．设计内容： 1）问题描述 以一个M*N的长方阵?表示迷宫，0和1分别?表示迷宫中?的通路和墙?壁。设计一个程?序，对任意设定?的迷宫，求出一条从?入口到出口?的通路，或得出米有?通路的结论?。 2）基本要求 a.实现一个以?链表作存储?结构的栈类?型，然后编写一?个求解迷宫?的非递归程?序。求得的通路?以三元组（i，j，d）的形式输出?，其中：（i，j）指示迷宫中?的一个坐标?，d表示走到?下一个坐标?的方向。 b.编写递归形?式的算法，求得迷宫中?所有可能的?通路。 3）测试数据 迷宫的测试?数据如下：左上角（1,1）为入口，右下角（8,9）为出口。 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 1 1 1 0 0 0 1 0 1 1 1 0 0 0 0 0 0 4）实现提示 计算机解迷?宫通常用的?是“穷举求解”方法，即从入口出?发，顺着某一个?方向进行探?索，若能走通，则继续往前?进；否则，沿着原路退?回，换一个方向?继续探索，直至出口位?置，求得一条通?路。假如所有可?能的通路都?探索到而未?能到达出口?，则设定的迷?宫没有通路?。 可以二维数?组存储迷宫?数据，通常设定入?口点的下标?为（1，1），出口点的下?标为（m，n）。为处理方便?起见，可在迷宫的?四周加一圈?障碍。对于迷宫中?任一位置，均可约定有?东、南、西、北四个方向?可通。 2．设计要求： 课程设计报?告规范 1)需求分析 a.程序的功能?。 b.输入输出的?要求。 2)概要设计 程序由哪些?模块组成以?及模块之间?的层次结构?、各模块的调?用关系；每个模块的?功能。 课题涉及的?数据结构和?数据库结构?；即要存储什?么数据，这些数据是?什么样的结?构，它们之间有?什么关系等?。 3)详细设计 a.采用C语言?定义相关的?数据类型。 b.写出各模块?的类C码算?法。 c.画出各函数?的调用关系?图、主要函数的?流程图。 4)调试分析以?及设计体会? a.测试数据：准备典型的?测试数据和?测试方案，包括正确的?输入及输出?结果和含有?错误的输入?及输出结果?。 b.程序调试中?遇到的问题?以及解决问?题的方法。 c.课程设计过?程经验教训?、心得体会。 5)使用说明 用户使用手?册：说明如何使?用你编写的?程序，详细列出每?一步的操作?步骤。 6)书写格式 见附带说明?。 7)附录 a.参考书目 b.源程序清单?（带注释） 目录 任务书………………………………………………………2 基本算法……………………………………………………7 需求分析……………………………………………………7 程序的功能?…………………………………………………7 输入输出的?要求……………………………………………7 程序算法分?析………………………………………………8 概要设计……………………………………………………8 设计中非递?归程序的模?块结构图…………………………8 程序的数据?结构和数据?库结构分析?………………………9 试探方向的?设计……………………………………………10 达某点，以避免发生?死循环……………………………11 详细设计……………………………………………………11 伪码设计……………………………………………………11 mgpat?h（）流程图…………………………………………12 调试分析……………………………………………………13 总结…………………………………………………………14 八丶 附录（源代码清单?）………………………………………17 一、基本算法 走迷宫的过?程可以模拟?为一个搜索?的过程：每到一处，总让它按东?、东南、南、西南、西、西北、北、东北8个方?向顺序试探?下一个位置?；如果某方向?可以通过，并且不曾到?达，则前进一步?，在新位置上?继续进行搜?索；如果8个方?向都走不通?或曾经到达?