第一章 任务概述
1.1背景
1.2总体任务要求
第二章 需求分析
2.1总体需求概述
2.2功能需求
2.3非功能需求
第三章 概要设计
3.1总体架构设计
3.2关键流程设计
第四章 详细设计
4.1界面详细设计
4.2数据结构详细设计
一、任务概述
1.1背景
以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
1.2总体任务要求
（1）实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路一三元组（i，j，d）的形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。
（2）编写递归形式的算法，求得迷宫中所有可能的通路；
（3）以方阵形式输出迷宫及其通路
二、需求分析
2.1总体需求概述
该程序可随机生成指定大小的迷宫，该迷宫有三种可能：1.无通路2.有一条通路3.有多条通路。通过可视化界面清晰地展示出通路。
2.2功能需求
（1）生成迷宫：通过指定长和宽随机生成对应大小的迷宫。
（2）有无通路：在生成迷宫的同时若无通路则弹出提示。
（3）若有通路：动态地指示出从起点到终点的一条通路、所有通路、最短通路。 2.3非功能需求 该程序界面应简洁清晰，操作简便，快速操作。
三、概要设计
3.1总体架构设计 使用程序时可完成以下操作：
四、详细设计
4.1界面详细设计
起始界面/功能界面
该界面为程序的界面及主界面，在控制区的迷宫高度、宽度中输入数字点击生成迷宫按钮，若不输入数值点击生成迷宫按钮则默认生成11*11的迷宫。
此时提示当前生成的迷宫没有通路，需再次点击生成迷宫，直到不提示“没有通路”即迷宫存在通路方可执行下面生成通路的操作。
此时没有提示“没有通路”，解锁生成通路的三个按钮，可点击操作。
4.2数据结构详细设计
各功能的实现思路：
（1）生成迷宫
迷宫分为三种情况：1）无通路 2）有一条通路 3）有多条通路1.将迷宫全置为障碍，将起点置为通路。2.递归地随机选取四个方向中的一个方向进行探路，若没有超出迷宫且该点为障碍则将该邻接点（与上一点之间间隔一个点）置为通路，并将邻接点与上一点的中间点置为通路。若当前点的四个方向都无法继续前进则退回上一个点，递归结束后则得到有唯一通路的迷宫。3.为实现无通路或多通路，生成迷宫范围内的随机数将若干点置为0或1。
（2）非递归求出一条通路或无通路
非递归的深度优先搜索算法：从起点出发，按照某一方向优先顺序向四周探路，走过的点设置为已访问过，压入栈中，若当前点为死路，则退回上一点，当前点出栈。直到当前点为终点。若为空，则没有通路。
（3）递归输出所有通路
深度优先搜索算法：从起点出发，按照某一方向优先顺序向四周递归地探路，将当前点设置为已访问过，将该点压入栈中，当某一方向的递归结束时，该点出栈，设置该点为未访问过，当到达终点时输出栈中的点，并将终点设置为未访问过。
（4）求迷宫最短通路
广度优先搜索算法：设置迷宫大小的二维数组用于存放每一个点的前驱。从起点出发，将起点放入队列中，按照某一方向优先顺序向四周探路，将邻接点放入队列中，记录邻接点的前驱。从终点递归输出前驱得到最短通路。
具体代码实现：
QT creator
widget.h
#ifndef WIDGET_H
#define WIDGET_H
#include <QWidget>
#include "mythread.cpp"
QT_BEGIN_NAMESPACE
namespace Ui { class Widget; }
QT_END_NAMESPACE
class Widget : public QWidget
{
Q_OBJECT
public:
Widget(QWidget *parent = nullptr);
~Widget();
private slots:
void on_pushButton_3_clicked();
void on_pushButton_clicked();
void on_pushButton_2_clicked();
void on_pushButton_4_clicked();
void on_pushButton_6_clicked();
private:
Ui::Widget *ui;
QVector<QVector<mybutton *> > btnsofwidget;
mythread * t;
ListStack<location> fp;
ListStack<location> *BFS;
ListStack<location> *DFS;
maze m;
};
#endif // WIDGET_H
liststack.cpp
#include<iostream>
#include <QDebug>
using namespace std;
template <class T>
class ListStack{
//内部节点类
public: class Node{
public:
T data;
Node *next;
Node(T t,Node *next)
{
this->data=t;
this->next=next;
}
};
Node *top;
//构造方法
ListStack<T>()
{
top=0;
}
//压栈
void push(T t)
{
Node *node=new Node(t,top);
top=node;
}
//出栈
T* pop() {
if(top==0){
throw "栈为空，元素不可出栈";//c++中直接throw
return 0;
}
Node *node=top;
top=top->next;
return &node->data;
}
//打印栈
void printStack()
{
Node *node=top;
while(node!=0)
{
cout<<node->data;
node=node->next;
}
}
//判断栈是否为空
bool isEmpty()
{
if(top==0)
return true;
else
return false;
}
//倒置栈
void revert()
{
ListStack<T> *l=new ListStack<T>();
while(!this->isEmpty())
{
l->push(*this->pop());
}
this->top=l->top;
}
};
//int main()
//{
// ListStack<int> list;
// list.push(1);
// list.push(2);
// list.pop();
// list.pop();
// list.printStack();
// cout<<list.isEmpty();
//}
main.cpp
#include "widget.h"
#include <QApplication>
#include <QDebug>
#include<musicthread.cpp>
int main(int argc, char *argv[])
{
QApplication a(argc, argv);
Widget w;
w.setWindowTitle("迷宫游戏 by xdl");
w.show();
return a.exec();
}
maze.cpp
#include"liststack.cpp"
#include<iostream>
#include<string>
#include <ctime>
#include<stdlib.h>
#include<time.h>
#include<queue>
#include<QMessageBox>
using namespace std;
#define random(x) (rand()%x)
template<class T>
class ArrayList
{
public:
int count;
T * shuzu[100];
ArrayList()
{
for(int i=0;i<100;i++)
shuzu[i]=0;
count=0;
}
T get(int i)
{
return *shuzu[i];
}
int size()
{
return count;
}
void add(T &t)//传地址的要传引用，否则地址会消失，变成空指针！
{
shuzu[count]=&t;
count++;
}
void print()
{
for(int i=0;i<100;i++)
{
if(shuzu[i]!=0)
{
cout<<*shuzu[i]<<endl;
}
else
break;
}
}
};
class location {
public:
int x;//横纵坐标
int y;
//空白构造方法
location()
{
}
location(int x,int y)
{
this->x=x;
this->y=y;
}
//重写输出运算符
friend ostream& operator<<(ostream& out,const location& obj)
{
std::string a = std::to_string(obj.x);
std::string b = std::to_string(obj.y);
out<<"location[x="+a+"y="+b+"]"<<endl;
return out;
}
//重写不等于运算符
friend bool operator==(const location& obj1,const location& obj2)
{
if(obj1.x==obj2.x&&obj1.y==obj2.y)
return true;
else
return false;
}
friend bool operator!=(const location& obj1,const location& obj2)
{
return !operator==(obj1,obj2);
}
};
class maze {
public:
int col;
int row;
int wall=1;
int blank=0;
int length;//邻接数组的长度
int ** migong;
bool ** visit;
ListStack<location> path;
ListStack<location> dfs;//用于DFS函数的栈
int adj[4][2] = { {0,2},{0,-2},{2,0},{-2,0} }; //用来生成迷宫计算邻接格
int bdj[4][2] = { {0,1},{0,-1},{-1,0},{1,0} };//按照上下左右的顺序探路,用于探路
location **pre;//用于BFS储存节点的前驱
//方法外不允许进行初始化，只能声明 ,此时已经调用不带参的构造函数
location start;
location exit;
location cur;
location next;
maze()
{
}
maze(int col,int row){
this->col=col;
this->row=row;
start.x=1,start.y=0;
init();
makeMaze();
initrand();
}
QString getMaze()
{
QString q="";
for(int i=0;i<col;i++)
{
for(int j=0;j<row;j++)
{
// QString temp=QString::number(migong[i][j])+" ";
q.append(QString::number(migong[i][j]));//用qstring的append函数来拼接字符串
q.append(" ");
}
q.append("<br>");
}
return q;
}
void outPut()
{
for(int i=0;i<col;i++)
{
for(int j=0;j<row;j++)
{
cout<<migong[i][j]<<" ";
}
cout<<endl;
}
}
void init()
{
visit=new bool*[col];
migong=new int*[col];
pre=new location*[col];
for(int i=0;i<col;i++)
{
visit[i]=new bool[row];
migong[i]=new int[row];
pre[i]=new location[row];
}
for(int i=0;i<col;i++)
{
for(int j=0;j<row;j++)
{
migong[i][j]=wall;
visit[i][j]=false;
pre[i][j]=location(-10,-10);
}
}
visit[start.x][start.y] = true;
migong[start.x][start.y] = blank;
cur = start; //将当前格标记为开始格
// outPut();
}
void makeMaze()
{
path.push(cur); //将当前格压入栈
srand((unsigned)time(NULL));//设置随机数种子，要放在循环外面
while(!path.isEmpty())
{
location * adjs = notVisitedAdj(cur);//寻找未被访问的邻接格
// int length= sizeof(adjs)/sizeof(adjs[0]);//取出数组的长度
if(length == 0)//c++获取数组长度
{
cur = *path.pop();//如果该格子没有可访问的邻接格，则跳回上一个格子
continue;
}
int ran=random(length);
next = adjs[ran]; //随机选取一个邻接格
// cout<<rand()<<endl;
int x = next.x;
int y = next.y;
//
path.push(next);
visit[x][y] = true;
migong[x][y] = blank;
migong[(cur.x + x) / 2][(cur.y + y) / 2] = blank; //移除当前格与下一个之间的墙壁
cur = next;//当前格等于下一格
}
}
location* notVisitedAdj(location node)
{
ArrayList<location> list;
location l0,l1,l2,l3;
for(int i=0;i<4;i++)
{
int x=node.x+adj[i][0];
int y=node.y+adj[i][1];
if(x>=0&&x<col&&y>=0&&y<row)
{
if(!visit[x][y])
{
if(i==0)
{
l0=location(x,y);
list.add(l0);
}
else if(i==1)
{
l1=location(x,y);
list.add(l1);
}
else if(i==2)
{
l2=location(x,y);
list.add(l2);
}
else
{
l3=location(x,y);
list.add(l3);
}
}
}
}
location * a = new location[list.size()];
//给邻接数组长度赋值
length=list.size();
for(int i = 0; i < list.size(); i++)
{
a[i] = list.get(i);
}
return a;
}
//随机设置通路抽取若干个位置设置为0或则1
void initrand()
{
int randcol=0;int randrow=0;
srand((unsigned)time(NULL));
for(int i=0;i<20;i++)
{
randcol=random(col);
randrow=random(row);
migong[randcol][randrow]=blank;
}
for(int i=0;i<10;i++)
{
randcol=random(col);
randrow=random(row);
migong[randcol][randrow]=wall;
}
//设置入口出口处为0
migong[1][0]=blank;
migong[col-2][row-1]=blank;
}
bool check(location l)//检查该点的四周是否有通路
{
int x=l.x;
int y=l.y;
for(int i=0;i<4;i++)
{
int nextx=x+bdj[i][0];
int nexty=y+bdj[i][1];
if(nextx>=0&&nextx<col&&nexty>=0&&nexty<row)
if(migong[nextx][nexty]==0)
return true;
}
return false;
}
ListStack<location> findPath()//生成一条通路
{
ListStack<location> result;
location cur=location(1,0);
migong[1][0]=-1;
result.push(cur);
exit=location(col-2,row-1);
while(cur!=exit)
{
if(!check(cur))
{
cur=*result.pop();
if(result.isEmpty())
{
// QMessageBox::information(NULL, "通告", "没有通路！");//弹出消息框提示没有通路
break;
}
else
{
cur=*result.pop();
result.push(cur);
}
}
else
{
int x=cur.x;
int y=cur.y;
for(int i=0;i<4;i++)
{
int nextx=x+bdj[i][0];
int nexty=y+bdj[i][1];
if(nextx>=0&&nextx<col&&nexty>=0&&nexty<row)
if(migong[nextx][nexty]==0)
{
cur=location(nextx,nexty);
result.push(cur);
migong[nextx][nexty]=-1;
break;
}
}
}
}
//将迷宫变为初始的迷宫
for(int i=0;i<col;i++)
for(int j=0;j<row;j++)
if(migong[i][j]==-1)
migong[i][j]=0;
// result.printStack();
result.revert();//倒置，原本的顺序是从重点逆着回来
return result;
}
void DFS(location cur,ListStack<location> &a)//生成所有通路
{
migong[cur.x][cur.y]=-1;
dfs.push(cur);
int x=cur.x,y=cur.y;
//如果走到终点了，输出路径
if(x==col-2&&y==row-1)
{
// dfs.printStack();
migong[x][y]=0;//将重点赋值回0
// cout<<"------------------"<<endl;
ListStack<location> t=dfs;
location lo;
while(!t.isEmpty())
{
lo=*t.pop();
a.push(lo);
}
}
else
{
for(int i=0;i<4;i++)
{
int nextx=x+bdj[i][0];
int nexty=y+bdj[i][1];
if(nextx>=0&&nextx<col&&nexty>=0&&nexty<row)
{
if(migong[nextx][nexty]==0)
{
location temp=location(nextx,nexty);
DFS(temp,a);//如果当前方向可以走，那么进去这个方向
}
}
}
}
cur=*dfs.pop();
migong[cur.x][cur.y]=0;
}
void BFS()
{
//初始化数组
int vis[col][row];
for(int i=0;i<col;i++)
for(int j=0;j<row;j++)
vis[i][j]=0;
queue<location> que;
cur=location(1,0);//起点为1，0
que.push(cur);
vis[1][0]=1;//访问过的地方设置为1
while(!que.empty())
{
location now=que.front();
que.pop();
if(now.x==col-2&&now.y==row-1)
return;//如果到达终点则返回
for(int i=0;i<4;i++)
{
location temp;
temp.x=now.x+bdj[i][0];
temp.y=now.y+bdj[i][1];
if(temp.x>=0&&temp.x<col&&temp.y>=0&&temp.y<row)
if(migong[temp.x][temp.y]==0&&vis[temp.x][temp.y]==0)
{
vis[temp.x][temp.y]=1;//如果bfs没走过这个地方，走到后设置为1；
que.push(temp);
pre[temp.x][temp.y]=now;//设置前驱
}
}
}
}
void printBFS(location c,ListStack<location> &a)//输入终点坐标和一个地址栈，由于是递归只能从参数传入引用，
{
if(c.x==1&&c.y==0)//起点为1，0
{
a.push(c);
return;
}
printBFS(pre[c.x][c.y],a);
a.push(c);
}
};
musicthread.cpp
#include <QThread>
#include<QSound>
#include<iostream>
using namespace std;
class musicthread :public QThread
{
public:
void run(){
QSound::play("C:\\Users\\吴彦祖\\Desktop\\数据结构课设\\冒险-Adventure_Full_爱给网_aigei_com.wav");
}
};
mybutton.cpp
#include <QPushButton>
class mybutton : public QPushButton
{
private: int zhi;
public:
mybutton()
{
this->zhi = 0;
this->setStyleSheet("background-color:rgb(255, 255, 255);");
}
void onfp()
{
this->setStyleSheet("background-color:rgb(255, 0, 0);");
}
void onBFS()
{
this->setStyleSheet("background-color:rgb(0, 255, 0);");
}
void onDFS(int b)
{
switch(b)
{
case 10:
this->setStyleSheet("background-color:rgb(0, 0, 255);");
break;
case 1:
this->setStyleSheet("background-color:rgb(100, 255, 250);");
break;
case 2:
this->setStyleSheet("background-color:rgb(255, 200, 100);");
break;
case 3:
this->setStyleSheet("background-color:rgb(0, 100, 255);");
break;
case 4:
this->setStyleSheet("background-color:rgb(0, 20, 100);");
break;
case 5:
this->setStyleSheet("background-color:rgb(100, 10, 20);");
break;
case 6:
this->setStyleSheet("background-color:rgb(50, 150, 50);");
break;
case 7:
this->setStyleSheet("background-color:rgb(200, 10, 10);");
break;
case 8:
this->setStyleSheet("background-color:rgb(200, 200, 0);");
break;
case 9:
this->setStyleSheet("background-color:rgb(0, 200, 200);");
break;
}
}
void off()
{
this->setStyleSheet("QPushButton{border:none;background:transparent;}");
}
};
mythread.cpp
#include "myButton.cpp"
#include <QThread>
#include <QEventLoop>
#include "maze.cpp"
#include<QTime>
#include<QTimer>
#include <sstream>
#include<QString>
using namespace std;
class mythread :public QThread
{
public:
mythread(QVector<QVector<mybutton *> > btns,ListStack<location> l,int flag)
{
this->btnsofthread = btns;
this->l=l;
this->flag=flag;
}
void run(){
QString r1="\"background-color:rgb(";
QString r2=", 0, 255);\"";
location *list;
if(flag==3)
{
int b=0;
while(!this->l.isEmpty())
{
QEventLoop eventloop;
QTimer::singleShot(100, &eventloop, SLOT(quit()));
eventloop.exec();
list=this->l.pop();
int x=list->x;
int y=list->y;
if(x==1&&y==0)
{
if(b==10)
b=1;
else
b++;
}
// btnsofthread[x][y]->setcolor();
// {
// for(int i=0;i<btnsofthread.size();i++)
// for(int j=0;j<btnsofthread[0].size();j++)
// {
// if(btnsofthread[i][j]->text()==0)
// btnsofthread[i][j]->off();
// }
// btnsofthread[x][y]->setcolor();
// }
btnsofthread[x][y]->onDFS(b);
}
}
else
while(!this->l.isEmpty())
{
QEventLoop eventloop;
QTimer::singleShot(100, &eventloop, SLOT(quit()));
eventloop.exec();
list=this->l.pop();
int x=list->x;
int y=list->y;
if(flag==1)
btnsofthread[x][y]->onfp();
else if(flag==2)
btnsofthread[x][y]->onBFS();
}
// for(int i=0;i<5;i++)
// for(int j=0;j<5;j++)
// {
// QEventLoop eventloop;
// QTimer::singleShot(100, &eventloop, SLOT(quit()));
// eventloop.exec();
// btnsofthread[i][j]->on();
// cout<<1<<endl;
// }
}
private :
QVector<QVector<mybutton *> > btnsofthread;
ListStack<location> l;
int flag;//生成一条通路为1，最短为2,3为所有通路
};
widget.cpp
#include "widget.h"
#include "ui_widget.h"
#include<iostream>
#include <QMessageBox>
#include<QThread>
#include<musicthread.cpp>
using namespace std;
Widget::Widget(QWidget *parent)
: QWidget(parent)
, ui(new Ui::Widget)
{
ui->setupUi(this);
}
Widget::~Widget()
{
delete ui;
}
void Widget::on_pushButton_3_clicked()
{
for(int i=0;i<ui->gridLayout->count();i++)
ui->gridLayout->itemAt(i)->widget()->deleteLater();//每次点击时需要清除上一次创建的迷宫，否则会覆盖产生错误
int height=ui->spinBox->value();
int width=ui->spinBox_2->value();
maze m;
if(height==0||width==0)
{
m=maze(11,11);
ui->spinBox->setValue(11);
ui->spinBox_2->setValue(11);
height=ui->spinBox->value();
width=ui->spinBox_2->value();
}
else
m=maze(height,width);
int **a=m.migong;
this->fp=m.findPath();//是否具有通路
this->m=m;
//清空指针
for(auto p = btnsofwidget.begin();p!=btnsofwidget.end();p++){
for(auto q = p->begin();q!=p->end();q++){
delete *q;
}
}
btnsofwidget.clear();
QVector<mybutton*> temp;
for(int i = 0;i<height;i++){
for(int j = 0;j<width;j++){
mybutton *btn = new mybutton;
if(a[i][j]==0)
{
btn->setText("0");
btn->setStyleSheet("QPushButton{border:none;background:transparent;}");
}
else
btn->setText("1");
ui->gridLayout->addWidget(btn,i,j,1,1);
temp.push_back(btn);
}
btnsofwidget.push_back(temp);
temp.clear();
}
if(fp.isEmpty())
{
QMessageBox::information(NULL, "通告", "没有通路！");//弹出消息框提示没有通路
ui->pushButton->setEnabled(false);//如果没有通路不允许点击其他按钮
ui->pushButton_2->setEnabled(false);
ui->pushButton_4->setEnabled(false);
}
else
{
ui->pushButton->setEnabled(true);
ui->pushButton_2->setEnabled(true);
ui->pushButton_4->setEnabled(true);
m.BFS();
this->BFS=new ListStack<location>;//要先给变量分配空间！！！！
m.printBFS(location(height-2,width-1),*this->BFS);//BFS赋值为最短路径
this->BFS->revert();
this->DFS=new ListStack<location>;
m.DFS(location(1,0),*this->DFS);
}
// QString q=m.getMaze();
// ui->textBrowser->setStyleSheet("color:red;border:5px solid gray;");
// QRegExp valueRegExp(QString("(%1)").arg("0"));
// valueRegExp.setCaseSensitivity(Qt::CaseInsensitive);
// q = q.replace(valueRegExp, "<font style='font-size:30px; color:blue;'>\\1</font>");
// QRegExp valueRegExp2(QString("(%1)").arg("1"));
// q = q.replace(valueRegExp2, "<font style='font-size:30px; color:red;'>\\1</font>");
// ui->textBrowser->setText(q);
// QMessageBox::information(NULL, "通告", "没有通路！");
}
void Widget::on_pushButton_clicked()
{
ui->pushButton_2->setEnabled(false);
ui->pushButton_3->setEnabled(false);
ui->pushButton_4->setEnabled(false);
t=new mythread(btnsofwidget,fp,1);
t->run();
ui->pushButton_2->setEnabled(true);
ui->pushButton_3->setEnabled(true);
ui->pushButton_4->setEnabled(true);
}
void Widget::on_pushButton_2_clicked()
{
ui->pushButton->setEnabled(false);
ui->pushButton_3->setEnabled(false);
ui->pushButton_4->setEnabled(false);
t=new mythread(btnsofwidget,*this->BFS,2);
// BFS.printStack();
t->run();
ui->pushButton->setEnabled(true);
ui->pushButton_3->setEnabled(true);
ui->pushButton_4->setEnabled(true);
}
void Widget::on_pushButton_4_clicked()
{
ui->pushButton->setEnabled(false);
ui->pushButton_3->setEnabled(false);
ui->pushButton_2->setEnabled(false);
t=new mythread(btnsofwidget,*this->DFS,3);
t->run();
ui->pushButton->setEnabled(true);
ui->pushButton_3->setEnabled(true);
ui->pushButton_2->setEnabled(true);
}
//void Widget::on_pushButton_6_clicked()
//{
// ui->pushButton_6->setEnabled(false);
// musicthread *t=new musicthread();
// t->run();
on_pushButton_6_clicked();
//}
版权声明：本文为xdl229原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。