南郵數據結構實驗三圖的基本運算及飛機換乘次數最少問題

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

2、實現了Graph,SeqQueue,結點類ENode,鄰接矩陣類MGraph,鄰接表LGraph類，包括幾種為不同傳入類型準備的構造函數。聲明所要求的函數，并在后續(xù)過程中實現函數功能，最后通過一個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 該圖的深度優(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、 測試和調試試驗二 飛機最少換乘次數問題一 、問題描述(1) 設有n個城市，編號為0n-1，m條航線的起點和終點由用戶輸入提供。尋找一條換乘次數最少的線路方案。(2) 提示：可以使用有向圖表示城市間的航線；只要兩城市間有航班，則圖中這兩點間存在一條權為1的邊；可以使用Dijkstra

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