南邮数据结构实验三

《南邮数据结构实验三》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.实验报告（2015/2016学年第一学期）课程名称数据结构实验名称图的基本运算及飞机换乘次数最少问题实验时间2015年12月4日指导单位计算机科学与技术系指导教师黄海平学生姓名陈明阳班级学号Q14010119学院(系)贝尔英才专业信息科技强化班word教育资料.实验报告实验名称图的基本运算及飞机换乘次数最少问题指导教师黄海平实验类型验证实验学时4实验时间12.4一、实验目的和要求飞机最少换乘次数问题。（1）设有n个城市，编号为0~n-1，m条航线的起点和终点由用户输入提供。寻找一条换乘次数最少的线路方案。（2）参考：可以使用有向图表示城市间的航线；只要两城市间有航班，则图中

2、这两点间存在一条权值为1的边；可以使用Dijkstra算法实现。二、实验环境(实验设备)VSUALSTUDIO2015三、实验原理及内容对象视图：源代码：Graph.hword教育资料.#include#includeusingnamespacestd;constintINF=2147483647;enumResultCode{Underflow,Duplicate,Failure,Success,NotPresent,OutOfBounds};templateclassGraph//抽象类{public:virtual

3、ResultCodeInsert(intu,intv,Tw)=0;virtualResultCodeRemove(intu,intv)=0;virtualboolExist(intu,intv)const=0;protected:intn,e;};templateclassMGraph:publicGraph//邻接矩阵类{public:MGraph(intmSize,constTnoedg);~MGraph();ResultCodeInsert(intu,intv,Tw);ResultCodeRemove(intu,intv);boolExist(in

4、tu,intv)const;intChoose(int*d,bool*s);voidDijkstra(intv,T*d,int*path);protected:T**a;TnoEdge;};templateMGraph::MGraph(intmSize,constTnoedg){n=mSize;e=0;noEdge=noedg;a=newT*[n];for(inti=0;i

5、MGraph::~MGraph(){for(inti=0;iResultCodeMGraph::Insert(intu,intv,Tw){if(u<0

6、

7、v<0

8、

9、u>n-1

10、

11、v>n-1

12、

13、u==v)returnFailure;if(a[u][v]!=noEdge)returnDuplicate;a[u][v]=w;a[v][u]=w;e++;returnSuccess;}templateResultCodeMGraph::Remove(intu,

14、intv){if(u<0

15、

16、v<0

17、

18、u>n-1

19、

20、v>n-1

21、

22、u==v)returnFailure;if(a[u][v]==noEdge)returnNotPresent;a[u][v]=noEdge;a[v][u]=noEdge;e--;returnSuccess;}templateboolMGraph::Exist(intu,intv)const{if(u<0

23、

24、v<0

25、

26、u>n-1

27、

28、v>n-1

29、

30、u==v

31、

32、a[u][v]==noEdge)returnfalse;returntrue;}templateintMGraph

33、::Choose(int*d,bool*s)//求最小d[i]{inti,minpos;Tmin;word教育资料.min=INF;minpos=-1;for(i=0;ivoidMGraph::Dijkstra(intv,T*d,int*path)//迪杰斯特拉算法{inti,k,w;if(v<0

34、

35、v>n-1)throwOutOfBounds;