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

1、 课课 程程 设设 计计 报报 告告 课程设计名称：数据结构课程设计数据结构课程设计 课程设计题目：迷宫算法 院（系）：计算机学院 专 业：计算机科学与技术 班 级：04010103 学 号：2010040101107 i 目目 录录 1 1 课程设计介绍课程设计介绍.1 1.1 课程设计内容.1 1.2 课程设计要求.1 2 2 课程设计原理课程设计原理.2 2.1 课设题目粗略分析.2 2.2 原理图介绍.3 2.2.1 功能模块图.3 2.2.2 流程图分析.3 3 数据结构分析数据结构分析.9 3.1 存储结构.9 3.2 算法描述.9 4 4 调试与分析调试与分析.11 4.1 调试

2、过程.11 4.2 程序执行过程.11 参考文献参考文献.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

5、和列数 y y 图 2.2 建立迷宫函数流程图 沈阳航空航天大学课程设计报告 5 2. 设置迷宫 图 2.3 设置迷宫函数流程图 设置迷宫内部，将内墙设为mx1y1=0， 开始 结束 输入迷宫的内墙数j,和具体位置x1 y1 输入迷宫的指点和终点 函数输出已建 立好的迷宫供用户检查 沈阳航空航天大学课程设计报告 6 3. 寻找路径 可以通过footprint(curpos); / 留下足迹，入栈push(足迹 加一curstep+; 继续进行判断 输入迷宫的起点和终点的坐标 输出此通路 输入i,j 结束 开始 输出迷宫 图 2.5 输出结果函数流程图 沈阳航空航天大学课程设计报告 8 3 数据

6、结构分析数据结构分析 3.13.1 存储结构存储结构 定义一个整型数组 postype 用来存储行列的值。 typedef struct / 栈的元素类型 int ord; / 通道块在路径上的序号 postype seat; / 通道块在迷宫中的坐标位置 int di; / 从此通道块走向下一通道块的方向(03 表示东北) selemtype; 栈的存储结构： #define stack_init_size 10/ 存储空间初始分配量 #define stackincrement 2/ 存储空间分配增量 / 栈的顺序存储表示 typedef struct sqstack selemtype

7、*base;/ 在栈构造之前和销毁之后，base 的值为 null selemtype *top;/ 栈顶指针 int stacksize;/ 当前已分配的存储空间，以元素为单位 sqstack;/ 顺序栈 3.23.2 算法描述算法描述 1.栈的基本操作的算法，简单算法说明如下： status initstack(sqstack *s) / 构造一个空栈 s，为栈底分配一个指定大小的存储空间 (*s).base = (selemtype *)malloc(stack_init_size*sizeof(selemtype); if( !(*s).base ) exit(0); (*s).top

8、 = (*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, selemtype e) / 插入元素 e 为新的栈顶元素。 if(*s).top - (*s).base = (*s).stacksize) / 栈满

9、，追加存储空间 (*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; status pop(sqstack *s,selemtype *e) / 若栈不空，则删除 s 的栈顶元素，用 e 返回其值，并返回 1；否则

10、返回 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( curpos=start; curstep=1; do if(pass(curpos)/ 当前位置可以通过，即是未曾走到过的通道块 foot

11、print(curpos); / 留下足迹 e =( curstep, curpos,1); push( / 入栈当前位置及状态 if(curpos.x=end.x curpos=nextpos(curpos,e.di); else/ 当前位置不能通过 if(!stackempty(s) pop( / 退栈到前一位置 curstep-; / 前一位置处于最后一个方向(北) while(e.di=3 pop( /留下不能通过的标记(-1) , 退 回一步 if(e.di3) / 没到最后一个方向(北) e.di+; push(/ 换下一个方向探索 curpos=nextpos(e.seat,e.

12、di); / 设定当前位置是该新方向 上的相邻块 while(!stackempty(s); 沈阳航空航天大学课程设计报告 11 return 0; 4 4 调试与分析调试与分析 4.14.1 调试过程调试过程 在调试程序是主要遇到一下几类问题： 1. 选择存储结构的问题：刚接到课设题目的时候，我就在想用什么来实现 迷宫的存储。用线性表还是数组，最后综合考虑决定用栈和数组结合的方式来实 现，用数组来建立迷宫和输出迷宫，用栈来查找路径并将生成的路径压入到栈中， 因为栈有先入后出的优点，所以比较容易实现。 2. 如何建立迷宫和怎么设置迷宫的问题：首先迷宫要有一定的范围怎么才 能让迷宫有序的进行，于

13、是我将迷宫的外围和障碍设置为 0，所有的可走路径设 置为 1，这样迷宫就清晰可见。 3. 如何去寻找路径问题 ：这是整个程序的核心。通过查找书籍得到了一个 算法：若当前位置“可通” ，则纳入当前路径，并继续朝下一位置搜索，即切换 下一位置为当前位置，如此重复到达出口；若不可通，就退回到前一通道，然后 继续寻找其他方向；若均不可通，则删除此路径。 4. 界面问题：这里就是运用了 switch(n)语句来实现的，这样增加了程序的 实用性。 沈阳航空航天大学课程设计报告 12 4.2 程序执行过程程序执行过程 系统使用说明： 1出现界面后选择 1，进行迷宫大小的设计（这里设计 3*3 大小的）：如图

14、 4.1 所示 图 4.1 2. 然后选择 2，开始设计迷宫的内部：如图 4.2 所示 图 4.2 3.选择 3，观察设计的是否满足你的要求：如图 4.3 所示 沈阳航空航天大学课程设计报告 13 图 4.3 4.选择 4，输入迷宫的起点和终点：如图 4.4 所示 图 4.4 5.选择 5，查看结果（路径由 1.2.3.4.5 表示出来）：如图 4.5 所示 沈阳航空航天大学课程设计报告 14 图 4.5 6选择 0，退出程序。 沈阳航空航天大学课程设计报告 15 参考文献参考文献 1 严蔚敏，吴伟民. .数据结构m.北京：清华大学出版社，2007. 2 胡圣荣, 周霭如, 罗穗萍.数据结构教

15、程与题解m.北京：清华大学出版社， 2011. 3 谭浩强. .c 程序设计m.北京：清华大学出版社，2005. 4 袁平波.数据结构实验指导m.合肥：中国科学技术大学出版社.2010. 5 殷人昆.数据结构m.北京：清华大学出版社.2011. 6 宁正元.算法与数据结构习题精解和实验指导m.北京. 清华大学出版社. 2007. 7 陈媛.算法与数据结构.第 2 版m.北京. 清华大学出版社.2011. 沈阳航空航天大学课程设计报告 16 附附 录（关键部分程序清单）录（关键部分程序清单） 程序代码程序代码 #include #include #include #include / 迷宫坐标位

16、置类型 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; / 当

17、前足迹,初值为 1 #define stack_init_size 10/ 存储空间初始分配量 #define stackincrement 2/ 存储空间分配增量 / 栈的顺序存储表示 typedef struct sqstack selemtype *base;/ 在栈构造之前和销毁之后，base 的值为 null selemtype *top;/ 栈顶指针 int stacksize;/ 当前已分配的存储空间，以元素为单位 sqstack; / 顺序栈 沈阳航空航天大学课程设计报告 17 /构造一个空栈 s int initstack(sqstack *s) / 为栈底分配一个指定大小的

18、存储空间 (*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; else return 0; /插入元素 e 为新的栈顶元素

19、。 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; r

20、eturn 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,通过路径为足迹 / 当迷宫 m 的 b 点的序号为 1(可通过路径)，return 1; 否则，return 0。 int pass(postype

21、 b) if(mb.xb.y=1) return 1; else return 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.x+=direcdi.x; c.y+=direcdi.y; return c; / 使迷宫 m 的 b 点的序号变为-1(不能

22、通过的路径) 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( curpos=start; do if(pass(curpos) / 当前位置可以通过，即是未曾走到过的通道块 footprint(curpos);

23、/ 留下足迹 e.ord=curstep; e.seat.x=curpos.x; e.seat.y=curpos.y; e.di=0; push( / 入栈当前位置及状态 curstep+; / 足迹加 1 if(curpos.x=end.x curpos=nextpos(curpos,e.di); else / 当前位置不能通过 if(!stackempty(s) pop( / 退栈到前一位置 curstep-; while(e.di=3 / 留下不能通过的标记(-1) pop( / 退回一步 curstep-; if(e.di3) / 没到最后一个方向(北) e.di+; / 换下一个方向

24、探索 push( curstep+;/ 设定当前位置是该新方向上的相邻块 curpos=nextpos(e.seat,e.di); while(!stackempty(s); return 0; / 输出迷宫的结构 void print(int x,int y) 沈阳航空航天大学课程设计报告 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; do system(cls); /清屏函数 printf(

25、 nnn); printf( 1 请输入迷宫的行数,列数(包括外墙)n); printf( 2 请输入迷宫内墙单元数n); printf( 3 迷宫结构如下n); printf( 4 输入迷宫的起点和终点n); printf( 5 输出结果n); printf( 0 退出n); printf(nn 请选择 ); scanf(%d, switch(n) case 1: printf(请输入迷宫的行数,列数(包括外墙)：(空格隔开); scanf(%d%d, 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: printf(请输入迷宫内墙单元数：); scanf(%d, printf(请依次输入迷宫内墙每个单元的行数,列数：(空格隔开)n); for(i=1;i=