数据结构 迷宫问题(栈、C).doc

合肥学院 计算机科学与技术系 课程设计报告 2012 ～2013 学年第二学期 课 程 数据结构与算法 课程设计名称 迷宫问题（栈） 学 生 姓 名 陈强 学 号 1104014026 指 导 教 师 李 红 专 业 班 级 计算机科学与技术11级 2013年3 月 题目：迷宫问题（栈）：以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。要求：首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。 问题分析和任务定义 此程序可以用二维数组存储迷宫数据，设定入口点的下标为（1，1），出口点的下标为（m,n）。为处理方便起见，在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通，并默认以东、南、西、北的顺序进行有哪些信誉好的足球投注网站路线。将走过的路线放入链栈中，当走出迷宫时，栈中及走出迷宫的路线；当走不出时，栈为空。 实现本程序需要解决以下几个问题： 如何通过二维数组建立并存储迷宫。 如何进行路径有哪些信誉好的足球投注网站。 按一个方向有哪些信誉好的足球投注网站不到出路时怎么办？ 将符合条件的路线存储。 有哪些信誉好的足球投注网站到出路时按顺序输出路线。 首先，可以用二维数组存储迷宫，0和1分别表示迷宫中的通路和障碍,为处理方便起见，建立迷宫时在迷宫四周加一圈障碍。例如一个5*5的迷宫用二维数组可表示为： int maze[7][7]= {1,1,1,1,1,1,1, 1,0,0,0,0,0,1, 1,1,1,1,1,0,1, 1,0,0,0,0,0,1, 1,0,1,1,1,1,1, 1,0,0,0,0,0,1, 1,1,1,1,1,1,1}; 路径有哪些信誉好的足球投注网站时，需要知道出口和入口的坐标，本程序默认为（1,1）、（m，n）。定义一个移动坐标(xc,yc），用以记录有哪些信誉好的足球投注网站路线时当前位置的坐标。有哪些信誉好的足球投注网站时默认按照东、南、西、北的优先顺序进行查找，其中，向东有哪些信誉好的足球投注网站用“1”表示，向南、向西、向北分别用“2”、“3”、“4”表示，“0”表示方向未知。当向东无路时，再向西查找……当某位置为通路时（maze[i][j]==0），则将这一步的信息放入栈中。同时，将此步设置为障碍，防止下一步有哪些信誉好的足球投注网站时出现“回头”的现象。若为障碍时，此时，将栈中元素出去，即沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。将栈中的元素输出，即寻找到的出迷宫的路线。假如所有可能的通路都探索到而未能到达出口，则所设的迷宫没有通路。如上面的例子中，最后输出的路线为：（1，1,1）、（1,2,1）、（1,3,1）、（1,4,1）、（1,5,2）、（2,5,2）、（3,5,3）、（3,4,3）、（3,3,3）、（3,2,3）、（3,1,2）、（4,1,2）、（5,1,1）、（5,2,1）、（5,3,1）、（5,4,1）、（5,5,0）。 数据结构的选择和概要设计 迷宫数据用二维数组int maze[SIZE+2][SIZE+2]来存储即可(迷宫四周加障碍，所以行列数加2)，在定义了迷宫的行列数后，利用两个for循环即可用键盘录入迷宫信息，并在迷宫周围加围墙。存储有哪些信誉好的足球投注网站路线按题目要求采用链栈的数据结构，用非递归的方法求解路线。图（1）为程序的流程图。 详细设计和编码 首先建立迷宫。用户自定义迷宫的行列数m、n，利用嵌套循环将迷宫信息存储于数组maze[m+2][n+2]中： for(i=0;im+2;i++) { for(j=0;jn+2;j++) { if(i==0||i==m+1||j==0||j==n+1) //在迷宫周围加障碍 maze[i][j]=1; else scanf(%d,maze[i][j]); } } 在对迷宫探索时，每一步都有四个方向可以有哪些信誉好的足球投注网站，为实现这一操作，可建立一个移动数组move[8]。向东有哪些信誉好的足球投注网站时坐标变化为横坐标不变，纵坐标加一，向南有哪些信誉好的足球投注网站时坐标变化为横坐标加一，纵坐标不变，向西有哪些信誉好的足球投注网站时坐标变化为横坐标不变，纵坐标减一，向北有哪些信誉好的足球投注网站时坐标变化为横坐标减一，纵坐标不变。这样就完成了向四个方向的有哪些信誉好的足球投注网站操作。建立链栈用于存储路线信息。链栈的数据域为包含了i，j，d的结构体，这样就能将路线的每一步信息存储下来。再建立一个移动坐标，以记录有哪些信誉好的足球投注网站过程中变