校園導(dǎo)游咨詢系統(tǒng)---數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(共35頁)

精選優(yōu)質(zhì)文檔-傾情為你奉上石家莊經(jīng)濟(jì)學(xué)院 本科生課程設(shè)計(jì)報(bào)告書 題 目 校園導(dǎo)游咨詢系統(tǒng) 姓名 顏建學(xué) 學(xué)號(hào) 1 學(xué) 院 信息工程學(xué)院 專業(yè) 計(jì)算機(jī)方向 指導(dǎo)教師 XXXXXX 完成日期： 2012-07-5校園導(dǎo)游咨詢系統(tǒng)1 需求分析本程序的主要目的是為了提供本學(xué)校的景點(diǎn)的路徑咨詢和來訪客人以及剛來報(bào)到的新生提供一個(gè)快捷方便的路徑咨詢，快速有效的提高了用戶的熟悉度。滿足用戶查詢的需要：1、從石家莊經(jīng)濟(jì)學(xué)院的平面地圖中選取出10個(gè)有代表性的景點(diǎn)。2、為來訪的客人提供圖中任意景點(diǎn)相關(guān)信息的查詢。當(dāng)用戶輸入正確時(shí)，為用戶輸出景點(diǎn)的相關(guān)信息；當(dāng)用戶輸入不合法時(shí)，提示用戶輸入有誤并返回讓用戶重新輸入。3、為來訪的客人提供圖中任意景點(diǎn)的路徑查詢，即查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的最短簡(jiǎn)單路徑。當(dāng)用戶輸入正確時(shí)，為用戶輸出任意兩景點(diǎn)的最短路徑；當(dāng)用戶輸入不合法時(shí)，提示用戶輸入有誤并返回讓用戶重新輸入。4、為來訪客人推薦參觀路線。2 概要設(shè)計(jì)1、抽象數(shù)據(jù)類型圖的定義如下：ADT Graph數(shù)據(jù)對(duì)象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。數(shù)據(jù)關(guān)系R：R=VRVR=(v,w)|v,wV,(v,w)表示v和w之間存在路徑基本操作P：CreatGraph70321(&G,V,VR)初始條件：V是圖的頂點(diǎn)集，VR是圖中邊的集合。操作結(jié)果：按V和VR的定義構(gòu)造圖G。DestroyGraph70321(&G)初始條件：圖G存在。操作結(jié)果：銷毀圖G。LocateVex70321(G,u)初始條件：圖G存在，u和G中頂點(diǎn)有相同特征。操作結(jié)果：若G中存在頂點(diǎn)u，則返回該頂點(diǎn)在圖中位置；否則返回其他信息。GetVex70321(G,v)初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)。操作結(jié)果：返回v的信息。FirstEdge70321(G,v)初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)。操作結(jié)果：返回依附于v的第一條邊。若該頂點(diǎn)在G中沒有鄰接點(diǎn)，則返回“空”。 NextEdge70321(G,v,w)初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)，w是v的鄰接頂點(diǎn)。操作結(jié)果：返回依附于v的（相對(duì)于w的）下一條邊。若不存在，則返回“空”。 InsertVex70321(&G,v)初始條件：圖G存在，v和圖中頂點(diǎn)有相同特征。操作結(jié)果：在圖中增添新頂點(diǎn)v。DeleteVex70321(&G,v)初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)。操作結(jié)果：刪除G中頂點(diǎn)v及其相關(guān)的邊。InsertEdge70321(&G,v,w)初始條件：圖G存在，v和w是G中兩個(gè)頂點(diǎn)。操作結(jié)果：在G中增添邊(v,w).DeleteEdge70321(&G,v,w)初始條件：圖G存在，v和w是G中兩個(gè)頂點(diǎn)。操作結(jié)果：在G中刪除邊(v,w)。GetShortestPath70321(G,st,nd,&Path)初始條件：圖G存在，st和nd是G中兩個(gè)頂點(diǎn)。操作結(jié)果：若st和nd之間存在路徑，則以Path返回兩點(diǎn)之間一條最短路徑，否則返回其他信息。ADT Graph主程序void main()初始化； do 接受命令（輸入景點(diǎn)信息或輸出最短路徑）； 處理命令； while（“命令”！=“退出”）；2、調(diào)用的函數(shù)有如下：void CreateUDN70321(int v,int a); /* 造圖函數(shù) */void narrate70321(); /*說明函數(shù)*/void ShortestPath70321(int num); /*最短路徑函數(shù)*/void output70321(int sight1,int sight2); /*輸出函數(shù)*/char Menu70321(); /* 主菜單 */void search70321(); /* 查詢景點(diǎn)信息 */char SearchMenu70321(); /* 查詢子菜單 */void HaMiTonian70321(int); /* 哈密爾頓圖的遍歷 */void NextValue70321(int); void display70321(); /* 顯示遍歷結(jié)果 */3、運(yùn)行主界面：*歡 迎 使 用 校 園 導(dǎo) 游 程 序*石*家*莊*經(jīng)*濟(jì)*學(xué)*院*制作者：信息工程學(xué)院 1 顏建學(xué) ！歡迎您的使用！ 景點(diǎn)名稱 （0）教學(xué)主樓 （1）足球場(chǎng) （2）燈光籃球場(chǎng) （3）惠馨園 （4）實(shí)驗(yàn)樓 （5）計(jì)算機(jī)實(shí)驗(yàn)室 （6）地球科學(xué)博物館 （7）學(xué)術(shù)報(bào)告廳 （8）圖書館 （9）噴泉 1、查詢景點(diǎn)路徑 2、查詢景點(diǎn)信息 3、推薦參觀路線 e、退出 子界面如下： 1、按照景點(diǎn)編號(hào)查詢 2、按照景點(diǎn)名稱查詢 e、返回 3、模塊圖表示如下：主程序模塊處理功能模塊無向圖存儲(chǔ)模塊為用戶輸出景點(diǎn)信息為用戶輸出兩景點(diǎn)最佳路徑推薦參觀路徑3 詳細(xì)設(shè)計(jì)從石家莊經(jīng)濟(jì)學(xué)院的平面地圖中選取出10個(gè)有代表性的景點(diǎn)，將其抽象成無向帶權(quán)網(wǎng)并用鄰接矩陣來表示。以圖中的頂點(diǎn)代表景點(diǎn)，存放景點(diǎn)名稱、代號(hào)、簡(jiǎn)介等信息，權(quán)值代表兩地之間的距離。1、 圖的存儲(chǔ)結(jié)構(gòu)如下：#define Max 20000#define NUM 9typedef struct ArcCell int adj; /* 相鄰接的景點(diǎn)之間的路程 */ArcCell; /* 定義邊的類型 */typedef struct VertexType70321 int number; /* 景點(diǎn)編號(hào) */ char *sight; /* 景點(diǎn)名稱 */ char *description; /* 景點(diǎn)描述 */VertexType; /* 定義頂點(diǎn)的類型 */typedef struct VertexType vexNUM; /* 圖中的頂點(diǎn)，即為景點(diǎn) */ ArcCell arcsNUMNUM; /* 圖中的邊，即為景點(diǎn)間的距離 */ int vexnum,arcnum; /* 頂點(diǎn)數(shù)，邊數(shù) */MGraph; /* 定義圖的類型2、該程序的算法如下：1)void CreateUDN70321(MGraph&G) /* 造圖函數(shù) */ /采用鄰接矩陣表示法，構(gòu)造無向網(wǎng)Gscanf(&G.vexnum,&G.arcnum,&IncInfo);/ IncInfo為0則各弧不含其它信息for(i=0;i< G.vexnum;+i)scanf(&G.vexsi);/構(gòu)造頂點(diǎn)向量for(i=0;i< G.vexnum;+i)/初始化鄰接矩陣for(j=0;j< G.vexnum;+j)G.arcsij=INFINITY,NULLfor(k=0;k< G.arcnum;+k)/構(gòu)造鄰接矩陣scanf(&v1,&v2,&w);/輸入一條邊依附的頂點(diǎn)及權(quán)值i=LocateVex(G,v1);j= LocateVex(G,v2);/確定V1和V2在G中的位置G.arcsij.adj=w;/弧<v1,v2>的權(quán)值If(IncInfo)Input(*G.arcsij.info);/若弧含有相關(guān)信息，則輸入G.arcsji= G.arcsij;/置<v1,v2>的對(duì)稱弧<v2,v1> Return OK; 2)void narrate70321() /* 說明函數(shù) */k=0;printf("ntt*歡 迎 使 用 校 園 導(dǎo) 游 程 序*n");printf("ntt*石*家*莊*經(jīng)*濟(jì)*學(xué)*院*n");printf("ntt制作者： 信息工程學(xué)院 1 顏建學(xué) ！歡迎您使用！n");printf("ntt_n");printf("ttttt 景點(diǎn)名稱ttn");printf("tt_n");for(i=0;i<NUM;i+)printf("tt (%2d)%-15stt",i,G.vexi.sight);if(i%2=(NUM-1)%2)printf("n");/奇數(shù)編號(hào)景點(diǎn)在右邊，偶數(shù)編號(hào)景點(diǎn)在左邊k=k+1;printf("tt_n");3) void ShortestPath70321(int num) /用迪杰斯特拉算法求G的v0頂點(diǎn)到其余頂點(diǎn)的最短路徑Pv及其帶權(quán)長(zhǎng)度 Dv/若Pvw為TRUE,則 w是從v0到v當(dāng)前求得最短路徑上的頂點(diǎn) /finalv為TRUE當(dāng)且僅當(dāng)v屬于S，即已經(jīng) 求得從 v0到v的最短路徑 for(v=0;v<G.vexnum;+v) Finalv=FALSE;Dv= G.arcsv0v; For(w=0;w< G.vexnum;+w)Pvw=FALSE; If (Dv<INFINITY)Pvv0=TRUE;Pvv=TRUE; /forDv0=0;finalv0=TRUE;/開始主循環(huán)，每次求得v0到某個(gè)頂點(diǎn)的最短路徑，并加v到S集For(i=1;i< G.vexnum;+i) Min=INFINITY; For(w=0;w< G.vexnum;+w) If(!finalw) If(Dw<min)v=w;min=Dw; Finalv=TRUE; For(w=0;w< G.vexnum;+w) If(!finalw&&(min+G.arcsvw<Dw) Dw= min+G.arcsvw; Pw=Pv;Pww=TRUE; /if /for / ShortestPath4) void output70321(int sight1,int sight2) /* 輸出函數(shù) */ if(sight2!=sight1) /* 如果景點(diǎn)二不和景點(diǎn)一輸入重合，則進(jìn)行. */ printf(從G.vexsight1.sight到G.vexsight2.sight的最短路徑是:);/* 輸出提示信息 */ printf(Da); /* 輸出sight1到sight2的最短路徑長(zhǎng)度，存放在D數(shù)組中 */ printf(G.vexsight1.sight); /* 輸出景點(diǎn)一的名稱 */ d=sight1; /* 將景點(diǎn)一的編號(hào)賦值給d */ for(c=0;c<NUM;+c) Pasight1=0; for(b=0;b<NUM;b+) if(G.arcsdb.adj<20000&&Pab) /* 如果景點(diǎn)一和它的一個(gè)臨界點(diǎn)之間存在路徑且最短路徑 */ printf(G.vexb.sight); /* 輸出此節(jié)點(diǎn)的名稱 */ q=q+1; /* 計(jì)數(shù)變量加一，滿8控制輸出時(shí)的換行 */ Pab=0; d=b; /* 將b作為出發(fā)點(diǎn)進(jìn)行下一次循環(huán)輸出，如此反復(fù) */ if(q%8=0) returnOK; 5)void main() /* 主函數(shù) */CreateUDN70321(NUM,11); do switch(Menu() case '1': narrate70321(); scanf(v0); scanf(v1); ShortestPath70321(v0); /* 計(jì)算兩個(gè)景點(diǎn)之間的最短路徑 */ Output70321(v0,v1); /* 輸出結(jié)果 */ break; case '2':search(); break; case '3': narrate70321(); HaMiTonian(x0); break; ; while(Menu()!='e'); 6) char Menu() /* 主菜單 */ do flag=1; narrate70321(); scanf(c); if(c='1'|c='2'|c='3'|c='e') flag=0; while(flag); return c;7) char SearchMenu70321() /* 查詢子菜單 */ do flag=1; narrate70321(); scanf(&c); if(c='1'|c='2'|c='e') flag=0; while(flag); return c;8) void search70321() /* 查詢景點(diǎn)信息 */do switch 70321(SearchMenu() case '1': narrate70321(); scanf(&num); for(i=0;i<NUM;i+) if(num=G.vexi.number) printf(G.vexi.description); break; if(i=NUM) printf(沒有找到！"); getchar70321(); break; case '2': narrate70321(); scanf(name); for(i=0;i<NUM;i+) if(!strcmp(name,G.vexi.sight) printfG.vexi.description); break; if(i=NUM) printf(沒有找到！"); break; while(SearchMenu()!='e');3、流程圖如下：開始造圖輸入您的選擇您的選擇是1？您的選擇是2？您的選擇是3？您的選擇是100？結(jié)束輸入您的第一個(gè)景點(diǎn)選擇輸入您的第二個(gè)景點(diǎn)選擇您的選擇是e？符合條件？計(jì)算最短路徑輸出結(jié)果按編號(hào)查詢？推薦最佳路徑輸入景點(diǎn)編號(hào)輸入景點(diǎn)名稱輸出結(jié)果輸出結(jié)果輸出結(jié)果否是否是否否是是否是是否是石家莊經(jīng)濟(jì)學(xué)院校園導(dǎo)游系統(tǒng)設(shè)計(jì)流程圖信息工程學(xué)院 計(jì)算機(jī)三班顏建學(xué) 14 編碼調(diào)試校園導(dǎo)游咨詢系統(tǒng)主界面如下圖1所示，輸入1進(jìn)行景點(diǎn)路徑查詢，輸入2進(jìn)行景點(diǎn)信息查詢，輸入3時(shí)推薦參觀路線，輸入e時(shí)則退出本系統(tǒng)。圖1當(dāng)輸入1時(shí)進(jìn)入一個(gè)選擇子菜單（輸入錯(cuò)誤時(shí)，保持原有狀態(tài)），正確輸入起點(diǎn)（2）（燈光籃球場(chǎng)）和終點(diǎn)（4）（實(shí)驗(yàn)樓），屏幕將打印出兩景點(diǎn)之間的最短路徑：燈光籃球場(chǎng)惠馨園實(shí)驗(yàn)樓，最短路徑為約430m。如下圖2所示： 圖2當(dāng)輸入的景點(diǎn)代號(hào)不在（0-9）之間時(shí)，程序提示重新輸入，直到輸入正確。測(cè)試數(shù)據(jù)：當(dāng)起點(diǎn)輸入10終點(diǎn)輸入12時(shí)，景點(diǎn)不存在，程序提示重新輸入；當(dāng)起點(diǎn)輸入0（教學(xué)主樓）終點(diǎn)輸入12時(shí)，終點(diǎn)景點(diǎn)不存在，程序提示重新輸入；當(dāng)起點(diǎn)輸入0（教學(xué)樓）終點(diǎn)輸入8（圖書館）時(shí)，景點(diǎn)都存在，屏幕打印出兩景點(diǎn)最短路徑：教學(xué)樓噴泉學(xué)術(shù)報(bào)告廳圖書館，最短路徑約為200m。如下圖3所示： 圖3按100推出此環(huán)節(jié)，當(dāng)在選擇主菜單選擇2時(shí)，出現(xiàn)如下圖4所示子菜單： 圖4當(dāng)輸入1時(shí)，則按景點(diǎn)編號(hào)查詢，當(dāng)輸入6（地球科學(xué)博物館）時(shí)，屏幕上打印出此景點(diǎn)信息：里面有著名的不尋?？铸埢划?dāng)輸入4（實(shí)驗(yàn)樓）時(shí)，屏幕上打印出此景點(diǎn)信息：各專業(yè)實(shí)驗(yàn)的重要場(chǎng)地；當(dāng)輸入12時(shí)，此景點(diǎn)不存在，屏幕上顯示：！沒*有*找*到?。划?dāng)輸入20時(shí)，此景點(diǎn)不存在，屏幕上顯示：！沒*有*找*到！。如下圖5所示： 圖5當(dāng)輸入2時(shí)，則按景點(diǎn)名稱查詢，當(dāng)輸入“圖書館”時(shí)，屏幕上打印出此景點(diǎn)信息：圖書館是莘莘學(xué)子學(xué)習(xí)的園地，里面有各科資料，每人可以任借五本書；當(dāng)輸入“計(jì)算機(jī)實(shí)驗(yàn)室”時(shí)，屏幕上打印出此景點(diǎn)信息：計(jì)算機(jī)專業(yè)實(shí)驗(yàn)實(shí)習(xí)場(chǎng)所；當(dāng)輸入“教學(xué)三號(hào)樓”時(shí)，此景點(diǎn)不存在，屏幕上顯示：！沒*有*找*到??；如下圖6所示： 圖6當(dāng)在選擇主菜單中輸入3時(shí)，則系統(tǒng)推薦旅游路徑：1）教學(xué)主樓足球場(chǎng)燈光籃球場(chǎng)惠馨園實(shí)驗(yàn)樓噴泉學(xué)術(shù)報(bào)告廳地球科學(xué)博物館計(jì)算機(jī)實(shí)驗(yàn)室圖書館校園出口2）教學(xué)主樓足球場(chǎng)燈光籃球場(chǎng)惠馨園實(shí)驗(yàn)樓噴泉學(xué)術(shù)報(bào)告廳圖書館計(jì)算機(jī)實(shí)驗(yàn)室地球科學(xué)博物館校園出口3）教學(xué)主樓地球科學(xué)博物館計(jì)算機(jī)實(shí)驗(yàn)室圖書館學(xué)術(shù)報(bào)告廳噴泉實(shí)驗(yàn)樓惠馨園燈光籃球場(chǎng)足球場(chǎng)校園出口如下圖7所示 圖7在選擇主菜單輸入錯(cuò)誤時(shí)，程序不作反應(yīng)，當(dāng)輸入e時(shí)，則退出，如下圖8所示 圖8由于本人的設(shè)計(jì)能力有限，在設(shè)計(jì)過程中難免出現(xiàn)錯(cuò)誤。本程序在調(diào)試時(shí)，出現(xiàn)了一個(gè)很棘手的錯(cuò)誤，出現(xiàn)了結(jié)構(gòu)體變量G的重復(fù)定義，經(jīng)過自己的多次修改，沒有成功，最后在老師的幫助下，將變量的定義從函數(shù)定義里放到了函數(shù)聲明里，成功的修改了那個(gè)問題。當(dāng)然還有一些簡(jiǎn)單的語法錯(cuò)誤，這些錯(cuò)誤都是比較好改的，在此就不一一列舉了。5 設(shè)計(jì)體會(huì)本次課程設(shè)計(jì)使我提高了應(yīng)用計(jì)算能力、編寫代碼的基本能力、繪畫流程圖能力，熟悉了規(guī)范和標(biāo)準(zhǔn)，同時(shí)對(duì)于本設(shè)計(jì)的課程都有了全面的復(fù)習(xí)，獨(dú)立思考的能力也有了提高。1、當(dāng)寫第一步需求分析時(shí)，本以為是問題的簡(jiǎn)單描述，所以寫的比較簡(jiǎn)單，但是讓老師驗(yàn)收沒有通過，經(jīng)過進(jìn)一步改進(jìn)，將問題詳細(xì)化了，并正確而準(zhǔn)確的描述了校園導(dǎo)游的輸入輸出問題，順利通過第一步的驗(yàn)收。概要設(shè)計(jì)還是比較簡(jiǎn)單的，畢竟還沒有到算法的描述部分，這一過程很簡(jiǎn)單的就通過了，但是自己感覺對(duì)主界面的設(shè)計(jì)不是很滿意，然后幾經(jīng)思索，設(shè)計(jì)出了自己較為滿意的界面。當(dāng)前兩步完成后心里便有壓力了，因?yàn)樗惴枋鰧?duì)我來說真的有點(diǎn)難。我多次查看書籍并上網(wǎng)查詢相關(guān)資料，終于把詳細(xì)設(shè)計(jì)部分做好了。在調(diào)試程序時(shí)有一個(gè)很棘手的問題，結(jié)構(gòu)體變量G出現(xiàn)了重復(fù)定義，最初在函數(shù)定義的文件中，后來把定義放到了函數(shù)聲明那個(gè)文件中才通過了2、 測(cè)試數(shù)據(jù)：當(dāng)輸入1時(shí)進(jìn)入一個(gè)選擇子菜單（輸入錯(cuò)誤時(shí)，保持原有狀態(tài)），正確輸入起點(diǎn)（2）（燈光籃球場(chǎng)）和終點(diǎn)（4）（實(shí)驗(yàn)樓），屏幕將打印出兩景點(diǎn)之間的最短路徑：燈光籃球場(chǎng)惠馨園實(shí)驗(yàn)樓，最短路徑為約430m。當(dāng)輸入的景點(diǎn)代號(hào)不在（0-9）之間時(shí)，程序提示重新輸入，直到輸入正確。測(cè)試數(shù)據(jù)：當(dāng)起點(diǎn)輸入10終點(diǎn)輸入12時(shí)，景點(diǎn)不存在，程序提示重新輸入；當(dāng)起點(diǎn)輸入0（教學(xué)主樓）終點(diǎn)輸入12時(shí)，終點(diǎn)景點(diǎn)不存在，程序提示重新輸入；當(dāng)起點(diǎn)輸入0（教學(xué)樓）終點(diǎn)輸入8（圖書館）時(shí)，景點(diǎn)都存在，屏幕打印出兩景點(diǎn)最短路徑：教學(xué)樓噴泉學(xué)術(shù)報(bào)告廳圖書館，最短路徑約為200m。當(dāng)輸入1時(shí)，則按景點(diǎn)編號(hào)查詢，當(dāng)輸入6（地球科學(xué)博物館）時(shí)，屏幕上打印出此景點(diǎn)信息：里面有著名的不尋?？铸埢?；當(dāng)輸入4（實(shí)驗(yàn)樓）時(shí)，屏幕上打印出此景點(diǎn)信息：各專業(yè)實(shí)驗(yàn)的重要場(chǎng)地；當(dāng)輸入12時(shí)，此景點(diǎn)不存在，屏幕上顯示：！沒*有*找*到！；當(dāng)輸入20時(shí)，此景點(diǎn)不存在，屏幕上顯示：！沒*有*找*到！。當(dāng)輸入2時(shí)，則按景點(diǎn)名稱查詢，當(dāng)輸入“圖書館”時(shí)，屏幕上打印出此景點(diǎn)信息：圖書館是莘莘學(xué)子學(xué)習(xí)的園地，里面有各科資料，每人可以任借五本書；當(dāng)輸入“計(jì)算機(jī)實(shí)驗(yàn)室”時(shí)，屏幕上打印出此景點(diǎn)信息：計(jì)算機(jī)專業(yè)實(shí)驗(yàn)實(shí)習(xí)場(chǎng)所；當(dāng)輸入“教學(xué)三號(hào)樓”時(shí)，此景點(diǎn)不存在，屏幕上顯示：！沒*有*找*到?。划?dāng)在選擇主菜單中輸入3時(shí)，則系統(tǒng)推薦旅游路徑：1）教學(xué)主樓足球場(chǎng)燈光籃球場(chǎng)惠馨園實(shí)驗(yàn)樓噴泉學(xué)術(shù)報(bào)告廳地球科學(xué)博物館計(jì)算機(jī)實(shí)驗(yàn)室圖書館出口2）教學(xué)主樓足球場(chǎng)燈光籃球場(chǎng)惠馨園實(shí)驗(yàn)樓噴泉學(xué)術(shù)報(bào)告廳圖書館計(jì)算機(jī)實(shí)驗(yàn)室地球科學(xué)博物館出口3）教學(xué)主樓地球科學(xué)博物館計(jì)算機(jī)實(shí)驗(yàn)室圖書館學(xué)術(shù)報(bào)告廳噴泉實(shí)驗(yàn)樓惠馨園燈光籃球場(chǎng)足球場(chǎng)出口在選擇主菜單輸入錯(cuò)誤時(shí)，程序不作反應(yīng)，當(dāng)輸入e時(shí)，則退出。本程序的時(shí)間復(fù)雜度主要發(fā)生在求最短路徑時(shí)，即算法里面的for循環(huán)語句，for循環(huán)語句三層嵌套，所以時(shí)間復(fù)雜度為n3。3、在圖的存儲(chǔ)時(shí)本程序采用的鄰接矩陣，也可以采用鄰接表；在求兩景點(diǎn)之間的最短路徑時(shí)本程序采用的迪杰斯特拉算法，也可以采用弗洛伊德算法。4、在本次課程設(shè)計(jì)中讓我進(jìn)一步熟悉了各種算法的使用，但感到自己在算法設(shè)計(jì)中還存在很大的不足，寫算法時(shí)無法脫離課本，更是需要老師、同學(xué)的幫助，甚至有的算法不得不從網(wǎng)上查詢，今后自己將更努力學(xué)習(xí)這門語言，多接觸解決各種問題的各種算法，這樣才能提高自己。6 致謝非常高興能和同學(xué)們一起在實(shí)驗(yàn)室做實(shí)驗(yàn)，感謝各位老師以及同學(xué)們對(duì)我的幫助，特別是老師循循善誘的教導(dǎo)和不拘一格的思路給予我無盡的啟迪；這次數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)的每個(gè)實(shí)驗(yàn)細(xì)節(jié)和每個(gè)數(shù)據(jù)，都離不開老師您的細(xì)心指導(dǎo)。在您們的幫助下讓我順利完成了這次課程設(shè)計(jì)。平時(shí)注重的理論知識(shí)多了些，造成我上機(jī)操作遇到了很多困難，但是老師和同學(xué)都很熱情的幫助我，在此我表示我誠摯的謝意。7 參考文獻(xiàn)1. 嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu)（語言版）M清華大學(xué)出版社 2008年11月2. 嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu)題集（語言版）M清華大學(xué)出版社 2008年11月3. 何欽銘數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)M浙江大學(xué)出版社 2007年8月18 源程序/daoyouzixunxitong70321.cpp: implementation of the daoyouzixunxitong70321 class.#include "StdAfx70321.h"#include "daoyouzixunxitong70321.h"int x11=0;int PNUMNUM;long int DNUM;MGraph G;daoyouzixunxitong70321:daoyouzixunxitong70321()void daoyouzixunxitong70321:main2()int v0,v1;char ck;CreateUDN70321(NUM,11); /景點(diǎn)個(gè)數(shù)加1 /調(diào)用CreateUNM()函數(shù)do ck=Menu70321();/調(diào)用Menu()switch(ck)case '1':system("cls");narrate70321();/調(diào)用narrate函數(shù)printf("nnttO(_)O 提示：輸入100退出此環(huán)節(jié)n");M:printf("ntt請(qǐng)選擇起點(diǎn)景點(diǎn)(09)："); scanf("%d",&v0); if(v0=100)break; printf("tt請(qǐng)選擇終點(diǎn)景點(diǎn)(09)："); /景點(diǎn)編號(hào) scanf("%d",&v1); if(v0>9|v1>9) printf("nttO(_)O 請(qǐng)重新輸入v0,v1:n"); goto M; ShortestPath70321(v0); /調(diào)用ShortestPath()函數(shù) output70321(v0,v1); /調(diào)用output()函數(shù) goto M; break;case '2':search70321();/調(diào)用search()函數(shù)break;case '3':system("cls");narrate70321();/調(diào)用 narrate()函數(shù)x0=1; /此處必須為x0=1 實(shí)際為x0=trueHaMiTonian70321(1); /調(diào)用哈密爾頓函數(shù) 遍歷應(yīng)該從第一個(gè)景點(diǎn)開始！如果想要修改，必須從HaMiTonian()和NextValue()內(nèi)部修改printf("nntttt請(qǐng)按Enter繼續(xù).n");getchar();getchar();break;while(ck!='e');void daoyouzixunxitong70321:CreateUDN70321(int v, int a)int i,j;G.vexnum=v; G.arcnum=a;for(i=0;i<G.vexnum;+i) G.vexi.number=i;G.vex0.sight="教學(xué)主樓"G.vex0.description="學(xué)校領(lǐng)導(dǎo)， * 辦公之地"G.vex1.sight="足球場(chǎng)"G.vex1.description="寬闊,非常適合運(yùn)動(dòng)"G.vex2.sight="燈光籃球場(chǎng)"G.vex2.description="籃球運(yùn)動(dòng)的最佳活動(dòng)場(chǎng)所"G.vex3.sight="惠馨園"G.vex3.description="石家莊經(jīng)濟(jì)學(xué)院惠馨園一、二樓是學(xué)生餐飲中心，三樓是教職工餐飲中心，四樓是綜合辦公之地，五樓是文藝文化活動(dòng)中心"G.vex4.sight="實(shí)驗(yàn)樓"G.vex4.description="各專業(yè)試驗(yàn)的重要場(chǎng)地"G.vex5.sight="計(jì)算機(jī)實(shí)驗(yàn)室"G.vex5.description="計(jì)算機(jī)專業(yè)的實(shí)驗(yàn)實(shí)習(xí)場(chǎng)所"G.vex6.sight="地球科學(xué)博物館"G.vex6.description="里面有著名的不尋?？铸埢?amp;quot;G.vex7.sight="學(xué)術(shù)報(bào)告廳"G.vex7.description="學(xué)術(shù)交流中心"G.vex8.sight="圖書館"G.vex8.description="圖書館是莘莘學(xué)子學(xué)習(xí)的園地，里面有各科資料，每人可以任借五本書"G.vex9.sight="噴泉"G.vex9.description="學(xué)校的盛大節(jié)日時(shí)就可以看見"for(i=0;i<G.vexnum;+i)for(j=0;j<G.vexnum;+j)G.arcsij.adj=Max;G.arcs01.adj=G.arcs10.adj=50;G.arcs09.adj=G.arcs90.adj=50;G.arcs12.adj=G.arcs21.adj=50;G.arcs23.adj=G.arcs32.adj=130;G.arcs34.adj=G.arcs43.adj=300;G.arcs05.adj=G.arcs50.adj=50;G.arcs25.adj=G.arcs52.adj=100;G.arcs06.adj=G.arcs60.adj=250;G.arcs67.adj=G.arcs76.adj=50;G.arcs49.adj=G.arcs94.adj=500;G.arcs56.adj=G.arcs65.adj=300;G.arcs58.adj=G.arcs85.adj=300;G.arcs78.adj=G.arcs87.adj=50;G.arcs79.adj=G.arcs97.adj=100;void daoyouzixunxitong70321:narrate70321()int i,k=0;printf("ntt*歡 迎 使 用 校 園 導(dǎo) 游 程 序*n");printf("ntt*石*家*莊*經(jīng)*濟(jì)*學(xué)*院*n");printf("ntt制作者： 信息工程學(xué)院 1 顏建學(xué) !歡迎您使用!n");printf("ntt_n");printf("ttttt 景點(diǎn)名稱ttn");printf("tt_n");for(i=0;i<NUM;i+)printf("tt 【%2d】%-15stt",i,G.vexi.sight);if(i%2=(NUM-1)%2)printf("n");/奇數(shù)編號(hào)景點(diǎn)在右邊，偶數(shù)編號(hào)景點(diǎn)在左邊k=k+1;printf("tt_n");void daoyouzixunxitong70321:ShortestPath70321(int num)int v,w,i,t; int finalNUM;int min;for(v=0;v<NUM;v+)finalv=0; Dv=G.arcsnumv.adj;for(w=0;w<NUM;w+)Pvw=0;if(Dv<20000) Pvnum=1;Pvv=1;Dnum=0; finalnum=1; for(i=0;i<NUM;+i) min=Max; for(w=0;w<NUM;+w)if(!finalw) if(Dw<min) v=w;min=Dw;finalv=1; for(w=0;w<NUM;+w) if(!finalw&&(min+G.arcsvw.adj)<Dw)Dw=min+G.arcsvw.adj;for(t=0;t<NUM;t+)Pwt=Pvt;Pww=1;void daoyouzixunxitong70321:output70321(int sight1, int sight2)int a,b,c,d,q=0;a=sight2; if(a!=sight1) printf("nttt從( %s )到( %s )的最短路徑是:nn",G.vexsight1.sight,G.vexsight2.sight);printf("ttt%s",G.vexsight1.sight); d=sight1; for(c=0;c<NUM;+c)gate:; Pasight1=0; for(b=0;b<NUM;b+) if(G.arcsdb.adj<20000&&Pab) printf("->%s",G.vexb.sight); q=q+1; Pab=0; d=b; if(q%10=0) printf("n"); goto gate; printf("t(最短距離為 %dm.)nt",Da); char daoyouzixunxitong70321:Menu70321()char c;int flag;doflag=1;system("cls");narrate70321(); /調(diào)用 narrate()函數(shù)printf("n");printf("tttn");printf("ttt 【1】查詢景點(diǎn)路徑 n");printf("ttt 【2】查詢景點(diǎn)信息 n");printf("ttt 【3】推薦參觀路線 n");printf("ttt 【e】退出 n");printf("tttn");printf("tttt請(qǐng)輸入您的選擇：");scanf("%c",&c);if(c='1'|c='2'|c='3'|c='e')flag=0;while(flag);return c;void daoyouzixunxitong70321:search70321()int num;int i;char c;char name20;char a4="100"dosystem("cls");c=SearchMenu70321(); /調(diào)用SearchMenu()函數(shù)switch (c)case '1': system("cls");narrate70321(); /調(diào)用 narrate()函數(shù)printf("ntttO(_)O提示：輸入100退出此環(huán)節(jié)n");N: printf("ntt請(qǐng)輸入您要查找的景點(diǎn)編號(hào)："); scanf("%d",&num); if(num!=100) for(i=0;i<NUM;i+) if(num=G.vexi.number) printf("ntt您要查找景點(diǎn)信息如下:"); printf("nnttt%-25sn",G.vexi.description); break; /if語句 /for語句 if(i=NUM) printf("nttt!沒*有*找*到!n"); /if語句 goto N; /if語句 break;case '2':system("cls");narrate70321(); /調(diào)用 narrate()函數(shù)printf("ntttO(_)O提示：輸入100退出此環(huán)節(jié)n");S:printf("ntt請(qǐng)輸入您要查找的景點(diǎn)名稱："); scanf("%s",name); if(!strcmp(name,a)break; for(i=0;i<NUM;i+) if(!strcmp(name,G.vexi.sight) printf("ntt您要查找景點(diǎn)信息如下:"); printf("nnttt%-25sn",G.vexi.description); break; /if語句 /for語句 if(i=NUM) printf("nttt!沒*有*找*到!n"); /if語句 goto S; break;/switch語句while(c!='e');/do while 語句char daoyouzixunxitong70321:SearchMenu70321()char c;int flag;doflag=1;system("cls");narrate70321(); /調(diào)用 narrate()函數(shù)printf("n");printf("tttn");printf("ttt 【1】按照景點(diǎn)編號(hào)查詢 n");printf("ttt 【2】按照景點(diǎn)名稱查詢 n");printf("ttt 【e】返回 n");printf("tttn");printf("tttt請(qǐng)輸入您的選擇：");scanf("%c",&c);if(c='1'|c='2'|c='e')flag=0;while(flag);return c;void daoyouzixunxitong70321:HaMiTonian70321(int m)if(m>10) return; L: NextValue70321(m);/調(diào)用NextValue()函數(shù) if(xm=0) return; if(m=9&&G.arcs0x10-1.adj!=20000)/景點(diǎn)個(gè)數(shù)減1 景點(diǎn)個(gè)數(shù)加1 display70321();/調(diào)用display()函數(shù) else HaMiTonian70321(m+1);/調(diào)用HaMiTonian()函數(shù) goto L; void daoyouzixunxitong70321:NextValue70321(int k)int j; l:xk=(xk+1)%11;/景點(diǎn)個(gè)數(shù)加1 if(xk=0) return; if(G.arcsxk-1-1xk-1.adj!=20000) for(j=0;j<k;j+) if(xj=xk) goto l; return; else goto l; void daoyouzixunxitong70321:display70321()int i=0;printf("nn");for(i=0;i<10;i+) / 景點(diǎn)個(gè)數(shù)printf("%s->",G.vexxi-1.sight);printf("校園出口");printf("n");/ 課程設(shè)計(jì).cpp : Defines the entry point for the console application./#include "StdAfx70321.h"#include "daoyouzixunxitong70321.h"#define Max 20000#define NUM 10 /景點(diǎn)個(gè)數(shù)int main(int argc, char* argv) daoyouzixunxitong70321 A; system("color 5f");/屬于stdio.hsystem("mode con: cols=100 lines=100");/屬于stdio.hA.main2();return 0;/ daoyouzixunxitong70321.h: interface for the daoyouzixunxitong70321 class.#if !defined(AFX_DAOYOUZIXUNXITONG70321_H_C0CBBABA_ED55_44AF_AEBF_FA64A9_INCLUDED_)#define AFX_DAOYOUZIXUNXITONG70321_H_C0CBBABA_ED55_44AF_AEBF_FA64A9_INCLUDED_#if _MSC_VER > 1000#pragma once#endif / _MSC_VER > 1000#include "stdio.h"#include "stdlib.h"#include "string.h"#define Max 20000#define NUM 10 typedef struct ArcCellint adj;ArcCell;typedef struct VertexTypeint number