1、數(shù)據(jù)結(jié)構(gòu)與算法實驗報告一、需求分析【問題描述】設(shè)計一個校園導(dǎo)游程序，為來訪的客人提供各種信息查詢服務(wù)。【基本要求】設(shè)計你所在學(xué)校的校園平面圖，所含景點不少于10個。以圖中頂點表示校內(nèi)各景點，存放景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關(guān)信息。為來訪客人提供圖中任意景點相關(guān)信息的查詢。為來訪客人提供圖中任意景點的問路查詢，即查詢?nèi)我鈨蓚€景點之間的一個最短的簡單路徑?！緶y試數(shù)據(jù)】由讀者根據(jù)實際情況指定?！緦崿F(xiàn)提示】一般情況下，校園的道路是雙向通行的，可設(shè)校園平面圖是一個無向網(wǎng)。頂點和邊均含有相關(guān)信息?！具x作內(nèi)容】(6)擴充每個景點的鄰接景點的方向等信息，使得路徑查詢結(jié)果能提供詳盡

2、的導(dǎo)向信息。1)抽象數(shù)據(jù)類型定義描述#includeusingnamespacestd;constintMaxSize=18;constintINFINITY=65535;最大值無窮classdirection;templateclassMGraph;templateclassVertexNode/定義景點結(jié)點，存儲景點信息friendclassMGraph;public:intvex;/景點名稱Tvexname;/景點名稱Tvexinf;/景點信息directiondir;/存放景點方位信息的direction類的dir。;classdirectionpublic:intIn;/存放在方向圖

3、中的橫坐標(biāo)，表示東西intcol;/存放在方向圖中的縱坐標(biāo)，表示南北;templateclassMGraph/定義無向圖的鄰接矩陣public:MGraph();構(gòu)造函數(shù)，初始化具有n個頂點的圖voidprintvexname();/顯示所有景點及景點代號voidprintvexinf(inti);/顯示代號為i景點的名稱及信息voidprintroad(inti,intj);顯示景點ij的最短路徑方案信息voidprintdir(inti,intj);/顯示景點i到j(luò)的方向信息，如“向東100m,向南200m”VertexNodeadjlistMaxSize;/存放景點全部信息的景點類數(shù)組i

4、ntvertexNum,arcNum;/圖的頂點數(shù)和邊數(shù)voidRoot(intp,intq);/遞歸尋找pq間的最短路徑intPathMaxSizeMaxSize,DistMaxSizeMaxSize;/創(chuàng)建Path和Dist分別存放兩點間最短路徑的前驅(qū)節(jié)點，兩點間最短路徑長度intLineMaxSize;/Line存放路徑intkkk;/在floyed算法中，做Line數(shù)組的標(biāo)記private:TvertexMaxSize;/存放圖中頂點的數(shù)組intarcMaxSizeMaxSize;/存放圖中邊的數(shù)組;2)功能模塊設(shè)計(如主程序模塊設(shè)計)ICiXUsersgujFbalaDeskttsp

5、XZZ期工程心曲u麗工程.bce卸有點統(tǒng)訊矩園園聘計導(dǎo)1A示詢雷J12-3-4-請輸入要選擇的功能號:intfuncchoiceO/系統(tǒng)功能選擇頁面intchoice;coutendl;cout歡迎進入校園導(dǎo)游咨詢平臺endl;cout1一顯示校園所有景點信息endl;cout2-查詢校園景點信息endl;cout3問路查詢系統(tǒng)endl;cout4-退出導(dǎo)游資訊平臺endl;coutendl;coutchoice;returnchoice;返回某景點信息模塊printvexinf(inti)最短路徑模塊Floyed遞歸算法Root(intp,intq)3)模塊層次調(diào)用關(guān)系圖主程序菜單模式顯示所

6、有景點信息模塊printvexinf(inti)查詢信息模塊printvexname()問路模塊printroad(inti,intj)方位信息模塊printdir(intp,intq)三、詳細(xì)設(shè)計/程序的頭文件#include#include#includeguide.husingnamespacestd;templateMGraphT:MGraph()/a為景點代號，b為景點名稱，c為景點信息，d為景點方位信息的橫坐標(biāo),e為景點方位信息的縱坐標(biāo)，s為存放景點鄰接矩陣信息的一維數(shù)組，根據(jù)其對稱性可以用公式賦值給二維數(shù)組arcints=0,1,0,0,2,0,0,0,2,0,0,0,2,3,0

7、,0,0,0,4,2,0,0,0,0,0,2,3,0,0,0,0,0,2,3,1,0,0,0,2,0,2,0,0,2,0,4,0,2,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,2,0,1,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0

8、,4,4,0,0,2,0;inta=0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17;char*b=南門,實驗樓,南圖,大活,睿思樓,大禮堂，南4教,知行樓,國交樓,南3教,南2教,南1教,北圖,北3教,北4教,北2教,北1教,北門;char*c=南校區(qū)正門,物理實驗樓,南校區(qū)圖書館,大學(xué)生活動中心，教師辦公樓、醫(yī)務(wù)室及留學(xué)生公寓,大禮堂，用于舉辦各種文藝演出,南校區(qū)第4教學(xué)樓,實習(xí)基地，計算機房等,國際交流中心，教職工餐廳,南校區(qū)第3教學(xué)樓,南校區(qū)第2教學(xué)樓,南校區(qū)第1教學(xué)樓,北校區(qū)圖書館,北校區(qū)第3教學(xué)樓,北校區(qū)第4教學(xué)樓,北校區(qū)第2教學(xué)樓,北校區(qū)第1

9、教學(xué)樓,北校區(qū)正門;intd=8,6,4,4,1,0,0,1,3,4,6,8,4,3,2,3,5,8;inte=8,8,8,10,8,10,7,6,6,6,6,6,3,1,0,0,0,2;inti,j;vertexNum=18;arcNum=30;for(i=0;ivertexNum;i+)adjlisti.vex=ai;adjlisti.vexname=bi;adjlisti.vexinf=ci;adjlisti.dir.ln=di;adjlisti.dir.col=ei;for(i=0;ivertexNum;i+)/初始化鄰接矩陣for(j=0;jvertexNum;j+)arcij=ar

10、cji=s(i*(i+1)/2+j;/根據(jù)s的對稱性，將一維數(shù)組中的數(shù)據(jù)賦給二維數(shù)組arctemplatevoidMGraph:printvexname()inti;for(i=0;ivertexNum;i+)coutadjlisti.vexadjlisti.vexnameendl;templatevoidMGraph:printvexinf(inti)coutiadjlisti.vexname:adjlisti.vexinfendl;templatevoidMGraph:printdir(inti,intj)intdx,nb;/臨時存放i與j之間的南北東西關(guān)系j在i的哪邊？dx=adjlis

11、tj.dir.col-adjlisti.dir.col;nb=adjlistj.dir.ln-adjlisti.dir.ln;if(dx0)/即j在i的東邊cout向東dx*100m,;elsecout向西dx*(0T00)m,;if(nb0)/即j在i的南邊cout向南nb*100m;elsecout向北nb*(0T00)m;templateclassTvoidMGraph:Root(intp,intq)if(Pathpq0)Root(p,Pathpq);Root(Pathpq,q);elseLinekkk=q;kkk+;templatevoidMGraph:printroad(inti,i

12、ntj)intp,q,m,k,item1,item2;for(p=0;pvertexNum;p+)for(q=0;qvertexNum;q+)Distpq=arcpq;/鄰接矩陣賦值for(k=0;kvertexNum;k+)for(p=0;p0)for(q=0;q0)if(DistpqDistpk+Distkq)|(Distpq=0)&(p!=q)Distpq=Distpk+Distkq;Pathpq=k;coutn=n;cout從adjlisti.vexname到adjlistj.vexname的最短路徑為：endl;cout;printdir(i,item2);cout-adjlisti

13、tem2.vexname;for(m=3;m=kkk-1;m+)item1=Linem;cout-;printdir(item1-1,item1);coutadjlistitem1.vexname;coutendl;coutn=n;=以下為main.cpp文件中主函數(shù)的實現(xiàn)=#include#includeguide.cppusingnamespacestd;intfuncchoice()/系統(tǒng)功能選擇頁面intchoice;cout=choice;returnchoice;voidmain()MGraphchar*mg;intfuncchoice();intfc;while(1)fc=fun

14、cchoice();if(fc=1)inti;for(i=0;img.vertexNum;i+)mg.printvexinf(i);elseif(fc=2)inti;mg.printvexname();coutendl請輸入所要查詢景點代號：;cini;mg.printvexinf(i);elseif(fc=3)inti,j;mg.printvexname();cout請輸入兩景點代號(我們將把最短路線反饋予您)：；cinij;mg.printroad(i,j);elseif(fc=4)break;elsecout輸入有誤，請重新輸入！endl;調(diào)試分析if遇到的問題及解決的辦法：在調(diào)試過程中

15、，最常見到的問題有以下幾種：1、忘記調(diào)用函數(shù)類模塊templateclassT,有些類中或者函數(shù)中涉及函數(shù)類模塊的調(diào)用，但忘記標(biāo)注會導(dǎo)致編譯錯誤。我的解決方法是在寫程序中，一旦寫到“T”，就立刻到前面找類模塊的定義，如果發(fā)現(xiàn)沒寫就趕緊補上；2、容易混淆指針和對象，若將p定義為指針，則調(diào)用P所指向的類的函數(shù)時應(yīng)該用“-”，若P為對象則可直接用“”調(diào)用類中的共有接函數(shù)。針對該問題，我的解決辦法是在紙上寫明各個類及類中的成員函數(shù)，標(biāo)清類型等，這樣一目了然，寫程序的時候查對起來也方便；3、容易將類或函數(shù)名中的大寫字母錯寫成小寫字母，有時甚至導(dǎo)致編譯正確，連接錯誤，error不能指出錯誤的情況發(fā)生，使程

16、序查對過程較長，我的解決辦法是，以后在編程中應(yīng)盡量使用統(tǒng)一的書寫形式，如全部大寫或全部小寫；4、“=”的應(yīng)用，很多時候是不能直接用“=”賦值的，要注意等號兩邊的類型是否一致，是否可以用=賦值等；5、雖然已經(jīng)養(yǎng)成了在寫多句函數(shù)的時候，先把花括號起打上，但改程序的過程中還是會有粗心導(dǎo)致花括號不成對等情況出現(xiàn)，編譯中自己很難根據(jù)error提示找到問題所在，是同學(xué)幫我檢查到的，這提醒我在日后檢查error時也要注意花括號是否完整，而且我的個習(xí)慣有益于這個錯誤的查找，那就是格式對齊，格式對齊可以讓程序目了然，檢查花括號也變得簡單輕松很多；6、運行程序后對程序進行改動，改動后運行程序時應(yīng)將之前的運行界面關(guān)

17、閉才可以繼續(xù)；Floyed算法的時間空間復(fù)雜性分析：本程序中的Floyed算法對鄰接矩陣每一個元素都進行了N(N即為景點個數(shù))遍比較，所以時間復(fù)雜度是0(23);存放兩點間最短路徑前驅(qū)結(jié)點的path矩陣占用了N*N的空間，所以時間復(fù)雜度是0(22)。經(jīng)驗體會：在涉及矩陣等算法的時候，一定要注意下標(biāo)是否是0開始的，對稱的鄰接矩陣賦值給arcij的同時不要忘記賦值給arcjio獲得用戶輸入時一步一步的提示用戶輸入，具有很強的實用性。本實習(xí)作業(yè)采用數(shù)據(jù)抽象的程序設(shè)計方法，使得設(shè)計思路清晰，實現(xiàn)時調(diào)試順利。用戶守則1本程序的運行環(huán)境為windows操作系統(tǒng)，可執(zhí)行文件為：a.exe為了界面更加友好特將

18、背景顏色設(shè)計為黑色，字體為白色。進入演示程序后即顯示文本形式的用戶界面：五、測試結(jié)果詳細(xì)列出每一步的操作說明。交件逼輻至吉搔入J：程鋅丄具西匚琴旳舀圧日耳|毘更G|V”叮區(qū)1諸鈾|display二MI4Li護T觸二土1對到*h編譯/鳩工X-魚扭也件Ak咎具Lw.1站呢-陀/zhlljjGAcady()打開Microsoft(R)DeveloperStudio二）新建一個工程Wii2ConsoleApplication-Step1of1WhatkindofConsoleApplicationdoyouwanttocreate?席Anemptyproject.!Asimpleapplication

19、AHello,World!application.AnapplicationthatsupportsMFC.旦上_個|MF個|E完成（三）選擇“anemptyproject”并單擊“完成”（四）在工程內(nèi)新建一個headerfile用于存放類的定義（五）新建一個sourcefile用于存放類的實現(xiàn)，函數(shù)定義（六）新建一個sourcefile用于編寫主函數(shù)七、測試結(jié)果CMJsersAgujfbalaDeeIdop匸期工程kDebu二朝工程sces=Ju1-=L寓公出生演B乙留文室各務(wù)辦等工房職心壬于計心學(xué)-樓氧，中穀門驗書動公正實圖懐堂再實國耕南龍IH?:JJtet-tet-t魯實南大！國南星二二

20、二012345&?nn醫(yī)雲(yún)于ww流鱉聶第第第第計交蕩區(qū)區(qū)蔭區(qū)區(qū)區(qū)區(qū)辺攵攵攵攵3421nJI-I-I-I-FT匕要舅誦蜜FJFJFJV.JV.JV.J012345&789111i1111珀息5-n闍息臺彌有點統(tǒng)訊園園人導(dǎo)4A示詢醫(yī)蚯-&-型炎1-2-請輸入要選擇的功能號:構(gòu)造函數(shù)中已經(jīng)將校園景點的代號、名稱、簡介等信息全部設(shè)好，只需根據(jù)主頁面提示輸入功能號，即可查詢景點信息；CAUs-ersgujfbalaDeekttjp匸期工程2曲u9匸期工程啟艾己:2實驗樓朗圖教黑國南.亠PAXJ-z1S342i.3匕匕匕匕匕匕即TUtTUt_L_L_L_L_L_L;10123456?67aa9iiiill

21、ilie奮鑼韶獲壤職工餐廳情輸入要選擇的功能號：.T在查詢校園景點信息時，頁面會顯示各個景點的名稱及代號，方便來訪者查詢景點CAUs-ersgujfbalaDeeIdopAZ麗工程kDebugX二期工程,exE歡_迎進入校IS頭驗樓tni?歡迎進A校舉遍-顯示松園所有號睹輸入兩景點代號我們將把最短路線反饋予您：Mgx樓至頑門的最理為：十-宀z丄圉翠樓-向東200-向南100n南圖-向西眄向北200m頭驗樓-向東500m,向北1000U1南門使用問路查詢系統(tǒng)時，頁面顯示各景點代號及名稱，方便來訪者輸入查詢信息。在該模塊中，還設(shè)計了各景點在地圖上的分布矩陣，根據(jù)景點的方位信息，輸出兩景點間的距離方

22、向信息可以讓來訪者更容易找到這些景點及線ICMisersgujfbalaXDetgXZZMSJl.exe網(wǎng)有占繞訊麺園園黑駢ww一導(dǎo)SA示詢番刪顯查、果燦二二岑1234請輸入要選擇的功能號：4Fi*es：5：nnykeytoczontzLime使用完程序后輸入4號功能鍵即可退出六、附錄（源代碼）#include#includeusingnamespacestd;constintMaxSize=18;constintINFINITY=65535;最大值無窮classdirection;templateclassMGraph;templateclassVertexNode/定義頭結(jié)點friendc

23、lassMGraph;public:intvex;/頂點名稱Tvexname;/頂點名稱Tvexinf;/頂點信息directiondir;/存放頂點方位信息的direction類的dir。;classdirectionpublic:intln;/存放在方向圖中的橫坐標(biāo)，表示東西intcol;/存放在方向圖中的縱坐標(biāo)，表示南北;templateclassMGraph/定義無向圖的鄰接矩陣public:MGraph();/構(gòu)造函數(shù)，初始化具有n個頂點的圖voidprintvexname();/顯示所有景點及景點代號voidprintvexinf(inti);/顯示代號為i景點的名稱及信息void

24、printroad(inti,intj);/顯示景點ij的最短路徑方案信息voidprintdir(inti,intj);/顯示景點i到j(luò)的方向信息，如“向東100m，向南200m”VertexNodeadjlistMaxSize;/存放景點全部信息的景點類數(shù)組intvertexNum,arcNum;/圖的頂點數(shù)和邊數(shù)voidRoot(intp,intq);遞歸尋找pq間的最短路徑intPathMaxSizeMaxSize,DistMaxSizeMaxSize;/創(chuàng)建Path和Dist分別存放兩點間最短路徑的前驅(qū)節(jié)點，兩點間最短路徑長度intLineMaxSize;/Line存放路徑intkk

25、k;/Line數(shù)組的標(biāo)記private:TvertexMaxSize;/存放圖中頂點的數(shù)組intarcMaxSizeMaxSize;/存放圖中邊的數(shù)組;*【以下為類的實現(xiàn)即類函數(shù)的定義】templateMGraphVT:MGraph()/a為景點代號，b為景點名稱，c為景點信息，d為景點方位信息的橫坐標(biāo)，e口為景點方位信息的縱坐標(biāo)/s為存放景點鄰接矩陣信息的一維數(shù)組，根據(jù)其對稱性可以用公式賦值給二維數(shù)組arc口ints=0,1,0,0,2,0,0,0,2,0,0,0,2,3,0,0,0,0,4,2,0,0,0,0,0,2,3,0,0,0,0,0,2,3,1,0,0,0,2,0,2,0,0,2,

26、0,4,0,2,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,2,0,1,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,4,4,0,0,2,0;inta=0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,

27、17;char*b=南門，實驗樓，南圖，大活,睿思樓,大禮堂，南4教,知行樓,國交樓,南3教,南2教,南1教,北圖,北3教,北4教,北2教,北1教,北門;char*c=南校區(qū)正門,物理實驗樓，南校區(qū)圖書館，大學(xué)生活動中心，教師辦公樓、醫(yī)務(wù)室及留學(xué)生公寓,大禮堂，用于舉辦各種文藝演出,南校區(qū)第4教學(xué)樓,實習(xí)基地，計算機房等,H豹總禽tF孵sHaF、滋岡W3孵魅蔚:岡B2舞魅殊、些岡B1孵魅憨n右雞岡ffl出蠱、止巍岡w3舞魅跨、&巍岡4孵魅竦J衛(wèi)嶷岡B2孵魅竦a憐惑岡W一舞世v憐席岡用0工気d口乂8、6A4FO、OP3A6、8A3、235、8MmtAII宀8A8、10,8、10、7、6、6、6、

28、6、6、3、r0、00、2Ma:jveltexNumHli?ttRZCSUWOffAuojAveltexNunv+iforliojvexuaEjvexnameHbmjvexmfHasdFHludmjdFcollasAveltexNunv+M3s:左含嫌福ffCJHOjJAVeltexNunvJ+iarcmullarcLj!=!llsc:M+eM2；二為舗s口s閔葵聯(lián)專憐鼻口口tempttteACttssTVvoidMGaphrv:pilltvexnameo-CinEuffAuojAveltexNunv+i8UEAAadjHS莒vexAA:AAadj=stsvexlulnleAAendi:tempfirteACfirssTVvoidMGmphATy.plilltvexillsnrt10-C8&AAAAaSAAtt&=WAu.ss3OAASSAAU&=WAu.s%AA3atempfirteACfirssTVvoidMGmphATy.plintdAsrt1c:nEsmtcbQnbvffi器一JITjHasMZIk濟*wjm-3S&77dxHadju%曰d78亍adjMmwdrcounbuadjHst曰d7mda:=:stmd7=fvossigsefvoss3&8&AA3M3AA3_W*M.OOAAHljse8gxa33aab_w*bBoxabbstempfirteACfirssTVvo