數(shù)據(jù)結(jié)構(gòu)小學(xué)期-算法演示程序?qū)嶒?yàn)報(bào)告(共23頁)

1、實(shí)習(xí)報(bào)告實(shí)驗(yàn)名稱：數(shù)據(jù)結(jié)構(gòu)基本算法演示程序 日期：2017年7月1 日姓名：于博 學(xué)號：20153236 班級：信1501-2 指導(dǎo)教師：陳娜 1實(shí)驗(yàn)題目 1) Prim 算法 輸入：無向圖（頂點(diǎn)序列，邊序列）功能要求：輸出最小生成樹的各組成邊及最小生成樹的權(quán)值2) Kruskal 算法 輸入：無向圖（頂點(diǎn)序列，邊序列）功能要求：輸出最小生成樹的各組成邊及最小生成樹的權(quán)值3) Floyd 算法 輸入：有向圖（頂點(diǎn)序列，有向邊序列） 功能要求：輸出各頂點(diǎn)對間最短路徑和路徑長度 4) Dijkstra 算法輸入：有向圖（頂點(diǎn)序列，有向邊序列），起始頂點(diǎn) 功能要求：輸出起始頂點(diǎn)到其它各頂點(diǎn)的最短路徑

2、和路徑長度2需求分析 本演示程序用C+編寫，完成四個算法的實(shí)現(xiàn), Prim 算法，Kruskal 算法，F(xiàn)loyd 算法，Dijkstra 算法 輸入的形式和輸入值的范圍： 整數(shù)，菜單項(xiàng)是1至5，其他輸入根據(jù)圖的實(shí)際情況。 輸出的形式：輸出最小生成樹，樹的各組成邊，所有路徑及源點(diǎn)到其他點(diǎn)的所有最短路徑。 程序所能達(dá)到的功能：四個算法Prim 算法，Kruskal 算法，F(xiàn)loyd 算法，Dijkstra 算法的實(shí)現(xiàn)。 測試數(shù)據(jù)：A 輸入3個點(diǎn)，3條邊。B 輸入1 3 50 1 2 20 2 3 10三組點(diǎn)及權(quán)值。 3概要設(shè)計(jì) 1)為了實(shí)現(xiàn)上述程序功能，需要定義樹、線性表的抽象數(shù)據(jù)類型： ADT

3、 Tree數(shù)據(jù)對象：D=ai|aiIntegerSet,i=0,1,2,n,n0數(shù)據(jù)關(guān)系：R=<ai,ai+1>|ai,ai+1 D ADT LinkList數(shù)據(jù)對象：D=ai|aiIntegerSet,i=0,1,2,n,n0數(shù)據(jù)關(guān)系：R=<ai,ai+1>|ai,ai+1 D 基本操作：a) Prim算法ok(Tree &t,int k)初始條件：樹結(jié)構(gòu)已存在操作結(jié)果：作為判斷函數(shù)的條件judge(Tree &t)初始條件：樹結(jié)構(gòu)已存在操作結(jié)果：判斷樹是否包含所有圖的結(jié)點(diǎn)show_prim()初始條件：樹結(jié)構(gòu)已存在，prim算法運(yùn)行成功操作結(jié)果：展示

4、prim算法,輸出最小生成樹b) Kruskal 算法Find(int x)初始條件：圖已存在操作結(jié)果：查尋父節(jié)點(diǎn)Union(int x,int y)初始條件：圖已存在操作結(jié)果：合并結(jié)點(diǎn)bool Com(Node x,Node y)初始條件：圖已存在操作結(jié)果：判斷結(jié)點(diǎn)權(quán)值show_kruskal()初始條件：圖已存在，kruskal算法運(yùn)行成功操作結(jié)果：展示kruskal算法，輸出各組成邊c) Floyd 算法F_Creategraph(F_MGraph *F_MGraph)操作結(jié)果：創(chuàng)建圖Floyd(F_MGraph *F_MGraph, int *iArrPath)初始條件：圖已存在操作結(jié)

5、果：運(yùn)行弗洛伊德算法PrintResult(F_MGraph *F_MGraph, int *iArrPath)初始條件：圖已存在操作結(jié)果：打印圖的信息show_floyd()初始條件：圖已存在，弗洛伊德算法運(yùn)行成功操作結(jié)果：展示弗洛伊德算法d) Dijkstra 算法createGraph(HeadNode *G, int nodeNum, int arcNum)操作結(jié)果：創(chuàng)建圖printGraph(HeadNode *G, int nodeNum)初始條件：圖已存在操作結(jié)果：打印圖getWeight(HeadNode *G, int begin, int end)初始條件：圖已存在操作結(jié)果

6、：得到出發(fā)點(diǎn)到終點(diǎn)權(quán)重Dijkstra(HeadNode *G, int nodeNum, int begin)初始條件：圖已存在，出發(fā)點(diǎn)已知操作結(jié)果：運(yùn)行迪杰斯特拉算法printPath(HeadNode *G, int end) 初始條件：圖已存，迪杰斯特拉算法運(yùn)行成功操作結(jié)果：打印路徑show_Dijkstra()初始條件：圖已存，迪杰斯特拉算法運(yùn)行成功操作結(jié)果：展示迪杰斯特拉算法menu()操作結(jié)果：在屏幕上顯示操作菜單2)本程序包含 17個函數(shù)：主函數(shù) main()菜單函數(shù)menu()Prim算法判斷函數(shù)ok()判斷樹是否包含所有圖的結(jié)點(diǎn)judge()展示prim算法函數(shù)show_p

7、rim()Kruskal算法查尋父節(jié)點(diǎn)函數(shù)Find()合并結(jié)點(diǎn)函數(shù)Union()判斷節(jié)點(diǎn)權(quán)值函數(shù)bool Com()展示kruskal算法函數(shù)show_kruskal()Floyd算法弗洛伊德創(chuàng)建圖F_Creategraph()弗洛伊德算法函數(shù)Floyd()打印圖信息函數(shù)PrintResult()展示弗洛伊德函數(shù)show_floyd()Dijistra算法創(chuàng)建圖createGraph()迪杰斯特拉算法函數(shù)Dijkstra ()打印路徑函數(shù)printPath()展示迪杰斯特拉函數(shù)show_Dijkstra()各函數(shù)間關(guān)系如下：4詳細(xì)設(shè)計(jì) /-Prim算法-/判斷函數(shù)-是否樹包含圖的所有結(jié)點(diǎn)voi

8、d judge(Tree &t) for(int i=1;i<t.v1;i+) for(int j=0;j<i;j+) int m; m=t.vj; for(int k=1;k<=t.v1;k+) if(t.amk<biaoji1) if(ok(t,k) biaoji1=t.amk; biaoji2=m; biaoji3=k; t.vi=biaoji3; t.e2*i-1=biaoji2; t.e2*i=biaoji3; /調(diào)用prim算法相關(guān)所有代碼void show_prim() cout<<"請輸入圖的點(diǎn)數(shù)和邊數(shù)"<&

9、lt;endl;/輸入提示 cin>>n>>m; t.v1=n; /給樹的結(jié)點(diǎn)總數(shù)和邊的結(jié)點(diǎn)總數(shù)賦值 t.e1=m; t.v=new intn; /結(jié)點(diǎn)數(shù)組 for(int i=0;i<n;i+) /循環(huán) 初始化 t.vi=0; t.e=new int2*n-1; /邊與結(jié)點(diǎn)數(shù)的關(guān)系 for(int i=0;i<2*n-1;i+) /循環(huán) 初始化 t.ei=0; t.a=new int *n+1; for(int i=0;i<=n;i+) t.ai=new intn+1; cout<<"請依次輸入各邊的兩端點(diǎn)及權(quán)值"&l

10、t;<endl; for(int i=1;i<=n;i+) for(int j=1;j<=n;j+) t.aij=10000; /初始化為無窮大 for(int i=1;i<=m;i+) /for循環(huán)輸入 cin>>m1>>m2>>count; t.am1m2=count; /無向網(wǎng)賦值 t.am2m1=count; judge(t); /判斷是否有全部葉子節(jié)點(diǎn) cout<<"最小生成樹為："<<endl; for(int i=1;i<n;i+) x=t.e2*i-1; y=t.e2*

11、i; cout<<x<<"->"<<y<<" "<<t.axy<<endl; sum+=t.axy; cout<<"最小生成樹的權(quán)值之和為："<<sum<<endl;/-kruskal算法-/int Find(int x) /查 if(x=Fatherx) return x; else return Find(Fatherx); void Union(int x,int y) /并 Fatherx=y ; int Top,

12、Edge; bool Com(Node x,Node y) return x.Weight<y.Weight; deque<Node>Map; /調(diào)用克魯斯卡爾的相關(guān)代碼void show_kruskal() cout<<"請輸入結(jié)點(diǎn)個數(shù)及邊數(shù)："<<endl; cin>>Top>>Edge; cout<<"請依次輸入兩點(diǎn)及權(quán)值："<<endl; for(i=1;i<=Top;i+) for(j=1;j<=Top;j+) cin>>x; if

13、(j>i && x!=100) y.Next=j; y.Priority=i; y.Weight=x; Map.push_back(y); sort(Map.begin(),Map.end(),Com); for(i=1;i<=Top;i+) Fatheri=i; cout<<"樹的各組成邊有："<<endl; for(i=0;i<Map.size();i+) if(count=Top-1) break; if(Find(Mapi.Priority)!=Find(Mapi.Next) Union(Mapi.Prior

14、ity,Mapi.Next); count+; if(Mapi.Priority>Mapi.Next) cout<<Mapi.Next<<"->"<<Mapi.Priority<<"->"<<endl; else cout<<Mapi.Priority<<"->"<<Mapi.Next<<endl; /-floyd算法-/圖的創(chuàng)建void F_Creategraph(F_MGraph *F_MGraph)

15、 cout << "請輸入頂點(diǎn)數(shù)和邊數(shù)" << endl; cin >> F_MGraph->Vcount >> F_MGraph->Ecount; for (int row = 1; row <= F_MGraph->Vcount; row+) /初始化為無窮,即不連通 for (int col = 1; col <= F_MGraph->Vcount; col+) F_MGraph->edgesrowcol = MAX_VALUE; cout << "請輸入起

16、始結(jié)點(diǎn) 最終結(jié)點(diǎn) 權(quán)重" << endl; for (int i = 1; i <= F_MGraph->Ecount; i+) /賦值 cin >> row >> col >> weight; F_MGraph->edgesrowcol = weight; /佛洛依德算法 void Floyd(F_MGraph *F_MGraph, int *iArrPath) for (int i = 1; i <= F_MGraph->Vcount; i+) for (int j = 1; j <= F_MGr

17、aph->Vcount; j+) iArrPathij = i; /初始化路徑表 for (int k = 1; k <= F_MGraph->Vcount; k+) for (int i = 1; i <= F_MGraph->Vcount; i+) for (int j = 1; j <= F_MGraph->Vcount; j+) if (F_MGraph->edgesik + F_MGraph->edgeskj < F_MGraph->edgesij) F_MGraph->edgesij = F_MGraph-&g

18、t;edgesik + F_MGraph->edgeskj; iArrPathij = iArrPathkj; /打印佛洛依德算法最短路徑void PrintResult(F_MGraph *F_MGraph, int *iArrPath) cout << "起點(diǎn) ->終點(diǎn)t距離tt最短路徑" << endl; for (int i = 1; i <= F_MGraph->Vcount; i+) for (int j = 1; j <= F_MGraph->Vcount; j+) if (i != j) cout

19、<< i << "->" << j << "tt" if (F_MGraph->edgesij = MAX_VALUE) cout << "無連通路徑" << "tt" << endl; else cout << F_MGraph->edgesij << "tt" std:stack<int> stackVertices; do k = iArrPathik;

20、 stackVertices.push(k); while (k != i); cout << stackVertices.top(); stackVertices.pop(); unsigned int nLength = stackVertices.size(); for (unsigned int nIndex = 0; nIndex < nLength; nIndex+) cout << " -> " << stackVertices.top(); stackVertices.pop(); cout <<

21、" -> " << j << endl; /調(diào)用弗洛伊德相關(guān)代碼void show_floyd() for (int i = 0; i < MAX_VALUE; i+) iArrPathi = new intMAX_VALUE; F_MGraph F_MGraph; for (int i = 0; i < MAX_VALUE; i+) F_MGraph.edgesi = new intMAX_VALUE; F_Creategraph(&F_MGraph); Floyd(&F_MGraph, iArrPath); Pr

22、intResult(&F_MGraph, iArrPath); /-Dijkstra算法-/創(chuàng)建圖函數(shù)void createGraph(HeadNode *G, int nodeNum, int arcNum) /G表示指向頭結(jié)點(diǎn)數(shù)組的第一個結(jié)點(diǎn)的指針 nodeNum表示結(jié)點(diǎn)個數(shù) arcNum表示邊的個數(shù) cout << "開始創(chuàng)建圖(" << nodeNum << ", " << arcNum << ")" << endl; /初始化頭結(jié)點(diǎn) for (i

23、nt i = 0; i < nodeNum; i+) Gi.nodeName = i+1; /位置0上面存儲的是結(jié)點(diǎn)v1,依次類推 Gi.inDegree = 0; /入度為0 Gi.link = NULL; /指針置空 /給邊賦權(quán)值 for (int j = 0; j < arcNum; j+) int begin, end, weight; /起點(diǎn) 終點(diǎn) 權(quán)值 cout << "請輸入 起始頂點(diǎn) 結(jié)束頂點(diǎn) 權(quán)值: " cin >> begin >> end >> weight; /輸入起點(diǎn) 終點(diǎn) 權(quán)值 D_No

24、de *node = new D_Node; /創(chuàng)建邊表插入鏈接表 node->adjvex = end - 1; /記錄終點(diǎn)信息 node->weight = weight; /賦權(quán)值 +Gend-1.inDegree; /邊的終點(diǎn)入度加1 node->next = Gbegin-1.link; /前插法 即后輸入的先打印（打印圖的時候是倒著的） Gbegin-1.link = node; /插入鏈接表的第一個位置 /打印圖函數(shù)void printGraph(HeadNode *G, int nodeNum) /輸出結(jié)點(diǎn)入度及以其為起點(diǎn)的邊 for (int i = 0;

25、i < nodeNum; i+) cout << "結(jié)點(diǎn)v" << Gi.nodeName << "的入度為"<< Gi.inDegree << ", 以它為起始頂點(diǎn)的邊為(起點(diǎn)-權(quán)重-終點(diǎn)): "<<endl; D_Node *node = Gi.link; while (node != NULL) /依附于該頂點(diǎn)的指針不為空，即還存在以該結(jié)點(diǎn)為起點(diǎn)的邊 cout << "v" << Gi.nodeName<

26、;<"-"<<node->weight<<"-"<<"v" << Gnode->adjvex.nodeName<<endl; node = node->next; /依次向后遍歷 cout << endl; /得到begin->end權(quán)重 int getWeight(HeadNode *G, int begin, int end) D_Node *node = Gbegin-1.link; while (node) if (node-

27、>adjvex = end - 1) return node->weight; node = node->next; /從begin開始，計(jì)算其到每一個頂點(diǎn)的最短路徑void Dijkstra(HeadNode *G, int nodeNum, int begin) /初始化所有結(jié)點(diǎn)的 for (int i = 0; i < nodeNum; i+) Gi.d = INT_MAX; /到每一個頂點(diǎn)的距離初始化為無窮大，頭文件包含limits，增強(qiáng)可移植性 Gi.isKnown = false; /到每一個頂點(diǎn)的最短距離為未知數(shù) Gbegin-1.d = 0; /到其本身

28、的距離為0 Gbegin-1.parent = -1; /表示該結(jié)點(diǎn)是起始結(jié)點(diǎn) while(true) /如果所有的結(jié)點(diǎn)的最短距離都已知, 那么就跳出循環(huán) bool ok = true; /表示是否全部ok for (int k = 0; k < nodeNum; k+) if (!Gk.isKnown) /只要有一個頂點(diǎn)的最短路徑未知,ok就設(shè)置為false ok = false; break; if (ok) return; /搜索未知結(jié)點(diǎn)中d最小的,將其變?yōu)閗nown int minIndex = -1; for (int i = 0; i < nodeNum; i+) if

29、 (!Gi.isKnown) if (minIndex = -1) minIndex = i; else if (GminIndex.d > Gi.d) minIndex = i; cout << "已知最短路徑的結(jié)點(diǎn)為: v" << (minIndex+1) << endl; GminIndex.isKnown = true; /將其加入最短路徑已知的頂點(diǎn)集 D_Node *node = GminIndex.link; / 將以minIndex為起始頂點(diǎn)的所有的d更新 while (node != NULL) int begin

30、= minIndex + 1; int end = node->adjvex + 1; int weight = getWeight(G, begin, end); if (GminIndex.d + weight < Gend-1.d) Gend-1.d = GminIndex.d + weight; Gend-1.parent = minIndex; /記錄最短路徑的上一個結(jié)點(diǎn) node = node->next; /打印到end-1的最短路徑void printPath(HeadNode *G, int end) if (Gend-1.parent = -1) cout

31、 << "v" << end; else if (end != 0) printPath(G, Gend-1.parent + 1); / 因?yàn)檫@里的parent表示的是下標(biāo)，從0開始，所以要加1 cout << " -> v" << end; /調(diào)用迪杰斯特拉的相關(guān)代碼void show_Dijkstra() HeadNode *G; /頭結(jié)點(diǎn) int nodeNum, arcNum; /頂點(diǎn)個數(shù)，邊的個數(shù) cout << "請輸入頂點(diǎn)個數(shù)，邊的個數(shù): " cin &

32、gt;> nodeNum >> arcNum; G = new HeadNodenodeNum; createGraph(G, nodeNum, arcNum); /創(chuàng)建圖 cout << "=" << endl; cout << "下面開始打印圖信息." << endl; printGraph(G, nodeNum); /打印圖 cout << "=" << endl; cout << "下面開始運(yùn)行dijkstra算法.

33、" << endl; Dijkstra(G, nodeNum, 1); /運(yùn)行Dijkstra算法 cout << "=" << endl; cout << "打印從v1開始所有的最短路徑" << endl; for (int k = 2; k <= nodeNum; k+) cout << "v1到v" << k << "的最短路徑為" << Gk-1.d << ":

34、" printPath(G, k); /打印最短路徑 cout << endl; 5調(diào)試分析1. 書本上的偽代碼大多都沒有初始化,注意初始化即可。2. 調(diào)試時要多增加幾個斷點(diǎn)和監(jiān)視對象。6使用說明程序名為 algorithms.exe，運(yùn)行環(huán)境為 DOS。程序執(zhí)行后顯示*歡迎來到算法演示程序* 1.Prim 算法 2.Kruskal算法 3.Floyd算法 4.Dijkstra算法 5.退出請選擇您的操作：在” 請選擇您的操作：”后輸入數(shù)字選擇執(zhí)行不同的功能。選擇 1：執(zhí)行Prim算法,輸入結(jié)點(diǎn)及邊的總數(shù)，起點(diǎn)終點(diǎn)和權(quán)值選擇 2：執(zhí)行Kruskal算法，輸入結(jié)點(diǎn)及邊的總數(shù)

35、，起點(diǎn)終點(diǎn)和權(quán)值選擇 3：執(zhí)行Floyd算法 輸入結(jié)點(diǎn)及邊的總數(shù)，起點(diǎn)終點(diǎn)和權(quán)值選擇4：執(zhí)行Dijkstra算法輸入結(jié)點(diǎn)及邊的總數(shù)，起點(diǎn)終點(diǎn)和權(quán)值選擇5：退出程序7測試結(jié)果圖 1圖 2圖 38.附錄/*4、 Prim 算法 輸入：無向圖（頂點(diǎn)序列，邊序列）功能要求：輸出最小生成樹的各組成邊及最小生成樹的權(quán)值5、 Kruskal 算法 輸入：無向圖（頂點(diǎn)序列，邊序列）功能要求：輸出最小生成樹的各組成邊及最小生成樹的權(quán)值6、 Floyd 算法 輸入：有向圖（頂點(diǎn)序列，有向邊序列） 功能要求：輸出各頂點(diǎn)對間最短路徑和路徑長度 7、 Dijkstra 算法輸入：有向圖（頂點(diǎn)序列，有向邊序列），起始頂點(diǎn)

36、 功能要求：輸出起始頂點(diǎn)到其它各頂點(diǎn)的最短路徑和路徑長度*/于博 20153236 2017/6/30#include<iostream>#include <stack> #include<limits> /增強(qiáng)程序可移植性，包含最值宏定義using namespace std;#include "deque" #include "algorithm" #define Max 100 #define MAX_VALUE 1000 /宏定義#define MAX_VERTEX_COUNT 20 /-Prim算法-/樹結(jié)構(gòu)

37、體struct Tree int *a; int *v; int *e; int v1; /葉子結(jié)點(diǎn)總數(shù) int e1; /邊的總數(shù);int ok(Tree &t,int k) int l=0; while(l<t.v1&&t.vl!=0) if(t.vl=k) return 0; l+; return 1; /判斷函數(shù)-是否樹包含圖的所有結(jié)點(diǎn)void judge(Tree &t) t.v0=1; for(int i=1;i<t.v1;i+) int biaoji1=10000; /標(biāo)記無窮大 int biaoji2=0; int biaoji3=0

38、; for(int j=0;j<i;j+) int m; m=t.vj; for(int k=1;k<=t.v1;k+) if(t.amk<biaoji1) if(ok(t,k) biaoji1=t.amk; biaoji2=m; biaoji3=k; t.vi=biaoji3; t.e2*i-1=biaoji2; t.e2*i=biaoji3; /調(diào)用prim算法相關(guān)所有代碼void show_prim() int x,y; /起點(diǎn)、終點(diǎn) Tree t; /樹 int n,m; int m1,m2; /起點(diǎn)、終點(diǎn) int count; /權(quán)值計(jì)數(shù) int sum=0; /權(quán)

39、值之和 cout<<"請輸入圖的點(diǎn)數(shù)和邊數(shù)"<<endl;/輸入提示 cin>>n>>m; t.v1=n; /給樹的結(jié)點(diǎn)總數(shù)和邊的結(jié)點(diǎn)總數(shù)賦值 t.e1=m; t.v=new intn; /結(jié)點(diǎn)數(shù)組 for(int i=0;i<n;i+) /循環(huán) 初始化 t.vi=0; t.e=new int2*n-1; /邊與結(jié)點(diǎn)數(shù)的關(guān)系 for(int i=0;i<2*n-1;i+) /循環(huán) 初始化 t.ei=0; t.a=new int *n+1; for(int i=0;i<=n;i+) t.ai=new intn+

40、1; cout<<"請依次輸入各邊的兩端點(diǎn)及權(quán)值"<<endl; for(int i=1;i<=n;i+) for(int j=1;j<=n;j+) t.aij=10000; /初始化為無窮大 for(int i=1;i<=m;i+) /for循環(huán)輸入 cin>>m1>>m2>>count; t.am1m2=count; /無向網(wǎng)賦值 t.am2m1=count; judge(t); /判斷是否有全部葉子節(jié)點(diǎn) cout<<"最小生成樹為："<<endl;

41、 for(int i=1;i<n;i+) x=t.e2*i-1; y=t.e2*i; cout<<x<<"->"<<y<<" "<<t.axy<<endl; sum+=t.axy; cout<<"最小生成樹的權(quán)值之和為："<<sum<<endl;/-prim算法結(jié)束-/-kruskal算法-/int FatherMax;/結(jié)點(diǎn)結(jié)構(gòu)體struct Node int Next; int Weight; /權(quán)重 int P

42、riority; /優(yōu)先級; int Find(int x) /查 if(x=Fatherx) return x; else return Find(Fatherx); void Union(int x,int y) /并 Fatherx=y ; int Top,Edge; bool Com(Node x,Node y) return x.Weight<y.Weight; deque<Node>Map; /調(diào)用克魯斯卡爾的相關(guān)代碼void show_kruskal() cout<<"請輸入結(jié)點(diǎn)個數(shù)及邊數(shù)："<<endl; cin&g

43、t;>Top>>Edge; int i,j; Node y;cout<<"請依次輸入兩點(diǎn)及權(quán)值："<<endl; for(i=1;i<=Top;i+) for(j=1;j<=Top;j+) int x; cin>>x; if(j>i && x!=100) y.Next=j; y.Priority=i; y.Weight=x; Map.push_back(y); sort(Map.begin(),Map.end(),Com); for(i=1;i<=Top;i+) Fatheri=i; int count=0; cout<<"樹的各組成邊有："<<endl; for(i=0;i<Map.size();i+) if(count=Top-1) break; if(Find(Mapi.Priority)!=Find(Mapi.Next) Union(Mapi.Priority,Mapi.Next); count+; if(Mapi.Priority>Mapi.Next) cout<<Mapi.Next<<"->"<<Mapi.Priority<<