数据结构课程设计报告

课程设计说明书课程名称：数 据 结 构 与 算法专业：软件工程班级：15-2：xx学号：2xxxxxx2指导教师：xx完成日期：2017年1月3日下载可编辑任 务 书题目：老鼠走迷宫设计容及要求：1. 课程设计任务容程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间走到粮仓处。2.课程设计要求1)老鼠形象可辨认，可用键盘操纵老鼠上下左右移动；2)迷宫的墙足够结实，老鼠不能穿墙而过；3)正确检测结果，若老鼠在规定时间走到粮仓处，提示成功，否则提示失败；4)添加编辑迷宫功能，可修改当前迷宫，修改容：墙变路、路变墙；5)找出走出迷宫的所有路径，以及最短路径；6)利用序列化功能实现迷宫地图文件的存盘和读出等功能。开发环境：QT Creator、 QT5.6.专业.整理.下载可编辑目 录1.引 言32.课题分析43.具体设计过程53.1 设计思路53.2 程序设计流程图53.3.函数实现说明64.程序运行结果85.软件使用说明126.结论13参 考 文 献13.专业.整理.下载可编辑1.引 言课程设计是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的、必不可少的一个教学环节。通常，课程设计中的问题比平时的习题复杂的多，也更接近实际。课程设计着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另一方面，能使书上的知识变“活”，起到深化理解和灵活掌握教学容的目的。平时的习题较偏重于如何编写功能单一的“小”算法，局限于一个或两个知识点，而课程设计题是软件设计的综合训练，包括问题分析，总体结构设计，用户界面设计、程序设计基本技能和技巧，多人合作，以至一整套软件工作规的训练和科学作风的培养。此外，还有很重要的一点是：计算机是比任何教师更严厉的检查者。为达到上述目的，使学生更好地掌握程序设计的基本方法和 C+语言的应用，本课程安排了课程设计环节，提供了各类题目供学生选择。每个设计题采取了统一的格式，由问题描述、基本要求、测试数据、实现提示和选做容等五个部分组成。问题描述旨在为学生建立问题提出的背景，指明问题“是什么”。基本要求则对问题进一步求精，划出问题的边界，指出具体的参量或前提条件，并规定该题的最低限度要求。测试数据部分旨在为检查学生上机作业提供方便。在实现提示部分，对实现中的难点及其解法思路等问题作了简要提示，提示的实现方法未必是最好的，学生不应拘泥与此，而应努力设计和开发更好的方法和结构。选做部分向那些尚有余力的读者提出了更高的要求，同时也能开拓其它读者的思路，在完成基本要求时就力求避免就事论事的不良思想方法，尽可能寻求具有普遍意义的解法，使得程序结构合理，容易修改、扩充和重用。.专业.整理.下载可编辑2.课题分析编写一个老鼠走迷宫的C+程序，包括以下功能：初始状态：迷宫处为空白，输入长宽设定迷宫大小，时间剩余为300s。具体要求如下：1. 点击生成迷宫，窗口左上方生成一个指定大小的迷宫，老鼠位于迷宫中央，粮仓位于迷宫右下角，开始计时。2. 可以通过键盘上的方向键控制老鼠移动。3. 点击显示路径按钮时，显示一条绿色的通道通向粮仓。4. 点击最短路径按钮时，显示一条绿色的通道（最短）通向粮仓。5. 点击拆墙/补墙时，老鼠可在迷宫自由移动，老鼠所走过的墙将变成路/路将变成墙。6. 点击取消作弊，恢复原始状态。即老鼠只能通过路。7. 当剩余时间为0时，弹出对话框，游戏失败，游戏结束。8. 当老鼠走到粮仓处时，弹出对话框，找到出口，游戏结束。9. 点击储存地图时，将当前地图以矩阵形势存于文件中；点击读取地图时，将文件中的数据赋予迷宫矩阵，创建迷宫。.专业.整理.下载可编辑3.具体设计过程3.1 设计思路定义迷宫节点，包含x，y（坐标）与 state（0为墙，1为通路），使用迷宫节点矩阵表示迷宫，使用回溯法创建迷宫节点矩阵。利用深度优先遍历寻找出老鼠到粮仓的所有路径，利用广度优先遍历寻找老鼠到粮仓的最短路径，将路径中的节点的 state 置为2，在普通模式下，老鼠仅可通过 state 为1的节点，当作弊模式开启时，老鼠可通过任意 state 的节点并且通过的节点的 state 值会相应的改变。打印迷宫时，state 为0的节点使用黑色矩形填充，state 为1的节点不填充，state 为2的使用绿色矩形填充。3.2 程序设计流程图_maze /迷宫节点box /路径节点box1 /最短路径节点int i;int i;int i;int j;int j;int j;int state;int direction;int pre;int num;class mazepublic:void paintEvent(QPaintEvent *);void keyPressEvent(QKeyEvent *);bool isOdd();/判断 lineedit 输入是否为奇数void creatMaze();/创建迷宫void findWay();/寻求路径（深度遍历）void findShortWay();/寻求最短路径（广度遍历）private:QTime _time;_maze *matrix; /定义一个迷宫节点数组stack *MazeStack; /定义一个栈用于存放迷宫节点 vector *FinalPath; /定义一个向量用于存放迷宫路径 stack *BoxStack; /定义一个栈用于存放寻路节点 queue *Box1Queue; /定义一个队列用于存放寻最短路节点 stack *Box1Stack; /定义一个栈用于存放寻最短路节点 int M; /迷宫矩阵的行.专业.整理.下载可编辑int N; /迷宫矩阵的列bool first;bool remove_wall; /判断是否进行拆墙bool repair_wall; /判断是否补墙/老鼠的坐标int X;int Y;private slots:void on_way_clicked();void on_shortway_clicked();void on_removewall_clicked();void on_cancelremove_clicked();void on_makemaze_clicked();void timerUpdate();void on_repairwall_clicked();void on_savemaze_clicked();void on_readmaze_clicked();3.3.函数实现说明(1) void keyPressEvent(QKeyEvent *e) 功能：实现使用键盘完成对老鼠的控制。(2) void paintEvent(QPaintEvent *) 功能：打印迷宫、路径、老鼠和粮仓。(3) void creatMaze(); 功能：生成迷宫使用算法：回溯法、栈(4) void findWay();.专业.整理.下载可编辑功能：寻找从老鼠到粮仓的路径。使用算法：深度优先遍历(5) void findShortWay();功能：寻找从老鼠到粮仓的最短路径。使用算法：广度优先遍历、队列(6) void timerUpdate();功能：更新剩余时间，当剩余时间为 0 时游戏结束。.专业.整理.下载可编辑4.程序运行结果1.初始状态2.点击生成迷宫，生成一个默认大小为25*25的迷宫.专业.整理.下载可编辑3.点击寻找路径4.点击最短路径.专业.整理.下载可编辑5.点击作弊拆墙（补墙）.专业.整理.下载可编辑6.存储迷宫7.读取迷宫.专业.整理.下载可编辑7. 时间耗尽时5.软件使用说明1.输入的长宽只能是奇数2.点击生成迷宫即可开始新的游戏3.该程序有一个局限性：只能存储一个迷宫，相应的，读取迷宫也只能读取上次存储的而不能选择。.专业.整理.下载可编辑6.结论课程设计是培养学生综合运用所学知识 ,发现,提出,分析和解决实际问题,锻炼实践能力的重要环节,是对我们的实际工作能力的具体训练和考察过程.随着科学技术发展的日新月异，当今计算机应用在生活中可以说得是无处不在。因此作为二十一世纪的大学来说掌握程序开发技术是十分重要的，而 C+语言又是最常见，功能最强大的一种高级语言，因此做好 C+语言课程设计是十分必要的。回顾起此次课程设计，至今我们仍感慨颇多，的确，自从拿到题目到完成整个编程，从理论到实践，在整整半个月的日子里，可以学到很多很多的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我们懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到问题，可以说得是困难重重，这毕竟第一次做的，难免会遇到过各种各样的问题，同时在设计的过程中发现了自己的不足之处，对一些前面学过的知识理解得不够深刻，掌握得不够牢固，比如说结构体，指针，链表通过这次课程设计之后，我们把前面所学过的知识又重新温故了一遍。参 考 文 献C+程序设计（第三版） C+ Primer Plus(第 6 版) QT 从入门到精通.专业.整理.下载可编辑数据结构与算法附录（源代码）maze.h#ifndef MAZE_H#define MAZE_H#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;struct _maze /定义迷宫节点，x、y 代表坐标，state 代表是否为墙int i;int j;int state; /0代表为墙，1 代表通路;.专业.整理.下载可编辑struct box /定义寻求路径节点int i;int j;int direction; /方向，0 上 1 右 2 下 3 左;struct box1 /定义寻求最短路径节点int i;int j;int pre;int num;namespace Ui class maze;class maze : public QWidgetQ_OBJECTpublic:explicit maze(QWidget *parent = 0);maze();void paintEvent(QPaintEvent *);void keyPressEvent(QKeyEvent *);bool isOdd();/判断 lineedit 输入是否为奇数void creatMaze();/创建迷宫void findWay();/寻求路径（深度遍历）void findShortWay();/寻求最短路径（广度遍历）private slots:void on_way_clicked();void on_shortway_clicked();void on_removewall_clicked();void on_cancelremove_clicked();void on_makemaze_clicked();void timerUpdate();void on_repairwall_clicked();private:Ui:maze *ui;QTime _time;.专业.整理.下载可编辑_maze *matrix; / 定义一个迷宫节点数组stack *MazeStack; /定义一个栈用于存放迷宫节点vector *FinalPath; /定义一个向量用于存放迷宫路径stack *BoxStack;/定义一个栈用于存放寻路节点queue *Box1Queue; /定义一个队列用于存放寻最短路节点stack *Box1Stack; /定义一个栈用于存放寻最短路节点int M; /迷宫矩阵的行int N; /迷宫矩阵的列bool first;bool remove_wall; /判断是否进行拆墙bool repair_wall; /判断是否补墙/老鼠的坐标int X;int Y;#endif / MAZE_Hmaze.cpp#include maze.h#include ui_maze.hmaze:maze(QWidget *parent) :QWidget(parent),ui(new Ui:maze)ui-setupUi(this);QTimer *time0 = new QTimer(this);connect(time0,SIGNAL(timeout(),this,SLOT(timerUpdate();time0-start(1000);first=true;M=11;N=11;matrix=new _maze*M;for(int i=0;iM;i+)matrixi=new _mazeN;for(int i=0;iM;i+)for(int j=0;jN;j+)matrixij.state=0;/初始化迷宫矩阵，将所有节点设置为墙matrixij.i=i;matrixij.j=j;/随机生成种子数.专业.整理.下载可编辑QTime time=QTime:currentTime();qsrand(time.msec()+time.second()*1000);MazeStack = new stack;FinalPath = new vector;BoxStack = new stack;Box1Stack = new stack;Box1Queue = new queue;X = 1;Y = 1;remove_wall=false;repair_wall=false;maze:maze()delete ui;void maze:keyPressEvent(QKeyEvent *e)if(remove_wall)/如果拆墙if(e-key()=87|e-key()=16777235)/上if(X1)matrixXY.state=1;X=X-1;else if(e-key()=83|e-key()=16777237)/下if(Xkey()=65|e-key()=16777234)/左if(Y1)matrixXY.state=1;Y=Y-1;.专业.整理.下载可编辑else if(e-key()=68|e-key()=16777236)/ 右if(YN-2)matrixXY.state=1;Y=Y+1;/当老鼠到达粮仓时，重新构建迷宫地图，使得存放路劲的容器置为空if(X=M-2&Y=N-2)QMessageBox:information(this,Reminder,Find the exit!,QMessageBox:Yes); for(int i=0;iM;i+)for(int j=0;jcreatMaze();remove_wall=false;repair_wall=false;ui-cancelremove-setEnabled(false);ui-removewall-setEnabled(true);ui-repairwall-setEnabled(true);ui-way-setEnabled(true);ui-shortway-setEnabled(true);ui-makemaze-setEnabled(true);FinalPath-clear();X=M/2;Y=N/2;if(X%2=0)X+=1;if(Y%2=0)Y+=1;_time.restart();else if(repair_wall)/如果拆墙if(e-key()=87|e-key()=16777235)/上if(X1)matrixXY.state=0;X=X-1;.专业.整理.下载可编辑else if(e-key()=83|e-key()=16777237)/ 下if(Xkey()=65|e-key()=16777234)/ 左if(Y1)matrixXY.state=0;Y=Y-1;else if(e-key()=68|e-key()=16777236)/ 右if(YN-2)matrixXY.state=0;Y=Y+1;/当老鼠到达粮仓时，重新构建迷宫地图，使得存放路劲的容器置为空if(X=M-2&Y=N-2)QMessageBox:information(this,Reminder,Find the exit!,QMessageBox:Yes); for(int i=0;iM;i+)for(int j=0;jcreatMaze();remove_wall=false;repair_wall=false;ui-cancelremove-setEnabled(false);ui-repairwall-setEnabled(true);ui-removewall-setEnabled(true);ui-way-setEnabled(true);ui-shortway-setEnabled(true);ui-makemaze-setEnabled(true);FinalPath-clear();X=M/2;Y=N/2;if(X%2=0)X+=1;.专业.整理.下载可编辑if(Y%2=0)Y+=1;_time.restart();elseint k;if(e-key()=87|e-key()=16777235)/上k=X-1;if(k0&matrixkY.state!=0)X=k;else if(e-key()=83|e-key()=16777237)/下k=X+1;if(kkey()=65|e-key()=16777234)/左k=Y-1;if(k0&matrixXk.state!=0)Y=k;else if(e-key()=68|e-key()=16777236)/右k=Y+1;if(kN-1&matrixXk.state!=0)Y=k;if(X=M-2&Y=N-2)QMessageBox:information(this,Reminder,Find the exit!,QMessageBox:Yes); for(int i=0;iM;i+)for(int j=0;jcreatMaze();FinalPath-clear();X=M/2;Y=N/2;if(X%2=0)X+=1;if(Y%2=0)Y+=1;.专业.整理.下载可编辑_time.restart();update();void maze:paintEvent(QPaintEvent *) /画出迷宫QPainter painter(this);painter.setPen(Qt:black);for(int i=FinalPath-size()-1;i=0;i-)matrixFinalPath-at(i).iFinalPath-at(i).j.state=2; if(FinalPath-at(i).i=X&FinalPath-at(i).j=Y) /当老鼠经过寻找迷宫路径时，使得 state=1 matrixFinalPath-at(i).iFinalPath-at(i).j.state=1;FinalPath-pop_back();if(!first)for(int i=0;iM;i+)for(int j=0;jxline-text().toInt()%2=0|ui-yline-text().toInt()%2=0)return false;return true;void maze:timerUpdate()/更新时间，时间为 0 时游戏结束int time1 = 300;if (time1-(_time.elapsed()/1000) 0)QMessageBox:information(this,Time Out!,Game over!,QMessageBox:Yes); for(int i=0;iM;i+)for(int j=0;jcreatMaze();FinalPath-clear();X=M/2;Y=N/2;if(X%2=0)X+=1;if(Y%2=0)Y+=1;_time.restart();QString runTime = QString:number(time1-(_time.elapsed()/1000); ui-timer-setText(runTime);/创建迷宫节点矩阵(回溯法)void maze:creatMaze()/先设置初始点为(3,3)int i=3,j=3;/设置随机数.专业.整理.下载可编辑int randNum=0;/设置迷宫节点矩阵初始点位置为通路matrixij.state=1;/定义一个临时节点_maze temp;temp.i=i;temp.j=j;temp.state=1;/false 表示访问的方向，bool Up=false;bool Down=false;bool Right=false;bool Left=false;/进入循环，不断生成迷宫矩阵，直至栈为空while(1)temp.i=i;temp.j=j;randNum=qrand()%4;switch(randNum)case 0:/上if(!Up&i2&matrixi-2j.state=0)MazeStack-push(temp);matrixi-2j.state=1;matrixi-1j.state=1;i=i-2;Up=false;Down=false;Right=false;Left=false;elseUp=true;break;case 1:/下if(!Down&ipush(temp);matrixi+2j.state=1;matrixi+1j.state=1;i=i+2;Up=false;Down=false;Right=false;.专业.整理.下载可编辑Left=false;elseDown=true;break;case 2:/ 左if(!Left&j2&matrixij-2.state=0)MazeStack-push(temp);matrixij-2.state=1;matrixij-1.state=1;j=j-2;Up=false;Down=false;Right=false;Left=false;elseLeft=true;break;case 3:/ 右if(!Right&jpush(temp);matrixij+2.state=1;matrixij+1.state=1;j=j+2;Up=false;Down=false;Right=false;Left=false;elseRight=true;break;if(Up&Down&Right&Left)/ 如果当前访问节点四个方向都没有可拆的节点，回溯if(!MazeStack-empty()i=MazeStack-top().i;j=MazeStack-top().j;MazeStack-pop();Up=false;Down=false;Right=false;.专业.整理.下载可编辑Left=false;else/ 如果栈为空的话就返回，此时迷宫矩阵已经创建完毕return;/用深度优先遍历的方法寻找路径,将路径数据保存在 FinalPath 容器中void maze:findWay()FinalPath-clear();int i,j,di,find;box box;box.i=X;box.j=Y;box.direction=-1;BoxStack-push(box);matrixXY.state=-1;while(1)i=BoxStack-top().i;j=BoxStack-top().j;di=BoxStack-top().direction;if(i=M-2&j=N-2)/如果当前栈顶为粮仓节点，将路径存放入 FinalPathwhile(!BoxStack-empty()_maze temp;temp.i=BoxStack-top().i;temp.j=BoxStack-top().j;temp.state=1;FinalPath-push_back(temp);BoxStack-pop();return;find=0;while(find=0&ditop().i-1;j=BoxStack-top().j;break;/向上寻路case 1:i=BoxStack-top().i;j=BoxStack-top().j+1;break;/向右寻路case 2:i=BoxStack-top().i+1;j=BoxStack-top().j;break;/向下寻路.专业.整理.下载可编辑case 3:i=BoxStack-top().i;j=BoxStack-top().j-1;break;/ 向左寻路if(matrixij.state=1)find=1;if(find=1)matrixij.state=-1;BoxStack-top().direction=di;box.i=i;box.j=j;box.direction=-1;BoxStack-push(box);elseBoxStack-pop();/用广度优先遍历的方法寻找迷宫路径，寻找的路径是最短路径void maze:findShortWay()FinalPath-clear();while(!Box1Queue-empty()Box1Queue-pop();int i,j,find=0,di,k=0,count=0;box1 box1;_maze temp;box1.i=X;box1.j=Y;box1.pre=-1;box1.num=k;Box1Queue-push(box1);matrixXY.state=-1;while(!Box1Queue-empty()&!find)i=Box1Queue-front().i;j=Box1Queue-front().j;box1.i=i;box1.j=j;box1.num=Box1Queue-front().num;box1.pre=Box1Queue-front().pre;.专业.整理.下载可编辑Box1Stack-push(box1);if(i=M-2&j=N-2)find=1;while(!Box1Stack-empty()temp.i=Box1Stack-top().i;temp.j=Box1Stack-top().j;temp.state=1;FinalPath-push_back(temp);count=Box1Stack-top().pre;/ 记录当前的路径节点的上一个坐标的下表 while(!Box1Stack-empty()&count!=Box1Stack-top().num) Box1Stack-pop();for(di=0;difront().i-1;j=Box1Queue-front().j;break; case 1:i=Box1Queue-front().i;j=Box1Queue-front().j+1;break; case 2:i=Box1Queue-front().i+1;j=Box1Queue-front().j;break; case 3:i=Box1Queue-front().i;j=Box1Queue-front().j-1;break; if(matrixij.state=1)k+;box1.i=i;box1.j=j;box1.num=k;box1.pre=Box1Queue-front().num;Box1Queue-push(box1);matrixij.state=-1;Box1Queue-pop();void maze:on_way_clicked()/使得迷宫矩阵的 state 为 2 的值变为 1for(int i=0;iM;i+)for(int j=0;jfindWay();this-setFocus(Qt:MouseFocusReason);update();void maze:on_shortway_clicked()/使得迷宫矩阵的 state 为 2 的值变为 1for(int i=0;iM;i+)for(int j=0;jfindShortWay();this-setFocus(Qt:MouseFocusReason);update();void maze:on_removewall_clicked()FinalPath-clear();/使得迷宫矩阵的 state 为 2 的值变为 1for(int i=0;iM;i+)for(int j=0;jway-setEnabled(false);this-setFocus(Qt:MouseFocusReason);ui-cancelremove-setEnabled(true);ui-removewall-setEnabled(false);ui-makemaze-setEnabled(false);.专业.整理.下载可编辑ui-shortway-setEnabled(false);ui-repairwall-setEnabled(true);QMessageBox:information(this,Reminder,You can remove wall now!,QMessageBox:Yes);void maze:on_repairwall_clicked()