最短距離問題數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告

1、DOC可編輯修改為你整理各種最新最全辦公范文雙擊可以刪除最短距離問題數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告題目：北海公園主要游覽景點(diǎn)之間最短距離問題一、課程設(shè)計(jì)題目：北海公園主要游覽景點(diǎn)之間最短距離問題二、問題定義：圖的最短路徑問題是指從指定的莫一點(diǎn)v開始，求得從該地點(diǎn)到圖中其它各地點(diǎn)的最短路徑。并且給由求得的最短 路徑的長(zhǎng)度及途徑的地點(diǎn)。除了完成最短路徑的求解外，還能對(duì)該圖進(jìn)行修改，如頂點(diǎn)以及邊的增刪、邊 上權(quán)值的修改等。三、需求分析1、設(shè)計(jì)北海公園的平面圖。選取若干個(gè)有代表性的景 點(diǎn)抽象成一個(gè)無向帶權(quán)圖，以圖中頂點(diǎn)表示公園內(nèi)各景點(diǎn)，邊上的權(quán)值表示兩景點(diǎn)之間的距離。2、輸入的形式：整型數(shù)字

2、輸入值的范圍：0-103、輸生的形式：二元組表示以鄰接矩陣存儲(chǔ)的圖4、程序所能達(dá)到的功能；輸由頂點(diǎn)信息：將公園內(nèi)各景點(diǎn)輸由。輸由邊的信息：將公園內(nèi)每?jī)蓚€(gè)位置的距離輸由。修改：修改兩個(gè)位置的距離，并重新輸由每?jī)蓚€(gè)位置的愛心用心恒心DOC可編輯修改為你整理各種最新最全辦公范文雙擊可以刪除距離；求最短路徑：輸由給定兩點(diǎn)之間的最短路徑的長(zhǎng)度及途 經(jīng)的地點(diǎn)，輸由任意一點(diǎn)與其他各點(diǎn)的最短路徑。刪除：刪除任意一條邊。插入：插入任意一條邊。5、算法涉及的基本理論分析：定義鄰接矩陣adjmatrix ;自定義頂點(diǎn)結(jié)構(gòu)體 VertexType ;定義鄰接表中的邊結(jié)點(diǎn)類型edgenode; switch 算法；狄克

3、斯特拉法求任意兩結(jié)點(diǎn)之間的最短路徑；6、題目研究和實(shí)現(xiàn)的價(jià)值。四、算法設(shè)計(jì)1、概要設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)本系統(tǒng)采用圖結(jié)構(gòu)類型存儲(chǔ)抽象北海公園地圖的信息。 其中：各景點(diǎn)間的鄰接關(guān)系用圖的鄰接矩陣類型存儲(chǔ)；景點(diǎn)信息用結(jié)構(gòu)數(shù) 組存儲(chǔ)，其中每個(gè)數(shù)組元素是一個(gè)結(jié)構(gòu)變量，包含景點(diǎn)編號(hào)、景點(diǎn)名稱兩個(gè)分量；圖的頂點(diǎn)個(gè)數(shù)分量MaxVertexNum表示，它是整型數(shù)據(jù)。主界面設(shè)計(jì)為了實(shí)現(xiàn)公園導(dǎo)游系統(tǒng)各功能的管理，首先設(shè)計(jì)一個(gè)含 有多個(gè)菜單項(xiàng)的主控菜單子程序以鏈接系統(tǒng)的各項(xiàng)子功能， 方便用戶使用本系統(tǒng)。系統(tǒng)功能設(shè)計(jì)a學(xué)校景點(diǎn)介紹公園景點(diǎn)介紹函數(shù) PrintMatrix 根據(jù)鄰接矩陣輸由二元 組表示實(shí)現(xiàn)。當(dāng)用戶選擇該功能，

4、系統(tǒng)即能輸由全部景點(diǎn)的 信息：包括景點(diǎn)編號(hào)、景點(diǎn)名稱。b查看瀏覽路線查看瀏覽路線采用狄克斯特拉算法實(shí)現(xiàn)。當(dāng)用戶選擇該功能，系統(tǒng)能根據(jù)用戶所在門起始編號(hào)，求由從該門到其它 景點(diǎn)的最短路徑線路。c更改圖的信息更改圖的信息功能主調(diào)函數(shù)change函數(shù)完成，可以實(shí)現(xiàn)圖的若干基本操作。例如：插入、刪除邊，重建圖等。2、主程序的流程以及各程序模塊之間的層次（調(diào)用）關(guān)系。公園抽象圖設(shè)計(jì)5 6 7 8 4 3 1 2 0模塊設(shè)計(jì)本程序包含3個(gè)模塊：主程序模塊、工作區(qū)模塊和無向 網(wǎng)操作模塊。主程序模塊 工作區(qū)模塊 無向網(wǎng)操作模塊3、詳細(xì)設(shè)計(jì)實(shí)現(xiàn)概要設(shè)計(jì)中定義的所有數(shù)據(jù)類型；鄰接矩陣的結(jié)構(gòu)體const int M

5、axVertexNum=9;const int MaxEdgeNum=16300typedef int WeightType;const WeightType MaxValue=28; / 頂點(diǎn)結(jié)構(gòu)體 struct VertexType int num_d;/ 頂點(diǎn)代號(hào) char name20;/頂點(diǎn)名稱;typedef VertexType vexlistMaxVertexNum;typedefintadjmatrixMaxVertexNumMaxVertexNum; /定義鄰接表中的邊結(jié)點(diǎn)類型 struct edgenode int adjvex;WeightType weight;edg

6、enode *next; ;所有函數(shù)的接口描述；/將二維數(shù)組里的數(shù)據(jù)傳輸給鄰接矩陣 void InitMatrix()/將景點(diǎn)名稱數(shù)據(jù)傳輸給頂點(diǎn)結(jié)構(gòu)體void InitVT()/鄰接矩陣的二元組表示void PrintMatrix( ) /PATHvoid PATH()/最短路徑：狄克斯特拉void Dijkstra( ) / 輸由最短路徑void Print( ) /插入路徑問題void change()所有函數(shù)的算法描述；/將二維數(shù)組data口的數(shù)據(jù)傳輸給鄰接矩陣GA voidInitMatrix(adjmatrix &GA,int data99) GAij=dataij;/將景點(diǎn)

7、名稱數(shù)據(jù)a傳輸給頂點(diǎn)結(jié)構(gòu)體VT void InitVT(VertexTypeVT9,char*a9) strcpy(VT,ai);/鄰接矩陣的二元組表示void PrintMatrix(adjmatrix GA,VertexType VT9) cout'>chose1; switch(chosel) case 1:PrintMatrix(GA,VT);/根據(jù)鄰接矩陣輸由二元組表示break;do cout>chose2; switch(chose2)case 1: cout>chose3; switch(chose3)case 1:

8、cout>insert1; cout>insert2;cout>insert3;change(insert1,insert2,insert3,GA); cout>insert1;cout>insert2;cout>insert3;change(insert1,insert2,insert3,GA); cout>insert1;cout>insert2;change(insert1,insert2,100000,GA);cout'>chose1; switch(chosel) case 1:PrintMatrix(GA,VT);/根據(jù)鄰接矩陣輸由二元組表示break;do cout>chose2; switch(chose2)您選擇的起點(diǎn)為東門start=2;Dijkstra(GA,dist,path,start,9);您選 擇的起點(diǎn)為前門start=0;Dijkstra(GA,dist,path,start,9);Print(path,start,VT); break;case 2: