校园地图设计——任意两点间的算法优化流程与while搭配switch语句的bug解读

建议大家看着篇文章之前，先把我的校园地图设计那篇文章了解一下，这篇文章是阐述程序设计中存留的优化问题

话不多说，先上代码

/输出任一两点间的最短路径与长度 void Dispath(int dist[], int path[], int vv,int ee,Graph g)//输出从源点v出发的所有最短路径 { int i, j, k; int d;//存放一条最短路径（逆向）及其顶点个数 string apath[MAXVEX]; for (i = 0; i < g.numVertexes; i++)//n为顶点个数，循环n次，输出源点到其余各个顶点的最短路径和路径长度 { if (i == ee){ cout << "从" << g.vexs[vv].name << "到" << g.vexs[ee].name << "的路径长度为:" << dist[i] << "\t路径为："; d = 0; apath[d] = g.vexs[i].name;//源点到i的最短路径上的终点为i，终点i存放在apath[0] k = path[i];//源点到i的最短路径上，顶点i的前一个顶点为k if (k == -1) //没有路径的情况 cout << "无路径\n"; else//存在源点到i的最短路径时输出该路径 { while (k != vv)//当k值等于源点编号时，循环结束 { d++; apath[d] = g.vexs[k].name;//将源点v到i的最短路径上所经过的顶点编号，逆序存放在apath[d] k = path[k]; } d++; apath[d] = g.vexs[vv].name;//存储源点v到i的最短路径上的起点v cout << apath[d];//先输出起点 for (j = d - 1; j >= 0; j--)//再输出其他顶点 { cout <<"->"<< apath[j]; } } } } } //求任一两地点之间的最短路径和长度 void shortestPath(Graph g, int v,int e) { int vv = v; int ee = e; int dist[MAXVEX], path[MAXVEX]; int F[MAXVEX]; int mindis, i, j, u; for (i = 0; i<g.numVertexes; i++) { dist[i] = g.arc[v][i]; //距离初始化 F[i] = 0; //F[]置空 if (g.arc[v][i]<INF) //路径初始化 等价于如果有边 path[i] = v; //顶点v到i有边时 else path[i] = -1; //顶点v到i没边时 } F[v] = 1; //源点v放入S中 for (i = 0; i<g.numVertexes; i++) //循环n次 { mindis = INF; for (j = 0; j<g.numVertexes; j++) if (F[j] == 0 && dist[j]<mindis) { u = j; mindis = dist[j]; } F[u] = 1; //顶点u加入S中 for (j = 0; j<g.numVertexes; j++) //修改不在s中的顶点的距离 if (F[j] == 0) if (dist[u] + g.arc[u][j]<dist[j]) { dist[j] = dist[u] + g.arc[u][j]; path[j] = u; } } Dispath(dist, path, vv,ee,g); //输出最短路径 cout << endl; }

快速回顾一下，shortestPath函数中的内容其实就是迪杰斯特拉算法的具体实现，而Dispath这个函数是用来“美观”地输出最短路径的（本质上不用这个函数也可以实现输出，只不过有点不美观），那我呢就把这些输出的冗余代码做了一个封装

优化思路

其实明眼的朋友一眼就能看出来，做了许多不必要的判断与循环操作，那么在哪里呢？我这里找出了三个不必要的地方

shortestPath函数中不需要将全部顶点的最短路径都求出来 当我们盯准了F[u]=1;这个操作的时候，可以知道当F[终点]=1 时，那么便不需要继续循环下去，此时可以用break语句跳出外层的for循环（F数组代表着顶点是否已完成最短路径的求解，如果完成值为1，未完成时值为0）Dispath函数中冗余的for循环 很明显这个for循环是不必要的，可能是因为当时赶着交课设，脑子发热…，因为我们已经拥有最终的dist和path数组，是不需要这个循环的；如果要说循环存在的唯一意义，那就是输出起始点至所有顶点的最短路径来用的，显然我们的题目需求只需要求任意两点之间的最短路径就可以了Dispath函数中冗余的if判断 这个失误是因为第二点的连锁反应所导致的（可能当时总是想着要求全部顶点最短路径的原因），咕咕在这里给大家道歉了，所以这个if语句也应当去掉

优化之后的代码

//输出任一两点间的最短路径与长度 void Dispath(int dist[], int path[], int vv,int ee,Graph g)//输出从源点v出发的所有最短路径 { int i,k; //存放其顶点个数 int d; //存放一条最短路径（逆向） string apath[MAXVEX]; cout << "从" << g.vexs[vv].name << "到" << g.vexs[ee].name << "的路径长度为:" << dist[ee] << "\t路径为："; d = 0; apath[d] = g.vexs[ee].name;//源点到i的最短路径上的终点为i，终点i存放在apath[0] k = path[ee];//源点到i的最短路径上，顶点i的前一个顶点为k if (k == -1) //没有路径的情况 cout << "无路径\n"; else//存在源点到i的最短路径时输出该路径 { while (k != -1)//当k值等于源点编号时，循环结束 { d++; apath[d] = g.vexs[k].name;//将源点v到i的最短路径上所经过的顶点编号，逆序存放在apath[d] k = path[k]; } cout << apath[d];//先输出起点 for (i = d - 1; i >= 0; i--)//再输出其他顶点 { cout <<"->"<< apath[j]; } } } //求任一两地点之间的最短路径和长度 void shortestPath(Graph g, int v,int e) { int vv = v; int ee = e; //dist数组用来存储顶点v到顶点e的最短路径的长度，path数组用来存储初始点到各个顶点的最短路径上的前驱顶点 int dist[MAXVEX], path[MAXVEX]; //F数组用来表示顶点是否已求出最短路径，如果求出置为1，未求出置为0 int F[MAXVEX]; int mindis, i, j, u; //对dist、path、F数组进行初始化 for (i = 0; i<g.numVertexes; i++) { //将起始点v到各个顶点之间的距离进行初始化 dist[i] = g.arc[v][i]; //F数组各个元素均置为0，均未求出最短路径 F[i] = 0; if (g.arc[v][i]<INF) //路径初始化 等价于如果有边 path[i] = v; //顶点v到i有边时 else path[i] = -1; //顶点v到i没边时 } F[v] = 1; //源点v放入F中 for (i = 0; i<g.numVertexes; i++) //循环n次 { mindis = INF; for (j = 0; j<g.numVertexes; j++) //找出未求出最短路径中的顶点中距离源点v最近的点 if (F[j] == 0 && dist[j]<mindis) { u = j; mindis = dist[j]; //令mindis存储dist数组中的最小值 } //顶点u加入S中，因为此时u是距离源点最近的点，代表已求出最短路径 F[u] = 1; //优化思路：如果F[ee]=1，那么就不用再更新dist数组和path数组的值了，也就是说终点的最短路径已求出 if (F[ee] != 1) { for (j = 0; j < g.numVertexes; j++) //修改不在s中的顶点的距离 if (F[j] == 0) if (dist[u] + g.arc[u][j] < dist[j]) { dist[j] = dist[u] + g.arc[u][j]; path[j] = u; } }else{ break; } } Dispath(dist, path, vv,ee,g); //输出最短路径 cout << endl; }

我们可以看到改动并不是很大，并且也不改变算法原本的时间复杂度，但是养成优化程序的习惯总是好的，至少在优化的过程中我们可以学到更多东西，也更加对自己的程序更加地了解

bug解读

这里我要说一个我在调试整个系统程序过程中遇到的问题，也就是while搭配switch语句会发生死循环或者出现程序输出失去控制（意料之外）的情况

先上出现bug的代码：

//功能实现 int function(){ Graph g; Graph *ptr = &g; createGraph(ptr); //邻接矩阵创建图 int v, e; int chose; string str, start, end; while (true) { menum(); cout << endl; cout << "请输入相应的数字编号" << endl; cin >> chose; switch (chose) { case 1: printGraph(g); break; case 2: cout << "请输入待查地点的名称:"; cin >> str; if (locates(ptr, str) == -1) { cout << "查询地点发生错误,请重新操作!!!!" << endl; break; } else { find(g, str); } break; case 3: cout << "请输入任意两地的名称，名称之间用空格隔开，以回车结束：" << endl; cin >> start >> end; v = locates(ptr, start); e= locates(ptr, end); if (v == -1 || e == -1) { cout << "查询地点发生错误,请重新操作!!!!" << endl; break; } else { shortestPath(g, v, e); } cout << endl; break; case 4: cout << "感谢您的光临！" << endl; return 0; default: cout << "操作数输入错误，请重新操作！" << endl; break; } //cin.ignore(100, '\n'); } }

情景如下：

情景一： 在我测试第二个功能（查询任意地点的基本信息）的时候，在程序中我写的是接收一个string类型的变量，但是当我输入带有空格的字符时，例如（“广东 中山”），此时是非法的，按程序的执行顺序来看，程序应该会跳出此循环，并再次显示菜单； 情景二： 当我测试菜单栏功能的时候，原本按正常输入的话是输入一个数字，那么case就会对我输入的数字进行一个匹配的操作，但是当我输入的是带有空格的字符的时候，例如（“6 哈萨 ”），此时是非法的输入，按程序的执行顺序来看，程序应该会进入default分支，并跳出循环和显示菜单栏。 （这个bug不仅仅局限于这两个场景，还会发生在其他的所有功能并且要求输出操作的上面）

分析：

情景一 我们仔细观察程序无限循环输出的部分

每次死循环都是输出菜单、提示输入的语句和请输入地点名称的提示，但是系统并没有让我们自行输入，而是像被自动接收了值一样！

那么回到我们测试功能二时输入的数据，“广东 中山”，很明显，程序里我只写了接收一个string类型的变量，但是输入的是两个string类型变量+一个空格+一个回车，但是系统只接收了第一个string变量“广东”，所以经过非法性判断后是非法的，应该跳出循环并继续显示菜单栏和提示输入语句。

**重点来了，为什么它没有接收我手动输入的“操作”编号呢？也没有接收我的手动输入的待查地点名称呢？而这一切完全像是系统给你演了一出剧。我的解释是：第一次输入的“ 2 ”这个值并没有被系统清除，而是保存在了数据缓存区，同理，第一次输入的“广东 中山”这个串也被保存在了数据缓存区，所以当程序在测试功能二时，进行非法判断报错之后，跳出switch语句之前，在数据缓存区是保存着“2 广东 中山”这一串数据的，所以当我们第二次进入while循环的时候，程序需要接收一个整型操作数，那么程序会自动从数据缓存区里先获取，因为这个动作比程序需要用户手动输入的优先级更高，所以程序会从“2（回车） 广东 中山（回车）”这个串中获取了“2（回车）”，回车代表输入流结束，所以代表着接收一个整型数据结束，所以会进入第二个功能的提示页面（“请输入待查地点的名称：”），但是注意，接收完了之后系统并没有清除数据缓冲区的内容

进入第二个功能里面后，我们知道系统会要求用户输入一个string类型的变量，那我们也知道数据缓存区里面还有着“2（回车） 广东 中山（回车）”这一串的字符（系统并没有清除），那么系统也会自动地从数据缓存区里面接收数据，也就是接受了“2（回车）”，那么近经过非法性判断后的结果肯定是会报错的，所以出现了“查询地点发生错误，请重新操作！！！”这么一个语句，至此会跳出switch语句，进行第三次循环，显而易见，程序必定会一直死循环下去。

情景二 我们也来观察一下此刻的死循环的部分

可以看到，程序要求用户输入整型操作数，但是我们输入了“6 哈萨（回车）”这一串字符，很明显，程序会走到default分支，因为程序接受了“ 6 哈萨（回车）”这个串，所以会提出操作数错误的警告，继而跳出switch语句，进入新的while循环；那么我们知道，数据缓存区里面始终存在着“6 哈萨（回车）”这一串字符，所以程序必定进入死循环。

解决方案：

当程序输入字符串，字符串和回车会存储在数据缓存区中，并不会自动清空，当下次输入操作来临时，输入流内的字符会自动给cin接收，而不会让用户手动输入。所以解决这类问题需要把数据缓存区中的字符串在下一次cin操作来临前都给清除掉。

我自己提供的方法就是在while循环最末尾、switch语句之后，加一句cin.ignore(100,’\n’),这一句话的作用就是把回车（包括回车）之前的100个字符从数据缓存区中清除出去，这样在进入新的while循环时，就不会出现数据缓存区总是残存数据的情况

总结

好啦，总结一下今天的主要内容

1. 任一两点之间最短路径的算法优化

算法优化能给我们带来意料之外的收获，也会让我们更加具有创造性，我觉得这是一个非常值得去思考的一件事** 3. while搭配switch语句出现死循环bug的解读

这个bug我之前也看过许多解读，因为出现问题就上百度看看嘛，但是咕咕表示很多都没有讲得很详细，所以我在这里作出了我自己的见解；如果发现文中存在错误之处，欢迎大家指正呀！