南邮数据结构实验三

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

2、存在 条权值为1的边；可以使用DijkStra算法实现。二、实验环境(实验设备)VSUAL STUDlO2015三、实验原理及内容对象视图： ® COnSOIeAPPIiCatiOn13® -MGraPhO 全局函0 ChoOSe(int * d, bool * S)七 Graph<T>0 DijkStra(int v. T * dt int * Path)Q ife0 Exist(intUI intv) COnStt> 七 MGraPh<T>0 InSert(int Ur int Vr T W)J 七 MGraPhUTA0 MGraPh(in

3、t mSize, COnSt T noedg) Q SS10 RemOVe(int Ur int V)/ f Graph<T>乞 a G 派生焚型0. noEdge七 MGraPh<T>夕 ReSUltCOde源代码：Graph.h# include<iostream># include<stri ng.h>USing namespace std;COnSt int INF = 2147483647;enum ReSUItCOde UnderfIOWI DUPIiCateI FaiIUrel SUCCeSSl NOtPresent, OUtofB

4、OUndS; template <class T>CIaSS GraPh 抽象类public:VirtUal ReSUltCOde Insert(int u, int v, T w) = O;VirtUal ReSUItCOde RemOVe(int UJ int V) = O;VirtUal bool Exist(int u, int V)COnSt = O;protected:int n, e;template <class T>ClaSS MGraPh :PUbliC Graph<T> 邻接矩阵类(public:MGraPh(int mSizej CO

5、nSt T nOedg);-MGraPh0；ReSUltCOde InSert(int u, int Vl T w);ReSUItCOde RemOVe(int UI int v);bool Exist(int u, int V)COnSt;int ChOOSe(int *d, bool *s);VOid DijkStra(int VI T *d, int *path);protected:T 4,*a;T noEdge;template <class T>MGraPh<T>:MGraPh(int mSiel COnSt noedg)(n = mSize;e = O;n

6、oEdge = nOedg;a = new T*n;for (int i = O; i<n; i+)ai = new Tn;for (int j = O; j<n; j÷÷)aij = n OEdge;aii = O;template <class T>MGraPh<T>:-MGraPhO(for (int i = 0; i<n; i+÷) deleteai;deletea;template <class T>ReSUItCOde MGraPh<T>:Insert(int Ul int Vl T W

7、)(if (u<0 H v<0 H u>n 1 VAn 1 U = V)return Failure;if (auv != noEdge)return DUPliCate;auM = w;avu = w;e÷÷return Success;template <class T>ReSUltCOde MGraPh<T>:Remove(int u, int V)if (u<0 H v<0 H u>n 1 v>n 1 U = V)return Failure;if (auv = noEdge)return NotPr

8、esent;au = noEdge;avu = noEdge;e-；return Success;tenplate<class -Abool MGraPh<T>:Exist(int UI int V)COnSt(if (u<0 H v<0 H u>n 1 IlVAn 1 U=Vll auv = noEdge) return false;return true;template <class T>int MGraPh<T>:ChOOSe(int *d, bool *s) 求最小di(int i, rinpos;一 min;min = I

9、NF;rinpos = -1;for (i = 0; i<n; i÷÷)if (di <= min&&!si)rin = di; minpos = i;return minpos;template <class >VOid MGraPh<T>:DijkStra(int v, T *dt int *path)/迪杰斯特拉算法(int i, k, w;if (v<0 v>n 1)throw OutOfBounds;bool *s = new booln;for (i = O; i<n; i÷+)si

10、 = false;di = avi;if (i!= v&&di<INF)Pathi = v;elsepathi = -1；sv = true;dv = O;for(i = lj<n; i+)k = ChOOSe(dl s);sk = true;for (W =O; w<n; w÷÷)if (!sw && (dk + akw)<dw) (dw = dk ÷ akw; pathw = k;源cpp# include<iostrear># include<stri ng.h>#include

11、HGraph.h"USing namespace std;int maiO(int n, r;COUt << "请输入城市个数Cin >> n;COUt « "请输入航线条数:Cin >> m;MGraPh<int>A(n, INF);int c, tCOUt请输入每条航线的起点和终点：,« endl;for (int i = O; i<m; i+÷)COUt «« i + 1 « ,:,;Cin >> C >> f;AJnSe

12、rt(Gt 1);Char s;do int v, w;CoUt « 请输入你的起点和终点:"；Cin >> V >> w;While (v<0 w<0 w>n - 11 v>n 1)(COUt <V ”输入错误!，没有该城市:”；Cin >> V >> w;int >b = new itn;int "d = new intn;int *path = new intn;A.Dijkstra(v, dj path);int e = n 1;int j, i,k = O;for O =

13、 O; j<n; j÷+)bj = -2;if (w!= V)(j = W；WhiIe (pathj != -1)be = pathj;e-;j = path;)if (e=二 n 1 H d = INF)COUt << ”这两点间无线路广« endl;elseCoUt << ,M, « V « ”城市到« W « 城市的换乘次数最小的线路方案为:”; for (k = 0; k<n; k+)(if (bk != -2)COUt << bk « T;COUt <<

14、W << endl;if (W = V)COUt W看来你钱比较多” « endl;deleteJb;deleted;deleteQpath;COUt « "请问是否继续查询路线?请输入Y/N:"Cin >> s;WhiIe (S != '¥&&s != 'y'&&s != h&&s != ,N,)CoUt « ”请问是否继续查询路线?请输入Y/N:*1;Cin >> s;) while (S = ,Y, S = Y);retu

15、rn 0;运行截图:资料.Z c:uierA107l6documenuvfcual studio 201 SProjectConso!eAlkatk) 13DebgC(aleAplkatio 13,e×e×睛输入瓠线条数:5请输入每条磁线的起点和终点： 轨斜：1 5希入错谋！没有该城市：1 4眦线2： 1 0菰履3: 1 3轨践4: 1 2航线5: 3 5嶄入错谋！，没有该域市:3 4请输入你的起点和终点：0 4从0城市到4城市的换乘次敛最小的炭疼方案为:0,1, 4 谐问是否继渎査询路线?请辎入Y/N:Y陰输入你的起点和终虫:2 5會入错误!，没有该城市：2 4从2城市到4城市的换乘次缴最小的统路方案为:2,1, 4 i窘问是否线渎査询路线?谊轲入Y/N:Y席输入你的起点和终点：4 4看来你钱比较多诲问是否逖渎舌询路綫?请驹入Y/N:、.实验报告四、实验"'结（包括问题和解决方法、心得体会、意见与建议等）使用邻接表表示的图½