课程设计报告示例：迷宫求解

《课程设计报告示例：迷宫求解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、安徽建筑大学课程设计报告课程名称：数据结构与算法课程设计题目：迷宫求解院系：数理系专业：信息与计算数学班级：学号：姓名：时间：数据结构课程设计报告——迷宫求解目录一、需求分析21.问题描述：22.基本要求2二、概要设计31.数据结构32.程序模块33.算法设计5三、详细设计71.数据类型定义72.函数实现代码73.函数之间的调用关系7四、调试分析7五、用户手册8六、测试结果8七、参考文献9八、附录1015数据结构课程设计报告——迷宫求解迷宫求解题目：以一个m×n长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍，设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有

2、通路的结论。(1)以二维数组存储迷宫数据；(2)求得的通路以二元组(i,j)的形式输出，其中（i,j）指示迷宫中的一个坐标。一、需求分析1.问题描述：在迷宫中求出从入口到出口的路径。经分析，一个简单的求解方法是：从入口出发，沿某一方向进行探索，若能走通，则继续向前走；否则沿原路返回，换一方向再进行搜索，直到所有可能的通路都探索到为止。即所谓的回溯法。求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。

3、为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中应用“栈”也就是自然而然的事了。假设“当前位置”指的是“在搜索过程中某一时刻所在图中某个方块位置”，则求迷宫中一条路径的算法的基本思想是：若当前位置"可通"，则纳入"当前路径"，并继续朝“下一位置”探索，即切换“下一位置”为“当前位置”，如此重复直至到达出口；若当前位置“不可通”，则应顺着“来向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周四个方块均“不可通”，则应从“当前路径”上删除该通道块。所谓“下一位置”指的是“当前位置

4、”四周四个方向（东、南、西、北）上相邻的方块。2.基本要求（1）以二维数组maze.adr[m+1][n+1]表示迷宫，其中mg[0][j]和mg[m+1][j](0jn)及mg[i][0]和mg[i][n](0im)为添加的一圈障碍，数组中以元素值为0表示通路，1表示障碍，限定迷宫大小m,n10。（2）用户以文件的形式输入迷宫的数据：文件中第一行的数据为迷宫的行数m和列数n;从第2行至第m+1行（每行n个数）为迷宫值，同一行的两个数之间用空白字符相隔。（3）迷宫入口为（1，1），出口为（m,n）。（4）每次移动只能从一个无障碍的单元到周围8个方向上任意无障碍的单元，编制程序给出

5、一条通过迷宫的路径或报告一个“无法通过”的信息。（5）本程序只求出一条成功的通路。3．测试数据见下表，当入口为（1，1）时，出口为（8，8）用一个字符类型的二微数组表示迷宫，数组中的每个元素表示一个小方格，取值“0”（表示可以进出）或“1”（表示不可以进出）随机产生一个8*8的迷宫，其中使用迷宫障碍坐标如下：（1，3），（1，7），（2，3），（2，7），（3，5），（3，6），（4，3），（4，4），（5，4），（6，2），（6，6），（7，2），（7，3），（7，4），（7，6），（7，7），（8，1）。15数据结构课程设计报告——迷宫求解二、概要设计1.数据结构栈（stac

6、k）是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有特殊含义，称为栈顶（top）,相应的，表头端称为栈底（bottom）。不含元素的空表称为空栈。假设栈S=（a1,a2,…，an），则称a1为栈底元素，an为栈顶元素。栈的修改是按后进先出的原则进行的。因此，栈又称为后进先出（ListInFirstOut）的线性表。在迷宫问题中，假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。由此，“纳入路径”的操作即为“当前位置入栈”；“从当前路径上删除前一通道块”的操作即为“出栈”。基本操作的函数原型说明。2.程序模块栈的顺序存储表示#defineS

7、tackSize100//假定预分配的栈空间最多为100个元素 typedefcharDataType;//假定栈元素的数据类型为字符 typedefstruct{     DataTypedata[StackSize];     inttop;    }SeqStack;基本操作的算法描述（1）置栈空 voidInitStack（SeqStack*S）   {//将顺序栈置空      S->top=-1;   }（2）判栈空 intStackEmpty（SeqStack*S）