数据结构课程设计报告老鼠走迷宫.doc

课程设计说明书

课程名称： 数 据 结 构 与 算 法
专业： 软件工程 班级： 15-2
姓名： xx 学号：2xxxxxx2
指导教师： xx

完成日期： 2017 年 1 月 3 日

任 务 书
题目：老鼠走迷宫
设计内容及要求：
1. 课程设计任务内容
程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。
2.课程设计要求
1)老鼠形象可辨认，可用键盘操纵老鼠上下左右移动；
2)迷宫的墙足够结实，老鼠不能穿墙而过；
3)正确检测结果，若老鼠在规定时间内走到粮仓处，提示成功，否则提示失败；
4)添加编辑迷宫功能，可修改当前迷宫，修改内容：墙变路、路变墙；
5)找出走出迷宫的所有路径，以及最短路径；
6)利用序列化功能实现迷宫地图文件的存盘和读出等功能。

开发环境：QT Creator、 QT5.6

目 录

1.引 言 2
2.课题分析 3
3.具体设计过程 4
3.1设计思路 4
3.2程序设计流程图 5
3.3.函数实现说明 6
4.程序运行结果 7
5.软件使用说明 11
6.结论 11
参 考 文 献 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 j;
int state;
int i;
int j;
int direction;
int i;
int j;
int pre;
int num;

class maze
public:
void paintEvent(QPaintEvent *);
void keyPressEvent(QKeyEvent *);
bool isOdd(); //判断lineedit输入是否为奇数
void creatMaze(); //创建迷宫
void findWay(); //寻求路径（深度遍历）
void findShortWay(); //寻求最短路径（广度遍历）
private:
QTime _time;
_maze **matrix; //定义一个迷宫节点数组
stack<_maze> *MazeStack; //定义一个栈用于存放迷宫节点
vector<_maze> *FinalPath; //定义一个向量用于存放迷宫路径
stack<box> *BoxStack; //定义一个栈用于存放寻路节点
queue<box1> *Box1Queue; //定义一个队列用于存放寻最短路节点
stack<box1> *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 <QLCDNumber>
#include <QTimer>
#include <QTime>
#include <QWidget>
#include <iostream>
#include <stack>
#include <vector>
#include <queue>
#include <QTime>
#include <QLineEdit>
#include <QPushButton>
#include <QPainter>
#include <QLabel>
#include <QMessageBox>
#include <QDebug>
#include <QKeyEvent>
#include <QPixmap>

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 QWidget
{
Q_OBJECT

public:
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<_maze> *MazeStack; //定义一个栈用于存放迷宫节点
vector<_maze> *FinalPath; //定义一个向量用于存放迷宫路径
stack<box> *BoxStack; //定义一个栈用于存放寻路节点
queue<box1> *Box1Queue; //定义一个队列用于存放寻最短路节点
stack<box1> *Box1Stack; //定义一个栈用于存放寻最短路节点
int M; //迷宫矩阵的行
int N; //迷宫矩阵的列
bool first;
bool remove_wall; //判断是否进行拆墙
bool repair_wall; //判断是否补墙
//老鼠的坐标
int X;
int Y;
};

#endif // MAZE_H

maze.cpp
#include "maze.h"
#include "ui_maze.h"

maze::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;i<M;i++)
{
matrix[i]=new _maze[N];
}
for(int i=0;i<M;i++)
for(int j=0;j<N;j++)
{
matrix[i][j].state=0;//初始化迷宫矩阵，将所有节点设置为墙
matrix[i][j].i=i;
matrix[i][j].j=j;
}
//随机生成种子数
QTime time=QTime::currentTime();
qsrand(time.msec()+time.second()*1000);
MazeStack = new stack<_maze>;
FinalPath = new vector<_maze>;
BoxStack = new stack<box>;
Box1Stack = new stack<box1>;
Box1Queue = new queue<box1>;
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(X>1)
{
matrix[X][Y].state=1;
X=X-1;
}
}
else if(e->key()==83||e->key()==16777237)//下
{
if(X<M-2)
{
matrix[X][Y].state=1;
X=X+1;
}
}
else if(e->key()==65||e->key()==16777234)//左
{
if(Y>1)
{
matrix[X][Y].state=1;
Y=Y-1;
}
}
else if(e->key()==68||e->key()==16777236)//右
{

if(Y<N-2)
{
matrix[X][Y].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;i<M;i++)
for(int j=0;j<N;j++)
matrix[i][j].state=0;
this->creatMaze();
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(X>1)
{
matrix[X][Y].state=0;
X=X-1;
}
}
else if(e->key()==83||e->key()==16777237)//下
{
if(X<M-2)
{
matrix[X][Y].state=0;
X=X+1;
}
}
else if(e->key()==65||e->key()==16777234)//左
{
if(Y>1)
{
matrix[X][Y].state=0;
Y=Y-1;
}
}
else if(e->key()==68||e->key()==16777236)//右
{

if(Y<N-2)
{
matrix[X][Y].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;i<M;i++)
for(int j=0;j<N;j++)
matrix[i][j].state=0;
this->creatMaze();
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();
}
}
else
{
int k;
if(e->key()==87||e->key()==16777235)//上
{
k=X-1;
if(k>0&&matrix[k][Y].state!=0)
X=k;
}
else if(e->key()==83||e->key()==16777237)//下
{
k=X+1;
if(k<M-1&&matrix[k][Y].state!=0)
X=k;
}
else if(e->key()==65||e->key()==16777234)//左
{
k=Y-1;
if(k>0&&matrix[X][k].state!=0)
Y=k;
}
else if(e->key()==68||e->key()==16777236)//右
{
k=Y+1;
if(k<N-1&&matrix[X][k].state!=0)
Y=k;
}
if(X==M-2&&Y==N-2)
{
QMessageBox::information(this,"Reminder","Find the exit!",QMessageBox::Yes);
for(int i=0;i<M;i++)
for(int j=0;j<N;j++)
matrix[i][j].state=0;
this->creatMaze();
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--)
{
matrix[FinalPath->at(i).i][FinalPath->at(i).j].state=2;
if(FinalPath->at(i).i==X&&FinalPath->at(i).j==Y) //当老鼠经过寻找迷宫路径时，使得state=1
{
matrix[FinalPath->at(i).i][FinalPath->at(i).j].state=1;
FinalPath->pop_back();
}
}

if(!first)
{
for(int i=0;i<M;i++)
for(int j=0;j<N;j++)
{
if(i==X&&j==Y)//画老鼠
{
painter.drawPixmap(j*20,i*20,20,20,QPixmap(":/img/img/mouse").scaled(20,20));
}
else if(i==M-2&&j==N-2)//画粮仓
{
painter.drawPixmap(j*20,i*20,20,20,QPixmap(":/img/img/door").scaled(20,20));
}
else
{
switch(matrix[i][j].state)
{
case 0://画墙壁
painter.setBrush(QBrush(Qt::black,Qt::SolidPattern));
painter.drawRect(QRect(j*20,i*20,20,20));
break;
case 1://画通路
//painter.setBrush(QBrush(Qt::white,Qt::SolidPattern));
//painter.drawRect(QRect(j*20,i*20,20,20));
break;
case 2://画迷宫寻找路径
painter.setBrush(QBrush(Qt::green,Qt::SolidPattern));
painter.drawRect(QRect(j*20,i*20,20,20));
break;
}
}
}
}
}

bool maze::isOdd()
{
if(ui->xline->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;i<M;i++)
for(int j=0;j<N;j++)
matrix[i][j].state=0;
this->creatMaze();
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;
//设置迷宫节点矩阵初始点位置为通路
matrix[i][j].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&&i>2&&matrix[i-2][j].state==0)
{