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

安徽建筑大学课程设计报告课程名称：数据结构与算法课程设计题目：迷宫求解院系：数理系专业：信息与计算数学班级：学号：姓名：时间：数据结构课程设计报告——迷宫求解1目录一、需求分析............................................................................................21.问题描述：...........................................................................................22.基本要求.............................................................................................2二、概要设计............................................................................................31.数据结构.............................................................................................32.程序模块.............................................................................................33.算法设计...............................................................................................5三、详细设计..............................................................................................71.数据类型定义.......................................................................................72.函数实现代码.......................................................................................73.函数之间的调用关系..........................................................................7四、调试分析..............................................................................................7五、用户手册..............................................................................................8六、测试结果..............................................................................................8七、参考文献..............................................................................................9八、附录......................................................................................................9数据结构课程设计报告——迷宫求解2迷宫求解题目：以一个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](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）本程序只求出一条成功的通路。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为栈顶元素。栈的修改是按后进先出的原则进行的。因此，栈又称为后进先出（ListInFirstOut）的线性表。在迷宫问题中，假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。由此，“纳入路径”的操作即为“当前位置入栈”；“从当前路径上删除前一通道块”的操作即为“出栈”。基本操作的函数原型说明。2.程序模块栈的顺序存储表示#defineStackSize100//假定预分配的栈空间最多为100个元素typedefcharDataType;//假定栈元素的数据类型为字符typedefstruct{DataTypedata[StackSize];inttop;}SeqStack;基本操作的算法描述（1）置栈空voidInitStack（SeqStack*S）{//将顺序栈置空S-top=-1;}（2）判栈空intStackEmpty（SeqStack*S）{returnS-top==-1;}（3）判栈满intStackFull（SeqStack*SS）{returnS-top==StackSize-1;}（4）进栈voidPush（S，x）{if(StackFull(S))Error(Stackoverflow);//上溢，退出运行S-data[++S-top]=x;//栈顶指针加1后将x入栈}（5）退栈数据结构课程设计报告——迷宫求解4DataTypePop（S）{if(StackEmpty(S))Error(Stackunderflow);//下溢，退出运行returnS-data[S-top--];//栈顶元素返回后将栈顶指针减1}（6）取栈顶元素DataTypeStackTop（S）{if(StackEmpty(S))Error(Stackisempty);returnS-data[S-top];}3各模块之间的调用关系以及算法设计（1）Stack.h中调用的base.h#includestdio.h#includestdlib.h#includestring.h#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-2typedefintStatus;（2）主程序maze.c中调用的stack.h#includebase.h#defineINIT_SIZE100//存储空间初始分配量#defineINCREMENT10//存储空间分配增量typedefstruct{//迷宫中r行c列的位置intr;intc;}PostType;typedefstruct{intord;//当前位置在路径上的序号PostTypeseat;//当前坐标intdi;//往下一坐标的方向}SElemType;//栈元素类型typedefstruct{SElemType*base;//栈基址,构造前销毁后为空SElemType*top;//栈顶intstackSize;//栈容量}Stack;//栈类型StatusInitStack(Stack&S){//构造空栈sS.base=(SElemType*)malloc(INIT_SIZE*sizeof(SElemType));数据结构课程设计报告——迷宫求解5if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base;S.stackSize=INIT_SIZE;returnOK;}//InitStackStatusStackEmpty(StackS){//若s为空返回TRUE,否则返回FALSEif(S.top==S.base)returnTRUE;returnFALSE;}//StackEmptyStatusPush(Stack&S,SElemTypee){//插入元素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;returnOK;}//pushStatusPop(Stack&S,SElemType&e){//若栈不空删除栈//顶元素用e返回并返回OK，否则返回ERRORif(S.top==S.base)returnERROR;e=*--S.top;returnOK;}//PopSt