迷宫问题的求解数据结构课程设计(北华大学吕磊).doc

《迷宫问题的求解数据结构课程设计(北华大学吕磊).doc》由会员分享，可在线阅读，更多相关《迷宫问题的求解数据结构课程设计(北华大学吕磊).doc（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构课程设计设计说明书 迷宫问题求解学生姓名学号班级成绩指导教师数学与计算机科学学院2012年3月2日数据结构课程设计评阅书题 目迷宫问题求解学生姓名马东学号指导教师评语及成绩成绩： 教师签名： 年 月 日答辩教师评语及成绩成绩： 教师签名： 年 月 日教研室意见总成绩： 室主任签名： 年 月 日注：指导教师成绩60%，答辩成绩40%，总成绩合成后按五级制记入。课程设计任务书20112012学年第二学期专业： 学号： 姓名： 课程设计名称： 数据结构课程设计 设 计 题 目： 迷宫问题求解 完 成 期 限：自 2012 年 2 月 20 日至 2012 年 3 月 2 日共 2 周 设计依

2、据、要求及主要内容（可另加附页）：设计要求:设计内容：输入一个任意大小的迷宫数据，设置入口、出口及障碍，借助栈结构求解走出迷宫的路径并输出。逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的功能说明），各个主要模块的算法，并画出模块之间的调用关系图；详细设计：定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体

3、。详细设计的结果是对数据结构和基本操作做出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架；程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚；程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果；结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析；编写课程设计报告；以上要求中前三个阶段的任务完成后，先将设计说明数

4、的草稿交指导老师面审，审查合格后方可进入后续阶段的工作。设计工作结束后，经指导老师验收合格后将设计说明书打印装订，并进行答辩。指导教师（签字）： 教研室主任（签字）： 批准日期： 年 月 日摘 要由计算机解迷宫时，通常用的是穷举求解的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路反回，换一个方向继续探索，直至所有可行的通路都探索到为止。为了保证在任何位置上都能沿原路返回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。显然要用到栈。关键词：迷宫；穷举；栈； 目 录1 课题描述12 问题分析和任务定义23 数据结构分析 33.1存储结构33.2算法描述34

5、流程图 65 程序编码106 程序测试与运行过程19 6.1程序调试19 6.2程序运行过程197 结果分析25 总结26 参考文献271 课题描述 本课程设计是解决迷宫求解的问题，从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中要应用“栈”的思想假设“当前位置”指的是“在搜索过程中的某一时刻所在图中某个方块位置”，则求迷宫中一条路径的算法的基本思想是：若当前位置“可通”，则纳入“当前路径”，并继续

6、朝“下一位置”探索，即切换“下一位置”为“当前位置”，如此重复直至到达出口；若当前位置“不可通”，则应顺着“来向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周4个方块均“不可通”，则应从“当前路径”上删除该通道块。所谓“下一位置”指的是当前位置四周4个方向（东、南、西、北）上相邻的方块。假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。由此，“纳入路径”的操作即为“当前位置入栈”；“从当前路径上删除前一通道块”的操作即为“出栈”。2 问题分析和任务定义根据课设题目要求，拟将整体程序分为四大模块。以下是四个模块的大体分析： 1 建立迷宫

7、：要建立迷宫首先就要建立存储结构，这里我用数组的方式建立的。根据用户输入的迷宫的大小（我设置的最大值为25可以根据要求调解）； 2 设置迷宫：这里将0设置围墙，1是可以通过的路径，-1是不可以通过路径，外墙是以设计好的，内墙需要用户来设置，障碍的难度可自行定义； 3 寻找路径：寻找路径我设置了四个方向0,1,1,0,0,-1,-1,0移动方向,依次为东南西北，首先向东走，若不成功则转换方向，成功则继续前进，将走过的路径进行标记，然后存入栈中； 4 输出结果：输出的结果分为两种，一种是用户建立的迷宫主要是让用户检查是否符合要求，第二种输出的是寻找完后的路径，路径用1 2 3 4来表示。3 数据结

8、构分析3.1存储结构定义一个整型数组PosType用来存储行列的值。typedef struct / 栈的元素类型 int ord; / 通道块在路径上的序号 PosType seat; / 通道块在迷宫中的坐标位置 int di; / 从此通道块走向下一通道块的方向(03表示东北) SElemType; 栈的存储结构：#define STACK_INIT_SIZE 10/ 存储空间初始分配量 #define STACKINCREMENT 2/ 存储空间分配增量 / 栈的顺序存储表示 typedef struct SqStackSElemType *base;/ 在栈构造之前和销毁之后，bas

9、e的值为NULL SElemType *top;/ 栈顶指针 int stacksize;/ 当前已分配的存储空间，以元素为单位 SqStack;/ 顺序栈 3.2算法描述 1.栈的基本操作的算法，简单算法说明如下：Status InitStack(SqStack *S)/构造一个空栈S，为栈底分配一个指定大小的存储空间(*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if( !(*S).base ) exit(0);(*S).top = (*S).base;/ 栈底与栈顶相同表示一个空栈(*S).stacksi

10、ze = STACK_INIT_SIZE;return 1;Status StackEmpty(SqStack S) / 若栈S为空栈（栈顶与栈底相同的），则返回1，否则返回0。if(S.top = S.base) return 1;else return 0;Status Push(SqStack *S, SElemType e)/插入元素e为新的栈顶元素。if(*S).top - (*S).base = (*S).stacksize) / 栈满，追加存储空间 (*S).base = (SElemType *)realloc(*S).base , (*S).stacksize + STACK

11、INCREMENT) * sizeof(SElemType);if( !(*S).base ) exit(0);(*S).top = (*S).base+(*S).stacksize;(*S).stacksize += STACKINCREMENT;*(*S).top)+=e;return 1;Status Pop(SqStack *S,SElemType *e)/若栈不空，则删除S的栈顶元素，用e返回其值，并返回1；否则返回0。if(*S).top = (*S).base) return 0;*e = *-(*S).top;return 1;1. 查找路径的算法，简单算法说明如下：Statu

12、s MazePath(PosType start,PosType end) / 若迷宫maze中存在从入口start到出口end的通道，则求得一条 / 存放在栈中(从栈底到栈顶)，并返回1；否则返回0 InitStack(&S); curpos=start; curstep=1;doif(Pass(curpos)/ 当前位置可以通过，即是未曾走到过的通道块 FootPrint(curpos); / 留下足迹 e =( curstep, curpos,1);Push(&S,e); / 入栈当前位置及状态 if(curpos.x=end.x&curpos.y=end.y) / 到达终点(出口) r

13、eturn 1;curpos=NextPos(curpos,e.di);else/ 当前位置不能通过 if(!StackEmpty(S)Pop(&S,&e); / 退栈到前一位置 curstep-; / 前一位置处于最后一个方向(北) while(e.di=3&!StackEmpty(S)MarkPrint(e.seat); Pop(&S,&e); /留下不能通过的标记(-1) , 退回一步if(e.di3) / 没到最后一个方向(北) e.di+; Push(&S,e);/ 换下一个方向探索curpos=NextPos(e.seat,e.di); / 设定当前位置是该新方向上的相邻块whil

14、e(!StackEmpty(S);return 0; 4. 流程图 4.1建立迷宫 构造空栈函数并判断，若是则建立迷宫，否则返回并构造空栈。开始 输入迷宫的行数x和列数y 构建一个空栈InitStack（SqStack *S） n判断栈是否为空 建立迷宫，将所有的周边值设置为 mx1y1=0 y 结束 图3.1建立迷宫函数流程图 4.2设置迷宫 先设置迷宫障碍和起点与终点坐标，障碍设为0，用printf函数输出开始输入迷宫的内墙数j和具体位置x1 y1输入迷宫的起点和终点&end.x,&end.y 设置迷宫内部，将内墙设为mx1y1=0可由Print（x,y）;函数输出已建立好的迷宫供用户检查

15、结束 图3.2设置迷宫函数的流程图4.3寻找路径 先输入起点与终点坐标。判断，若能通过则留下足迹，入栈，足迹加一并继续判断，若不能，则换方向继续判断。开始输入迷宫的起点和终点坐标&begin x/y,&end x/yif(MazePath(beign,end)求的路径（判断） N可以通过Footprint(curpos);/留下足迹，入栈Push（&S,e），足迹加一curstep+，继续进行判断N不可通过，换个方向继续判断是否到终点 Y判断是否有路径 Y找到路径输出迷宫找不到路径 N 结束 图3.3寻找路径函数流程图4.4输出结果 开始 输入i，j Print(x,y);输出此通路 输出迷宫

16、 结束 图3.4输出结果流程图5 程序编码#include#include#include#include/ 迷宫坐标位置类型typedef struct int x;/ 行值 int y;/ 列值 PosType;#define MAXLENGTH 25 / 设迷宫的最大行列为25 typedef int MazeTypeMAXLENGTHMAXLENGTH; / 迷宫数组行列 typedef struct / 栈的元素类型 int ord; / 通道块在路径上的序号 PosType seat; / 通道块在迷宫中的坐标位置 int di; / 从此通道块走向下一通道块的方向(03表示东北)

17、 SElemType;/ 全局变量 MazeType m; / 迷宫数组 int curstep=1; / 当前足迹,初值为1 #define STACK_INIT_SIZE 10/ 存储空间初始分配量 #define STACKINCREMENT 2/ 存储空间分配增量 / 栈的顺序存储表示 typedef struct SqStackSElemType *base;/ 在栈构造之前和销毁之后，base的值为NULL SElemType *top;/ 栈顶指针 int stacksize;/ 当前已分配的存储空间，以元素为单位 SqStack;/ 顺序栈/构造一个空栈Sint InitSta

18、ck(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;/插入元素

19、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;ret

20、urn 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;voi

21、d FootPrint(PosType a) / 使迷宫m的a点的序号变为足迹(curstep)，表示经过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;/ 若迷宫maze中存在从入口st

22、art到出口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); / 入栈当前位置及状态 cur

23、step+; / 足迹加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+; /

24、换下一个方向探索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); void main()PosType begin,end;int i,j,x,y,x1,y1,n,k;dosystem(cls); /清屏函数printf( nnn);printf( 1请输入迷宫

25、的行数,列数(包括外墙)n);printf( 2请输入迷宫内墙单元数n);printf( 3迷宫结构如下n);printf( 4输入迷宫的起点和终点n);printf( 5输出结果n);printf( 0退出n);printf(nn请选择 ); scanf(%d,&n);switch(n)case 1: printf(请输入迷宫的行数,列数(包括外墙)：(空格隔开); scanf(%d%d, &x, &y); for(i=0;ix;i+) / 定义周边值为0(同墙) m0i=0;/ 迷宫上面行的周边即上边墙 mx-1i=0;/ 迷宫下面行的周边即下边墙 for(j=1;jy-1;j+) mj0

26、=0;/ 迷宫左边列的周边即左边墙 mjy-1=0;/ 迷宫右边列的周边即右边墙 for(i=1;ix-1;i+)for(j=1;jy-1;j+)mij=1; / 定义通道初值为1 break; case 2: printf(请输入迷宫内墙单元数：); scanf(%d,&j); printf(请依次输入迷宫内墙每个单元的行数,列数：(空格隔开)n); for(i=1;i=j;i+) scanf(%d%d,&x1,&y1);mx1y1=0; break; case 3:Print(x,y);printf(输入0退出);scanf(%d,&k);break; case 4: printf(请输入

27、起点的行数,列数：（空格隔开）); scanf(%d%d,&begin.x,&begin.y); printf(请输入终点的行数,列数：（空格隔开）); scanf(%d%d,&end.x,&end.y);break; case 5: if(MazePath(begin,end) / 求得一条通路 printf(此迷宫从入口到出口的一条路径如下:n);Print(x,y); / 输出此通路 elseprintf(此迷宫没有从入口到出口的路径n);printf(输入0退出);scanf(%d,&k);break;while(n!=0);6 程序测试与运行 6.1 程序调试 在调试程序是主要遇到一

28、下几类问题： 1.选择存储结构的问题：刚接到课设题目的时候，我就在想用什么来实现迷宫的存储。用线性表还是数组，最后综合考虑决定用栈和数组结合的方式来实现，用数组来建立迷宫和输出迷宫，用栈来查找路径并将生成的路径压入到栈中，因为栈有先入后出的优点，所以比较容易实现。2.如何建立迷宫和怎么设置迷宫的问题：首先迷宫要有一定的范围怎么才能让迷宫有序的进行，于是我将迷宫的外围和障碍设置为0，所有的可走路径设置为1，这样迷宫就清晰可见。3.如何去寻找路径问题 ：这是整个程序的核心。通过查找书籍得到了一个算法：若当前位置“可通”，则纳入当前路径，并继续朝下一位置搜索，即切换下一位置为当前位置，如此重复到达出

29、口；若不可通，就退回到前一通道，然后继续寻找其他方向；若均不可通，则删除此路径。4界面问题：这里就是运用了switch(n)语句来实现的，这样增加了程序的实用性。6.2程序运行过程出现界面后选择1，：进行迷宫大小的设计如图5.1所示 图5.1 进行迷宫大小的设计选择2，开始设计迷宫的内部：如图5.2所示 图5.2设计迷宫的内部观察设计的是否满足你的要求：如图 5.3所示 图5.3观察设计的是否满足你的要求输入迷宫的起点和终点：如图5.4所示(见下页) 图5.4输入起点和终点选择5，查看结果（路径由1.2.3.4.5表示出来）：如图5.5所示 图5.5查看结果无通路情况。如图5.6、5.7所示（

30、见下页） 图5.6无通路情况 图5.7无通路情况有多条通路的情况，如图5.8 5.9 5.10所示（见下页） 图5.8多条通路的情况 图5.9多条通路的情况 图5.10多条通路的情况之所以程序选择这条通路，是因为它探索的顺序是东-南-西-北。7 结果分析通过此次课程设计，是我对于数据结构有了更深的了解，更新的认识。数据结构是一门重要的课程，只有数据结构学得扎实了，才能对于计算机有更深的应用，所以学好数据结构是很重要的。经过两周的上机设计，我实现了简单的迷宫求解，能够简单的实现求解过程。但是还存在着不足之处，程序不能循环执行、求路径时遇见有多条路径的情况下，只能找出一条，并且不一定是最优路径。有

31、待改进。 总结本次课程设计是一个关于迷宫求解的问题，虽然刚听到有一些迷茫但是通过老师和同学的帮助最后还是有了结果，同时有了很多的体会和经验。课程设计涉及很多的范围，这就需要我重新的温习以前学过的C语言的知识和数据结构的算法，别且通过这个过程我又发现了我自身的不足，同时也巩固了我的C语言和数据结构。这对我以后的学习是非常有帮助的。但在运行测试的时候，我发现程序不能循环输入，多通路下只能选择一条通路。在进行最优路径搜索时，我查阅了资料，知道要运用图与队列的相关知识，但试了很多次没有试出来。这都需要以后进行不断的学习来改进。 参考文献1 严蔚敏. 数据结构（C语言版）M. 北京：清华大学出版社,1997.2 谭浩强. C程序设计（第三版）M. 北京：清华大学出版社，2005.1. 3 二霍红卫算法设计与分析西安西安电子科技大学出版社，2005.113-127.4 陈杰.计算机专业课程设计中的需求分析J.集美大学学报，2009，10(2)：8992.5 高一凡. 数据结构算法实现及解析M . 西安:西安电子科技大学出版社, 2002