南邮数据结构实验三图的基本运算及飞机换乘次数最少问题

1、 实 验 报 告（ 2015 / 2016 学年 第 2学期） 课程名称数据结构A实验名称图的基本运算及飞行换乘次数最少问题实验时间年月日指导单位计算机科学与技术系指导教师 学生姓名班级学号学院(系)专 业 试验一 图的基本运算1、 问题描述（1） 验证教材中关于在邻接矩阵和邻接表两种不同存储结构上实现图的基本运算的算法（见程序9.1程序9.8）； （2） 在邻接矩阵存储结构上实现图的深度和广度优先遍历算法；（3）设计主函数，测试上述运算；（4）提示：扩充MGraph类，在扩充类上增加DFS和BFS函数；2、 概要设计 图如下所示，显示了名为operation_of_map的（默认文

2、件名）工程，实现了Graph,SeqQueue,结点类ENode,邻接矩阵类MGraph,邻接表LGraph类，包括几种为不同传入类型准备的构造函数。声明所要求的函数，并在后续过程中实现函数功能，最后通过一个main函数求解。3、 详细设计1. 类与类的层次结构Graph类public:virtual 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;protected:int n,

3、e;SeqQueue类 MGraph类public:SeqQueue(int mSize);SeqQueue() deleteq; bool IsEmpty() const return front = rear; bool IsFull() const return (rear + 1) % maxSize = front; bool Front(T &x)const;bool EnQueue(T x);bool DeQueue();void Clear() front = rear = 0; private:int front, rear;int maxSize;T*q;publi

4、c:MGraph(int mSize, const T& noedg);MGraph();ResultCode Insert(int u, int v, T&w);ResultCode Remove(int u, int v);bool Exist(int u, int v)const;void DFS();void BFS();protected:T*a;T noEdge;void DFS(int v, bool*visited);void BFS(int v, bool*visited);ENode类LGraph类public:ENode() nextArc = NULL;

5、 ENode(int vertex, T weight, ENode *next)adjVex = vertex;w = weight;nextArc = next;int adjVex;T w;ENode *nextArc;public:LGraph(int mSize);LGraph();ResultCode Insert(int u, int v, T&w);ResultCode Remove(int u, int v);bool Exist(int u, int v)const;protected:ENode<T>*a;四、程序代码#include "st

6、dafx.h"#include<iostream>using namespace std;const int INFTY = 2147483640;enum ResultCode Underflow, Duplicate, Failure, Success, NotPresent ;template<class T>class Graphpublic:virtual ResultCode Insert(int u, int v, T&w) = 0;virtual ResultCode Remove(int u, int v) = 0;virtual b

7、ool Exist(int u, int v)const = 0;protected:int n, e;template<class T>class SeqQueuepublic:SeqQueue(int mSize);SeqQueue() deleteq; bool IsEmpty() const return front = rear; bool IsFull() const return (rear + 1) % maxSize = front; bool Front(T &x)const;bool EnQueue(T x);bool DeQueue();void C

8、lear() front = rear = 0; private:int front, rear;int maxSize;T*q;template<class T>SeqQueue<T>:SeqQueue(int mSize)maxSize = mSize;q = new TmaxSize;front = rear = 0;template<class T>bool SeqQueue<T>:Front(T &x)constif (IsEmpty()return false;x = q(front + 1) % maxSize;return

9、 true;template<class T>bool SeqQueue<T>:EnQueue(T x)/在队尾插入xif (IsFull()cout << "Full" << endl;return false;qrear = (rear + 1) % maxSize = x;return true;template<class T>bool SeqQueue<T>:DeQueue()/删除队头元素if (IsEmpty()cout << "Underflow" <

10、;< endl;return false;front = (front + 1) % maxSize;return true;template<class T>class MGraph :public Graph<T>/邻接矩阵类public:MGraph(int mSize, const T& noedg);MGraph();ResultCode Insert(int u, int v, T&w);ResultCode Remove(int u, int v);bool Exist(int u, int v)const;void DFS();vo

11、id BFS();protected:T*a;T noEdge;void DFS(int v, bool*visited);void BFS(int v, bool*visited);template<class T>MGraph<T>: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;int j = 0;for (j;j<n;j+)aij = noEdge;aij = 0;

12、template<class T>MGraph<T>:MGraph()/析构函数for (int i = 0;i<n;i+)deleteai;deletea;template<class T>ResultCode MGraph<T>:Insert(int u, int v, T&w)/插入函数if (u<0 | v<0 | u>n - 1 | v>n - 1 | u = v)return Failure;if (auv != noEdge)return Duplicate;auv = w;e+;return

13、Success;template <class T>ResultCode MGraph<T>:Remove(int u, int v)/删除函数if (u<0 | v<0 | u>n - 1 | v>n - 1 | u = v)return Failure;if (auv = noEdge)return NotPresent;auv = noEdge;e-;return Success;template<class T>bool MGraph<T>:Exist(int u, int v)const/判断边是否存在if (u

14、<0 | v<0 | u>n - 1 | v>n - 1 | u = v | auv = noEdge)return false;return true;template<class T>void MGraph<T>:DFS()/深度遍历bool *visited = new booln;for (int i = 0;i<n;i+)visitedi = false;for (int i = 0;i<n;i+)if (!visitedi)DFS(i, visited);deletevisited;template<class T&

15、gt;void MGraph<T>:DFS(int v, bool *visited)visitedv = true;cout << " " << v;for (int i = 0;i<n;i+)if (avi != noEdge&&avi != 0 && !visitedi)DFS(i, visited);template<class T>void MGraph<T>:BFS() /广度遍历bool *visited = new booln;for (int i = 0;i&

16、lt;n;i+)visitedi = false;for (int i = 0;i<n;i+)if (!visitedi)BFS(i, visited);deletevisited;template<class T>void MGraph<T>:BFS(int v, bool *visited)SeqQueue<int> q(n);visitedv = true;cout << " " << v;q.EnQueue(v);while (!q.IsEmpty()q.Front(v);q.DeQueue();fo

17、r (int i = 0;i<n;i+)if (avi != noEdge&&avi != 0 && !visitedi)visitedi = true;cout << " " << i;q.EnQueue(i);template<class T> /结点类 class ENodepublic:ENode() nextArc = NULL; ENode(int vertex, T weight, ENode *next)adjVex = vertex;w = weight;nextArc = next

18、;int adjVex;T w;ENode *nextArc;template<class T>class LGraph :public Graph<T> /邻接表类public:LGraph(int mSize);LGraph();ResultCode Insert(int u, int v, T&w);ResultCode Remove(int u, int v);bool Exist(int u, int v)const;protected:ENode<T>*a;template <class T>LGraph<T>:L

19、Graph(int mSize)/构造函数n = mSize;e = 0;a = new ENode<T>*n;for (int i = 0;i<n;i+)ai = NULL;template <class T>LGraph<T>:LGraph()ENode<T> *p, *q;for (int i = 0;i<n;i+)p = ai;q = p;while (p)p = p->nextArc;delete q;q = p;deletea;template <class T>bool LGraph<T>:

20、Exist(int u, int v)const/判断边是否存在if (u<0 | v<0 | u>n - 1 | v>n - 1 | u = v)return false;ENode<T>*p = au;while (p&&p->adjVex != v)p = p->nextArc;if (!p)return false;else return true;template<class T>ResultCode LGraph<T>:Insert(int u, int v, T&w)/插入if (u&

21、lt;0 | v<0 | u>n - 1 | v>n - 1 | u = v)return Failure;if (Exist(u, v)return Duplicate;ENode<T>*p = new ENode<T>(v, w, au);au = p;e+;return Success;template<class T>ResultCode LGraph<T>:Remove(int u, int v) /删除if (u<0 | v<0 | u>n - 1 | v>n - 1 | u = v)retu

22、rn Failure;ENode<T>*p = au, *q;q = NULL;while (p&&p->adjVex != v)q = p;p = p->nextArc;if (!p)return NotPresent;if (q)q->nextArc = p->nextArc;elseau = p->nextArc;delete p;e-;return Success;int main() /主函数int n, g;cout << "请输入元素的个数："cin >> n;MGraph<

23、;int>A(n, INFTY);LGraph<int>B(n);cout << "请输入边的条数:"cin >> g;int*a = new intg;int*b = new intg;int*w = new intg;for (int i = 0;i<g;i+)cout << "请输入边及权值："cin >> ai >> bi >> wi;A.Insert(ai, bi, wi);B.Insert(ai, bi, wi);cout << &qu

24、ot;该图的深度优先遍历为:" << endl;A.DFS();cout << endl;cout << "该图的广度优先遍历为：" << endl;A.BFS();cout << endl;cout << "请输入要搜索的边："int c, d;cin >> c >> d;if (A.Exist(c, d)cout << "邻接矩阵中该边存在！" << endl;elsecout << &qu

25、ot;邻接矩阵中该边不存在！" << endl;if (B.Exist(c, d)cout << "邻接表中该边存在！" << endl;elsecout << "邻接表中该边不存在！" << endl;cout << "请输入要删除的边："int e, f;cin >> e >> f;if (A.Remove(e, f) = Success)cout << "邻接矩阵中删除该边成功！" <&

26、lt; endl;else if (A.Remove(e, f) = NotPresent)cout << "邻接矩阵中该边不存在！" << endl;elsecout << "输入错误！" << endl;if (B.Remove(e, f) = Success)cout << "邻接表中删除该边成功！" << endl;else if (B.Remove(e, f) = NotPresent)cout << "邻接表中该边不存在！&quo

27、t; << endl;elsecout << "邻接表中输入错误！" << endl;cout << "删除该边后该图的深度优先遍历为：" << endl;A.DFS();cout << endl;cout << "删除该边后该图的广度优先遍历为：" << endl;A.BFS();cout << endl;return 0;4、 测试和调试试验二 飞机最少换乘次数问题一 、问题描述(1) 设有n个城市，编号为0n-1，m条航线

28、的起点和终点由用户输入提供。寻找一条换乘次数最少的线路方案。(2) 提示：可以使用有向图表示城市间的航线；只要两城市间有航班，则图中这两点间存在一条权为1的边；可以使用Dijkstra算法实现。(3) 思考：如果是城市公交车的最少换乘问题，将如何解决？假如希望使用类似的算法，则图中的边如何设置？2、 概要设计首先创建抽象类Graph与邻接表类 MGraph，首先创建结点与边也就是城市与航向条数，之后调用邻接表类的迪杰斯特拉算法实现计算三、详细设计 1.类与类的层次结构：Graph类MGraph类public:virtual ResultCode Insert(int u, int v, T w

29、) = 0;virtual ResultCode Remove(int u, int v) = 0;virtual bool Exist(int u, int v)const = 0;protected:int n, e;public:MGraph(int mSize, const T noedg);MGraph();ResultCode Insert(int u, int v, T w);ResultCode Remove(int u, int v);bool Exist(int u, int v)const;int Choose(int* d, bool* s);void Dijkstra

30、(int v, T* d, int* path);protected:T*a;T noEdge;template<class T>四、程序代码#include "stdafx.h"#include<iostream>#include<string.h>using namespace std;const int INF = 2147483647;enum ResultCode Underflow, Duplicate, Failure, Success, NotPresent, OutOfBounds ;template<class

31、T>class Graph /抽象类public:virtual 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;protected:int n, e;template<class T>class MGraph :public Graph<T> /邻接矩阵类public:MGraph(int mSize, const T noedg);MGraph();Resu

32、ltCode Insert(int u, int v, T w);ResultCode Remove(int u, int v);bool Exist(int u, int v)const;int Choose(int* d, bool* s);void Dijkstra(int v, T* d, int* path);protected:T*a;T noEdge;template<class T>MGraph<T>:MGraph(int mSize, const T noedg)n = mSize;e = 0;noEdge = noedg;a = new T*n;fo

33、r (int i = 0;i<n;i+)ai = new Tn;for (int j = 0;j<n;j+)aij = noEdge;aii = 0;template<class T>MGraph<T>:MGraph()for (int i = 0;i<n;i+)deleteai;deletea;template<class T>ResultCode MGraph<T>:Insert(int u, int v, T w)if (u<0 | v<0 | u>n - 1 | v>n - 1 | u = v)r

34、eturn Failure;if (auv != noEdge)return Duplicate;auv = w;e+;return Success;template<class T>ResultCode MGraph<T>:Remove(int u, int v)if (u<0 | v<0 | u>n - 1 | v>n - 1 | u = v)return Failure;if (auv = noEdge)return NotPresent;auv = noEdge;e-;return Success;template<class T&

35、gt;bool MGraph<T>:Exist(int u, int v)constif (u<0 | v<0 | u>n - 1 | v>n - 1 | u = v | auv = noEdge)return false;return true;template<class T>int MGraph<T>:Choose(int* d, bool* s) /求最小diint i, minpos;T min;min = INF;minpos = -1;for (i = 0;i<n;i+)if (di <= min&&

36、amp;!si)min = di;minpos = i;return minpos;template<class T>void MGraph<T>:Dijkstra(int v, T* d, int* path)/迪杰斯特拉算法int i, k, w;if (v<0 | v>n - 1)throw OutOfBounds;bool* s = new booln;for (i = 0;i<n;i+)si = false;di = avi;if (i != v&&di<INF)pathi = v;elsepathi = -1;sv =

37、 true;dv = 0;for (i = 1;i<n;i+)k = Choose(d, s);sk = true;for (w = 0;w<n;w+)if (!sw && (dk + akw)<dw)dw = dk + akw;pathw = k;int main()int n, m;cout << "请输入城市个数："cin >> n;cout << "请输入航线条数："cin >> m;MGraph<int>A(n, INF);int c, f;cout << "请输入每条航线的起点和终点：" << endl;i