数据结构课程设计--迷宫问题.doc

长 沙 学 院课程设计说明书题目迷宫问题系(部)计算机科学与技术系专业(班级)2012软件工程（服务外包）9班姓名高锐学号2012022907指导教师付细楚起止日期2013.12.09 2013.12.21课程设计任务书课程名称：数据结构与算法设计题目：迷宫问题已知技术参数和设计要求：问题描述：以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。迷宫问题要求求出从入口（1，1）到出口（m,n）的一条通路，或得出没有通路的结论。基本要求：首先实现一个以链表作存储结构的栈类型，然后编写一个求迷宫问题的非递归程序，求得的通路以三元组（i，j，d）的形式输出，其中：（i，j）指示迷宫中的一个坐标， d表示走到下一坐标的方向。测试数据：迷宫用伪随机数产生程序产生。左上角（1，1）为入口，右下角（m,n）为出口。选作内容：1编写递归形式的算法，求得迷宫中的所有可能的通路2以方阵的形式输出迷宫及其通路迷宫中的所有可能的通路设计工作量：40课时工作计划：见课表指导教师签名：日期：2013.12.12教研室主任签名： 日期：系主任签名： 日期：长沙学院课程设计鉴定表姓名高锐学号2012022907专业软件工程班级12软9班设计题目迷宫问题指导教师付细楚指导教师意见：评定等级： 教师签名： 日期： 答辩小组意见：评定等级：答辩小组长签名：日期：教研室意见：教研室主任签名： 日期： 系（部）意见：系主任签名：日期：说明课程设计成绩分“优秀”、“良好”、“中等”、“及格”、“不及格”五类；摘要 计算机系的课程设计，我设计了一个迷宫系统，利用了链表栈结构来保存所走的宫路径，可以实现寻找迷宫通路的功能，当无法找到出口时，可提示用户不存在。当输入行数和列数（包括外墙）、迷宫内墙单元数、迷宫内墙每个单元的行数和列数就可以自动生成一个迷宫。关键词：课程设计，数据结构，迷宫，链表栈；目录第1章 设计内容与要求21.1设计内容21.2设计要求2第2章 需求分析32.1功能需求分析32.2软件功能32.3需求分析用例42.4求迷宫路径的基本思想42.5输入的形式和输入值的范围42.6输出的形式42.7程序所能达到的功能42.8迷宫求解流程图5第3章 系统设计63.1界面设计63.2函数设计63.3结构设计73.4算法设计8第4章 系统实现154.1输出迷宫的结构154.2迷宫的实现17第5章 总结21参考文献22附录23第1章 设计内容与要求1.1设计内容设计一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。迷宫问题要求求出从入口（1，1）到出口（m,n）的一条通路，或得出没有通路的结论。1.2设计要求创建一个以链表作存储结构的栈类型，编写一个求迷宫问题的非递归程序，求得的通路以三元组（i，j，d）的形式输出，其中：（i，j）指示迷宫中的一个坐标， d表示走到下一坐标的方向。 第2章 需求分析2.1功能需求分析求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向在继续探索，直至搜有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中应用“栈”也就是自热而然的事了2.2软件功能迷宫问题以一个m*n的长方阵表示迷宫0和1分别表示迷宫中的通路和障碍通路以三元组（i，j，d）的形式输出 图1.1 系统功能结构图1、迷宫的建立：迷宫中存在通路和障碍，为了方便迷宫的创建，可用0表示通路，用1表示障碍，这样迷宫就可以用0、1矩阵来描述。2、迷宫的存储：迷宫是一个矩形区域，可以使用二维数组表示迷宫，这样迷宫的每一个位置都可以用其行列号来唯一指定，但是二维数组不能动态定义其大小，我们可以考虑先定义一个较大的二维数组mazeM+2N+2,然后用它的前m行n列来存放元素，即可得到一个mn的二维数组，这样(0,0)表示迷宫入口位置，(m-1,n-1)表示迷宫出口位置。3、迷宫路径的搜索：首先从迷宫的入口开始，如果该位置就是迷宫出口，则已经找到了一条路径，搜索工作结束。否则搜索其上、下、左、右位置是否是障碍，若不是障碍，就移动到该位置，然后再从该位置开始搜索通往出口的路径；若是障碍就选择另一个相邻的位置，并从它开始搜索路径。为防止搜索重复出现，则将已搜索过的位置标记为2，同时保留搜索痕迹，在考虑进入下一个位置搜索之前，将当前位置保存在一个队列中，如果所有相邻的非障碍位置均被搜索过，且未找到通往出口的路径，则表明不存在从入口到出口的路径。这实现的是广度优先遍历的算法，如果找到路径，则为最短路径。2.3需求分析用例表1-1 “管理员用户登陆”功能需求分析用例功能点编号ATQ0101功能点名称迷宫问题角色任意功能说明用户能通过本功能点进出迷宫。事件流程1、 用户输入迷宫的行数和列数。2、 用户按照行数和列数用1和0构造出一个迷宫。3、 用户输入进点坐标和出点坐标。4、 按回车键就可得出出入迷宫的路径。前置条件无后置条件无输入数据迷宫的行数和列数以及出入口坐标输出数据（i，j，d）即迷宫的坐标(i，j)和走到下一坐标的方向d。备注无2.4求迷宫路径的基本思想若当前位置可通，则纳入当前路径，并继续朝“下一位置”探索，即切换“下一位置”为“当前位置”，如此重复直至到达出口；若当前位置“不可通”，则应顺着“来向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周四个方块均“不可通”，则应从“当前路径”上删除该通道块。所谓“下一位置”指的是“当前位置”四周四个方向（东、南、西、北）上相邻的方块。2.5输入的形式和输入值的范围以0，1输入表示迷宫，0为通路，1为障碍。向电脑输入由0和1组成的二维数组。2.6输出的形式“0”表示通道，“1”表示障碍。然后输出走出迷宫的路径。2.7程序所能达到的功能实现输出迷宫通道，当迷宫无通道时显示“找不到通路”。定义添加迷宫创建迷宫从迷宫入口开始寻路上左右下判断个方向是否通路迷宫无解求解完毕程序结束2.8迷宫求解流程图评审：某些方块文字描述过多，可以图表化一点点罗列观察起来会更明了。表1-1 “管理员用户登陆”功能需求分析用例，表中好像内容与管理员没有衔接关系，从其他地方拷贝资料借鉴时应注意更改全面。功能点编号跟所做的课程设计标题有关联应该好点，不然是多余的，例如更改为MG113。分析过程中没有考虑多条通路进行折取最短路径，也没说明只有一条通路。但是系统结构功能图比较好，整体思路比较清晰，对迷宫求解这个设计探索的还是比较熟悉。 等级：良好 评分：85分 评审人：张立评审时间：2013-12-11第3章 系统设计3.1界面设计请输入迷宫的行数,列数(包括外墙)：(空格隔开)5 5请输入迷宫内墙单元数：2请依次输入迷宫内墙每个单元的行数,列数：(空格隔开)1 23 2迷宫结构如下: 0 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 0 0 0 0 0 0请输入起点的行数,列数：（空格隔开）1 1请输入终点的行数,列数：（空格隔开）3 3此迷宫从入口到出口的一条路径如下: 0 0 0 0 0 0 1 0 1 0 0 2 3 4 0 0 1 0 5 0 0 0 0 0 0请按任意键继续. . 3.2函数设计#include #include #include /* malloc() */ #include /* INT_MAX */ #include /* EOF(=ZF6),NULL */ #include /* atoi() */ #include /* eof() */ #include /* floor(),ceil(),abs() */ #include /* exit() */#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE 3.3结构设计定义地图的大小，节点，走的方向，用链表实现栈的思想，运用头插法，将每一个新节点的是都插入到链表中，一个类栈的操作。#define STACK_INIT_SIZE 10#define STACK_INCREMENT 2typedef struct SqStack SElemType *base;SElemType *top;int stacksize;SqStack;3.4算法设计/ 迷宫坐标位置类型typedef struct int x;/ 行值 int y;/ 列值 PosType;#define MAXLENGTH 25 / 设迷宫的最大行列为25 typedef int MazeTypeMAXLENGTHMAXLENGTH; / 迷宫数组行列 typedef struct / 栈的元素类型 int ord; / 通道块在路径上的序号 PosType seat; / 通道块在迷宫中的坐标位置 int di; / 从此通道块走向下一通道块的方向(03表示东北) SElemType;/ 全局变量 MazeType m; / 迷宫数组 int curstep=1; / 当前足迹,初值为1 #define STACK_INIT_SIZE 10/ 存储空间初始分配量 #define STACKINCREMENT 2/ 存储空间分配增量 / 栈的顺序存储表示 P46 typedef struct SqStackSElemType *base;/ 在栈构造之前和销毁之后，base的值为NULL SElemType *top;/ 栈顶指针 int stacksize;/ 当前已分配的存储空间，以元素为单位 SqStack;/ 顺序栈/*实现*/ /构造一个空栈Sint InitStack(SqStack *S)/ 为栈底分配一个指定大小的存储空间(*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if( !(*S).base )exit(0);(*S).top = (*S).base;/ 栈底与栈顶相同表示一个空栈(*S).stacksize = STACK_INIT_SIZE;return 1;/ 若栈S为空栈（栈顶与栈底相同的），则返回1，否则返回0。int StackEmpty(SqStack S)if(S.top = S.base)return 1;elsereturn 0;/插入元素e为新的栈顶元素。int Push(SqStack *S, SElemType e)if(*S).top - (*S).base = (*S).stacksize)/ 栈满，追加存储空间(*S).base = (SElemType *)realloc(*S).base , (*S).stacksize + STACKINCREMENT) * sizeof(SElemType);if( !(*S).base )exit(0);(*S).top = (*S).base+(*S).stacksize;(*S).stacksize += STACKINCREMENT;*(*S).top)+=e;/ 这个等式的+ * 优先级相同，但是它们的运算方式，是自右向左return 1;/若栈不空，则删除S的栈顶元素，用e返回其值，并返回1；否则返回0。int Pop(SqStack *S,SElemType *e)if(*S).top = (*S).base)return 0;*e = *-(*S).top;/ 这个等式的+ * 优先级相同，但是它们的运算方式，是自右向左return 1;/ 定义墙元素值为0,可通过路径为1,不能通过路径为-1,通过路径为足迹 / 当迷宫m的b点的序号为1(可通过路径)，return 1; 否则，return 0。int Pass(PosType b) if(mb.xb.y=1)return 1;elsereturn 0;/ 使迷宫m的a点的序号变为足迹(curstep)，表示经过 void FootPrint(PosType a)ma.xa.y=curstep;/ 根据当前位置及移动方向，返回下一位置 PosType NextPos(PosType c,int di)PosType direc4=0,1,1,0,0,-1,-1,0; / 行增量,列增量 / 移动方向,依次为东南西北 c.x+=direcdi.x;c.y+=direcdi.y;return c;/ 使迷宫m的b点的序号变为-1(不能通过的路径)void MarkPrint(PosType b) mb.xb.y=-1;/ 算法3.3 P51/ 若迷宫maze中存在从入口start到出口end的通道，则求得一条 / 存放在栈中(从栈底到栈顶)，并返回1；否则返回0 int MazePath(PosType start,PosType end) SqStack S;PosType curpos;SElemType e;InitStack(&S);curpos=start;doif(Pass(curpos)/ 当前位置可以通过，即是未曾走到过的通道块 FootPrint(curpos); / 留下足迹 e.ord=curstep;e.seat.x=curpos.x;e.seat.y=curpos.y;e.di=0;Push(&S,e); / 入栈当前位置及状态 curstep+; / 足迹加1 if(curpos.x=end.x&curpos.y=end.y) / 到达终点(出口) return 1;curpos=NextPos(curpos,e.di);else/ 当前位置不能通过 if(!StackEmpty(S)Pop(&S,&e); / 退栈到前一位置 curstep-;/ 前一位置处于最后一个方向(北) while(e.di=3&!StackEmpty(S)MarkPrint(e.seat); / 留下不能通过的标记(-1) Pop(&S,&e); / 退回一步 curstep-;if(e.di3) / 没到最后一个方向(北) e.di+; / 换下一个方向探索Push(&S,e);curstep+;/ 设定当前位置是该新方向上的相邻块curpos=NextPos(e.seat,e.di);while(!StackEmpty(S);return 0;/ 输出迷宫的结构 void Print(int x,int y) int i,j;for(i=0;ix;i+)for(j=0;jy;j+)printf(%3d,mij);printf(n); int main()PosType begin,end;int i,j,x,y,x1,y1;printf(请输入迷宫的行数,列数(包括外墙)：(空格隔开);scanf(%d%d, &x, &y);for(i=0;ix;i+) / 定义周边值为0(同墙) m0i=0;/ 迷宫上面行的周边即上边墙 mx-1i=0;/ 迷宫下面行的周边即下边墙 for(j=1;jy-1;j+)mj0=0;/ 迷宫左边列的周边即左边墙 mjy-1=0;/ 迷宫右边列的周边即右边墙 for(i=1;ix-1;i+)for(j=1;jy-1;j+)mij=1; / 定义通道初值为1 printf(请输入迷宫内墙单元数：);scanf(%d,&j);printf(请依次输入迷宫内墙每个单元的行数,列数：(空格隔开)n);for(i=1;i=j;i+)scanf(%d%d,&x1,&y1);mx1y1=0; / 定义墙的值为0 printf(迷宫结构如下:n);Print(x,y);printf(请输入起点的行数,列数：（空格隔开）);scanf(%d%d,&begin.x,&begin.y);printf(请输入终点的行数,列数：（空格隔开）);scanf(%d%d,&end.x,&end.y);if(MazePath(begin,end) / 求得一条通路 printf(此迷宫从入口到出口的一条路径如下:n);Print(x,y); / 输出此通路 elseprintf(此迷宫没有从入口到出口的路径n);system(pause);return 0;*/评审：界面设计过于简陋，不太美观。结构设计里可以分步描述自己设计该程序的结构思路，更细致化，使人一目了然。比如该设计是迷宫求解，其实就是栈的应用问题，结构设计第一步可以设计建栈问题，第二步入栈（也就是你的入队）。等等。算法设计中应有流程图，而不是笼统的一些代码。你所有设计的流程图下面应标有名称，如图2.1.3 *流程图。不过整个设计还是有一定的思考，结构设计里流程图也比较清晰，还对上部分我评论的需求分析的建议作出了相应的改进，很不错！加油！ 等 级：良好 评 分：83评审人：张立评审时间：2013-12-16第4章 系统实现4.1输出迷宫的结构void Print(int x,int y) int i,j;for(i=0;ix;i+)for(j=0;jy;j+)printf(%3d,mij);printf(n); int main()PosType begin,end;int i,j,x,y,x1,y1;printf(请输入迷宫的行数,列数(包括外墙)：(空格隔开);scanf(%d%d, &x, &y);for(i=0;ix;i+) / 定义周边值为0(同墙) m0i=0;/ 迷宫上面行的周边即上边墙 mx-1i=0;/ 迷宫下面行的周边即下边墙 for(j=1;jy-1;j+)mj0=0;/ 迷宫左边列的周边即左边墙 mjy-1=0;/ 迷宫右边列的周边即右边墙 for(i=1;ix-1;i+)for(j=1;jy-1;j+)mij=1; / 定义通道初值为1 printf(请输入迷宫内墙单元数：);scanf(%d,&j);printf(请依次输入迷宫内墙每个单元的行数,列数：(空格隔开)n);for(i=1;i= (*S).stacksize)/ 栈满，追加存储空间(*S).base = (SElemType *)realloc(*S).base , (*S).stacksize + STACKINCREMENT) * sizeof(SElemType);if( !(*S).base )exit(0);(*S).top = (*S).base+(*S).stacksize;(*S).stacksize += STACKINCREMENT;*(*S).top)+=e;/ 这个等式的+ * 优先级相同，但是它们的运算方式，是自右向左return 1;/若栈不空，则删除S的栈顶元素，用e返回其值，并返回1；否则返回0。int Pop(SqStack *S,SElemType *e)if(*S).top = (*S).base)return 0;*e = *-(*S).top;/ 这个等式的+ * 优先级相同，但是它们的运算方式，是自右向左return 1;/ 定义墙元素值为0,可通过路径为1,不能通过路径为-1,通过路径为足迹 / 当迷宫m的b点的序号为1(可通过路径)，return 1; 否则，return 0。int Pass(PosType b) if(mb.xb.y=1)return 1;elsereturn 0;/ 使迷宫m的a点的序号变为足迹(curstep)，表示经过 void FootPrint(PosType a)ma.xa.y=curstep;/ 根据当前位置及移动方向，返回下一位置 PosType NextPos(PosType c,int di)PosType direc4=0,1,1,0,0,-1,-1,0; / 行增量,列增量 / 移动方向,依次为东南西北 c.x+=direcdi.x;c.y+=direcdi.y;return c;/ 使迷宫m的b点的序号变为-1(不能通过的路径)void MarkPrint(PosType b) mb.xb.y=-1;/ 算法3.3 P51/ 若迷宫maze中存在从入口start到出口end的通道，则求得一条 / 存放在栈中(从栈底到栈顶)，并返回1；否则返回0 int MazePath(PosType start,PosType end) SqStack S;PosType curpos;SElemType e;InitStack(&S);curpos=start;doif(Pass(curpos)/ 当前位置可以通过，即是未曾走到过的通道块 FootPrint(curpos); / 留下足迹 e.ord=curstep;e.seat.x=curpos.x;e.seat.y=curpos.y;e.di=0;Push(&S,e); / 入栈当前位置及状态 curstep+; / 足迹加1 if(curpos.x=end.x&curpos.y=end.y) / 到达终点(出口) return 1;curpos=NextPos(curpos,e.di);else/ 当前位置不能通过 if(!StackEmpty(S)Pop(&S,&e); / 退栈到前一位置 curstep-;/ 前一位置处于最后一个方向(北) while(e.di=3&!StackEmpty(S)MarkPrint(e.seat); / 留下不能通过的标记(-1) Pop(&S,&e); / 退回一步 curstep-;if(e.di= (*S).stacksize)/ 栈满，追加存储空间(*S).base = (SElemType *)realloc(*S).base , (*S).stacksize + STACKINCREMENT) * sizeof(SElemType);if( !(*S).base )exit(0);(*S).top = (*S).base+(*S).stacksize;(*S).stacksize += STACKINCREMENT;*(*S).top)+=e;/ 这个等式的+ * 优先级相同，但是它们的运算方式，是自右向左return 1;/若栈不空，则删除S的栈顶元素，用e返回其值，并返回1；否则返回0。int Pop(SqStack *S,SElemType *e)if(*S).top = (*S).base)return 0;*e = *-(*S).top;/ 这个等式的+ * 优先级相同，但是它们的运算方式，是自右向左return 1;/ 定义墙元素值为0,可通过路径为1,不能通过路径为-1,通过路径为足迹 / 当迷宫m的b点的序号为1(可通过路径)，return 1; 否则，return 0。int Pass(PosType b) if(mb.xb.y=1)return 1;elsereturn 0;/ 使迷宫m的a点的序号变为足迹(curstep)，表示经过 void FootPrint(PosType a)ma.xa.y=curstep;/ 根据当前位置及移动方向，返回下一位置 PosType NextPos(PosType c,int di)PosType direc4=0,1,1,0,0,-1,-1,0; / 行增量,列增量 / 移动方向,依次为东南西北 c.x+=direcdi.x;c.y+=direcdi.y;return c;/ 使迷宫m的b点的序号变为-1(不能通过的路径)void MarkPrint(PosType b) mb.xb.y=-1;/ 算法3.3 P51/ 若迷宫maze中存在从入口start到出口end的通道，则求得一条 / 存放在栈中(从栈底到栈顶)，并返回1；否则返回0 int MazePath(PosType start,PosType end) SqStack S;PosType curpos;SElemType e;InitStack(&S);curpos=start;doif(Pass(curpos)/ 当前位置可以通过，即是未曾走到过的通道块 FootPrint(curpos); / 留下足迹 e.ord=curstep;e.seat.x=curpos.x;e.seat.y=curpos.y;e.di=0;Push(&S,e); / 入栈当前位置及状态 curstep+; / 足迹加1 if(curpos.x=end.x&curpos.y