}
}
}
}
}
5.源代码
#include
struct ArcCell { int adj; //存放弧长
bool *info; //是否用过该弧 };
struct _MGraph {
char vexs[20]; //存放站点 ArcCell arcs[20][20]; //
typedef int Path[20][20][20]; typedef int Distanc[20][20];
class MGraph //没用私有成员 {
public: _MGraph mgraph;// void DestroyGraph(); //析构函数销毁图 int LocateVex (char u); // 返回顶点在图中的位置 bool CreateDN(); //构造有向网 void ShortestPath_FLOYD(Path &P,Distanc &D); };
bool MGraph::CreateDN()//构造有向网 { int i,j ,w; char v1, v2; cout<<\请输入站点个数，直接可达线路的条数: \ cin>>mgraph.vexnum>>mgraph.arcnum ;
cout<<\请输入各站点名: \ for(i = 0;i
void MGraph::DestroyGraph() { for(int i = 0 ;i } int MGraph::LocateVex(char u) { for(int i = 0 ;i<20;i++) { if(u == mgraph.vexs[i]) { return i; } } return -1; } void MGraph::ShortestPath_FLOYD(Path &P,Distanc &D)//求每对顶点间的最短路径 // 用Floyd算法求有向网G中各对顶点v和w之间的最短路径P[v][w]及其带权长度D[v][w] // 若P[v][w][u]为TRUE，则u是从v到w当前求得最短路径上的顶点。 { int u,v,w,i; for(v = 0;v P[v][w][i] = P[v][u][i]||P[u][w][i];//从v到w的路径经过从v到u和从u到w的所有路径 } } } } } void main() { MGraph g; Path p; // 3维数组 Distanc d; // 2维数组 int s,t,k; char v1,v2; float sum=0; cout<<\欢迎使用交通指南系统**************\\n\ g.CreateDN(); cout<<\请依次输入您的出发站和目的站站点名称：\ cin>>v1>>v2; s=g.LocateVex (v1); t=g.LocateVex (v2); g.ShortestPath_FLOYD(p,d); if(s!=t) { int a=s; cout<<\由站点\到站点\途中经过站点：\ for(k = 0;k cout<<\感谢您的使用！*****************\ cout<<\祝您旅途愉快！*****************\ g.DestroyGraph(); } 6.举例测试及运行结果 例： 10 B 20 A 15 15 C 20 30 D 7.收获与体会 这是一个实际应用题。本实验的核心代码是用FLOYD算法求有向网G中各对顶点v和w之间的最短路径P[v][w]及其带权长度D[v][w],其中利用到了一些稍许繁琐的数据存储结构。通过本实验，我觉得熟练掌握所学的算法对于编程解决实际问题非常有效。我们应该在平时多用我们所学的数据结构知识编写程序，尝试解决实际的问题。 刚开始的时候，根据书上的提示自己编写好程序输入电脑，然后编译的时候，出现了许许多多各种各样的问题，回头查看程序，自己却很难找到问题所在，于是查阅各种资料，问了身边很多同学，终于将程序顺利调试出来了。通过这个系统的实现，我从输入代码跟运行调试的整个过程中学习到了很多东西，也了解到系统出现问题的时候的各种错误应该如何解决。 这次的实验使我了解到，平时对知识的积累相当重要，同时也要注重课上老师的讲解，老师在课上的延伸是课本上所没有的，这些知识对于我们对程序的编写有很大的作用，同时，编程也要求我们有足够的耐心，细细推敲。越着急可能就越无法得到我们想要的结果，遇到不会的问题要多多请教，知识是在实践与向别人请教的过程中积累的，所以问是至关重要的，只要肯下功夫很多东西都是可以完成的。 数据结构这门课程更加注重设计灵活、巧妙的算法，提高程序运行效率，这对我逻辑思维能力的提高有相当大的帮助。虽然这学期学完了这门课程，但我在以后的学习中不会放下数据结构，而是经常回顾温习，并多从生活中寻找和发现问题，进而尝试用数据结构的知识设计算法，并进行简单的实现。相信这样的积累过程对我今后的学习生活大有帮助，让我受益终生。