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

(1)以二维数组存储迷宫数据；(2)求得的通路以二元组( i , j )的形式输出，其中（i, j）指示迷宫中的一个坐标。

一、需求分析1. 问题描述：在迷宫中求出从入口到出口的路径。

经分析，一个简单的求解方法是：从入口出发，沿某一方向进行探索，若能走通，则继续向前走；否则沿原路返回，换一方向再进行搜索，直到所有可能的通路都探索到为止。

即所谓的回溯法。

求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。

由于计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。

为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。

因此，在求迷宫通路的算法中应用“栈”也就是自然而然的事了。

假设“当前位置”指的是“在搜索过程中某一时刻所在图中某个方块位置”，则求迷宫中一条路径的算法的基本思想是：若当前位置"可通"，则纳入"当前路径"，并继续朝“下一位置”探索，即切换“下一位置”为“当前位置”，如此重复直至到达出口；若当前位置“不可通”，则应顺着“来向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周四个方块均“不可通”，则应从“当前路径”上删除该通道块。

所谓“下一位置”指的是“当前位置”四周四个方向（东、南、西、北）上相邻的方块。

2. 基本要求（1）以二维数组maze.adr[m+1][n+1]表示迷宫，其中mg[0][j]和mg[m+1][j](0 j n)及mg[i][0]和mg[i][n](0 i m)为添加的一圈障碍，数组中以元素值为0表示通路，1表示障碍，限定迷宫大小m,n 10。

（2）用户以文件的形式输入迷宫的数据：文件中第一行的数据为迷宫的行数m和列数n;从第2行至第m+1行（每行n个数）为迷宫值，同一行的两个数之间用空白字符相隔。

（3）迷宫入口为（1，1），出口为（m,n）。

（4）每次移动只能从一个无障碍的单元到周围8个方向上任意无障碍的单元，编制程序给出一条通过迷宫的路径或报告一个“无法通过”的信息。

（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）。

二、概要设计1. 数据结构栈（stack）是限定仅在表尾进行插入或删除操作的线性表。

因此，对栈来说，表尾端有特殊含义，称为栈顶（top）,相应的，表头端称为栈底（bottom）。

不含元素的空表称为空栈。

假设栈S=（a1,a2,…，an），则称a1为栈底元素，an为栈顶元素。

栈的修改是按后进先出的原则进行的。

因此，栈又称为后进先出（List In First Out）的线性表。

在迷宫问题中，假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。

由此，“纳入路径”的操作即为“当前位置入栈”；“从当前路径上删除前一通道块”的操作即为“出栈”。

基本操作的函数原型说明。

2. 程序模块栈的顺序存储表示#define StackSize 100 //假定预分配的栈空间最多为100个元素typedef char DataType;//假定栈元素的数据类型为字符typedef struct{DataType data[StackSize];int top;}SeqStack;基本操作的算法描述（1）置栈空void InitStack（SeqStack *S）{//将顺序栈置空S->top=-1;}（2）判栈空int StackEmpty（SeqStack *S）{return S->top==-1;}（3）判栈满int StackFull（SeqStack *SS）{return S->top==StackSize-1;}（4）进栈void Push（S，x）{if (StackFull(S))Error("Stack overflow"); //上溢，退出运行S->data[++S->top]=x;//栈顶指针加1后将x入栈}（5）退栈DataType Pop（S）{if(StackEmpty(S))Error("Stack underflow"); //下溢，退出运行return S->data[S->top--];//栈顶元素返回后将栈顶指针减1}（6）取栈顶元素DataType StackTop（S）{if(StackEmpty(S))Error("Stack is empty");return S->data[S->top];}3各模块之间的调用关系以及算法设计（1）Stack.h中调用的base.h#include <stdio.h>#include <stdlib.h>#include <string.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;（2）主程序maze.c中调用的stack.h#include "base.h"#define INIT_SIZE 100 //存储空间初始分配量#define INCREMENT 10 //存储空间分配增量typedef struct{ //迷宫中r行c列的位置int r;int c;}PostType;typedef struct{int ord; //当前位置在路径上的序号PostType seat;//当前坐标int di; //往下一坐标的方向}SElemType; //栈元素类型typedef struct{SElemType* base;//栈基址,构造前销毁后为空SElemType* top;//栈顶int stackSize; //栈容量}Stack; //栈类型Status InitStack(Stack &S){ //构造空栈sS.base=(SElemType*)malloc(INIT_SIZE *sizeof(SElemType));if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base;S.stackSize=INIT_SIZE;return OK;}//InitStackStatus StackEmpty(Stack S){//若s为空返回TRUE,否则返回FALSEif(S.top==S.base)return TRUE;return FALSE;}//StackEmptyStatus Push(Stack &S,SElemType e){//插入元素e为新的栈顶元素if(S.top-S.base >=S.stackSize){//栈满，加空间S.base=(SElemType*)realloc(S.base,(S.stackSize+INCREMENT)*sizeof(SElemType));if(!S.base)exit(OVERFLOW); //存储分配失败S.top=S.base+S.stackSize;S.stackSize+=INCREMENT;}*S.top++=e;return OK;}//pushStatus Pop(Stack &S,SElemType &e){//若栈不空删除栈//顶元素用e返回并返回OK，否则返回ERRORif(S.top==S.base)return ERROR;e=*--S.top;return OK;}//PopStatus DestroyStack(Stack &S){//销毁栈S,free(S.base);S.top=S.base;return OK;}//DestroyStack3. 算法设计求迷宫中一条从入口到出口的路径的算法可简单描述如下：设定当前位置的初值为入口位置；do｛若当前位置可通，则｛将当前位置插入栈顶；// 纳入路径若该位置是出口位置，则结束；// 求得路径存放在栈中否则切换当前位置的东邻方块为新的当前位置；｝否则{若栈不空且栈顶位置尚有其他方向未被探索，则设定新的当前位置为: 沿顺时针方向旋转找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通，则｛删去栈顶位置；// 从路径中删去该通道块若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空；｝｝while (栈不空）；在此，尚需说明一点的是，所谓当前位置可通，指的是未曾走到过的通道块，即要求该方块位置不仅是通道块，而且既不在当前路径上（否则所求路径就不是简单路径），也不是曾经纳入过路径后又从路径上删除的通道块（否则只能在死胡同内转圈）。

typedef struct {int ord; // 通道块在路径上的“序号”PosType seat; // 通道块在迷宫中的“坐标位置”int di; // 从此通道块走向下一通道块的“方向”} SElemType; // 栈的元素类型Status MazePath ( MazeType maze, PosType start, PosType end ) {// 若迷宫maze中从入口start到出口end的通道，// 则求得一条存放在栈中（从栈底到栈顶），并返回// TRUE；否则返回FALSEInitStack(S); curpos = start;// 设定“当前位置”为“入口位置”curstep = 1; // 探索第一步do {if (Pass (curpos)) {// 当前位置可以通过，即是未曾走到过的通道块FootPrint (curpos); // 留下足迹e = ( curstep, curpos, 1 );Push (S,e); // 加入路径if ( curpos == end ) return (TRUE);// 到达终点（出口）curpos = NextPos ( curpos, 1 );// 下一位置是当前位置的东邻curstep++; // 探索下一步}else { // 当前位置不能通过if (!StackEmpty(S)) {Pop (S,e);while (e.di==4 && !StackEmpty(S)) {MarkPrint (e.seat);Pop (S,e); // 留下不能通过的标记，并退回一步} // whileif (e.di<4) {e.di++;Push ( S, e);// 换下一个方向探索curpos = NextPos (curpos, e.di );// 设定当前位置是该新方向上的相邻块} // if} // if} // else} while ( !StackEmpty(S) );return (FALSE);} // MazePath三、详细设计1. 数据类型定义typedef struct{int r;int c;char adr[MAXLEN][MAXLEN];}MazeType; //迷宫类型2. 函数实现代码●初始化迷宫Status InitMaze(MazeType &maze)●可通位置Status Pass(MazeType maze,PostType curpos)●标记非通路Status MarkPrint(MazeType &maze,PostType curpos)●迷宫maze从入口start到end的通道Status MazePath(MazeType &maze,PostType start,PostType end)●标记路径信息void PrintMaze(MazeType &maze)3. 函数之间的调用关系首先调用InitMaze(maze)，创建和初始化迷宫，初始化成功后输入迷宫的入口和出口坐标。