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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告題目：北海公園主要游覽景點之間最短距離問題一、課程設(shè)計題目：北海公園主要游覽景點之間最短距離問題二、問題定義：（由教師指定）圖的最短路徑問題是指從指定的某一點V開始，求得從該地點到圖中其它各地點的最短路徑。并且給出求得的最短路徑的長度及途徑的地點。除了完成最短路徑的求解外，還能對該圖進行修改，如頂點以及邊的增刪、邊上權(quán)值的修改等。三、 需求分析1、 設(shè)計北海公園的平面圖。選取若干個有代表性的景點抽象成一個無向帶權(quán)圖，以圖中頂點表示公園內(nèi)各景點，邊上的權(quán)值表示兩景點之間的距離。2、 輸入的形式：整型數(shù)字輸入值的范圍：0-103、 輸出的形式：由二元組表示以鄰接矩陣存儲的圖4、 程序所能達到的功能；（1） 輸出頂點信息：將公園內(nèi)各景點輸出。（2） 輸出邊的信息：將公園內(nèi)每兩個位置的距離輸出。（3） 修改：修改兩個位置的距離，并重新輸出每兩個位置的距離；（4） 求最短路徑：輸出給定兩點之間的最短路徑的長度及途經(jīng)的地點，輸出任意一點與其他各點的最短路徑。（5） 刪除：刪除任意一條邊。（6）插入：插入任意一條邊。5、算法涉及的基本理論分析：定義鄰接矩陣adjmatrix；自定義頂點結(jié)構(gòu)體VertexType；定義鄰接表中的邊結(jié)點類型edgenode；switch算法；狄克斯特拉法（Dijkstra）求任意兩結(jié)點之間的最短路徑；6、題目研究和實現(xiàn)的價值。四、 算法設(shè)計1、概要設(shè)計（1）存儲結(jié)構(gòu)設(shè)計本系統(tǒng)采用圖結(jié)構(gòu)類型存儲抽象北海公園地圖的信息。其中：各景點間的鄰接關(guān)系用圖的鄰接矩陣類型（adjmatrix）存儲；景點（頂點）信息用結(jié)構(gòu)數(shù)組（WrtexType）存儲，其中每個數(shù)組元素是一個結(jié)構(gòu)變量，包含景點編號、景點名稱兩個分量；圖的頂點個數(shù)由分量MaxV^rtexNum表示，它是整型數(shù)據(jù)。2）主界面設(shè)計為了實現(xiàn)公園導(dǎo)游系統(tǒng)各功能的管理，首先設(shè)計一個含有多個菜單項的主控菜單子程序以鏈接系統(tǒng)的各項子功能，方便用戶使用本系統(tǒng)。3）系統(tǒng)功能設(shè)計a學(xué)校景點介紹公園景點介紹由函數(shù)PrintMatrix根據(jù)鄰接矩陣輸出二元組表示實現(xiàn)。當(dāng)用戶選擇該功能，系統(tǒng)即能輸出全部景點的信息：包括景點編號、景點名稱b查看瀏覽路線查看瀏覽路線采用狄克斯特拉（Dijkstra）算法實現(xiàn)。當(dāng)用戶選擇該功能,系統(tǒng)能根據(jù)用戶所在門起始編號，求出從該門到其它景點的最短路徑線路。c更改圖的信息更改圖的信息功能由主調(diào)函數(shù)change函數(shù)完成，可以實現(xiàn)圖的若干基本操作。例如：插入、刪除邊，重建圖等。2、主程序的流程以及各程序模塊之間的層次（調(diào)用）關(guān)系。（2）模塊設(shè)計本程序包含3個模塊：主程序模塊、工作區(qū)模塊和無向網(wǎng)操作模塊。主程序模塊 k工作區(qū)模塊 無向網(wǎng)操作模塊3、詳細設(shè)計（1）實現(xiàn)概要設(shè)計中定義的所有數(shù)據(jù)類型//鄰接矩陣的結(jié)構(gòu)體constintMaxVertexNum=9;constintMaxEdgeNum=16300;typedefintWeightType;constWeightTypeMaxValue=28;//頂點結(jié)構(gòu)體structVertexType{intnum_d;〃頂點代號charname[20];〃頂點名稱};typedefVertexTypevexlist[MaxVertexNum];typedefintadjmatrix[MaxVertexNum][MaxVertexNum];//定義鄰接表中的邊結(jié)點類型structedgenode{intadjvex;WeightTypeweight;edgenode*next;};2)所有函數(shù)的接口描述；//將二維數(shù)組里的數(shù)據(jù)傳輸給鄰接矩陣voidInitMatrix()//將景點名稱數(shù)據(jù)傳輸給頂點結(jié)構(gòu)體voidInitVT()//鄰接矩陣的二元組表示voidPrintMatrix()//PATHvoidPATH()//最短路徑：狄克斯特拉voidDijkstra()//輸出最短路徑voidPrint()//插入路徑問題voidchange()3)所有函數(shù)的算法描述(只需要寫出偽碼算法)；//將二維數(shù)組data[][]的數(shù)據(jù)傳輸給鄰接矩陣GAvoidInitMatrix(adjmatrix&GA,intdata[9][9]){GA[i][j]=data[i][j];}〃將景點名稱數(shù)據(jù)a[]傳輸給頂點結(jié)構(gòu)體VT[]voidInitVT(VertexTypeVT[9],char*a[9]){strcpy(VT[i].name,a[i]);//鄰接矩陣的二元組表示voidPrintMatrix(adjmatrixGA,VertexTypeVT[9]){cout<<"V={";cout<<i<<"--"<<VT[i].name<<',';cout<<"8--"<<VT[8].name<<'}'<<endl;cout<<"E={";cout<<'<'<<i<<','<<j<<'>'<<GA[i][j]<<',';cout<<'}'<<endl;}//輸出最短路徑voidPrint(edgenode*path[9],intbegin,VertexTypeVT[9]){coutvv"從起點到達"《VT[i].namevv"的最短路徑為"vv"-----";coutvvVT[p->adjvex].namevv"f";coutvvVT[i].namevv"\n";coutvv"無法通行至"vvVT[i].namevv"，請檢查路徑問題！"vvendl;}//插入路徑問題voidchange(intx,inty,intz,adjmatrix&GA){GA[x][y]=z;GA[y][x]=z;}(4)對主程序和其他模塊也都需要寫出偽碼算法voidmain(){char*a[9]={};//動態(tài)字符串?dāng)?shù)組intdata[9][9]={};adjmatrixGA;//定義鄰接矩陣VertexTypeVT[];//定義頂點結(jié)構(gòu)體InitVT(VT,a);〃傳輸頂點數(shù)據(jù)InitMatrix(GA,data);〃傳輸結(jié)構(gòu)體數(shù)據(jù)intdist[];edgenode*path[];intchose1=0,chose2=0,chose3=0,jidong_1=0,start=0,insert1=-1,insert2=-1,insert3=-1;//循環(huán),選擇,機動元素docout<<"* 歡迎使用北海公園路徑查詢程序 *\n";cout<<"* *"<<endl;cin>>chose1;switch(chose1){case1:PrintMatrix(GA,VT);〃根據(jù)鄰接矩陣輸出二元組表示break;case2:do{coutvv"*歡迎進行最短路徑選擇界面!請輸入您從哪個門進入!*\n";cout<<" \n"<<endl;cin>>chose2;switch(chose2){case1:coutvv"您選擇的起點為東門"vvendl;start=2;Dijkstra(GA,dist,path,start,9);Print(path,start,VT);break;case2:coutvv"您選擇的起點為前門"vvendl;start=0;Dijkstra(GA,dist,path,start,9);Print(path,start,VT);break;case3:coutvv"您選擇的起點為后門"vvendl;start=5;Dijkstra(GA,dist,path,start,9);Print(path,start,VT);break;case0:system("cls");〃清屏語句coutvv"退出成功，返回主菜單!\n"vvendl;break;default:system("cls");〃清屏語句coutvv"您的輸入有誤，返回最短路徑界面重新輸入!"vvendl;break;}}while(chose2!=0);break;case3:do{coutvv"*歡迎進入路徑修改界面!*\n";cin>>chose3;switch(chose3){case1:coutvv"請輸入插入路徑的起點"；cin>>insert1;coutvv"請輸入插入路徑的終點";cin>>insert2;coutvv"請輸入插入路徑的路長"；cin>>insert3;change(insert1,insert2,insert3,GA);coutvv"插入成功!\n"vvendl;break;case2:coutvv"請輸入修改路徑的起點"；cin>>insert1;coutvv"請輸入修改路徑的終點"；cin>>insert2;coutvv"請輸入修改路徑的路長"；cin>>insert3;change(insert1,insert2,insert3,GA)；coutvv"修改成功!\n"vvendl；break；case3:coutvv"請輸入刪除路徑的起點"；cin>>insert1；coutvv"請輸入刪除路徑的終點"；cin>>insert2；change(insert1,insert2,100000,GA)；coutvv"刪除成功!\n"vvendl；break；case0:break；default:coutvv"您的輸入有誤，即將返回路徑修改界面"vvendl;break；}while(chose3!=0);system("cls");〃清屏語句break;case4:system("cls");〃清屏語句coutvv"退出成功?歡迎您再次使用本系統(tǒng)?0(n_H)O謝謝"vvendl;break;default:coutvv"您的輸入有誤，即將返回主菜單!\n\n\n"vvendl;break;}}while(chose1!=4);}(5)畫出函數(shù)的調(diào)用關(guān)系圖。系統(tǒng)子程序及功能設(shè)計本系統(tǒng)共設(shè)置18個子程序，各子程序的函數(shù)名及功能說明如下。InitVT(VT,a);//傳輸頂點數(shù)據(jù)InitMatrix(GA,data);〃傳輸結(jié)構(gòu)體數(shù)據(jù)PrintMatrix(GA,VT);〃根據(jù)鄰接矩陣輸出二元組表示(4)Dijkstra(GA,dist,path,start,9);Print(path,start,VT);//用Dijkstra算法，求一個景點到其他景點間的最短路徑，并打印(5)change(insert1,insert2,insert3,GA);〃修改圖，包括增刪邊，修改權(quán)(6)switch函數(shù)主要調(diào)用關(guān)系圖圖中數(shù)字是各函數(shù)的編號五、算法實現(xiàn)六、軟件測試七、技術(shù)討論（可選）八、收獲與體會本次實踐讓我們小組懂得如何運用圖結(jié)構(gòu)來編寫與地圖有關(guān)的查詢程序，小組成員發(fā)揮團隊合作精神，分工合作，各盡其職，在短時間內(nèi)完成程序編寫n|x九、軟件運行的部分截圖及說明n|xg*C:\Docu*entsandSetting5\Ad*inistrator\桌面'實踐周1程序\Debug\北海公園■■■課雲(yún)為皆2商甬聶石「：直片讓塀問題？ *H課雲(yún)為皆2商甬聶石「：直片讓塀問題？ *舷可以在此系統(tǒng)申查詢北海公國有―—卜您可以在此系統(tǒng)申查詢游覽北羈公園的最短路隹…—卜同時，你也可以對北海公園的路徑進行插入，樓改，刪除等操作?岀i4U冃?功1?改的入2?倏||^<行需請尊所，請徑4?您徑，路入屢籍輸選及路園請您占4S岀i4U冃?功1?改的入2?倏||^<行需請尊所，請徑4?您徑，路入屢籍輸選及路園請您占4S亠宇在詢詢北出I-主菜單界面“*C:\Docu*entsandSettings\Ad*inistrator\桌面1實踐周1程序\Debug\北海公園■■■□|xPS：噱驟量二匸蠶,終點》兩景點之間的路徑距離〉卜<0—團城〔刖門），1—慶霄樓,2—白塔〔東門），3—春雨林堂,4—小西天,5—親蠶殿〔后門）丄一九龍壁汚一碧鮮亭胡一北海植物園〉E=?0,1>1500,<0,2>2000,<1,0>1500,<1,2>500,<2,0>2000,<2,1>500,<2,3>4000,<3,2>4000,<3,4>3000,<3,5>1800,<4,3>3000,<4,6>2000,<4,8>1000,<5,3>1800,<5,7>500,<6,4>2000,<6,7>1500,<7,5>500,<7,6>1500,<7,8>1000,<8,4>1000,<8,6>1000,>H 歡迎使用北海公區(qū)拠可以在此系統(tǒng)申查詢北海公園有—卜您可以在此系統(tǒng)申查詢游覽北輯公園的巖短路程問:卜同吋，你也可以對北海公園的路徑進行插入，樓改:查詢罔予 *青點，舌詢景點之間的路徑？-―丁問題？ *、,刪除等操作？-.■77也i4U冃，功it改的入2t修|§|^<行需請尊所，請徑4*您徑，路入誓番輸選及路園請您點磧亠^?-在詢詢北岀查詢景點及路徑3*C:\Docu>entsandSettings\.Ad*inistrator\桌面X.實踐周'程序\Debug\北海公園■■■「您選擇的起點為東il艮聲養(yǎng)達團?.￡?隊起點到澳起點到伙起點到一儂起點痢達（前rp您選擇的起點為東il艮聲養(yǎng)達團?.￡?隊起點到澳起點到伙起點到一儂起點痢達（前rp的最趣路徑為——白塔（東門團城（前門）婁禹墓短路徑為——白fc?n）丁慶晝樓斗白塔（東門）?春市林堂?小西天r——白選（東節(jié)一春雨林堂一iSt?備番鶉矗不達 i龍頭首為——百塔（東門親蠶殿（后門從起點到達九龍壁的最趣路徑為——白塔（東門）-春雨林堂-親蠶殿（后門）-碧鮮幕一九龍壁￡起點到達碧鮮亭的最短路徑為——白塔（東門）-春雨林堂-親蠶殿（后門）-碧鮮艮起點到達北再植物園的最短路徑為——白塔（東門）-春雨林堂-親蠶殿（后門）-骨鮮亭-北海植勃園b可以根據(jù)各個景點的最趣路徑確定您的游覽路線。_入入入界_進進進此一OZZEZ岀￥(曹退心園園園豐-公公公回您1*2*3*_入入入界_進進進此一OZZEZ岀￥(曹退心園園園豐-公公公回您1*2*3*輸吹吹請請請請請面查詢從東門進入各景點的最短路徑返回主菜單肆縉臺賢一＜肆縉臺賢一＜地點,終點》兩景點之間的路徑距離卜<0—團城〔刖門），1—慶霄樓,2—白塔〔東門），3—春雨林堂,4—小西天,5—親蠶殿〔后門）丄一九龍壁汚一碧鮮亭胡一北海植物園〉E=?0,1>1500,<0,2>2000,<1,0>1500,<1,2>500,<2,0>2000,<2,1>500,<2,3>4000,<3,2>4000,<3,4>3000,<3,5>1800,<4,3>3000,<4,6