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

安徽建筑大学 课课 程程 设设 计计 报报 告告 课程名称： 数据结构与算法课程设计数据结构与算法课程设计 题 目： 迷宫求解迷宫求解 院 系： 数理系数理系 专 业： 信息与计算数学信息与计算数学 班 级： 学 号： 姓 名： 时 间： 数据结构课程设计报告迷宫求解 1 目 录 一一 、需求分析、需求分析 .2 1. 问题描述：问题描述：2 2. 基本要求基本要求.2 二、二、 概要设计概要设计 .3 1. 数据结构数据结构.3 2. 程序模块程序模块.3 3. 算法设计算法设计5 三、详细设计三、详细设计 .7 1. 数据类型定义数据类型定义7 2. 函数实现代码函数实现代码7 3. 函数之间的调用关系函数之间的调用关系7 四、调试分析四、调试分析 .7 五、用户手册五、用户手册 .8 六、测试结果六、测试结果 .8 七、参考文献七、参考文献 .9 八、附录八、附录 .10 数据结构课程设计报告迷宫求解 2 迷宫求解题目迷宫求解题目： 以一个 mn 长方阵表示迷宫，0 和 1 分别表示迷宫中的通路和障碍，设计一个程序，对任意 设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。(1)以二维数组存储迷宫数 据；(2)求得的通路以二元组( i , j )的形式输出，其中（i, j）指示迷宫中的一个坐标。 一一 、需求分析、需求分析 1. 问题描述：问题描述： 在迷宫中求出从入口到出口的路径。经分析，一个简单的求解方法是：从入口出发，沿某一 方向进行探索，若能走通，则继续向前走；否则沿原路返回，换一方向再进行搜索，直到所有可 能的通路都探索到为止。即所谓的回溯法。 求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时，通常 用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否 则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位 置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此， 在求迷宫通路的算法中应用“栈”也就是自然而然的事了。 假设“当前位置”指的是“在搜索过程中某一时刻所在图中某个方块位置”，则求迷宫中一条路径 的算法的基本思想是：若当前位置“可通“，则纳入“当前路径“，并继续朝“下一位置”探索，即切换 “下一位置”为“当前位置”，如此重复直至到达出口；若当前位置“不可通”，则应顺着“来向”退回到 “前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周四个方块均“不可 通”，则应从“当前路径”上删除该通道块。所谓“下一位置”指的是“当前位置”四周四个方向（东、 南、西、北）上相邻的方块。 2. 基本要求基本要求 （1）以二维数组 maze.adrm+1n+1表示迷宫，其中 mg0j和 mgm+1j(0 j n)及 mgi0和 mgin(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） 。 数据结构课程设计报告迷宫求解 3 二、二、 概要设计概要设计 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 dataStackSize; 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） 退栈 数据结构课程设计报告迷宫求解 4 DataType Pop（S） if(StackEmpty(S) Error(“Stack underflow“); /下溢，退出运行 return S-dataS-top-;/栈顶元素返回后将栈顶指针减 1 （6） 取栈顶元素 DataType StackTop（S） if(StackEmpty(S) Error(“Stack is empty“); return S-dataS-top; 3 各模块之间的调用关系以及算法设计 （1）Stack.h 中调用的 base.h #include #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef 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 数据结构课程设计报告迷宫求解 5 if(!S.base) exit(OVERFLOW);/存储分配失败 S.top=S.base; S.stackSize=INIT_SIZE; return OK; /InitStack Status StackEmpty(Stack S) /若 s 为空返回 TRUE,否则返回 FALSE if(S.top=S.base) return TRUE; return FALSE; /StackEmpty Status Push(Stack if(!S.base) exit(OVERFLOW); /存储分配失败 S.top=S.base+S.stackSize; S.stackSize+=INCREMENT; *S.top+=e; return OK; /push Status Pop(Stack e=*-S.top; return OK; /Pop Status DestroyStack(Stack S.top=S.base; return OK; /DestroyStack 3. 算法设计算法设计 求迷宫中一条从入口到出口的路径的算法可简单描述如下： 设定当前位置的初值为入口位置； 数据结构课程设计报告迷宫求解 6 do 若当前位置可通， 则将当前位置插入栈顶； / 纳入路径 若该位置是出口位置，则结束；/ 求得路径存放在栈中 否则切换当前位置的东邻方块为新的当前位置； 否则 若栈不空且栈顶位置尚有其他方向未被探索， 则设定新的当前位置为: 沿顺时针方向旋转 找到的栈顶位置的下一相邻块； 若栈不空但栈顶位置的四周均不可通， 则 删去栈顶位置； / 从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空； while (栈不空） ； 在此，尚需说明一点的是，所谓当前位置可通，指的是未曾走到过的通道块，即要求该方块位置 不仅是通道块，而且既不在当前路径上（否则所求路径就不是简单路径） ，也不是曾经纳入过路径 后又从路径上删除的通道块（否则只能在死胡同内转圈） 。 typedef struct int ord; / 通道块在路径上的“序号” PosType seat; / 通道块在迷宫中的“坐标位置” int di; / 从此通道块走向下一通道块的“方向” SElemType; / 栈的元素类型 Status MazePath ( MazeType maze, PosType start, PosType end ) / 若迷宫 maze 中从入口 start 到出口 end 的通道， / 则求得一条存放在栈中（从栈底到栈顶） ，并返回 / TRUE；否则返回 FALSE InitStack(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 数据结构课程设计报告迷宫求解 7 Pop (S,e); / 留下不能通过的标记，并退回一步 / while if (e.di存盘。 对文件进行编译和链接 在程序编写后，需要将其编译成可执行文件，需要用“compile”中的 F9 进行编译和链接。 然后看文件中是否存在错误，存在错误改正，直到没有错误。 运行 采用相关功能“compile”菜单，运行已形成好的可执行文件。如果源程序文件尚未编译或链接， 选择此项目时系统也会进行编译和链接，如果程序中没有错误，再进行处理后的可执行文件。与 此功能对应的快捷键为+ 六、测试结果六、测试结果 输入数据：当入口为（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，-1） 输入过程如下图所示：输入时(-1，-1）结束，接着输入入口参数（1，1） 然后输入出口参数（8，8） ，运行： 数据结构课程设计报告迷宫求解 9 运行结果如下图所示： 上图中”1”表示围墙和障碍物。 ”表示走过但不是通路.而”0”就是所要求的老鼠走过的最小路径. 七、参考文献七、参考文献 1 Richard F. Gilberg, Behrouz A. Forouzan. DataData StructureStructure. Brooks/Cole, Thomson Asia Pte Ltd, USA, 2000. 2 严蔚敏, 吴伟民. 数据结构（第二版）. 北京：清华大学出版社, 1992. 3 数据结构（C 语言版） 李云清 杨庆红 揭安全 编著 人民邮电出版社 4 C 语言程序设计（第二版） 谭浩强 著 清华大学出版社 5 数据结构课程设计 苏仕华 等编著 机械工业出版社 八、附录八、附录 原程序文件名清单: /base.h #include #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int Status; 数据结构课程设计报告迷宫求解 10 /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 if(!S.base) exit(OVERFLOW);/存储分配失败 S.top=S.base; S.stackSize=INIT_SIZE; return OK; /InitStack Status StackEmpty(Stack S) /若 s 为空返回 TRUE,否则返回 FALSE if(S.top=S.base) return TRUE; return FALSE; /StackEmpty Status Push(Stack if(!S.base) exit(OVERFLOW); /存储分配失败 S.top=S.base+S.stackSize; S.stackSize+=INCREMENT; 数据结构课程设计报告迷宫求解 11 *S.top+=e; return OK; /push Status Pop(Stack e=*-S.top; return OK; /Pop Status DestroyStack(Stack S.top=S.base; return OK; /DestroyStack /maze.c #include “stack.h“ #define MAXLEN 10/迷宫包括外墙最大行列数目 typedef struct int r; int c; char adrMAXLENMAXLEN;/可取 * # MazeType; /迷宫类型 Status InitMaze(MazeType printf(“Enter row and column numbers: “); scanf(“%d%d“, /迷宫行和列数 for(i=0;imaze.r | nmaze.c)/越界 数据结构课程设计报告迷宫求解 12 exit(ERROR); maze.adrmn=1;/迷宫障碍用#标记 printf(“Enter blocks coordinate(-1,-1) to end): “); scanf(“%d%d“, /while return OK; /InitMaze Status Pass(MazeType maze,PostType curpos) /当前位置可通则返回 TURE,否则返回 FALSE if(maze.adrcurpos.rcurpos.c= )/可通 return TRUE; else return FALSE; /Pass Status FootPrint(MazeType /“*“表示可通 return OK; /FootPrint PostType NextPos(PostType cpos=curpos; switch(i) /1.2.3.4 分别表示东,南,西,北方向 case 1 : cpos.c+=1; break; case 2 : cpos.r+=1; break; case 3 : cpos.c-=1; break; case 4 : cpos.r-=1; break; default: exit(ERROR); return cpos; /Nextpos Status MarkPrint(MazeType /“表示曾走过但不通 return OK; /MarkPrint Status MazePath(MazeType PostType curpos; int curstep;/当前序号,1.2.3.4 分别表示东,南,西,北方向 数据结构课程设计报告迷宫求解 13 SElemType e; InitStack(S); curp