数据结构实验七

1、实 验 报 告（2014 / 2015 学年 第 一 学期）课程名称数据结构使用C+语言描述实验名称图的基本运算及飞机换乘次数最少问题实验时间2014年12月3日指导单位计算机科学与技术系指导教师学生姓名班级学号学院(系)专 业实 验 报 告实验名称图的基本运算及飞机换乘次数最少问题指导教师实验类型上机实验学时4实验时间2014年12月3日一、 实验目的和要求1. 验证在邻接矩阵和邻接表实现图的基本运算的算法；在邻接矩阵存储结构上实现图的深度和宽度优先遍历算法。2.设有n个城市，编号为0n1，m条航线的起点和终点由用户输入提供。寻找一条换乘次数最少的线路方案。提示：可以使用有向图表示城市间的航

2、线。只要两城市间有航班，则图中这两点间存在一条权为1的边。可以使用Dijkstra算法实现。思考：如果是城市公交车的最少换乘问题，将如何解决？假如希望使用类似的算法，则图中的边如何设置？二、实验环境(实验设备)Vs2013 win8.1实验原理及内容:实验一：1）掌握在图的邻接矩阵和邻接表存储结构实现图的基本运算的算法2）学习使用图算法解决应用问题的方法 邻接矩阵的遍历与邻接表的遍历类似，都是通过递归来实现。以下是代码：void ExtMGraph:DFS()bool *visited = new booln;for (int i = 0; in; i+)visitedi = false;fo

3、r (i = 0; in; i+)if (!visitedi)DFS(i, visited);cout endl;deletevisited;templatevoid ExtMGraph:DFS(int v, bool *visited)visitedv = true;cout v;for (int u = 0; un; u+)if (avu != noEdge & !visitedu)DFS(u, visited);templatevoid ExtMGraph:BFS()bool *visited = new booln;for (int i = 0; in; i+)visitedi = f

4、alse;for (int i = 0; in; i+)if (!visitedi)BFS(i, visited);deletevisited;templatevoid ExtMGraph:BFS(int v, bool *visited)SeqQueueq(Vertices();visitedv = true;cout v;q.EnQueue(v);while (!q.IsEmpty()q.Front(v);q.DeQueue();for (int i = 0; in; i+)if (!visitedi & avi != noEdge)visitedi = true;cout i;q.EnQ

5、ueue(i);在主函数中只要添加该代码：#include”extMGraph.h”void main()int weight = 3;int noEdge = 1000;int k = 1; int l = 2;ExtMGraph extMGraph2(8,noEdge);extMGraph2.Insert(1, 2, k);extMGraph2.Insert(1, 4, k);extMGraph2.Insert(2, 3, k);extMGraph2.Insert(4, 3, k);extMGraph2.Insert(4, 5, k);extMGraph2.Insert(3, 6, k);

6、extMGraph2.Insert(5, 7, k);extMGraph2.Insert(6, 7, k); extMGraph2.DFS();extMGraph2.BFS(); 实验二：飞机的换乘问题。具体实现代码:Graph.h:#includeusing namespace std;enum ResultCode Underflow,Overflow,Success,Duplicate,NotPresent ;void showResultCode(ResultCode result)int r = (int)result;switch (result)case 0:cout Resul

7、tCode: Underflow endl; break;case 1:cout ResultCode: Overflow endl; break;case 2:cout ResultCode: Success endl; break;case 3:cout ResultCode: Duplicate endl; break;case 4:cout ResultCode: NotPresent endl; break;default: cout Exception occured:unknown resultcode endl;template class Graphpublic:virtua

8、l ResultCode Insert(int u, int v, T&w) = 0;virtual ResultCode Remove(int u,int v) = 0;virtual bool Exist(int u,int v)const = 0;virtual int Verticles()const return n; protected:int n, e;/e为边数;MGraph.h:#includeGraph.htemplate class MGraph :public Graphpublic:MGraph(int mSize, const T& noedg);MGraph();

9、ResultCode Insert(int u, int v, T&w);ResultCode Remove(int u, int v);bool Exist(int u, int v)const;protected:T *a;T noEdge;template MGraph:MGraph(int mSize, const T&noedg)n = mSize; e = 0; noEdge = noedg;a = new T*n;for (int i = 0; i n; i+)ai = new Tn;for (int j = 0; j n; j+)aij = noEdge;aii = 0;tem

10、plate MGraph:MGraph()for (int i = 0; i n; i+) deleteai;deletea;template bool MGraph:Exist(int u, int v)constif (u0 | vn - 1 | vn - 1 | u = v | auv = noEdge) return false;return true;template ResultCode MGraph:Insert(int u, int v, T&w)if (u 0 | vn - 1 | u = v) return Overflow;if (auv != noEdge) retur

11、n Duplicate;auv = w; e+; return Success;template ResultCode MGraph:Remove(int u, int v)if (u 0 | vn - 1 | u = v) return Overflow;if (auv = noEdge) return NotPresent;auv = noEdge; e-; return Success; extMGraph.h:#includeMGraph.h#includeSeqQueue.h#define INFTY 10000templateclass ExtMGraph :public MGra

12、phpublic:ExtMGraph(int mSize, const T&noedg) :MGraph(mSize, noedg)void DFS();void BFS();int Choose(int *d, bool *s);void Dijkstra(int v, T *d, int *path);void ShowDijkstra(int v, int flag);void Floyd(T *d, int *path);int Vertices() return n; private:void DFS(int v, bool *visited);void BFS(int v, boo

13、l *visited);templatevoid ExtMGraph:DFS()bool *visited = new booln;for (int i = 0; in; i+)visitedi = false;for (i = 0; in; i+)if (!visitedi)DFS(i, visited);cout endl;deletevisited;templatevoid ExtMGraph:DFS(int v, bool *visited)visitedv = true;cout v;for (int u = 0; un; u+)if (avu != noEdge & !visite

14、du)DFS(u, visited);templatevoid ExtMGraph:BFS()bool *visited = new booln;for (int i = 0; in; i+)visitedi = false;for (int i = 0; in; i+)if (!visitedi)BFS(i, visited);deletevisited;templatevoid ExtMGraph:BFS(int v, bool *visited)SeqQueueq(Vertices();visitedv = true;cout v;q.EnQueue(v);while (!q.IsEmp

15、ty()q.Front(v);q.DeQueue();for (int i = 0; in; i+)if (!visitedi & avi != noEdge)visitedi = true;cout i;q.EnQueue(i);templateint ExtMGraph:Choose(int *d, bool *s)int i, minpos;T min;min = INFTY;minpos = -1;for (i = 0; in; i+)if (dimin&!si)min = di;minpos = i;return minpos;templatevoid ExtMGraph:Dijks

16、tra(int v, T *d, int *path)int i, k, w;if (vn - 1)cout out of bounds! endl;return;bool *s = new booln;for (i = 0; in; i+)si = false;di = avi;if (i != v&diINFTY)pathi = v;else pathi = -1;sv = true;dv = 0;for (i = 0; in - 1; i+)k = Choose(d, s);sk = true;for (w = 0; wn; w+)if (!sw & dk + akwdw)dw = dk

17、 + akw;pathw = k;templatevoid ExtMGraph:ShowDijkstra(int v, int flag)T *d = new Tn;int *path = new intn;int temp;Dijkstra(v, d, path);for (int i = 0; in; i+)cout i : ;if (i = v)cout 该处为源点 endl;else if (pathi = -1)cout 没有路径 endl;elsecout i - ;temp = pathi;while (pathtemp != -1)cout temp -;temp = path

18、temp;if (flag = 0)cout temp endl -total weight: di endl;if (flag = 1)cout temp endl -change flight di - 1 times endl;else if (flag = 2)cout temp endl -change bus di - 1 times endl;deleted;deletepath;templatevoid ExtMGraph:Floyd(T *d, int *path)int i, j, k;for (i = 0; in; i+)for (j = 0; j n; j+)dij =

19、 aij;if (i != j &aijINFTY)pathij = i;else pathij = -1;for (k = 0; kn; k+)for (i = 0; in; i+)for (j = 0; jn; j+)if (dik + dkjdij)dij = dik + dkj;pathij = akj;FlightManagement.h:#includeExtMGraph.h/#includeExtLGraph.hclass FlightManagementpublic:static int inputCity(istream & in, ostream & out);static

20、 ExtMGraph* inputFlight(istream & in, ostream & out, int city, const int&noedge);static int inputSource(istream & in, ostream & out);static void Process(ExtMGraph *extMGraph, int t);int FlightManagement:inputCity(istream & in, ostream & out)int city;out city;return city;ExtMGraph* FlightManagement:i

21、nputFlight(istream & in, ostream & out, int city, const int& noedge)ExtMGraph *extMGraph = new ExtMGraph (city, noedge);out Please input the flights: (source,end) end up with # c;while (c != #)if (c = () | (c = ) | (c = ,)in c;continue;if (c = 0) & (c source;in c;in end;extMGraph-Insert(source, end,

22、 weight);in c;return extMGraph;int FlightManagement:inputSource(istream & in, ostream & out)int t;out t;return t;void FlightManagement:Process(ExtMGraph *extMGraph, int t)extMGraph-ShowDijkstra(t, 1);/t为起点Manager.h:#includeFlightManagement.hclass BusManagementpublic:static int inputbusStation(istrea

23、m & in, ostream & out);static ExtMGraph* inputRoutine(istream & in, ostream & out, int busStation, const int&noedge);static int inputSource(istream & in, ostream & out);static void Process(ExtMGraph *extMGraph, int t);int BusManagement:inputbusStation(istream & in, ostream & out)int busStation;out b

24、usStation;return busStation;void clear(int *t, int n);ExtMGraph* BusManagement:inputRoutine(istream & in, ostream & out, int busStation, const int& noedge)ExtMGraph *extMGraph = new ExtMGraph(busStation, noedge);out Please input the Routines: (source,end) end up with # Vertices();/返回节点数目int *routine

25、 = new intn;clear(routine, n);/routei=-1int i = 0;in c;while (c != #)if (c = ()in c;while (c != )if (c = ,)in c;continue;else if (c = 0) & (c routinei+;in c;for (int j = 0; ji; j+) for (int x = j + 1; xInsert(routinej, routinex, weight);extMGraph-Insert(routinex, routinej, weight);clear(routine, n);

26、i = 0;in c;return extMGraph;int BusManagement:inputSource(istream & in, ostream & out)int t;out t;return t;void BusManagement:Process(ExtMGraph *extMGraph, int t)extMGraph-ShowDijkstra(t, 2);void clear(int *t, int n)for (int i = 0; i inquery;while (1)if (inquery = b)inqueryBus(noEdge);else if (inque

27、ry = f)/飞机inqueryFlight(noEdge);else if (inquery = x)/退出cout Inquery complete. endl;break;elsecout Wrong input! Please input again. endl inquery;void Manager:message()cout f-flight inquery endl;cout b-bus inquery endl;cout x-exit inquery endl;cout Please input the type of inquery you want: ;void Man

28、ager:inqueryBus(int noEdge)int source;int busStation = BusManagement:inputbusStation(cin, cout);/输入公交车站点个数ExtMGraph* pointer = BusManagement:inputRoutine(cin, cout, busStation, noEdge);/构图source = BusManagement:inputSource(cin, cout);while (1)if (source = busStation)/输入异常cout Wrong input of source point. endl;cout Please input again:(0=source busStation ) endl;source = BusManage