《迷宫问题 课程设计》由会员分享，可在线阅读，更多相关《迷宫问题 课程设计（24页珍藏版）》请在金锄头文库上搜索。
1、1目目 录录第一部分第一部分 引言引言第二部分第二部分 课程设计报告课程设计报告第一节 课程设计目的第二节 课程设计内容和要求2.1 问题描述2.2 设计要求第 3 节 课程设计总体方案及分析3.1 问题分析3.2 概要设计3.3 详细设计3.4 测试结果3.5 参考文献第三部分第三部分 课程设计总结课程设计总结附录(源代码)2第一部分第一部分 引言引言数据结构是一门理论性强、思维抽象、难度较大的课程，是基础课和专业课之间的桥梁。该课程的先行课程是计算机基础、程序设计语言、离散数学等，后续课程有操作系统、编译原理、数据库原理、软件工程等。 通过本门课程的学习，我们应该能透彻地理解各种数据对象的
2、特点，学会数据的组织方法和实现方法，并进一步培养良好的程序设计能力和解决实际问题的能力，而且该课程的研究方法对我们学生在校和离校后的学习和工作，也有着重要的意义。数据结构是软件工程专业的一门核心专业基础课程，在该专业的课程体系中起着承上启下的作用，学好数据结构对于提高理论认知水平和实践能力有着极为重要的作用。学习数据结构的最终目的是为了获得求解问题的能力。对于现实世界中的问题，应该能从中抽象出一个适当的数学模型，该数学模型在计算机内部用相应的数据结构来表示，然后设计一个解此数学模型的算法，再进行编程调试，最后获得问题的解答。基于此原因，暑期我们开设了数据结构课程设计。针对数据结构课程的特点，着
3、眼于培养我们的实践能力。实习课程是为了加强编程能力的培养，鼓励学生使用新兴的编程语言。相信通过数据结构课程实践，无论是理论知识，还是实践动手能力，同学们都会有不同程度上的提高。第二部分第二部分 课程设计报告课程设计报告第一节第一节 课程设计目的课程设计目的仅仅认识到栈和队列是一种特殊的线性表是远远不够的，本次实习的目的在于使学生深入了解栈和队列的特征，以便在实际问题背景下灵活运用它，同时还将巩固这种数据结构的构造方法。3第二节第二节 课程设计内容和要求课程设计内容和要求 2.1 问题描述： 迷宫问题是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒子中设置了许多墙
4、，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口走到出口，而不走错一步。老鼠经过多次试验最终学会走通迷宫的路线。设计一个计算机程序对任意设定的矩形迷宫,求出一条从入口到出口的通路，或得出没有通路的结果。2.2 设计要求：要求设计程序输出如下：(1) 建立一个大小为 mm 的任意迷宫（迷宫数据可由用户输入或由程序自动生成），并在屏幕上显示出来；（2）在屏幕上输出迷宫和通路；第三节第三节 课程设计总体方案及分析课程设计总体方案及分析3.1 问题分析：1.迷宫的建立：迷宫中存在通路和障碍，为了方便迷
5、宫的创建，可用 0 表示通路，用 1 表示障碍，#表示墙壁，这样迷宫就可以用 0、1 矩阵来描述，2.迷宫的存储：迷宫是一个矩形区域，可以使用二维数组表示迷宫，这样迷宫的每一个位置都可以用其行列号来唯一指定，但是二维数组不能动态定义其大小，我们可以考虑先定义一个较大的二维数组 mazeM+2M+2,然后用它的前 m 行 m 列来存放元素，即可得到4一个 mm 的二维数组，这样(0,0)表示迷宫入口位置，(m-1,m-1)表示迷宫出口位置。注：其中 M，M 分别表示迷宫最大行、列数，本程序 M 的最大值为 9，当然用户也可根据需要，调整其大小。3.迷宫路径的搜索：首先从迷宫的入口开始，如果该位置
6、就是迷宫出口，则已经找到了一条路径，搜索工作结束。否则搜索其上、下、左、右位置是否是障碍，若不是障碍，就移动到该位置，然后再从该位置开始搜索通往出口的路径；若是障碍就选择另一个相邻的位置，并从它开始搜索路径。为防止搜索重复出现，则将已搜索过的位置用函数进行判断和标记，同时保留搜索痕迹，在考虑进入下一个位置搜索之前，将当前位置保存在一个队列中，如果所有相邻的非障碍位置均被搜索过，且未找到通往出口的路径，则表明不存在从入口到出口的路径。这实现的是广度优先遍历的算法，如5果找到路径，则最短路径。搜索算法流程图如下所示：3.2 概要设计1.构建一个二维数组 mazeM+2M+2用于存储迷宫矩阵自动或手
7、动生成迷宫，即为二维数组 mazeM+2M+2赋值构建一个队列用于存储迷宫路径6建立迷宫节点,用于存储迷宫中每个节点的访问情况实现搜索算法屏幕上显示操作菜单2.本程序包含 12 个函数：(1)主函数 main()(2)Status InitStack(SqStack /创建一个空栈 S(3)Status Push(SqStack /插入新元素 a(4)Status Pop(SqStack /删除栈顶元素，a 返回其值(5)Status StackEmpty(SqStack S);/检查是否空栈(6)Status MazePath(int maze1212,SqStack /找通路(7)void
8、 Initmaze(int maze1212,int size); /初始化迷宫(8)void printmaze(int maze1212,int size); /显示迷宫(9)Status Pass(int maze1212,PosType CurPos); /判断当前位置是否可通(10)void Markfoot(int maze1212, PosType CurPos); /标记当前位置不可通(11)PosType NextPos(PosType CurPos, int Dir); /进入下一位置(12)void printpath(int maze1212,SqStack S,int
9、 size); /显示通路3.3 详细设计程序设计的基本思想，原理和算法描述：此算法最大的优点是支持图形化输入与输出，观察效果好 迷宫求解问题主要运用了堆栈的性质 求迷宫中一条从入口到出口的路径的算法描述： do 若当前位置可通 则 将当前位置插入栈顶;若该位置时出口位置，则结束 ；否则切换当前位置为东邻方块为新的当前位置;7否则若栈不空且栈顶位置尚有其他方向未经探索，则设定新的当前位置为沿顺时针方向旋转的栈顶位置的下一相邻模块若栈不空但栈顶位置的四周均不可通则 删去栈顶位置;若栈不空，则重新测试新的栈顶位置直至找到一个可通的相邻模块或出栈至栈空 ；while(栈不空)实现的函数为/*若迷宫
10、maze 中从入口 start 到出口 end 的通道，则求得一条存放在栈中 */Status MazePath(int maze1212,SqStack int curstep;SElemType e;8InitStack(S);curpos = start; / 设定“当前位置“为“入口位置curstep = 1; / 探索第一步do if (Pass(maze,curpos) / 当前位置可通过，即是未曾走到过的通道块 Markfoot(maze,curpos); / 留下足迹e.di =1;e.ord = curstep;e.seat= curpos;Push(S,e); / 加入路径
11、if (curpos.row=end.row / 到达终点（出口）curpos = NextPos(curpos, 1); / 下一位置是当前位置的东邻curstep+; / 探索下一步 else / 当前位置不能通过if (!StackEmpty(S) 9Pop(S,e);while (e.di=4 / 留下不能通过的标记，并退回一步Pop(S,e); if (e.diseat.rowp-seat.line=2; /标记为路径中的点p+;然后显示通路时只要等于 2 的地方就打印一个 0，否则打印空格。 if(mazeij=2) printf(“%c “,0);else printf(“ “)
12、;4.进入下一位置PosType NextPos(PosType CurPos, int Dir); /进入下一位置时按顺时针方向/向下一位置探索5.堆栈操作，包括创建，入栈，出栈，判空。Status InitStack(SqStack /创建一个空栈 SStatus Push(SqStack /插入新元素 aStatus Pop(SqStack /删除栈顶元素，a 返回其值Status StackEmpty(SqStack S); /检查是否空栈3.3 测试结果BuildLog-Configuration:BuildLog-Configuration: 迷宫求解迷宫求解 - - Win32W
13、in32 Debug-Debug-13CommandCommand LinesLinesResultsResults迷宫求解迷宫求解.exe.exe - - 0 0 error(s),error(s), 0 0 warning(s)warning(s)错误输入错误输入正确路径正确路径143.5 参考文献1. 谭浩强 M. 北京：清华大学出版社， 2006.2. 严蔚敏 M. 北京：清华大学出版社 3. 王华 , 叶爱亮 等 .M. 北京：机械工业出版社 4. 钱新贤 ,程兆炜等 . M. 北京：人民邮电出版社，2000. 第三部分第三部分 课程设计总结课程设计总结通过这段时间的课程设计，本人对软件专业的应用，数据结构的作用以及 C 语言的使用都有了更深的了解。尤其是 C 语言的进步让我深刻的感受到任何所学的知识都需要实践，没有实践就无法真正理解这些知识以及掌握它们，使其成为自己的财富。在理论学习和上机实践的各个环节中，通过自主学习和请教老师，我收获了不少。当然也遇到不少的问题，也正是因为这些问题引发的思考给我带了收获。从当初不喜欢上机写程序到现在能主动写程序，15从当初拿着程序不只如何下手到现在知道如何分析问题，如何
