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

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, e;SeqQueue

3、类 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;public:MGraph(int m

4、Size, 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; ENode(int vertex, T w

5、eight, 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*a;四、程序代码#include stdafx.h#includeusing namespace std;const i

6、nt INFTY = 2147483640;enum ResultCode Underflow, Duplicate, Failure, Success, NotPresent ;templateclass Graphpublic: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;templateclass SeqQueuepublic:S

7、eqQueue(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;templateSeqQueue:SeqQueue(int mSize)

8、maxSize = mSize;q = new TmaxSize;front = rear = 0;templatebool SeqQueue:Front(T &x)constif (IsEmpty()return false;x = q(front + 1) % maxSize;return true;templatebool SeqQueue:EnQueue(T x)/在队尾插入xif (IsFull()cout Full endl;return false;qrear = (rear + 1) % maxSize = x;return true;templatebool SeqQueue

9、:DeQueue()/删除队头元素if (IsEmpty()cout Underflow endl;return false;front = (front + 1) % maxSize;return true;templateclass MGraph :public Graph/邻接矩阵类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 D

10、FS();void BFS();protected:T*a;T noEdge;void DFS(int v, bool*visited);void BFS(int v, bool*visited);templateMGraph:MGraph(int mSize, const T&noedg)/构造函数n = mSize;e = 0;noEdge = noedg;a = new T*n;for (int i = 0;in;i+)ai = new Tn;int j = 0;for (j;jn;j+)aij = noEdge;aij = 0;templateMGraph:MGraph()/析构函数f

11、or (int i = 0;in;i+)deleteai;deletea;templateResultCode MGraph:Insert(int u, int v, T&w)/插入函数if (u0 | vn - 1 | vn - 1 | u = v)return Failure;if (auv != noEdge)return Duplicate;auv = w;e+;return Success;template ResultCode MGraph:Remove(int u, int v)/删除函数if (u0 | vn - 1 | vn - 1 | u = v)return Failur

12、e;if (auv = noEdge)return NotPresent;auv = noEdge;e-;return Success;templatebool MGraph:Exist(int u, int v)const/判断边是否存在if (u0 | vn - 1 | vn - 1 | u = v | auv = noEdge)return false;return true;templatevoid MGraph:DFS()/深度遍历bool *visited = new booln;for (int i = 0;in;i+)visitedi = false;for (int i =

13、0;in;i+)if (!visitedi)DFS(i, visited);deletevisited;templatevoid MGraph:DFS(int v, bool *visited)visitedv = true;cout v;for (int i = 0;in;i+)if (avi != noEdge&avi != 0 & !visitedi)DFS(i, visited);templatevoid MGraph:BFS() /广度遍历bool *visited = new booln;for (int i = 0;in;i+)visitedi = false;for (int

14、i = 0;in;i+)if (!visitedi)BFS(i, visited);deletevisited;templatevoid MGraph:BFS(int v, bool *visited)SeqQueue q(n);visitedv = true;cout v;q.EnQueue(v);while (!q.IsEmpty()q.Front(v);q.DeQueue();for (int i = 0;in;i+)if (avi != noEdge&avi != 0 & !visitedi)visitedi = true;cout i;q.EnQueue(i);template /结

15、点类 class ENodepublic:ENode() nextArc = NULL; ENode(int vertex, T weight, ENode *next)adjVex = vertex;w = weight;nextArc = next;int adjVex;T w;ENode *nextArc;templateclass LGraph :public Graph /邻接表类public:LGraph(int mSize);LGraph();ResultCode Insert(int u, int v, T&w);ResultCode Remove(int u, int v);

16、bool Exist(int u, int v)const;protected:ENode*a;template LGraph:LGraph(int mSize)/构造函数n = mSize;e = 0;a = new ENode*n;for (int i = 0;in;i+)ai = NULL;template LGraph:LGraph()ENode *p, *q;for (int i = 0;inextArc;delete q;q = p;deletea;template bool LGraph:Exist(int u, int v)const/判断边是否存在if (u0 | vn -

17、1 | vn - 1 | u = v)return false;ENode*p = au;while (p&p-adjVex != v)p = p-nextArc;if (!p)return false;else return true;templateResultCode LGraph:Insert(int u, int v, T&w)/插入if (u0 | vn - 1 | vn - 1 | u = v)return Failure;if (Exist(u, v)return Duplicate;ENode*p = new ENode(v, w, au);au = p;e+;return

18、Success;templateResultCode LGraph:Remove(int u, int v) /删除if (u0 | vn - 1 | vn - 1 | u = v)return Failure;ENode*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;co

19、ut n;MGraphA(n, INFTY);LGraphB(n);cout g;int*a = new intg;int*b = new intg;int*w = new intg;for (int i = 0;ig;i+)cout ai bi wi;A.Insert(ai, bi, wi);B.Insert(ai, bi, wi);cout 该图的深度优先遍历为: endl;A.DFS();cout endl;cout 该图的广度优先遍历为： endl;A.BFS();cout endl;cout c d;if (A.Exist(c, d)cout 邻接矩阵中该边存在！ endl;else

20、cout 邻接矩阵中该边不存在！ endl;if (B.Exist(c, d)cout 邻接表中该边存在！ endl;elsecout 邻接表中该边不存在！ endl;cout e f;if (A.Remove(e, f) = Success)cout 邻接矩阵中删除该边成功！ 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) =

21、 NotPresent)cout 邻接表中该边不存在！ endl;elsecout 邻接表中输入错误！ endl;cout 删除该边后该图的深度优先遍历为： endl;A.DFS();cout endl;cout 删除该边后该图的广度优先遍历为： endl;A.BFS();cout endl;return 0;4、 测试和调试试验二 飞机最少换乘次数问题一 、问题描述(1) 设有n个城市，编号为0n-1，m条航线的起点和终点由用户输入提供。寻找一条换乘次数最少的线路方案。(2) 提示：可以使用有向图表示城市间的航线；只要两城市间有航班，则图中这两点间存在一条权为1的边；可以使用Dijkstra

22、算法实现。(3) 思考：如果是城市公交车的最少换乘问题，将如何解决？假如希望使用类似的算法，则图中的边如何设置？2、 概要设计首先创建抽象类Graph与邻接表类 MGraph，首先创建结点与边也就是城市与航向条数，之后调用邻接表类的迪杰斯特拉算法实现计算三、详细设计 1.类与类的层次结构：Graph类MGraph类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;

23、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(int v, T* d, int* path);protected:T*a;T noEdge;template四、程序代码#include stdafx.h#include#incl

24、udeusing namespace std;const int INF = 2147483647;enum ResultCode Underflow, Duplicate, Failure, Success, NotPresent, OutOfBounds ;templateclass 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;pro

25、tected:int n, e;templateclass MGraph :public Graph /邻接矩阵类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(int v, T* d, int* path);protected:T*a;T noEdge;templa

26、teMGraph:MGraph(int mSize, const T noedg)n = mSize;e = 0;noEdge = noedg;a = new T*n;for (int i = 0;in;i+)ai = new Tn;for (int j = 0;jn;j+)aij = noEdge;aii = 0;templateMGraph:MGraph()for (int i = 0;in;i+)deleteai;deletea;templateResultCode MGraph:Insert(int u, int v, T w)if (u0 | vn - 1 | vn - 1 | u

27、= v)return Failure;if (auv != noEdge)return Duplicate;auv = w;e+;return Success;templateResultCode MGraph:Remove(int u, int v)if (u0 | vn - 1 | vn - 1 | u = v)return Failure;if (auv = noEdge)return NotPresent;auv = noEdge;e-;return Success;templatebool MGraph:Exist(int u, int v)constif (u0 | vn - 1 | vn - 1 | u = v | auv = noEdge)return false;return true;templateint MGraph:Choose(int* d, bool* s) /求最小diint i, minpos;T min;min = INF;minpos = -1;for (i = 0;in;i+)if (di = min&!si)min = di;minpos = i;return minpos;templatevoid MGraph:Dijkstra(int v, T* d, int* path)/迪杰斯特拉算法int i, k,