文档介绍：NANCHANGUNIVERSITY课程设计报告课程名称:计算机技术综合课程设计题目:数据结构求迷宫路径学院:信息工程系:计算机专业:计算机科学与技术班级:计算机<3>班学号:022008139学生姓名:罗强时间:…………………………………………………………..………………………………………………………………………………..………………………………………………………………………………..…………………………………………………………..…………………………………………………………………………………………………………………………………………………………………..33..算法设计……………………………………………………………………………….…………………………………………………………..……………………………………………………………………….……………………………………………………………………….……………………………………………………………..………………………………………………………….………………………………………………………….………………………………………………………….…………………………………………………………………..9原程序文件清单数据结构求迷宫路径题目:以一个m×n长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍,设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。(1)以二维数组存储迷宫数据;(2)求得的通路以二元组(i,j)的形式输出,其中(i,j)指示迷宫中的一个坐标。:在迷宫中求出从入口到出口的路径。经分析,一个简单的求解方法是:从入口出发,沿某一方向进行探索,若能走通,则继续向前走;否则沿原路返回,换一方向再进行搜索,直到所有可能的通路都探索到为止。即所谓的回溯法。求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时,通常用的是“穷举求解”的方法,即从入口出发,顺某一方向向前探索,若能走通,则继续往前走;否则沿原路退回,换一个方向再继续探索,直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回,显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此,在求迷宫通路的算法中应用“栈”也就是自然而然的事了。假设“当前位置”指的是“在搜索过程中某一时刻所在图中某个方块位置”,则求迷宫中一条路径的算法的基本思想是:若当前位置"可通",则纳入"当前路径",并继续朝“下一位置”探索,即切换“下一位置”为“当前位置”,如此重复直至到达出口;若当前位置“不可通”,则应顺着“来向”退回到“前一通道块”,然后朝着除“来向”之外的其他方向继续探索;若该通道块的四周四个方块均“不可通”,则应从“当前路径”上删除该通道块。所谓“下一位置”指的是“当前位置”四周四个方向(东、南、西、北)上相邻的方块。(1)[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)本程序只求出一条成功的通路。,当入口为(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)。(stack)是限定仅在表尾进行插入或删除操作的线性表。因此,对栈来说,表尾端有特殊含义,称为栈顶(top),相应的,表头端称为栈底(bottom)。不含元素的空表称为空栈。假设栈S=(a1,a2,…,an),则称a1为栈底元素,an为栈顶元素。栈的修改