數(shù)據(jù)結(jié)構(gòu)課程設(shè)計故宮導(dǎo)游咨詢(最短路徑)

1、 故宮導(dǎo)游咨詢數(shù)學(xué)與計算機(jī)學(xué)院課程設(shè)計說明書課 程 名 稱: 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計 課 程 代 碼: 6014389 題 目: 故宮導(dǎo)游咨詢 年級/專業(yè)/班: 學(xué) 生 姓 名: 學(xué) 號: 開 始 時 間: 2011 年 12 月 9 日完 成 時 間: 2011 年 12 月 23 日課程設(shè)計成績：學(xué)習(xí)態(tài)度及平時成績（30）技術(shù)水平與實際能力（20）創(chuàng)新（5） 說明書（計算書、圖紙、分析報告）撰寫質(zhì)量（45）總 分（100）指導(dǎo)教師簽名： 年 月 日目 錄引 言- 4 -1、需求分析- 4 -1.1任務(wù)與分析- 4 -2 概要設(shè)計- 1 -2.1 adt描述- 1 -2.2程序模塊結(jié)構(gòu)- 2

2、 -2.3各功能模塊- 2 -3詳細(xì)設(shè)計- 3 -3.1結(jié)構(gòu)體定義- 3 -3.2 初始化- 3 -3.3 插入操作- 4 -3.4、錄入信息- 4 -3.5修改操作- 5 -3.6查詢操作- 6 -3.7刪除操作- 6 -3.8求到某一景點(diǎn)的路徑- 8 -3.9求到所有景點(diǎn)的路徑- 10 -3.10求到所有景點(diǎn)的路徑- 12 -3.11主函數(shù)- 15 -4 調(diào)試分析- 18 -4.1測試數(shù)據(jù)- 19 -4.2調(diào)試問題- 19 -4.3算法時間復(fù)雜度- 19 -4.4經(jīng)驗和體會- 19 -5用戶使用說明- 19 -6測試結(jié)果- 19 -6.1錄入信息- 19 -6.2查詢景點(diǎn)模塊- 21 -6

3、.3修改模塊- 22 -6.4插入模塊- 23 -6.5刪除模塊- 24 -6.6查詢到某景點(diǎn)最佳路徑- 25 -6.7查詢到所有景點(diǎn)的最短路徑。- 26 -結(jié) 論- 28 -致 謝- 29 -參考文獻(xiàn)- 30 -摘 要隨著計算機(jī)的普及，涉及計算機(jī)相關(guān)的科目也越來越普遍，其中數(shù)據(jù)結(jié)構(gòu)是計算機(jī)專業(yè)重要的專業(yè)基礎(chǔ)課程與核心課程之一，為適應(yīng)我國計算機(jī)科學(xué)技術(shù)的發(fā)展和應(yīng)用，學(xué)好數(shù)據(jù)結(jié)構(gòu)非常必要，然而要掌握數(shù)據(jù)結(jié)構(gòu)的知識非常難，所以對“數(shù)據(jù)結(jié)構(gòu)”的課程設(shè)計比不可少。本說明書是對“故宮導(dǎo)游咨詢”課程設(shè)計的說明。首先是對需求分析的簡要闡述，說明系統(tǒng)要完成的任務(wù)和相應(yīng)的分析，并給出測試數(shù)據(jù)。其次是概要設(shè)計，說

4、明所有抽象數(shù)據(jù)類型的定義、主程序的流程以及各程序模塊之間的層次關(guān)系，以及adt描述。然后是詳細(xì)設(shè)計，描述實現(xiàn)概要設(shè)計中定義的基本功操作和所有數(shù)據(jù)類型，以及函數(shù)的功能及代碼實現(xiàn)。再次是對系統(tǒng)的調(diào)試分析說明，以及遇到的問題和解決問題的方法。然后是用戶使用說明書的闡述，然后是測試的數(shù)據(jù)和結(jié)果的分析，最后是對本次課程設(shè)計的結(jié)論。關(guān)鍵詞：計算機(jī)、課程設(shè)計、數(shù)據(jù)結(jié)構(gòu) 引 言 數(shù)據(jù)結(jié)構(gòu)是計算機(jī)專業(yè)重要的專業(yè)基礎(chǔ)課程與核心課程之一，在計算機(jī)領(lǐng)域應(yīng)用廣泛，計算機(jī)離不開數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計為了能使我們掌握所學(xué)習(xí)的知識并有應(yīng)用到實際的設(shè)計中的能力，對于掌握這門課程的學(xué)習(xí)方法有極大的意義。本課程設(shè)計的題目為“故

5、宮導(dǎo)游咨詢”，完成相應(yīng)的錄入信息、查找、修改、刪除、計算功能等等。本課程設(shè)計采用的編程環(huán)境為microsoft visual stdio 6.0。1、需求分析 游客游覽某一景點(diǎn)時，對景點(diǎn)都不熟悉。特別是對于象故宮這樣的大型景點(diǎn)，如果隨便參觀的話，可能會錯過一些景點(diǎn)，也可能走許多冤枉路。為了方便游客，需要一套軟件系統(tǒng)，能夠為游客提供：查詢景點(diǎn)信息，給出到某個景點(diǎn)的最佳路線，給出到所有景點(diǎn)的最佳路線。為系統(tǒng)管理員提供以下功能：添加和撤銷景點(diǎn)，添加和撤銷旅游線路，修改景點(diǎn)信息。 1.1任務(wù)與分析 此系統(tǒng)要完成對故宮景點(diǎn)信息的儲存、修改、刪除、添加和查詢最短路線，因為涉及到最短路線問題，所以數(shù)據(jù)結(jié)構(gòu)優(yōu)

6、先考慮采用圖的鄰接矩陣儲存結(jié)構(gòu)，景點(diǎn)和旅游線路可以構(gòu)成圖狀結(jié)構(gòu)，景點(diǎn)作為圖的頂點(diǎn)，旅游線路作為圖的邊，邊上的權(quán)值作為景點(diǎn)間的距離。此結(jié)構(gòu)便于完成任務(wù)的各種操作。1.2測試數(shù)據(jù) 圖1 測試數(shù)據(jù)2 概要設(shè)計 2.1 adt描述 adt graph數(shù)據(jù)對象：d故宮景點(diǎn)和路徑數(shù)據(jù)關(guān)系：rvrvr=|v,wv，表示頂點(diǎn)v和頂點(diǎn)w之間的邊；基本操作： void creat();/錄入景點(diǎn)和路徑的信息。void select();/查找某景點(diǎn)的信息。void xiugai();/修改某景點(diǎn)的信息。void insert();/插入新的景點(diǎn)和路徑信息。void delet();/刪除景點(diǎn)和路徑信息。void

7、shortpath1();/查詢到某景點(diǎn)的最短路徑。void shortpath2();/查詢到所有景點(diǎn)的最短路徑。void main();/主函數(shù)。2.2程序模塊結(jié)構(gòu) 圖2 程序模塊結(jié)構(gòu)2.2.1 結(jié)構(gòu)體定義景點(diǎn)的結(jié)構(gòu)體定義如下：struct ding string dingdian; string xinxi;2.3各功能模塊錄入模塊:void creat()錄入景點(diǎn)和路徑的信息，并儲存。查詢景點(diǎn)模塊:void select()查找某景點(diǎn)的信息。修改模塊:void xiugai()修改某景點(diǎn)的信息。插入模塊:void insert()插入新的景點(diǎn)和路徑信息。刪除模塊:void delet(

8、)刪除景點(diǎn)和路徑信息。查詢到某景點(diǎn)最佳路徑:void shortpath1()：查詢到某景點(diǎn)的最短路徑。查詢到查詢到所有景點(diǎn)的最短路徑:void shortpath2()查詢到所有景點(diǎn)的最短路徑3詳細(xì)設(shè)計3.1結(jié)構(gòu)體定義景點(diǎn)的結(jié)構(gòu)體定義如下：struct ding string dingdian; string xinxi;3.2 初始化構(gòu)造函數(shù)初始化變量：graph:graph() for(int i=0;imaxvertices;i+) verticesi.dingdian=0; for(i=0;imaxvertices;i+) for(int j=0;jmaxvertices;j+)if

9、(i=j)edgeij=0;elseedgeij=maxweight;nume=0;numv=0;3.3 插入操作插入路徑和景點(diǎn)信息： void graph:insert() int i,vi,vj,w,x,y; coutxy; cout輸入添加景點(diǎn)名稱:endl; for(i=0;iy;i+) coutnumv+i+1verticesnumv+i.dingdian;cout verticesnumv+i.xinxi;cout添加成功!endl; for(i=0;ix;i+) coutvivjw; edgevi-1vj-1=w; edgevj-1vi-1=w; cout添加成功!endl; n

10、ume=x+nume; numv=y+numv;3.4、錄入信息void graph:creat() int i,vi,vj,w; coutnumenumv; cout輸入景點(diǎn)名稱:endl; for(i=0;inumv;i+) couti+1verticesi.dingdian;coutverticesi.xinxi; for(i=0;inume;i+) coutvivjw; edgevi-1vj-1=w; edgevj-1vi-1=w; 3.5修改操作void graph:xiugai() string a,c; int b=0; couta; for(int i=0;inumv;i+)

11、if(verticesi.dingdian=a) coutc;verticesi.xinxi=c;b+;cout修改成功!endl;if(b=0)cout不存在該景點(diǎn)！endl;3.6查詢操作void graph:select() string a; int b=0; couta; for(int i=0;inumv;i+)if(verticesi.dingdian=a)coutverticesi.xinxiendl;b+;if(b=0)cout不存在該景點(diǎn)！endl;3.7刪除操作void graph:delet() int x,y,z,k,v; coutkz; for(int j=0;jk

12、;j+) coutv; for(int i=0;inumv;i+) if(i!=v-1) edgev-1i=maxweight;edgeiv-1=maxweight; cout撤銷成功!endl; for(int i=0;iz;i+) coutxy; if(edgex-1y-1!=maxweight) edgex-1y-1=maxweight; edgey-1x-1=maxweight; cout撤銷成功!endl; nume-; else cout不存在該路線!endl; 3.8求到某一景點(diǎn)的路徑void graph:shortpath1() int v,v1; string b,c; co

13、utb; coutc; for(int i=0;inumv;i+)if(verticesi.dingdian=b)v=i; for( i=0;inumv;i+)if(verticesi.dingdian=c)v1=i; for( i=0;inumv;i+) disti=edgevi;si=0;if(i!=v&distimaxweight)pathi=v;elsepathi=-1; sv=1; distv=0; for(i=0;inumv;i+) float min=maxweight;int u=v;for(int j=0;jnumv;j+)if(!sj&distjmin)u=j;min=di

14、stj;su=1;for(int w=0;wnumv;w+) if(!sw&edgeuwmaxweight&distu+edgeuwdistw)distw=distu+edgeuw;pathw=u; for( i=0;inumv;i+) if(i!=v&i=v1&disti!=maxweight) string c10; int j=0; int k=i; cout從b到verticesi.dingdian的; cout最佳路徑長度為:; coutdisti米 ; cout大約需要走disti/100分鐘 ; cout=1;n-) coutcn; if(n!=1) cout; coutendl

15、; 3.9求到所有景點(diǎn)的路徑void graph:shortpath2() int v; string b; coutb; for(int i=0;inumv;i+)if(verticesi.dingdian=b)v=i; for( i=0;inumv;i+) disti=edgevi;si=0;if(i!=v&distimaxweight)pathi=v;elsepathi=-1; sv=1; distv=0; for(i=0;inumv;i+) float min=maxweight;int u=v;for(int j=0;jnumv;j+)if(!sj&distjmin)u=j;min=

16、distj;su=1;for(int w=0;wnumv;w+) if(!sw&edgeuwmaxweight&distu+edgeuwdistw)distw=distu+edgeuw;pathw=u; for( i=0;inumv;i+) if(i!=v&disti!=maxweight) string c10; int j=0; int k=i; cout從b到verticesi.dingdian的; cout最佳路徑長度為:; coutdisti米 ; cout大約需要走disti/100分鐘 ; cout=1;n-) coutcn; if(n!=1) cout; coutendl; 3

17、.10求到所有景點(diǎn)的路徑void graph:shortpath2() int v; string b; coutb; for(int i=0;inumv;i+) if(verticesi.dingdian=b) v=i; for( i=0;inumv;i+) disti=edgevi; si=0; if(i!=v&distimaxweight) pathi=v; elsepathi=-1; sv=1; distv=0; for(i=0;inumv;i+) float min=maxweight;int u=v;for(int j=0;jnumv;j+)if(!sj&distjmin)u=j;

18、min=distj;su=1;for(int w=0;wnumv;w+)if(!sw&edgeuwmaxweight&distu+edgeuwdistw)distw=distu+edgeuw;pathw=u; for( i=0;inumv;i+) if(i!=v&disti!=maxweight) string c10; int j=0; int k=i; cout從b到verticesi.dingdian的; cout最佳路徑長度為:; coutdisti米 ; cout大約需要走disti/100分鐘 ; cout=1;n-) coutcn; if(n!=1) cout; coutendl

19、; 3.11主函數(shù)void main() graph a; for(;) char c; system(cls); cout*endl; cout* 登錄! *endl; cout*endl; cout* a、管理員 *endl; cout* b、游客 *endl; cout* c、退出 *endl; cout* 請選擇(a、b、c)*endl; cout*c; if(c=a) int d;char b;coutd;if(d=123)for(;)system(cls);cout*endl;cout* 歡迎登陸故宮管理系統(tǒng) *endl;cout*endl;cout* a、錄入景點(diǎn)和路徑信息 *e

20、ndl;cout* b、修改景點(diǎn)信息 *endl;cout* c、插入景點(diǎn)和路徑 *endl;cout* d、刪除景點(diǎn)和路徑 *endl; cout* e、退出 *endl;cout* 請選擇(a、b、c、d、e) *endl;cout*b; if(b=a) a.creat(); system(pause); if(b=b) a.xiugai(); system(pause);if(b=c)a.insert(); system(pause);if(b=d)a.delet(); system(pause); if(b=e)break;elsecout密碼錯誤!endl;system(pause)

21、; if(c=b) char b; for(;) system(cls);cout*endl; cout* 歡迎登陸故宮導(dǎo)游系統(tǒng) *endl;cout*endl;cout* a、查詢信息 *endl;cout* b、查詢到景點(diǎn)的最佳路徑 *endl;cout* c、查詢到所有景點(diǎn)的最佳路徑 *endl; cout* d、退出 *endl;cout* 請選擇(a、b、c、d) *endl;cout*b;if(b=a) a.select(); system(pause); if(b=b)a.shortpath1();system(pause);if(b=c)a.shortpath2();syste

22、m(pause);if(b=d)break; if(c=c) break; 4 調(diào)試分析4.1測試數(shù)據(jù)測試數(shù)據(jù)見圖1.4.2調(diào)試問題 在調(diào)試過程中遇到輸出路徑算法有錯誤，當(dāng)刪除一條路徑時時不能正確輸出相應(yīng)路徑，然后對輸出路徑的條件進(jìn)行改進(jìn)，增加了條件，測試成功。 4.3算法時間復(fù)雜度錄入：時間復(fù)雜度為o(n);查詢景點(diǎn)信息: 時間復(fù)雜度為o(n);修改景點(diǎn)信息: 時間復(fù)雜度為o(n);插入景點(diǎn)和路徑: 當(dāng)插入的景點(diǎn)和路徑為x，y時，若x=y時間復(fù)雜度為o(x)反之為o(y);刪除景點(diǎn)和路徑: 當(dāng)刪除的景點(diǎn)和路徑為x，y時，若x=y時間復(fù)雜度為o(x)反之為o(y);查詢到某景點(diǎn)最佳路徑；此算法為迪杰斯特拉算法時間復(fù)雜度為o(n*n);查詢到所有景點(diǎn)的最短路徑: 此算法為迪杰斯特拉算法時間復(fù)雜度為o(n*n);4.4經(jīng)驗和體會在本次課程設(shè)計中主要是對圖的數(shù)據(jù)結(jié)構(gòu)操作，所有剛開始對知識不是很熟悉操作起來有一定難度，容易在程序的關(guān)鍵地方但經(jīng)過翻閱教材能較好的解決問題。5用戶使用說明本系統(tǒng)是關(guān)于故宮的管理系統(tǒng)分為兩類用戶，管理