数据结构课程设计报告迷宫算法

《数据结构课程设计报告迷宫算法》由会员分享，可在线阅读，更多相关《数据结构课程设计报告迷宫算法（24页珍藏版）》请在装配图网上搜索。

1、 课课 程程 设设 计计 报报 告告课程设计名称：数据结构课程设计数据结构课程设计课程设计题目：迷宫算法 院（系）：计算机学院专 业：计算机科学与技术班 级：04010103学 号：2010040101107 I 目目 录录1 1 课程设计介绍课程设计介绍.11.1 课程设计内容.11.2 课程设计要求.12 2 课程设计原理课程设计原理.22.1 课设题目粗略分析.22.2 原理图介绍.32.2.1 功能模块图.32.2.2 流程图分析.33 数据结构分析数据结构分析.93.1 存储结构.93.2 算法描述.94 4 调试与分析调试与分析.114.1 调试过程.114.2 程序执行过程.11

2、参考文献参考文献.13附附 录（关键部分程序清单）录（关键部分程序清单）.14 1 1 1 课程设计介绍课程设计介绍1.11.1 课程设计内容课程设计内容编写算法能够生成迷宫，并且求解迷宫路径（求解出任意一条到出口的路径即可）：1. 迷宫用上下左右四种走法；2. 迷宫的大小和复杂程度可以由用户定义；3. 入口出口也由用户自己选择。1.21.2 课程设计要求课程设计要求1.不必演示求解过程，只需要输出迷宫求解的路径；2.参考相应资料完成课设。沈阳航空航天大学课程设计报告 2 2 2 课程设计原理课程设计原理2.12.1 课设题目粗略分析课设题目粗略分析根据课设题目要求，拟将整体程序分为四大模块。

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

4、完后的路径，路径用 1 2 3 4来表示。沈阳航空航天大学课程设计报告 3 2.22.2 原理图介绍原理图介绍2.2.12.2.1 功能模块图功能模块图迷宫求解建立迷宫设置迷宫寻找路径输出结果图 2.1 功能模块图如图 2.1 所示 沈阳航空航天大学课程设计报告 4 2.2.2 流程图分析流程图分析 1.建立迷宫开始构建一个空栈InitStack(SqStack *S)判断栈是否为空N建立迷宫,将所有的周边值设为mx1y1=0;结束输入迷宫的行数x和列数yY图 2.2 建立迷宫函数流程图沈阳航空航天大学课程设计报告 5 2. 设置迷宫图 2.3 设置迷宫函数流程图设置迷宫内部，将内墙设为mx1

5、y1=0，开始结束输入迷宫的内墙数j,和具体位置x1 y1输入迷宫的指点和终点&end.x,&end.y可由Print(x,y);函数输出已建立好的迷宫供用户检查沈阳航空航天大学课程设计报告 6 3. 寻找路径可以通过FootPrint(curpos); / 留下足迹，入栈Push(&S,e);足迹加一curstep+; 继续进行判断输入迷宫的起点和终点的坐标&begin.x,&begin.y，&end.x,&end.y结束开始判断if(MazePath(begin,end)求的路径判断是否到终点不可以通过，换个方向继续判断找到路径YYNN判断是否有路径Y找不到路径输出迷宫N 图 2.4 寻找

6、路径函数流程图沈阳航空航天大学课程设计报告 7 4.输出结果Print(x,y); 输出此通路输入i,j结束开始输出迷宫图 2.5 输出结果函数流程图沈阳航空航天大学课程设计报告 8 3 数据结构分析数据结构分析3.13.1 存储结构存储结构定义一个整型数组 PosType 用来存储行列的值。typedef struct / 栈的元素类型 int ord; / 通道块在路径上的序号 PosType seat; / 通道块在迷宫中的坐标位置 int di; / 从此通道块走向下一通道块的方向(03 表示东北) SElemType; 栈的存储结构：#define STACK_INIT_SIZE 1

7、0/ 存储空间初始分配量 #define STACKINCREMENT 2/ 存储空间分配增量 / 栈的顺序存储表示 typedef struct SqStackSElemType *base;/ 在栈构造之前和销毁之后，base 的值为 NULL SElemType *top;/ 栈顶指针 int stacksize;/ 当前已分配的存储空间，以元素为单位 SqStack;/ 顺序栈3.23.2 算法描述算法描述1.栈的基本操作的算法，简单算法说明如下：Status InitStack(SqStack *S)/ 构造一个空栈 S，为栈底分配一个指定大小的存储空间(*S).base = (SE

8、lemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if( !(*S).base ) exit(0);(*S).top = (*S).base; / 栈底与栈顶相同表示一个空栈(*S).stacksize = STACK_INIT_SIZE;return 1;Status StackEmpty(SqStack S)沈阳航空航天大学课程设计报告 9 / 若栈 S 为空栈（栈顶与栈底相同的） ，则返回 1，否则返回0。if(S.top = S.base) return 1;else return 0;Status Push(SqStack *S,

9、SElemType e)/ 插入元素 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;Stat

10、us Pop(SqStack *S,SElemType *e)/ 若栈不空，则删除 S 的栈顶元素，用 e 返回其值，并返回 1；否则返回0。if(*S).top = (*S).base) return 0;*e = *-(*S).top;return 1;2.查找路径的算法，简单算法说明如下：Status MazePath(PosType start,PosType end) / 若迷宫 maze 中存在从入口 start 到出口 end 的通道，则求得一条 / 存放在栈中(从栈底到栈顶)，并返回 1；否则返回 0 沈阳航空航天大学课程设计报告 10 InitStack(&S); curpo

11、s=start; curstep=1;doif(Pass(curpos)/ 当前位置可以通过，即是未曾走到过的通道块 FootPrint(curpos); / 留下足迹 e =( curstep, curpos,1);Push(&S,e); / 入栈当前位置及状态 if(curpos.x=end.x&curpos.y=end.y) / 到达终点(出口) return 1;curpos=NextPos(curpos,e.di);else/ 当前位置不能通过 if(!StackEmpty(S)Pop(&S,&e); / 退栈到前一位置 curstep-; / 前一位置处于最后一个方向(北) whi

12、le(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); / 设定当前位置是该新方向上的相邻块while(!StackEmpty(S);沈阳航空航天大学课程设计报告 11 return 0;4 4 调试与分析调试与分析4.14.1 调试过程调试过程在调试程序是主要遇到一下几类问题：1. 选择存储结构的问题：刚接到课设题目的时候，我就在想用什么

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

14、，则删除此路径。4. 界面问题：这里就是运用了 switch(n)语句来实现的，这样增加了程序的实用性。沈阳航空航天大学课程设计报告 12 4.2 程序执行过程程序执行过程系统使用说明：1出现界面后选择 1，进行迷宫大小的设计（这里设计 3*3 大小的）：如图 4.1所示 图 4.1 2. 然后选择 2，开始设计迷宫的内部：如图 4.2 所示 图 4.23.选择 3，观察设计的是否满足你的要求：如图 4.3 所示沈阳航空航天大学课程设计报告 13 图 4.34.选择 4，输入迷宫的起点和终点：如图 4.4 所示 图 4.45.选择 5，查看结果（路径由 1.2.3.4.5 表示出来）：如图 4

15、.5 所示沈阳航空航天大学课程设计报告 14 图 4.56选择 0，退出程序。沈阳航空航天大学课程设计报告 15 参考文献参考文献1 严蔚敏，吴伟民. .数据结构M.北京：清华大学出版社，2007. 2 胡圣荣, 周霭如, 罗穗萍.数据结构教程与题解M.北京：清华大学出版社，2011.3 谭浩强. .C 程序设计M.北京：清华大学出版社，2005.4 袁平波.数据结构实验指导M.合肥：中国科学技术大学出版社.2010. 5 殷人昆.数据结构M.北京：清华大学出版社.2011.6 宁正元.算法与数据结构习题精解和实验指导M.北京. 清华大学出版社.2007.7 陈媛.算法与数据结构.第 2 版M

16、.北京. 清华大学出版社.2011.沈阳航空航天大学课程设计报告 16 附附 录（关键部分程序清单）录（关键部分程序清单）程序代码程序代码#include#include#include#include/ 迷宫坐标位置类型typedef struct int x;/ 行值 int y;/ 列值 PosType;#define MAXLENGTH 25 / 设迷宫的最大行列为 25 typedef int MazeTypeMAXLENGTHMAXLENGTH; / 迷宫数组行列 typedef struct / 栈的元素类型 int ord; / 通道块在路径上的序号 PosType seat;

17、 / 通道块在迷宫中的坐标位置 int di; / 从此通道块走向下一通道块的方向(03 表示东北) 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

18、;/ 当前已分配的存储空间，以元素为单位 SqStack; / 顺序栈沈阳航空航天大学课程设计报告 17 /构造一个空栈 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

19、，否则返回 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).

20、top = (*S).base+(*S).stacksize;(*S).stacksize += STACKINCREMENT;*(*S).top)+=e;return 1;/若栈不空，则删除 S 的栈顶元素，用 e 返回其值，并返回 1；否则返回 0。int Pop(SqStack *S,SElemType *e)沈阳航空航天大学课程设计报告 18 if(*S).top = (*S).base)return 0;*e = *-(*S).top; / 这个等式的+ * 优先级相同，但是它们的运算方式，是自右向左return 1;/ 定义墙元素值为 0,可通过路径为 1,不能通过路径为-1,通过

21、路径为足迹/ 当迷宫 m 的 b 点的序号为 1(可通过路径)，return 1; 否则，return 0。int Pass(PosType b) if(mb.xb.y=1)return 1;elsereturn 0;void 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.

22、x+=direcdi.x;c.y+=direcdi.y;return c;/ 使迷宫 m 的 b 点的序号变为-1(不能通过的路径)void MarkPrint(PosType b) mb.xb.y=-1;/ 若迷宫 maze 中存在从入口 start 到出口 end 的通道，则求得一条 / 存放在栈中(从栈底到栈顶)，并返回 1；否则返回 0 int MazePath(PosType start,PosType end) SqStack S;PosType curpos;SElemType e;沈阳航空航天大学课程设计报告 19 InitStack(&S);curpos=start;doif

23、(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); / 退栈到前一位置 cur

24、step-;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)沈阳航空航天大学课程设计报告

25、20 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 请输入迷宫的行数,列数(包括外墙)n);printf( 2 请输入迷宫内墙单元数n);printf( 3 迷宫结构如下n);printf( 4 输入迷宫的起点和终点n);printf( 5 输出结果n);printf( 0 退出n);printf(nn 请选择 ); scanf(

26、%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=0; / 迷宫左边列的周边即左边墙 mjy-1=0;/ 迷宫右边列的周边即右边墙 沈阳航空航天大学课程设计报告 21 for(i=1;ix-1;i+)for(j=1;jy-1;j+)mij=1; / 定义通道初值为 1 break; case 2: p

27、rintf(请输入迷宫内墙单元数：); 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(请输入起点的行数,列数：（空格隔开）); scanf(%d%d,&begin.x,&begin.y); printf(请输入终点的行数,列数：（空格隔开）); scanf(%d%d,&end.x,&end.y);br

28、eak; case 5: if(MazePath(begin,end) / 求得一条通路 printf(此迷宫从入口到出口的一条路径如下:n);Print(x,y); / 输出此通路 elseprintf(此迷宫没有从入口到出口的路径n);printf(输入 0 退出);scanf(%d,&k);break;while(n!=0);沈阳航空航天大学课程设计报告 22 课程设计总结：课程设计总结：本次课程设计是一个关于迷宫求解的问题，虽然刚听到有一些迷茫但是通过老师和同学的帮助最后还是有了结果，同时有了很多的体会和经验。1. 课程设计涉及很多的范围，这就需要我重新的温习以前学过的 C 语言的知识

29、和数据结构的算法，别且通过这个过程我又发现了我自身的不足，同时也巩固了我的 C 语言和数据结构。这对我以后的学习是非常有帮助的。2. 同时在这次程序设计过程中，我自己有很多不会或者不懂的地方，这时候就会有老师和同学的帮助，帮助我解决问题，同时我也会对这个知识点有更加深刻的了解。而且大家在交流不同的思路，我也可以了解更多的算法，这样我的理解思路有可以增加，这样也增加了我和同学老师的情谊，这就是现代社会所讲的团队合作。3. 这次课程设计时间因为中间有考试，所以时间有一点短，但我在过程中所体会的快乐，程序结果出来时刻的那种喜悦是让我无法忘记的。这种在学习中编程，在于大家探讨中学习，会使我们每个人都有很大的进步，也让我们明白了团队的重要性，这对我也后的学习和生活有很大的帮助。指导教师评语：指导教师(签字)： 年 月 日课程设计成绩