基于Qt实现的寻宝路径规划程序

Lily1203

发布日期: 2020-11-17 15:23:26 浏览量: 99
评分:
star star star star star star star star star star_border
*转载请注明来自write-bug.com

一、课题内容和要求

1.1 课题内容

有一幅如图所示的藏宝图,请设计算法要求从入口到出口,必须经过“食品”和“宝藏”的地方,不得经过“强盗”的地方。

1.2 课题要求

  • 自行设计藏宝图(无向图),不与题目一致

  • 要求图中结点不得小于8个,“食品”、“宝藏”和“强盗”的布局位置不可以是直线完成关系,需有交叉

  • 选择合适算法输出寻宝路径

  • 支持根据map.txt文件中的图的结点位置坐标和图中所有条边的两个结点,输出藏宝图

  • 根据回溯法,支持输入开始,结束,宝藏,食品,强盗的结点号,输出符合要求的路径

本课题“寻宝路径规划系统”的功能框架图如图1所示。

二、数据结构说明

边结点结构体

  1. struct EdgeNode
  2. {
  3. bool isVisited; //该边是否被访问过
  4. //顶点对应的下标
  5. int adjvex;
  6. //指向下一个邻接点
  7. struct EdgeNode *next;
  8. };

顶点结点结构体

  1. struct VexNode
  2. {
  3. string name;//顶点名称
  4. EdgeNode * firstEdge;//指向第一条关联该结点的边
  5. };

结点数据结构

  1. struct
  2. {
  3. std::string name;
  4. QPoint pos;
  5. }vex[MAX];

三、算法设计

下图为“寻宝规划路径系统”数据结构框架。

其中adjMulList是顶点数组指针,所用的顶点结点以顺序方式存储在一维数组中;vexnum和edgenum是无向图的结点个数和边个数;treasureMap类是用来存储所有从文件中读取的结点名和坐标信息的类,search_str是用来存储遍历的结点的坐标和名称的变量。VexNode结构体是点结点,name是结点的名称,firstEdge是EdgeNode类型的指针,指向该顶点的第一条边的结点。

EdgeNode结构体是边结点,isVisited为标志域,用来标记该条边是否已被访问过;adjvex为顶点域,next为链域。

GreatAMLGraph函数用来构建邻接多重表,LocationVex函数通过城市名找到该城市在表结点的位置。AMLGraph、~AMLGraph函数分别是类的构造函数和析构函数,printPath是寻找路径的函数。

程序的执行流程如图3。

3.1 头插法构建邻接表

头插法在头结点之后插入数据,并将头结点指向新插入的数据。

该算法流程图如图4所示。

3.2 回溯法寻找路径

回溯法的基本行为是搜索,搜索过程使用剪枝函数来为了避免无效的搜索。回溯法按深度优先策略搜索符合要求路径。首先从开始结点出发搜索路径,当算法搜索至路径的某一结点时,先利用cond函数判断该结点是否可行。如果不可行,则跳过含该结点搜索,逐层向其祖先结点回溯;否则,进入该结点,继续按深度优先策略搜索。

该算法流程图如图5所示。

四、详细设计

graph.h

  1. //边结点
  2. struct EdgeNode
  3. {
  4. bool isVisited; //该边是否被访问过
  5. //顶点对应的下标
  6. int adjvex;
  7. //指向下一个邻接点
  8. struct EdgeNode *next;
  9. };
  10. //顶点结点
  11. struct VexNode
  12. {
  13. string name;//顶点名称
  14. EdgeNode * firstEdge;//指向第一条关联该结点的边
  15. };
  16. class Map
  17. {
  18. public:
  19. struct
  20. {
  21. public:
  22. std::string name;
  23. QPoint pos;
  24. }vex[MAX];
  25. };
  26. class AMLGraph
  27. {
  28. public:
  29. VexNode * adjMulList; //顶点数组指针
  30. int vexnum; //定点数目
  31. int edgenum; //边数目
  32. QVector<QPoint> points;
  33. QVector<QPoint> points_search;
  34. public:
  35. Map treasureMap;
  36. string search_str;
  37. AMLGraph();
  38. ~AMLGraph();
  39. void CreatAMLGraph();
  40. int LocationVex(string name);
  41. void printPath(int vi, int vj, int vm, int vn, int vp,int d);
  42. };

graph.cpp

  1. #define MAX 100
  2. //辅助变量,记录该顶点是否被访问过
  3. int visited[MAX];
  4. int path[MAX];
  5. AMLGraph::AMLGraph()
  6. {
  7. // vexnum = 8;
  8. // edgenum = 11;
  9. adjMulList = new VexNode[MAX];
  10. }
  11. AMLGraph::~AMLGraph()
  12. {
  13. delete [] adjMulList;
  14. }
  15. void AMLGraph::CreatAMLGraph()
  16. {
  17. QString qpath;
  18. string path;
  19. qpath = QCoreApplication::applicationDirPath();
  20. path = string((const char *)qpath.toLocal8Bit());
  21. path.append("\\map.txt");
  22. fstream inFile;
  23. inFile.open(path);
  24. if (!inFile.is_open())
  25. {
  26. std::cout << "open failed"<<endl;
  27. exit(0);
  28. }
  29. int x, y;
  30. for (int i = 0; i < vexnum; ++i)
  31. {
  32. inFile >> adjMulList[i].name;
  33. inFile >> x >> y;
  34. treasureMap.vex[i].pos.setX(x);
  35. treasureMap.vex[i].pos.setY(y);
  36. treasureMap.vex[i].name = adjMulList[i].name;
  37. adjMulList[i].firstEdge = nullptr;
  38. }
  39. //头插法
  40. for (int i = 0; i < edgenum; ++i)
  41. {
  42. EdgeNode * e = new EdgeNode;
  43. e->isVisited = false;
  44. string v1, v2;
  45. inFile >> v1 >> v2;
  46. int a = LocationVex(v1);
  47. int b = LocationVex(v2);
  48. //points 为了画路线
  49. for (int j = 0; j < vexnum; ++j)
  50. {
  51. if (v1 == treasureMap.vex[j].name)
  52. points.push_back(treasureMap.vex[j].pos);
  53. if (v2 == treasureMap.vex[j].name)
  54. points.push_back(treasureMap.vex[j].pos);
  55. }
  56. e->adjvex = b;
  57. e->next = adjMulList[a].firstEdge;
  58. adjMulList[a].firstEdge=e;
  59. EdgeNode * f = new EdgeNode;
  60. f->adjvex = a;
  61. f->next = adjMulList[b].firstEdge;
  62. adjMulList[b].firstEdge = f;
  63. }
  64. inFile.close();
  65. //std::cout << "无向图构造完成" << std::endl;
  66. }
  67. //返回顶点在数组中的索引
  68. int AMLGraph::LocationVex(string name)
  69. {
  70. for (int i = 0; i < vexnum; ++i)
  71. {
  72. if (adjMulList[i].name.compare(name) == 0)
  73. return i;
  74. else if (adjMulList[i].name.substr(0, 2).compare(name) == 0)
  75. return i;
  76. }
  77. return -1;
  78. }
  79. int cond(int path[],int d,int vm, int vn, int vp)
  80. {
  81. int flag1 = 0, flag2 = 0, flag3 = 1, i;
  82. for (i = 0; i <= d; i++)
  83. {
  84. if (path[i] == vm)
  85. {
  86. flag1 = 1;//此路径经过了食品
  87. break;
  88. }
  89. }
  90. for (i = 0; i <= d; i++)
  91. {
  92. if (path[i] == vn)
  93. {
  94. flag2 = 1;//此路径经过了宝藏
  95. break;
  96. }
  97. }
  98. for (i = 0; i <= d; i++)
  99. {
  100. if (path[i] == vp)
  101. {
  102. flag3 = 0;//此路径经过了强盗
  103. break;
  104. }
  105. }
  106. return flag1&&flag2&&flag3;
  107. }
  108. void AMLGraph::printPath(int vi, int vj, int vm, int vn, int vp,int d)
  109. {
  110. int i,v;
  111. string pathstring;
  112. EdgeNode *p;
  113. visited[vi] = 1;
  114. ++d;//d指明所经过的顶点数目
  115. path[d] = vi;
  116. if (vi == vj && cond(path,d,vm, vn, vp)==1)
  117. {
  118. cout << endl;
  119. for (i = 0; i <= d; i++)
  120. {
  121. stringstream ss;//将int型变量转为string
  122. ss<<path[i];
  123. string pathstring = ss.str();
  124. search_str.append(pathstring.substr(0, 2) + "->");
  125. }
  126. //exit(0);
  127. }
  128. p =adjMulList[vi].firstEdge;
  129. while (p != NULL)
  130. {
  131. v = p->adjvex;
  132. if (visited[v]==0)
  133. printPath(v, vj, vm, vn, vp,d);
  134. p = p->next;
  135. }
  136. visited[vi] = 0;
  137. --d;
  138. }
  139. mainwindow.cpp
  140. MainWindow::MainWindow(QWidget *parent) :
  141. QMainWindow(parent),
  142. ui(new Ui::MainWindow)
  143. {
  144. ui->setupUi(this);
  145. is_create = false;
  146. }
  147. void MainWindow::paintEvent(QPaintEvent *)
  148. {
  149. int r = 20; //半径
  150. QPainter painter(this);
  151. //修改背景颜色
  152. painter.setBrush(Qt::white);
  153. painter.drawRect(0, 0, this->width(), this->height());
  154. if (is_create)
  155. {
  156. //绘制地图
  157. painter.setPen(QPen(Qt::black,2));
  158. QPoint o;
  159. QString qname;
  160. for (int i = 0; i < graph.vexnum; ++i)
  161. {
  162. painter.drawEllipse(graph.treasureMap.vex[i].pos, r, r);
  163. o = graph.treasureMap.vex[i].pos;
  164. QRect rect(o.x()-r, o.y()-r, 2*r, 2*r);
  165. qname = QString(QString::fromLocal8Bit(graph.treasureMap.vex[i].name.c_str()));
  166. painter.drawText(rect,qname,QTextOption(Qt::AlignCenter));
  167. }
  168. //绘制基本路线
  169. painter.setPen(QPen(Qt::black,2));
  170. painter.drawLines(graph.points);
  171. is_create = false;
  172. }
  173. }
  174. MainWindow::~MainWindow()
  175. {
  176. delete ui;
  177. }
  178. void MainWindow::on_xianshi_clicked()
  179. {
  180. int vexnum, edgenum;
  181. QString qvexnum = ui->lineEdit_vex->text();
  182. string str_vexnum = string((const char *)qvexnum.toLocal8Bit());
  183. QString qdegenum = ui->lineEdit_edge->text();
  184. string str_edgenum = string((const char *)qdegenum.toLocal8Bit());
  185. stringstream ss1(str_vexnum);
  186. stringstream ss2(str_edgenum);
  187. ss1 >> vexnum;
  188. ss2 >> edgenum;
  189. graph.vexnum = vexnum;
  190. graph.edgenum = edgenum;
  191. graph.points.clear();
  192. graph.CreatAMLGraph();
  193. is_create = true;
  194. update();
  195. }
  196. void MainWindow::on_chaxun_clicked()
  197. {
  198. int vexnum, edgenum;
  199. QString qvexnum = ui->lineEdit_vex->text();
  200. string str_vexnum = string((const char *)qvexnum.toLocal8Bit());
  201. QString qdegenum = ui->lineEdit_edge->text();
  202. string str_edgenum = string((const char *)qdegenum.toLocal8Bit());
  203. stringstream ss6(str_vexnum);
  204. stringstream ss7(str_edgenum);
  205. ss6 >> vexnum;
  206. ss7 >> edgenum;
  207. graph.vexnum = vexnum;
  208. graph.edgenum = edgenum;
  209. graph.points.clear();
  210. graph.CreatAMLGraph();
  211. is_create = true;
  212. int kaishi2,jieshu2,baozang2,shipin2,qiangdao2;
  213. string output;
  214. QString qoutput;
  215. QString kaishi;
  216. string kaishi1;
  217. QString jieshu;
  218. string jieshu1;
  219. QString baozang;
  220. string baozang1;
  221. QString shipin;
  222. string shipin1;
  223. QString qiangdao;
  224. string qiangdao1;
  225. //获取输入框中的QString,并转化为string
  226. kaishi=ui->kaishi->text();
  227. kaishi1 = string((const char *)kaishi.toLocal8Bit());
  228. jieshu=ui->jieshu->text();
  229. jieshu1 = string((const char *)jieshu.toLocal8Bit());
  230. baozang=ui->baozang->text();
  231. baozang1 = string((const char *)baozang.toLocal8Bit());
  232. shipin=ui->shipin->text();
  233. shipin1 = string((const char *)shipin.toLocal8Bit());
  234. qiangdao=ui->qiangdao->text();
  235. qiangdao1 = string((const char *)qiangdao.toLocal8Bit());
  236. stringstream ss1(kaishi1);
  237. stringstream ss2(jieshu1);
  238. stringstream ss3(baozang1);
  239. stringstream ss4(shipin1);
  240. stringstream ss5(qiangdao1);
  241. ss1 >> kaishi2;
  242. ss2 >> jieshu2;
  243. ss3 >> baozang2;
  244. ss4 >> shipin2;
  245. ss5 >> qiangdao2;
  246. //将上次的搜索结果清掉
  247. graph.search_str.clear();
  248. output.clear();
  249. ui->label_6->setText("");
  250. graph.points_search.clear();
  251. graph.printPath(kaishi2,jieshu2,shipin2,baozang2,qiangdao2,-1);
  252. output.erase(0, output.length());
  253. output.append("The road is :\n");
  254. output.append(graph.search_str.substr(0, graph.search_str.length()-2));
  255. qoutput = QString(QString::fromLocal8Bit(output.c_str()));
  256. ui->label_6->setText(qoutput);
  257. //QLabel自动换行
  258. ui->label_6->adjustSize();
  259. ui->label_6->setGeometry(QRect(180, 600, 540, 280)); //四倍行距
  260. ui->label_6->setWordWrap(true);
  261. ui->label_6->setAlignment(Qt::AlignTop);
  262. update();
  263. }

五、测试数据及其结果分析

当食品结点为1号结点,宝藏结点为6号结点,强盗结点为4号结点时,可找到的路径为0 1 2 5 6 7,如图6所示。

当食品结点为1号结点,宝藏结点为2号结点,强盗结点为3号结点时,可找到的路径为0 2 1 4 6 7,0 1 4 2 5 6 7,0 1 2 5 6 7和0 1 2 4 6 7,如图7所示。

六、算法设计和程序调试过程中的问题

  • 问题1:使用邻接多重表作为数据结构时,寻找路径时找下一个结点出现了问题
    解决方法:将邻接多重表改成邻接表,这样,p指向下一个结点时只需用“p->adjvex”即可

  • 问题2:QT无法读取txt文件
    解决方法:将QFile改成“path.append(“\map.txt”)”,并将txt放置在debug文件中

  • 问题3:写void printPath()函数时,输出不了路径
    解决方法:在函数最后要将d减1,因为递归过后,visited数组要从visited[0]开始

  • 问题4:无法在label_6中输出路径
    解决方法:先将path[i]转换成string型变量,在将它存储到search_str中,最后将它存到qoutput中输出

  • 问题5:printPath()函数在mainwindow里无法运行
    解决方法:将输入框中的QString转化为string,再将string转换成int型变量

七、课程设计总结

这次实验,我本来是用vs2017写的程序,大概3天就写完了,后来一直在忙用QT写界面。本来以为网上可能有先人的经验可以借鉴,没想到网上基本上没有用QT写无向图的,基本上是java,但由于我原来的代码时c++,我又不怎么擅长java,于是我就在网上搜索QT绘图的方法,一点一点把代码写出来了。

对于此次我的c++源代码,因为老师提醒我们用回溯法,我写起来并没有什么太大的难度。但写QT的时候,真的是煞费苦心。主要的内容在graph.h,graph.cpp和mainwindow.cpp里,graph.h里放主要的结构体和类,graph.cpp里是功能的实现,mainwindow.cpp主要是界面的实现。而从界面里读取的内容一般是QString类型,要把他转换出string型。还有就是要注意头文件的添加。

在这次课程设计中,我收获很多。收获最多的就是如何画无向图,QCoreApplication的应用,如何将Qstring转换成string,string和int相互转换的方法,如何用append函数读取文件,赋值等。更让我收获的是写代码的耐心和细心,还有在网路上搜索资料的方法。而感受也有许多,除了累还有一种满满的收获感。

上传的附件 cloud_download 算法与数据结构程序设计报告.docx ( 585.88kb, 1次下载 ) cloud_download search2.zip ( 9.11kb, 1次下载 )
error_outline 下载需要12点积分

发送私信

2
文章数
2
评论数
最近文章
eject