C语言程序设计走迷宫游戏程序设计.pdf

课程设计报告 设计题目：迷宫游戏 学生姓名：专业班级：计算机科学与技术 学 号：指导教师：完成日期：目 录 第 1 章 绪论.3 1.1 课程设计选题的目的.3 1.2 课程设计选题的背景和意义.3 1.2.1 课程设计的背景.3 1.2.2 课程设计的意义.3 1.3 课题研究的主要内容.3 第 2 章 系统需求分析.4 2.1 输入/输出形式和输出值的范围.4 2.1.1 输入/输出形式的范围.4 2.1.2 输出值的范围.4 2.2 程序功能.4 第 3 章 概要设计.4 3.1 设计思想.4 3.2 实现方法.4 3.3 函数间的关系.5 第 4 章 详细设计.5 4.1 实现定义的数据类型.5 4.2 实现定义操作伪代码算法.5 第 5 章 问题描述及解决方案.6 5.1 问题描述.6 5.2 问题的解决方案.6 第 6 章 测试并列出测试结果.7 第 7 章 总 结.8 7.1 设计体会.8 7.1.1 系统的优点.8 7.1.2 本系统的不足.8 7.1.3 可改进的地方.8 7.2 结束语.9 致 谢.9 参考文献.9 附 录.10 第 1 章 绪论 1.1 课程设计选题的目的 为大家解决一些生活中实际的问题，在这个过程中，自身的能力也在不断地提高。此次程序设计综合运用所学知识解决实际问题，将课堂的书本知识有效的在程序中体现出来，让学生更理解 C+功能之强大，进一步让学生对面向对象的方法以及 C+的编程思想有较好的了解和认识。此外，此次设计培养独立开发、设计、调试、运行程序的能力，激发学生较强的自学兴趣，锻炼学生之间以及学生与老师的沟通能力，培养学生之间的合作精神，让彼此更好的认识到合作的重要性，使学生在今后的学习中加强对合作精神的培养。1.2 课程设计选题的背景和意义 1.2.1 课程设计的背景 儿童智力游戏的一种，同时也锻炼人的思维能力。当我们在一个迷宫中时怎样避免重复的走一些路，避免怎样走投无路，无路可走，什么样的迷宫可走，怎样就知道迷宫无出口了，通过回溯法帮我们解答，动脑子想办法，看看计算机是怎么实现以最快的方式走出你设的迷宫的。1.2.2 课程设计的意义 一般来说，课程设计要比教学实验复杂一些，涉及的深度深，而且更加实用些。其目的是通过课程设计的综合训练，培养学生分析解决实际问题和编程等动手能力，最终目标是想通过这种形式，帮助学生系统掌握 C+这门课程的主要内容，使老师更好的完成教学任务。结合实际应用的要求，使课程设计既覆盖教学所要求的知识点，又接近工程的实际需要，训练自己实际分析问题和解决问题以及编程的能力。通过详细的实例分析，循环渐进的描述，启发学生顺利的完成设计。课程设计将设计要求、需求分析、算法设计、编程和实例测试运行分开，为学生创造分析问题、独立思考的条件。只要学生在吃透要求和算法的前提下，完全可以不按书中提示的参考程序，自己设计出更具有特色的程序。1.3 课题研究的主要内容 要求完成构造迷宫，输入入口出口，输出迷宫路径。功能要求如下：1构建迷宫：可以系统构建，也可以用户自己构建，输入 1 为不通，输入 0 为通路。显示构建好的迷宫。2输出路径：输入入口与出口，利用编好的函数对迷宫进行试探，有路径输出路径，无路径提示用户此迷宫无出口。3最短路径：输出走出此迷宫的最短路径，即不用走回头路的一条路径。4要求系统有一定的容错性，给用户必要的提示。第 2 章 系统需求分析 2.1 输入/输出形式和输出值的范围 2.1.1 输入/输出形式的范围 迷宫中建立数组时，首先输入迷宫的行数和列数。边围规定为 1，在程序中已赋值，内围用 0、1 输入，不用其他的数字，若输入错误会提示重新输入；然后选择系统创建的迷宫还是自己创建迷宫，输入选项 1 或 2（输入其他选项按 2 处理）；迷宫创建好后，输入入口和出口坐标（入口必须为通路即 0，否则系统会报错，重新输入），找到路径或无路径；接下来会提示寻找其他路径还是退出此迷宫，输入 1 或 2 进行选择；选择 1，则继续输入迷宫入口和出口，选择 2 或其他，则退出。若还想创建别的迷宫就在接下来输入 y 或 Y，输入其他则退出程序。2.1.2 输出值的范围 在迷宫设计中若输入出口超出迷宫大小，即为无路径；输出无限制。2.2 程序功能 在迷宫问题中，可由操作者自己设定迷宫大小，迷宫内部构造有两个选择，系统设计，节省时间，也可由操作者自己设计，迷宫入口和出口并能保证入口为通路，若有路径会显示其路径并显示最短路径。一个迷宫有不同入口和出口，可寻求多条路径。第 3 章 概要设计 3.1 设计思想 迷宫中用回溯法从八个方向向前试探，用队列保存探测到的通路，建立一个数组模拟迷宫，将各个函数结合在一起。3.2 实现方法 迷宫中定义 move 数组，从东顺时针探测；进队出队完成探测；自己创建 maze 数组，并输入入口点和出口点，再进行计算。3.3 函数间的关系 第 4 章 详细设计 4.1 实现定义的数据类型（1）迷宫数组定义为结构体包含两个整型数据，迷宫出口和入口的值定义为整型。（2）迷宫内部的设计时各坐标点设置成栈内整型。（3）迷宫中求最短路径时定义结构体类型表示队列，包含整型坐标点，和整型下标；又有整型的队首尾指针。4.2 实现定义操作伪代码算法 求一般路径伪代码：while(栈不空)栈顶元素=(x,y,d)出栈;求出下一个要试探的方向 d+;while(还有剩余试探方向)创建迷宫 寻找路径 最短路径 main 恢复迷宫 结束 输入其他入口出口 创建其他迷宫 if(d 方向可走)(x,y,d)入栈;求新点坐标(i,j);将新点(i,j)切换成当前点(x,y);if(x,y)=(m,n)结束;else 重置 d=0;else d+;求解最短路径伪代码：(x,y)入队;while(队列不为空)队首元素出队;for(方向为 0;方向总方向数;改变方向)到达点坐标;if(此坐标点为通路)入队;if(到达出口点)输出路径;恢复迷宫;当前点搜索完，取下一点搜索;第 5 章 问题描述及解决方案 5.1 问题描述 方向设置，路径存储，迷宫图的存储，路径的求解，出口入口的设置。5.2 问题的解决方案 迷宫问题中，采用 move 数组存储方向，采用二维数组存储迷宫图，采用栈存储路径，采用队列算出最短路径，参数传递出口入口和迷宫的大小。第 6 章 测试并列出测试结果 第 7 章 总 结 7.1 设计体会 7.1.1 系统的优点 迷宫问题中，突出优点为采用了时间随机函数，系统自动生成迷宫，节约用户时间。此外，用两种不同的存储方式（栈和队列）对迷宫进行探究。界面清晰、通俗易懂、操作简便、结构严谨、逻辑习惯强。7.1.2 本系统的不足 对于迷宫问题，输入迷宫内部结构时，输入形式为 0、1 空格或回车，输入形式有误时，会使程序无法运行下去，有时还会进入死循环。输入入口坐标时，没有容错，若大于迷宫规模，程序会出错。7.1.3 可改进的地方（1）各个菜单界面可以设计的更为美观，更简洁易懂。（2）可以从各个方面考虑设置容错机制使程序更健壮。7.2 结束语 课程设计中感受到自己知识的匮乏，需要学习的东西很多，不能总是局限于书本，在课程设计中出现问题时，应该及时与周围同学交流，多交流才能使学到的东西更深入到心里，总之，这是一次不错的锻炼，专业水平不说能提高什么，但在过程中学到的学习方法应该是能受益终生的！致 谢 在心里总是想感谢几个人，在课程设计过程中，由于自己时间安排不当与专业基础知识的不扎实，课程设计的时间总是感觉不够，在课程设计中也遇到了很多困难，好多时候都想止步不前，但因为有身边的这群人，帮助我度过难关，有的鼓励我，有的引导我，我也渐渐放平心境，学会怎么去思考，怎么去解决遇到的问题，怎么让程序运行起来，其实我们都是学生，但是他们比我做的好，我应该向他们学习，学习面对困难的态度与理智，学习坚韧的品行课程设计结束了，但感觉收获了很多，不仅仅是任务完成了，更让我了解到身边这群值得我珍惜的朋友是多么的难得。这仅仅是一个小小的课程设计，以后还要面对各种各样的更大的困难与逆境，只要坚持，找到正确的方法，相信一切都会克服的。参考文献 1周霭如、林伟健 C+程序设计基础 电子工业出版社 2Mark Allen Weiss 数据结构与算法分析 C+描述 人民邮电出版社 3严蔚敏、吴伟民 数据结构 C 语言版 清华大学出版社 5姚伯元 课程设计(论文)规范化管理与培养学生综合素质 中国高等教育网教学研究 6朱明方、吴及 数据结构教程 机械工业出版社 附 录#include#include#include#include#include using namespace std;typedef struct int x,y;item;typedef struct int x,y,d;Datetype;typedef stack stack_int;void path(int*maze,int,int,int,int);void printpath();#define NUM 100 /队列大小；typedef struct int x,y;/所到点的坐标；int pre;/前驱点的下标；SqType;/队列；int front,rear;/队首指针与队尾指针；void printpath(SqType sq,int)/打印路径 int i;i=rear;do i=sqi.pre;/回溯；while(i!=-1);void restore(int*maze,int m,int n)/恢复迷宫 for(int i=1;i=m;i+)for(int j=1;j=n;j+)if(mazeij=-1)mazeij=0;int path1(int*maze,int m,int n,int c,int d,int x1,int y1)/最短路径 /m,n 为迷宫的长和宽，c，d 为迷宫入口坐标，x1，y1 为迷宫出口坐标；maze 为迷宫；item move8=0,1,1,1,1,0,1,-1,0,-1,-1,-1,-1,0,-1,1;/坐标增量数组；SqType sqNUM;int x,y,i,j,v;front=rear=0;sq0.x=c;sq0.y=d;sq0.pre=-1;if(mazecd=0)mazecd=-1;/入口点入队；else goto G;while(front=rear)/队列不为空 x=sqfront.x;y=sqfront.y;for(v=0;v8;v+)i=x+movev.x;j=y+movev.y;if(mazeij=0)rear+;sqrear.x=i;sqrear.y=j;sqrear.pre=front;mazeij=-1;/访问过的坐标点，入队；if(i=x1&j=y1)最短路径为：最短路径为：printpath(sq,rear);/输出路径；restore(maze,m,n);/恢复迷宫；return 1;/for v;front+;/当前点搜索完，取下一个点搜索 /while/while 无路径。无路径。return 0;void path(int*maze,int a,int b,int m,int n)item move8=0,1,1,1,1,0,1,-1,0,-1,-1,-1,-1,0,-1,1;stack_int st;Datetype temp;int x,y,d,i,j;进口输入有误。进口输入有误。temp.x=a;temp.y=b;temp.d=-1;/初始化入口点坐标及方向；st.push(temp);while(!st.empty()temp=st.top();st.pop();x=temp.x;y=temp.y;d=temp.d+1;while(d8)i=x+moved.x;j=y+moved.y;if(mazeij=0)/该点可到达；temp.x=x;temp.y=y;temp.d=d;/坐标及方向；st.push(temp);/坐标及方向入栈；x=i;y=j;mazexy=-1;/到达新点；if(x=m&y=n)迷宫路径为迷宫路径为 Datetype t;while(!st.empty()t=st.top();st.pop();/输出路径；coutmn;int*maze=new int*m+2;for(i=0;i=m+1;i+)mazei=new intn+2;/申请迷宫的空间；for(i=0;i=m+1;i+)mazei0=1;for(i=0;i=n+1;i+)maze0i=1;for(i=0;i=m+1;i+)mazein+1=1;for(i=0;is;srand(time(0);/系统时间随机函数；for(i=1;i=m;i+)for(j=1;j=n;j+)mazeij=rand()%2;/随机赋值 maze11=0;/(1,1)点为可通过点；mazemn=0;/(m,n)点为可通过点；else 请输入迷宫：请输入迷宫：行行列列输入必须为0 或 1；for(i=1;i=m;i+)/输入第 i 行迷宫的构造；for(j=1;jmazeij;A:if(mazeij!=0&mazeij!=1)请再次输入：请再次输入：cinmazeij;goto A;/判错；迷宫如下：迷宫如下：显示用户输入的迷宫；for(i=0;i=m+1;i+)for(j=0;j=n+1;j+)coutijcd;path(maze,i,j,c,d);/调用路径函数，输出路径；coutendl;/格式设置；restore(maze,m,n);/恢复迷宫；path1(maze,m,n,i,j,c,d);/输出最短路径；coutl;if(l=1)restore(maze,m,n);/恢复迷宫；goto H;else return;/跳出此函数；void main()do 欢迎到达迷宫界面欢迎到达迷宫界面 printpath();couts;