




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、實驗報告(一) 有向圖的路徑問題1. 結(jié)構(gòu)體 typedef struct ArcNodeint adjvex; /地點序號char data;int weight; /權(quán)重struct ArcNode *nextarc;ArcNode;typedef struct VNodechar data; /地點名 ArcNode *firstarc;VNode,AdjListMVNum;typedef structAdjList vertices;int vexnum; /地點數(shù)量int arcnum; /邊數(shù)ALGraph;2. 函數(shù)int LocateVex( ALGraph G,char ve
2、x) /找到地點對應序號void Insert_vex( ALGraph &G , int i, int vex) /插入頂點void Insert_arc( ALGraph &G ,char v1,char v2,int weight) /插入信息/創(chuàng)建有向圖void CreatALGraph ( ALGraph &G )/Floyd算法void Floyd( ALGraph &G ,int TMVNumMVNum,int pathMVNumMVNum)void Find( ALGraph G ,int TMVNumMVNum,int pathMVNumMVN
3、um)3. 截圖4. 實驗心得重點是Floydy算法總體不難,做多了也就簡單了。5. 源代碼 #include "iostream"#include "string"using namespace std;#define MaxInt 32767#define MVNum 100typedef struct ArcNodeint adjvex; /地點序號char data;int weight; /權(quán)重struct ArcNode *nextarc;ArcNode;typedef struct VNodechar data; /地點名 ArcNode
4、*firstarc;VNode,AdjListMVNum;typedef structAdjList vertices;int vexnum; /地點數(shù)量int arcnum; /邊數(shù)ALGraph;int LocateVex( ALGraph G,char vex) /找到地點對應序號for( int i = 0; i <G.vexnum ;i+ )if( G.verticesi.data = vex )return i;void Insert_vex( ALGraph &G , int i, int vex) /插入頂點G.verticesi.data = vex;G.ver
5、ticesi.firstarc = NULL;void Insert_arc( ALGraph &G ,char v1,char v2,int weight) /插入信息ArcNode *p1;p1 = new ArcNode;int i,j;i = LocateVex(G,v1);j = LocateVex(G,v2);p1->adjvex = j; /頂點序號p1->data = G.verticesj.data; /頂點p1->weight = weight; /權(quán)值p1->nextarc = G.verticesi.firstarc; G.vertice
6、si.firstarc = p1;/創(chuàng)建有向圖void CreatALGraph ( ALGraph &G )G.vexnum = 6;G.arcnum = 8;/信息初始化Insert_vex( G,0,'A');Insert_vex( G,1,'B');Insert_vex( G,2,'C');Insert_vex( G,3,'D');Insert_vex( G,4,'E');Insert_vex( G,5,'F'); /頂點1,頂點2,權(quán)值Insert_arc( G,'A
7、9;,'C',10);Insert_arc( G,'A','E',30);Insert_arc( G,'A','F',100);Insert_arc( G,'B','C',5);Insert_arc( G,'C','D',50);Insert_arc( G,'D','F',10);Insert_arc( G,'E','D',20);Insert_arc( G,'E',
8、9;F',60);/輸出信息for( int i = 0; i <G.vexnum; i + )ArcNode *p1;p1 = G.verticesi.firstarc;while(p1)cout<<G.verticesi.data<<"t"<<p1->data<<"t"<<p1->weight<<endl;p1 = p1->nextarc;cout<<endl;/Floyd算法void Floyd( ALGraph &G ,in
9、t TMVNumMVNum,int pathMVNumMVNum)/初始化默認值for(int m = 0; m < G.vexnum ; m +)for(int n = 0;n < G.vexnum; n +)Tmn = MaxInt;pathmn = -1;/初始化賦值for( int i = 0; i < G.vexnum ; i +)ArcNode *p;p = G.verticesi.firstarc;while(p)Tip->adjvex = p->weight;pathip->adjvex = i;p = p->nextarc;for(i
10、nt k = 0;k < G.vexnum; k+)for(i = 0;i < G.vexnum ; i+)for( int j =0; j < G.vexnum; j +)if( Tik+Tkj < Tij )Tij = Tik+Tkj;pathij = pathkj; /j的前驅(qū)變?yōu)閗void Find( ALGraph G ,int TMVNumMVNum,int pathMVNumMVNum)char v1,v2;cout<<endl<<"請輸入要查詢的兩個點:"cin>>v1>>v2;int
11、i,j;i = LocateVex(G,v1);j = LocateVex(G,v2);/輸出最短時間并 循環(huán)查找前驅(qū)int t = j;if(pathit != -1 && i != t)cout<<v1<<" "<<v2<<" 有路徑!"<<endl;else cout<<v1<<" "<<v2<<" 沒有路徑!"<<endl;int main()ALGraph G;Creat
12、ALGraph( G );int TMVNum MVNum ;int pathMVNumMVNum ;Floyd(G,T,path);cout<<endl;doFind(G,T,path);cout<<endl<<"continue? Y/N"char select;cin>>select;if(select = 'n' | select = 'N')break;while(1);return 0;(二) 有向圖的路徑問題1. 結(jié)構(gòu)體typedef struct ArcNodeint adjve
13、x; /地點序號char data;double money; /權(quán)重struct ArcNode *nextarc;ArcNode;typedef struct VNodechar data; /地點名 ArcNode *firstarc;VNode,AdjListMVNum;typedef structAdjList vertices;int vexnum; /地點數(shù)量int arcnum; /邊數(shù)ALGraph;2. 函數(shù) int LocateVex( ALGraph G,char vex) /找到地點對應序號void Insert_vex( ALGraph &G , int i
14、, int vex) /插入頂點void Insert_arc( ALGraph &G ,char v1,char v2,int weight) /插入信息/創(chuàng)建有向圖void CreatALGraph ( ALGraph &G )/Floyd算法void Floyd( ALGraph &G ,int TMVNumMVNum,int pathMVNumMVNum)void Find( ALGraph G ,int TMVNumMVNum,int pathMVNumMVNum)3. 截圖4. 實驗心得實驗不難。重點是輸出最短路徑的算法。5. 源代碼#include &qu
15、ot;iostream"#include "string"using namespace std;#define MaxInt 32767#define MVNum 100typedef struct ArcNodeint adjvex; /地點序號char data;double money; /權(quán)重struct ArcNode *nextarc;ArcNode;typedef struct VNodechar data; /地點名 ArcNode *firstarc;VNode,AdjListMVNum;typedef structAdjList vertic
16、es;int vexnum; /地點數(shù)量int arcnum; /邊數(shù)ALGraph;int LocateVex( ALGraph G,char vex) /找到地點對應序號for( int i = 0; i <G.vexnum ;i+ )if( G.verticesi.data = vex )return i;void Insert_vex( ALGraph &G , int i, int vex) /插入頂點G.verticesi.data = vex;G.verticesi.firstarc = NULL;void Insert_arc( ALGraph &G ,c
17、har v1,char v2,double money) /插入信息ArcNode *p1;p1 = new ArcNode;int i,j;i = LocateVex(G,v1);j = LocateVex(G,v2);p1->adjvex = j; /頂點序號p1->data = G.verticesj.data; /頂點p1->money = money; /權(quán)值p1->nextarc = G.verticesi.firstarc; G.verticesi.firstarc = p1;/創(chuàng)建有向圖void CreatALGraph ( ALGraph &G
18、 )G.vexnum = 6;G.arcnum = 8;/信息初始化Insert_vex( G,0,'A');Insert_vex( G,1,'B');Insert_vex( G,2,'C');Insert_vex( G,3,'D');Insert_vex( G,4,'E');Insert_vex( G,5,'F'); /頂點1,頂點2,權(quán)值Insert_arc( G,'A','C',1);Insert_arc( G,'A','E',3
19、);Insert_arc( G,'A','F',10);Insert_arc( G,'B','C',0.5);Insert_arc( G,'C','D',5);Insert_arc( G,'D','F',1);Insert_arc( G,'E','D',2);Insert_arc( G,'E','F',6);/輸出信息for( int i = 0; i <G.vexnum; i + )ArcNode
20、 *p1;p1 = G.verticesi.firstarc;while(p1)cout<<G.verticesi.data<<"t"<<p1->data<<"t"<<p1->money<<endl;p1 = p1->nextarc;cout<<endl;/Floyd算法void Floyd( ALGraph &G ,int TMVNumMVNum,int pathMVNumMVNum)/初始化默認值for(int m = 0; m < G
21、.vexnum ; m +)for(int n = 0;n < G.vexnum; n +)Tmn = MaxInt;pathmn = -1;/初始化賦值for( int i = 0; i < G.vexnum ; i +)ArcNode *p;p = G.verticesi.firstarc;while(p)Tip->adjvex = p->money;pathip->adjvex = i;p = p->nextarc;for(int k = 0;k < G.vexnum; k+)for(i = 0;i < G.vexnum ; i+)for(
22、 int j =0; j < G.vexnum; j +)if( Tik+Tkj < Tij )Tij = Tik+Tkj;pathij = pathkj; /j的前驅(qū)變?yōu)閗void Find( ALGraph G ,int TMVNumMVNum,int pathMVNumMVNum)char v1,v2;cout<<endl<<"請輸入要查詢的兩個點:"cin>>v1>>v2;int i,j;i = LocateVex(G,v1);j = LocateVex(G,v2);/輸出最短時間并 循環(huán)查找前驅(qū)int t = j;if(pathit != -1 && i != t)cout<<G.verticesi.data<<&qu
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 教學資源整合與秋季應用計劃
- 2025年貴金屬靶材項目發(fā)展計劃
- 2025年面板封接玻璃合作協(xié)議書
- 2025年工業(yè)清洗清理設備:工業(yè)吸塵設備合作協(xié)議書
- 2025年電商大數(shù)據(jù)項目發(fā)展計劃
- 強化互動反饋的按鈕動畫設計
- 小學生勵志成長故事讀后感
- 基因檢測技術(shù)研發(fā)合同
- 2025年制動氣室項目發(fā)展計劃
- 智慧城市規(guī)劃與建設協(xié)議
- 血液凈化中心感染的危險因素及預防措施課件
- 2024電力系統(tǒng)安全規(guī)定
- 產(chǎn)品設計與開發(fā)的系統(tǒng)工程方法
- 脊柱骨折與脊髓損傷護理課件
- 預防留置針脫落
- 痛風護理疑難病例討論
- 《大學生職業(yè)能力訓練》
- 人民警察忠誠品質(zhì)
- 冠狀動脈搭橋手術(shù)后的健康生活促進
- 小學二年級語文上冊閱讀理解專項訓練20篇(含答案)
- 2024年中考語文名著閱讀知識(考點)專題10《水滸傳》真題精練(單一題)(解析版)
評論
0/150
提交評論