欧美精品一二区,性欧美一级,国产免费一区成人漫画,草久久久久,欧美性猛交ⅹxxx乱大交免费,欧美精品另类,香蕉视频免费播放

《大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》最短路徑問(wèn)題實(shí)驗(yàn)報(bào)告材料

上傳人:痛*** 文檔編號(hào):83696175 上傳時(shí)間:2022-05-02 格式:DOC 頁(yè)數(shù):16 大?。?18KB
收藏 版權(quán)申訴 舉報(bào) 下載
《大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》最短路徑問(wèn)題實(shí)驗(yàn)報(bào)告材料_第1頁(yè)
第1頁(yè) / 共16頁(yè)
《大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》最短路徑問(wèn)題實(shí)驗(yàn)報(bào)告材料_第2頁(yè)
第2頁(yè) / 共16頁(yè)
《大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》最短路徑問(wèn)題實(shí)驗(yàn)報(bào)告材料_第3頁(yè)
第3頁(yè) / 共16頁(yè)

下載文檔到電腦,查找使用更方便

10 積分

下載資源

還剩頁(yè)未讀,繼續(xù)閱讀

資源描述:

《《大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》最短路徑問(wèn)題實(shí)驗(yàn)報(bào)告材料》由會(huì)員分享,可在線閱讀,更多相關(guān)《《大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》最短路徑問(wèn)題實(shí)驗(yàn)報(bào)告材料(16頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、word 目錄 一、概述 1 二、系統(tǒng)分析 1 三、概要設(shè)計(jì) 2 四、詳細(xì)設(shè)計(jì) 5 5 6 7 五、運(yùn)行與測(cè)試 8 參考文獻(xiàn) 11 附錄 12 15 / 16 交通咨詢系統(tǒng)設(shè)計(jì)〔最短路徑問(wèn)題〕 一、概述 在交通網(wǎng)絡(luò)日益興旺的今天,針對(duì)人們關(guān)心的各種問(wèn)題,利用計(jì)算機(jī)建立一個(gè)交通咨詢系統(tǒng)。在系統(tǒng)中采用圖來(lái)構(gòu)造各個(gè)城市之間的聯(lián)系,圖中頂點(diǎn)表示城市,邊表示各個(gè)城市之間的交通關(guān)系,所帶權(quán)值為兩個(gè)城市間的消耗。這個(gè)交通咨詢系統(tǒng)可以回答旅客提出的各種問(wèn)題,例如:如何選擇一條路徑使得從A城到B城途中中轉(zhuǎn)次數(shù)最少;如何選擇一條路徑使得從A城到B城里程最短;如何選擇一

2、條路徑使得從A城到B城花費(fèi)最低等等的一系列問(wèn)題。 二、系統(tǒng)分析 設(shè)計(jì)一個(gè)交通咨詢系統(tǒng),能咨詢從任何一個(gè)城市頂點(diǎn)到另一城市頂點(diǎn)之間的最短路徑(里程)、最低花費(fèi)或是最少時(shí)間等問(wèn)題。對(duì)于不同的咨詢要求,可輸入城市間的路程、所需時(shí)間或是所需費(fèi)用等信息。 針對(duì)最短路徑問(wèn)題,在本系統(tǒng)中采用圖的相關(guān)知識(shí),以解決在實(shí)際情況中的最短路徑問(wèn)題,本系統(tǒng)中包括了建立圖的存儲(chǔ)結(jié)構(gòu)、單源最短問(wèn)題、對(duì)任意一對(duì)頂點(diǎn)間最短路徑問(wèn)題三個(gè)問(wèn)題,這對(duì)以上幾個(gè)問(wèn)題采用了迪杰斯特拉算法和弗洛伊德算法。并未本系統(tǒng)設(shè)置一人性化的系統(tǒng)提示菜單,方便使用者的使用。 三、概要設(shè)計(jì) 可以將該系統(tǒng)大致分為三個(gè)局部: ①  建立交通網(wǎng)絡(luò)圖的

3、存儲(chǔ)結(jié)構(gòu); ②  解決單源最短路徑問(wèn)題; ③  實(shí)現(xiàn)兩個(gè)城市頂點(diǎn)之間的最短路徑問(wèn)題。 交通咨詢系統(tǒng) 迪杰斯特拉算法〔單源最短路徑〕 費(fèi)洛依德算法〔任意頂點(diǎn)對(duì)間最短路徑〕 建立圖的存儲(chǔ)結(jié)構(gòu)義 迪杰斯特拉算法流圖: 弗洛伊德算法流圖: 四、詳細(xì)設(shè)計(jì) 建立圖的存儲(chǔ)結(jié)構(gòu) 定義交通圖的存儲(chǔ)結(jié)構(gòu)。鄰接矩陣是表示圖形中頂點(diǎn)之間相鄰關(guān)系的矩陣。設(shè)G=(V,E)是具有n個(gè)頂點(diǎn)的圖,如此G的鄰接矩陣是具有如下定義的n階方陣。 注:一

4、個(gè)圖的鄰接矩陣表示是唯一的!其表示需要用一個(gè)二維數(shù)組存儲(chǔ)頂點(diǎn)之間相鄰關(guān)系的鄰接矩陣并且還需要用一個(gè)具有n個(gè)元素的一維數(shù)組來(lái)存儲(chǔ)頂點(diǎn)信息〔下標(biāo)為i的元素存儲(chǔ)頂點(diǎn)的信息〕。 鄰接矩陣的存儲(chǔ)結(jié)構(gòu): #define MVNum 100 //最大頂點(diǎn)數(shù) typedef struct { VertexType vexs[MVNum];//頂點(diǎn)數(shù)組,類(lèi)型假定為char型 Adjmatrix arcs[MVNum][MVNum];//鄰接矩陣,假定為int型 }MGraph; 注:由于有向圖的鄰接矩陣是不對(duì)稱的,故程序運(yùn)行時(shí)只需要輸入所有有向邊與其權(quán)值即可。 單源最

5、短路徑 單源最短路徑問(wèn)題:有向圖(帶權(quán)),期望找出從某個(gè)源點(diǎn)S∈V到G中其余各頂點(diǎn)的最短路徑。 迪杰斯特拉算法即按路徑長(zhǎng)度遞增產(chǎn)生諸頂點(diǎn)的最短路徑算法。 算法思想:設(shè)有向圖G=(V,E),其中V={1,2,……n},cost是表示G的鄰接矩陣, cost[i][j]表示有向邊的權(quán)。假如不存在有向邊,如此cost[i][j] 的權(quán)為無(wú)窮大〔這里取值為32767〕。設(shè)S是一個(gè)集合,集合中一個(gè)元素表示一個(gè)頂點(diǎn),從源點(diǎn)到這些頂點(diǎn)的最短距離已經(jīng)求出。設(shè)頂點(diǎn)V1為源點(diǎn),集合S的初態(tài)只包含頂點(diǎn)V1。數(shù)組dist記錄從源點(diǎn)到其它各頂點(diǎn)當(dāng)前的最短距離,其初值為dist[i]= cos

6、t[i][j],i=2,……n。從S之外的頂點(diǎn)集合V-S中選出一個(gè)頂點(diǎn)w,使dist[w] 的值最小。于是從源點(diǎn)到達(dá)w只通過(guò)S中的頂點(diǎn),把w參加集合S中,調(diào)整dist中記錄的從源點(diǎn)到V-S中每個(gè)頂點(diǎn)v的距離:從原來(lái)的dist[v]和dist[w]+cost[w][v]中選擇較小的值作為新的dist[v]。重復(fù)上述過(guò)程,直到S中包含V中其余頂點(diǎn)的最短路徑。 最終結(jié)果是:S記錄了從源點(diǎn)到該頂點(diǎn)存在最短路徑的頂點(diǎn)集合,數(shù)組dist記錄了從源點(diǎn)到V中其余各頂點(diǎn)之間的最短路徑,path是最短路徑的路徑數(shù)組,其中path[i]表示從源點(diǎn)到頂點(diǎn)i之間的最短路徑的前驅(qū)頂點(diǎn)。 任意一對(duì)頂點(diǎn)之間的

7、最短路徑 任意頂點(diǎn)對(duì)之間的最短路徑問(wèn)題,是對(duì)于給定的有向網(wǎng)絡(luò)圖G=(V,E),要對(duì)G中任意一對(duì)頂點(diǎn)有序?qū)?,“V,W(V≠W)〞,找出V到W的最短路徑。而要解決這個(gè)問(wèn)題,可以依次把有向網(wǎng)絡(luò)圖中每個(gè)頂點(diǎn)作為源點(diǎn),重復(fù)執(zhí)行前面的迪杰斯特拉算法n次,即可求得每對(duì)之間的最短路徑。 費(fèi)洛伊德算法的根本思想:假設(shè)求從Vi到Vj的最短路徑。如果存在一條長(zhǎng)度為arcs[i][j]的路徑,該路徑不一定是最短路徑,還需要進(jìn)展n次試探。首先考慮路徑是否存在。如果存在,如此比擬路徑的路徑長(zhǎng)度,取長(zhǎng)度較短者為當(dāng)前所求得。該路徑是中間頂點(diǎn)序號(hào)不大

8、于1的最短路徑。其次,考慮從vi到vj是否包含有頂點(diǎn)v2為中間頂點(diǎn)的路徑< vi,…,v2,…,vj>,假如沒(méi)有,如此說(shuō)明從vi到vj的當(dāng)前最短路徑就是前一步求出的;假如有,那么可分解為,而這兩條路徑是前一次找到的中間點(diǎn)序號(hào)不大于1的最短路徑,將這兩條路徑長(zhǎng)度相加就得到路徑的長(zhǎng)度。將該長(zhǎng)度與前一次中求得的從vi到vj的中間頂點(diǎn)序號(hào)不大于1的最短路徑比擬,取其長(zhǎng)度較短者作為當(dāng)前求得的從vi到vj的中間頂點(diǎn)序號(hào)不大于2的最短路徑。依此類(lèi)推……直至頂點(diǎn)vn參加當(dāng)前從vi到vj的最短路徑后,選出從vi到vj的中

9、間頂點(diǎn)序號(hào)不大于n的最短路徑為止。由于圖G中頂點(diǎn)序號(hào)不大于n,所以vi到vj的中間頂點(diǎn)序號(hào)不大于n的最短路徑,已考慮了所有頂點(diǎn)作為中間頂點(diǎn)的可能性,因此,它就是vi到vj的最短路徑。 五、運(yùn)行與測(cè)試 3 測(cè)試實(shí)例1:利用如如下圖所示的有向圖來(lái)測(cè)試 13 17 7 1 61 74 76 32 64 6 4 56 26 2 45 5 測(cè)試實(shí)例2:利用如下圖求交通網(wǎng)絡(luò)圖〔無(wú)向圖〕的最短路徑。 2553 某某 704 1 695 2 349 某某 某某 511 812 3 4 某某 5

10、 1579 651 2368 某某 1385 7 某某 6 實(shí)例1運(yùn)行結(jié)果: 實(shí)例2運(yùn)行結(jié)果: 六、總結(jié)與心得 該課程設(shè)計(jì)主要是從日常生活中經(jīng)常遇到的交通網(wǎng)絡(luò)問(wèn)題入手,進(jìn)而利用計(jì)算機(jī)去建立一個(gè)交通咨詢系統(tǒng),以處理和解決旅客們關(guān)心的各種問(wèn)題〔當(dāng)然此次試驗(yàn)最終主要解決的問(wèn)題是:最短路徑問(wèn)題〕。 這次試驗(yàn)中我深刻的了解到了樹(shù)在計(jì)算機(jī)中的應(yīng)用是如何的神奇與靈活,對(duì)于很多的問(wèn)題我們可以通過(guò)樹(shù)的相關(guān)知識(shí)來(lái)解決,特別是在解決最短路徑問(wèn)題中,顯得尤為重要。 經(jīng)過(guò)著次實(shí)驗(yàn),我了

11、解到了關(guān)于樹(shù)的有關(guān)算法,如:迪杰斯特拉算法、弗洛伊德算法等,對(duì)樹(shù)的學(xué)習(xí)有了一個(gè)更深的了解。 參考文獻(xiàn) 【1】《數(shù)據(jù)結(jié)構(gòu)》嚴(yán)蔚敏.清華大學(xué). 【2】《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》蘇仕華.極械工業(yè). 附錄 #include #include #define MVNum 100 #define Maxint 32767 enum boolean{FALSE,TRUE}; typedef char VertexType; typedef int Adjmatrix; typedef struct{ VertexType vexs[MVNum]

12、; Adjmatrix arcs[MVNum][MVNum]; }MGraph; int D1[MVNum],p1[MVNum]; int D[MVNum][MVNum],p[MVNum][MVNum]; void CreateMGraph(MGraph * G,int n,int e) { int i,j,k,w; for(i=1;i<=n;i++) G->vexs[i]=(char)i; for(i=1;i<=n;i++) for(j=1;j<=n;j++) G->arcs[i][j]=Maxint; printf("輸入%d條邊的i.j

13、與w:\n",e); for(k=1;k<=e;k++){ scanf("%d,%d,%d",&i,&j,&w); G->arcs[i][j]=w; } printf("有向圖的存儲(chǔ)結(jié)構(gòu)建立完畢!\n"); } void Dijkstra(MGraph *G,int v1,int n) { int D2[MVNum],p2[MVNum]; int v,i,w,min; enum boolean S[MVNum]; for(v=1;v<=n;v++){ S[v]=FALSE; D2[v]=G->arcs[v1][v];

14、 if(D2[v]arcs[v][w]arcs[v][

15、w]; p2[w]=v; } } printf("路徑長(zhǎng)度 路徑\n"); for(i=1;i<=n;i++){ printf("%5d",D2[i]); printf("%5d",i);v=p2[i]; while(v!=0){ printf("<-%d",v); v=p2[v]; } printf("\n"); } } void Floyd(MGraph *G,int n) { int i,j,k,v,w; for(i=1;i<=n;i++) for(j=1;j<=n;j++)

16、 { if( G->arcs[i][j]!=Maxint) p[i][j]=j; else p[i][j]=0; D[i][j]=G->arcs[i][j]; } for(k=1;k<=n;k++) { for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if(D[i][k]+D[k][j]

17、 } void main() { MGraph *G; int m,n,e,v,w,k; int xz=1; G=(MGraph *)malloc(sizeof(MGraph)); printf("輸入圖中頂點(diǎn)個(gè)數(shù)和邊數(shù)n,e:"); scanf("%d,%d",&n,&e); CreateMGraph(G,n,e); while(xz!=0){ printf("************求城市之間最短路徑************\n"); printf("=========================================\n

18、"); printf("1.求一個(gè)城市到所有城市的最短路徑\n"); printf("2.求任意的兩個(gè)城市之間的最短路徑\n"); printf("=========================================\n"); printf("請(qǐng)選擇 :1或2,選擇0退出:\n"); scanf("%d",&xz); if (xz==2){ Floyd(G,n); printf("輸入源點(diǎn)〔或起點(diǎn)〕和終點(diǎn):v,w:"); scanf("%d,%d",&v,&w); k=p[v][w];

19、 if (k==0) printf("頂點(diǎn)%d 到 %d 無(wú)路徑!\n",v,w); else { printf("從頂點(diǎn)%d 到 %d 最短路徑路徑是:%d",v,w,v); while (k!=w){ printf("--%d",k); k=p[k][w]; } printf("--%d",w); printf("徑路長(zhǎng)度:%d\n",D[v][w]); } } else if(xz==1) printf("求單源路徑,輸入源點(diǎn)v:"); scanf("%d",&v); Dijkstra(G,v,n); } printf("完畢求最短路徑,再見(jiàn)!\n"); }

展開(kāi)閱讀全文
溫馨提示:
1: 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

相關(guān)資源

更多
正為您匹配相似的精品文檔
關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號(hào):ICP2024067431號(hào)-1 川公網(wǎng)安備51140202000466號(hào)


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺(tái),本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請(qǐng)立即通知裝配圖網(wǎng),我們立即給予刪除!