南郵數(shù)據(jù)結(jié)構(gòu)實驗三圖的基本運算及飛機換乘次數(shù)最少問題

1、 實 驗 報 告（ 2015 / 2016 學年 第 2學期） 課程名稱數(shù)據(jù)結(jié)構(gòu)A實驗名稱圖的基本運算及飛行換乘次數(shù)最少問題實驗時間年月日指導單位計算機科學與技術(shù)系指導教師 學生姓名班級學號學院(系)專 業(yè)試驗一 圖的基本運算1、 問題描述（1） 驗證教材中關(guān)于在鄰接矩陣和鄰接表兩種不同存儲結(jié)構(gòu)上實現(xiàn)圖的基本運算的算法（見程序9.1程序9.8）； （2） 在鄰接矩陣存儲結(jié)構(gòu)上實現(xiàn)圖的深度和廣度優(yōu)先遍歷算法；（3）設(shè)計主函數(shù)，測試上述運算；（4）提示：擴充MGraph類，在擴充類上增加DFS和BFS函數(shù)；2、 概要設(shè)計 圖如下所示，顯示了名為operation_of_map的（默認文件名）工程，

2、實現(xiàn)了Graph,SeqQueue,結(jié)點類ENode,鄰接矩陣類MGraph,鄰接表LGraph類，包括幾種為不同傳入類型準備的構(gòu)造函數(shù)。聲明所要求的函數(shù)，并在后續(xù)過程中實現(xiàn)函數(shù)功能，最后通過一個main函數(shù)求解。3、 詳細設(shè)計1. 類與類的層次結(jié)構(gòu)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)/構(gòu)造函數(shù)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()/析構(gòu)函數(shù)f

11、or (int i = 0;in;i+)deleteai;deletea;templateResultCode MGraph:Insert(int u, int v, T&w)/插入函數(shù)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)/刪除函數(shù)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 /結(jié)

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)/構(gòu)造函數(shù)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() /主函數(shù)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 該圖的深度優(yōu)先遍歷為: endl;A.DFS();cout endl;cout 該圖的廣度優(yōu)先遍歷為： 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 刪除該邊后該圖的深度優(yōu)先遍歷為： endl;A.DFS();cout endl;cout 刪除該邊后該圖的廣度優(yōu)先遍歷為： endl;A.BFS();cout endl;return 0;4、 測試和調(diào)試試驗二 飛機最少換乘次數(shù)問題一 、問題描述(1) 設(shè)有n個城市，編號為0n-1，m條航線的起點和終點由用戶輸入提供。尋找一條換乘次數(shù)最少的線路方案。(2) 提示：可以使用有向圖表示城市間的航線；只要兩城市間有航班，則圖中這兩點間存在一條權(quán)為1的邊；可以使用Dijkstra

22、算法實現(xiàn)。(3) 思考：如果是城市公交車的最少換乘問題，將如何解決？假如希望使用類似的算法，則圖中的邊如何設(shè)置？2、 概要設(shè)計首先創(chuàng)建抽象類Graph與鄰接表類 MGraph，首先創(chuàng)建結(jié)點與邊也就是城市與航向條數(shù)，之后調(diào)用鄰接表類的迪杰斯特拉算法實現(xiàn)計算三、詳細設(shè)計 1.類與類的層次結(jié)構(gòu)：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,