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

1、-. z- . - .可修編-數(shù)學(xué)與計(jì)算機(jī)學(xué)院課程設(shè)計(jì)說明書課 程 名 稱:數(shù)據(jù)構(gòu)造與算法課程設(shè)計(jì) 課 程 代 碼: 6014389 題 目:故宮導(dǎo)游咨詢年級/專業(yè)/班:學(xué) 生 姓 名:學(xué) 號:開 始 時(shí) 間:2011 年12月 9日完 成 時(shí) 間:2011年12月23日課程設(shè)計(jì)成績：學(xué)習(xí)態(tài)度及平時(shí)成績30技術(shù)水平與實(shí)際能力20創(chuàng)新5 說明書計(jì)算書、圖紙、分析報(bào)告撰寫質(zhì)量45總 分100指導(dǎo)教師簽名：年月日-. z目錄TOC o 1-2 h z uHYPERLINK l _Toc312350913引言 PAGEREF _Toc312350913 h - 4 -HYPERLINK l _Toc3

2、123509141、需求分析 PAGEREF _Toc312350914 h - 4 -HYPERLINK l _Toc3123509151.1任務(wù)與分析 PAGEREF _Toc312350915 h - 4 -HYPERLINK l _Toc3123509162 概要設(shè)計(jì) PAGEREF _Toc312350916 h - 1 -HYPERLINK l _Toc3123509172.1 ADT描述 PAGEREF _Toc312350917 h - 1 -HYPERLINK l _Toc3123509182.2程序模塊構(gòu)造 PAGEREF _Toc312350918 h - 2 -HYPE

3、RLINK l _Toc3123509192.3各功能模塊 PAGEREF _Toc312350919 h - 2 -HYPERLINK l _Toc3123509203詳細(xì)設(shè)計(jì) PAGEREF _Toc312350920 h - 3 -HYPERLINK l _Toc3123509213.1構(gòu)造體定義 PAGEREF _Toc312350921 h - 3 -HYPERLINK l _Toc3123509223.2 初始化 PAGEREF _Toc312350922 h - 3 -HYPERLINK l _Toc3123509233.3 插入操作 PAGEREF _Toc312350923

4、h - 4 -HYPERLINK l _Toc3123509243.4、錄入信息 PAGEREF _Toc312350924 h - 4 -HYPERLINK l _Toc3123509253.5修改操作 PAGEREF _Toc312350925 h - 5 -HYPERLINK l _Toc3123509263.6查詢操作 PAGEREF _Toc312350926 h - 6 -HYPERLINK l _Toc3123509273.7刪除操作 PAGEREF _Toc312350927 h - 6 -HYPERLINK l _Toc3123509283.8求到*一景點(diǎn)的路徑 PAGERE

5、F _Toc312350928 h - 8 -HYPERLINK l _Toc3123509293.9求到所有景點(diǎn)的路徑 PAGEREF _Toc312350929 h - 10 -HYPERLINK l _Toc3123509303.10求到所有景點(diǎn)的路徑 PAGEREF _Toc312350930 h - 12 -HYPERLINK l _Toc3123509313.11主函數(shù) PAGEREF _Toc312350931 h - 15 -HYPERLINK l _Toc3123509324 調(diào)試分析 PAGEREF _Toc312350932 h - 18 -HYPERLINK l _To

6、c3123509334.1測試數(shù)據(jù) PAGEREF _Toc312350933 h - 19 -HYPERLINK l _Toc3123509344.2調(diào)試問題 PAGEREF _Toc312350934 h - 19 -HYPERLINK l _Toc3123509354.3算法時(shí)間復(fù)雜度 PAGEREF _Toc312350935 h - 19 -HYPERLINK l _Toc3123509364.4經(jīng)歷和體會 PAGEREF _Toc312350936 h - 19 -HYPERLINK l _Toc3123509375用戶使用說明 PAGEREF _Toc312350937 h -

7、19 -HYPERLINK l _Toc3123509386測試結(jié)果 PAGEREF _Toc312350938 h - 19 -HYPERLINK l _Toc3123509396.1錄入信息 PAGEREF _Toc312350939 h - 19 -HYPERLINK l _Toc3123509406.2查詢景點(diǎn)模塊 PAGEREF _Toc312350940 h - 21 -HYPERLINK l _Toc3123509416.3修改模塊 PAGEREF _Toc312350941 h - 22 -HYPERLINK l _Toc3123509426.4插入模塊 PAGEREF _To

8、c312350942 h - 23 -HYPERLINK l _Toc3123509436.5刪除模塊 PAGEREF _Toc312350943 h - 24 -HYPERLINK l _Toc3123509446.6查詢到*景點(diǎn)最正確路徑 PAGEREF _Toc312350944 h - 25 -HYPERLINK l _Toc3123509456.7查詢到所有景點(diǎn)的最短路徑。 PAGEREF _Toc312350945 h - 26 -HYPERLINK l _Toc312350946結(jié)論 PAGEREF _Toc312350946 h - 28 -HYPERLINK l _Toc31

9、2350947致 PAGEREF _Toc312350947 h - 29 -HYPERLINK l _Toc312350948參考文獻(xiàn) PAGEREF _Toc312350948 h - 30 -摘 要隨著計(jì)算機(jī)的普及，涉及計(jì)算機(jī)相關(guān)的科目也越來越普遍，其中數(shù)據(jù)構(gòu)造是計(jì)算機(jī)專業(yè)重要的專業(yè)根底課程與核心課程之一，為適應(yīng)我國計(jì)算機(jī)科學(xué)技術(shù)的開展和應(yīng)用，學(xué)好數(shù)據(jù)構(gòu)造非常必要，然而要掌握數(shù)據(jù)構(gòu)造的知識非常難，所以對數(shù)據(jù)構(gòu)造的課程設(shè)計(jì)比不可少。本說明書是對故宮導(dǎo)游咨詢課程設(shè)計(jì)的說明。首先是對需求分析的簡要闡述，說明系統(tǒng)要完成的任務(wù)和相應(yīng)的分析，并給出測試數(shù)據(jù)。其次是概要設(shè)計(jì)，說明所有抽象數(shù)據(jù)類型的定義

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

11、錄入信息、查找、修改、刪除、計(jì)算功能等等。本課程設(shè)計(jì)采用的編程環(huán)境為Microsoft Visual Stdio 6.0。1、需求分析游客游覽*一景點(diǎn)時(shí)，對景點(diǎn)都不熟悉。特別是對于象故宮這樣的大型景點(diǎn)，如果隨便參觀的話，可能會錯(cuò)過一些景點(diǎn)，也可能走許多冤枉路。為了方便游客，需要一套軟件系統(tǒng)，能夠?yàn)橛慰吞峁翰樵兙包c(diǎn)信息，給出到*個(gè)景點(diǎn)的最正確路線，給出到所有景點(diǎn)的最正確路線。為系統(tǒng)管理員提供以下功能：添加和撤銷景點(diǎn)，添加和撤銷旅游線路，修改景點(diǎn)信息。1.1任務(wù)與分析此系統(tǒng)要完成對故宮景點(diǎn)信息的儲存、修改、刪除、添加和查詢最短路線，因?yàn)樯婕暗阶疃搪肪€問題，所以數(shù)據(jù)構(gòu)造優(yōu)先考慮采用圖的鄰接矩陣儲存

12、構(gòu)造，景點(diǎn)和旅游線路可以構(gòu)成圖狀構(gòu)造，景點(diǎn)作為圖的頂點(diǎn)，旅游線路作為圖的邊，邊上的權(quán)值作為景點(diǎn)間的距離。此構(gòu)造便于完成任務(wù)的各種操作。1.2測試數(shù)據(jù) 圖1 測試數(shù)據(jù)2 概要設(shè)計(jì)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 *iugai();/修改*景點(diǎn)的信息。void insert();/插入新的景點(diǎn)和路徑信息。void delet();/刪除景點(diǎn)和路徑信息。void shortpath1();/查

13、詢到*景點(diǎn)的最短路徑。void shortpath2();/查詢到所有景點(diǎn)的最短路徑。Void main();/主函數(shù)。2.2程序模塊構(gòu)造 圖2 程序模塊構(gòu)造構(gòu)造體定義景點(diǎn)的構(gòu)造體定義如下：struct dingstring dingdian;string *in*i;2.3各功能模塊錄入模塊:void Creat()錄入景點(diǎn)和路徑的信息，并儲存。查詢景點(diǎn)模塊:void select()查找*景點(diǎn)的信息。修改模塊:void *iugai()修改*景點(diǎn)的信息。插入模塊:void insert()插入新的景點(diǎn)和路徑信息。刪除模塊:void delet()刪除景點(diǎn)和路徑信息。查詢到*景點(diǎn)最正確路徑:

14、void shortpath1()：查詢到*景點(diǎn)的最短路徑。查詢到查詢到所有景點(diǎn)的最短路徑:void shortpath2()查詢到所有景點(diǎn)的最短路徑3詳細(xì)設(shè)計(jì)3.1構(gòu)造體定義景點(diǎn)的構(gòu)造體定義如下：struct dingstring dingdian;string *in*i;3.2 初始化構(gòu)造函數(shù)初始化變量：Graph:Graph()for(int i=0;iMA*Vertices;i+)Verticesi.dingdian=0;for(i=0;iMA*Vertices;i+)for(int j=0;jMA*Vertices;j+)if(i=j)Edgeij=0;elseEdgeij=MA*

15、weight;numE=0;numV=0;3.3 插入操作插入路徑和景點(diǎn)信息：void Graph:insert()int i,vi,vj,w,*,y;cout*y;cout輸入添加景點(diǎn)名稱:endl;for(i=0;iy;i+)coutnumV+i+1VerticesnumV+i.dingdian;cout VerticesnumV+i.*in*i;cout添加成功!endl;for(i=0;i*;i+)coutvivjw;Edgevi-1vj-1=w;Edgevj-1vi-1=w;cout添加成功!endl;numE=*+numE;numV=y+numV;3.4、錄入信息void Grap

16、h:Creat()int i,vi,vj,w;coutnumEnumV;cout輸入景點(diǎn)名稱:endl;for(i=0;inumV;i+)couti+1Verticesi.dingdian;coutVerticesi.*in*i;for(i=0;inumE;i+)coutvivjw;Edgevi-1vj-1=w;Edgevj-1vi-1=w;3.5修改操作void Graph:*iugai()string a,c;int b=0;couta;for(int i=0;inumV;i+)if(Verticesi.dingdian=a)coutc;Verticesi.*in*i=c;b+;cout修

17、改成功!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.*in*iendl;b+;if(b=0)cout不存在該景點(diǎn)！endl;3.7刪除操作void Graph:delet()int *,y,z,k,v;coutkz;for(int j=0;jk;j+)coutv; for(int i=0;inumV;i+) if(i!=v-1) Edgev-1i=MA*weight;E

18、dgeiv-1=MA*weight; cout撤銷成功!endl;for(int i=0;iz;i+)cout*y;if(Edge*-1y-1!=MA*weight)Edge*-1y-1=MA*weight;Edgey-1*-1=MA*weight;cout撤銷成功!endl;numE-;elsecout不存在該路線!endl;3.8求到*一景點(diǎn)的路徑void Graph:shortpath1()int v,v1;string b,c;coutb;coutc;for(int i=0;inumV;i+)if(Verticesi.dingdian=b)v=i;for( i=0;inumV;i+)i

19、f(Verticesi.dingdian=c)v1=i;for( i=0;inumV;i+)disti=Edgevi;si=0;if(i!=v&distiMA*weight)pathi=v;elsepathi=-1;sv=1;distv=0;for(i=0;inumV;i+)float min=MA*weight;int u=v;for(int j=0;jnumV;j+)if(!sj&distjmin)u=j;min=distj;su=1;for(int w=0;wnumV;w+)if(!sw&EdgeuwMA*weight&distu+Edgeuwdistw)distw=distu+Edge

20、uw;pathw=u; for( i=0;inumV;i+) if(i!=v&i=v1&disti!=MA*weight) 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.9求到所有景點(diǎn)的路徑void Graph:shortpath2()int v;string b;coutb;for(int i=0;inumV;i+)if(Verti

21、cesi.dingdian=b)v=i;for( i=0;inumV;i+)disti=Edgevi;si=0;if(i!=v&distiMA*weight)pathi=v;elsepathi=-1;sv=1;distv=0;for(i=0;inumV;i+)float min=MA*weight;int u=v;for(int j=0;jnumV;j+)if(!sj&distjmin)u=j;min=distj;su=1;for(int w=0;wnumV;w+)if(!sw&EdgeuwMA*weight&distu+Edgeuwdistw)distw=distu+Edgeuw;pathw

22、=u; for( i=0;inumV;i+) if(i!=v&disti!=MA*weight) 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.10求到所有景點(diǎn)的路徑void Graph:shortpath2()int v;string b; coutb;for(int i=0;inumV;i+)if(Verticesi.dingdi

23、an=b)v=i;for( i=0;inumV;i+)disti=Edgevi;si=0;if(i!=v&distiMA*weight)pathi=v;elsepathi=-1;sv=1;distv=0;for(i=0;inumV;i+)float min=MA*weight;int u=v;for(int j=0;jnumV;j+)if(!sj&distjmin)u=j;min=distj;su=1;for(int w=0;wnumV;w+)if(!sw&EdgeuwMA*weight&distu+Edgeuwdistw)distw=distu+Edgeuw;pathw=u; for( i=

24、0;inumV;i+) if(i!=v&disti!=MA*weight) 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.11主函數(shù)void main()Graph a;for(;)char c;system(cls);cout*endl;cout* 登錄! *endl;cout*endl;cout* A、管理員 *endl;cout

25、* 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)和路徑信息 *endl;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

26、=A) a.Creat(); system(pause); if(b=B) a.*iugai(); system(pause);if(b=C)a.insert(); system(pause);if(b=D)a.delet(); system(pause); if(b=E)break;elsecout密碼錯(cuò)誤!endl;system(pause);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

27、* 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();system(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)試過程中遇到輸出路徑算法有錯(cuò)誤，當(dāng)刪除一條路徑時(shí)時(shí)不能正確輸出相應(yīng)路徑，然后對輸出路徑的條件進(jìn)展改良，增加了條件，測試成功。4.3算法時(shí)間復(fù)雜度錄入：時(shí)間復(fù)雜度為O(n);查詢景點(diǎn)信息: 時(shí)間復(fù)雜度為O(n);修改景點(diǎn)信息: 時(shí)間復(fù)雜度為O(n);插入景點(diǎn)和路徑: 當(dāng)插入的景點(diǎn)和路徑為*，y時(shí)，假設(shè)*=y時(shí)間復(fù)雜度為O(*)反之為O(y);刪除景點(diǎn)和路徑: 當(dāng)刪除的景點(diǎn)和路徑為*，y時(shí)，假設(shè)*=