數(shù)據(jù)結(jié)構(gòu)課程設計故宮導游(最短路徑)(共34頁)

《數(shù)據(jù)結(jié)構(gòu)課程設計故宮導游(最短路徑)(共34頁)》由會員分享，可在線閱讀，更多相關《數(shù)據(jù)結(jié)構(gòu)課程設計故宮導游(最短路徑)(共34頁)（34頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)學與計算機學院課程設計說明書課 程 名 稱: 數(shù)據(jù)結(jié)構(gòu)與算法課程設計 課 程 代 碼: 題 目: 故宮導游咨詢 年級/專業(yè)/班: 學 生 姓 名: 學 號: 開 始 時 間: 2011 年 12 月 9 日完 成 時 間: 2011 年 12 月 23 日課程設計成績：學習態(tài)度及平時成績（30）技術水平與實際能力（20）創(chuàng)新（5） 說明書（計算書、圖紙、分析報告）撰寫質(zhì)量（45）總 分（100）指導教師簽名： 年 月 日專心-專注-專業(yè)目錄摘 要隨著計算機的普及，涉及計算機相關的科目也越來越普遍，其中數(shù)據(jù)結(jié)構(gòu)是計算機專業(yè)重要的專業(yè)基礎課程與核心課程之一，為適應我國計

2、算機科學技術的發(fā)展和應用，學好數(shù)據(jù)結(jié)構(gòu)非常必要，然而要掌握數(shù)據(jù)結(jié)構(gòu)的知識非常難，所以對“數(shù)據(jù)結(jié)構(gòu)”的課程設計比不可少。本說明書是對“故宮導游咨詢”課程設計的說明。首先是對需求分析的簡要闡述，說明系統(tǒng)要完成的任務和相應的分析，并給出測試數(shù)據(jù)。其次是概要設計，說明所有抽象數(shù)據(jù)類型的定義、主程序的流程以及各程序模塊之間的層次關系，以及ADT描述。然后是詳細設計，描述實現(xiàn)概要設計中定義的基本功操作和所有數(shù)據(jù)類型，以及函數(shù)的功能及代碼實現(xiàn)。再次是對系統(tǒng)的調(diào)試分析說明，以及遇到的問題和解決問題的方法。然后是用戶使用說明書的闡述，然后是測試的數(shù)據(jù)和結(jié)果的分析，最后是對本次課程設計的結(jié)論。關鍵詞：計算機、課程

3、設計、數(shù)據(jù)結(jié)構(gòu) 引 言 數(shù)據(jù)結(jié)構(gòu)是計算機專業(yè)重要的專業(yè)基礎課程與核心課程之一，在計算機領域應用廣泛，計算機離不開數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)課程設計為了能使我們掌握所學習的知識并有應用到實際的設計中的能力，對于掌握這門課程的學習方法有極大的意義。本課程設計的題目為“故宮導游咨詢”，完成相應的錄入信息、查找、修改、刪除、計算功能等等。本課程設計采用的編程環(huán)境為Microsoft Visual Stdio 6.0。1、需求分析 游客游覽某一景點時，對景點都不熟悉。特別是對于象故宮這樣的大型景點，如果隨便參觀的話，可能會錯過一些景點，也可能走許多冤枉路。為了方便游客，需要一套軟件系統(tǒng)，能夠為游客提供：查詢景點

4、信息，給出到某個景點的最佳路線，給出到所有景點的最佳路線。為系統(tǒng)管理員提供以下功能：添加和撤銷景點，添加和撤銷旅游線路，修改景點信息。 1.1任務與分析 此系統(tǒng)要完成對故宮景點信息的儲存、修改、刪除、添加和查詢最短路線，因為涉及到最短路線問題，所以數(shù)據(jù)結(jié)構(gòu)優(yōu)先考慮采用圖的鄰接矩陣儲存結(jié)構(gòu)，景點和旅游線路可以構(gòu)成圖狀結(jié)構(gòu)，景點作為圖的頂點，旅游線路作為圖的邊，邊上的權值作為景點間的距離。此結(jié)構(gòu)便于完成任務的各種操作。1.2測試數(shù)據(jù) 圖1 測試數(shù)據(jù)2 概要設計 2.1 ADT描述 ADT Graph數(shù)據(jù)對象：D故宮景點和路徑數(shù)據(jù)關系：RVRVR=|v,wV，表示頂點v和頂點w之間的邊；基本操作：

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

6、void Creat()錄入景點和路徑的信息，并儲存。查詢景點模塊:void select()查找某景點的信息。修改模塊:void xiugai()修改某景點的信息。插入模塊:void insert()插入新的景點和路徑信息。刪除模塊:void delet()刪除景點和路徑信息。查詢到某景點最佳路徑:void shortpath1()：查詢到某景點的最短路徑。查詢到查詢到所有景點的最短路徑:void shortpath2()查詢到所有景點的最短路徑3詳細設計3.1結(jié)構(gòu)體定義景點的結(jié)構(gòu)體定義如下：struct ding string dingdian; string xinxi;3.2 初始化構(gòu)

7、造函數(shù)初始化變量：Graph:Graph() for(int i=0;iMAXVertices;i+) Verticesi.dingdian=0; for(i=0;iMAXVertices;i+) for(int j=0;jMAXVertices;j+)if(i=j)Edgeij=0;elseEdgeij=MAXweight;numE=0;numV=0;3.3 插入操作插入路徑和景點信息： void Graph:insert() int i,vi,vj,w,x,y; coutxy; cout輸入添加景點名稱:endl; for(i=0;iy;i+) coutnumV+i+1Verticesnu

8、mV+i.dingdian;cout VerticesnumV+i.xinxi;cout添加成功!endl; for(i=0;ix;i+) coutvivjw; Edgevi-1vj-1=w; Edgevj-1vi-1=w; cout添加成功!endl; numE=x+numE; numV=y+numV;3.4、錄入信息void Graph:Creat() int i,vi,vj,w; coutnumEnumV; cout輸入景點名稱:endl; for(i=0;inumV;i+) couti+1Verticesi.dingdian;coutVerticesi.xinxi; for(i=0;i

9、numE;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+) if(Verticesi.dingdian=a) coutc;Verticesi.xinxi=c;b+;cout修改成功!endl;if(b=0)cout不存在該景點！endl;3.6查詢操作void Graph:select() string a; int b=0; couta; for(int i=0;inumV;i+)if(Verti

10、cesi.dingdian=a)coutVerticesi.xinxiendl;b+;if(b=0)cout不存在該景點！endl;3.7刪除操作void Graph:delet() int x,y,z,k,v; coutkz; for(int j=0;jk;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=MAXweigh

11、t; Edgey-1x-1=MAXweight; cout撤銷成功!endl; numE-; else cout不存在該路線!endl; 3.8求到某一景點的路徑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+)if(Verticesi.dingdian=c)v1=i; for( i=0;inumV;i+) disti=Edgevi;si=0;if(i!=v&distiMAXweight)p

12、athi=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=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&i=v1&disti!=MAXweight) string c10; int j=0;

13、int k=i; cout從b到Verticesi.dingdian的; cout最佳路徑長度為:; coutdisti米 ; cout大約需要走disti/100分鐘 ; cout=1;n-) coutcn; if(n!=1) cout; coutendl; 3.9求到所有景點的路徑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

14、)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=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

15、 k=i; cout從b到Verticesi.dingdian的; cout最佳路徑長度為:; coutdisti米 ; cout大約需要走disti/100分鐘 ; cout=1;n-) coutcn; if(n!=1) cout; coutendl; 3.10求到所有景點的路徑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&distiMAXweig

16、ht) 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=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;

17、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* B、游客 *endl; cout* C、退出 *endl; cout* 請選擇(A、B、C)*en

18、dl; 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、錄入景點和路徑信息 *endl;cout* B、修改景點信息 *endl;cout* C、插入景點和路徑 *endl;cout* D、刪除景點和路徑 *endl; cout* E、退出 *endl;cout* 請選擇(A、B、C、D、E) *endl;cout*b; if(b=A) a.Creat(); system(pause); if(b=B) a.xiuga

19、i(); system(pause);if(b=C)a.insert(); system(pause);if(b=D)a.delet(); system(pause); if(b=E)break;elsecout密碼錯誤!endl;system(pause); if(c=B) char b; for(;) system(cls);cout*endl; cout* 歡迎登陸故宮導游系統(tǒng) *endl;cout*endl;cout* A、查詢信息 *endl;cout* B、查詢到景點的最佳路徑 *endl;cout* C、查詢到所有景點的最佳路徑 *endl; cout* D、退出 *endl;c

20、out* 請選擇(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)試過程中遇到輸出路徑算法有錯誤，當刪除一條路徑時時不能正確輸出相應路徑，然后對輸出路徑的條件進行改進，增加了條件，測試成功。 4.3算法時間復雜度錄入：時間復雜度為O(n);查詢景點信息: 時間復雜度為O

21、(n);修改景點信息: 時間復雜度為O(n);插入景點和路徑: 當插入的景點和路徑為x，y時，若x=y時間復雜度為O(x)反之為O(y);刪除景點和路徑: 當刪除的景點和路徑為x，y時，若x=y時間復雜度為O(x)反之為O(y);查詢到某景點最佳路徑；此算法為迪杰斯特拉算法時間復雜度為O(n*n);查詢到所有景點的最短路徑: 此算法為迪杰斯特拉算法時間復雜度為O(n*n);4.4經(jīng)驗和體會在本次課程設計中主要是對圖的數(shù)據(jù)結(jié)構(gòu)操作，所有剛開始對知識不是很熟悉操作起來有一定難度，容易在程序的關鍵地方但經(jīng)過翻閱教材能較好的解決問題。5用戶使用說明本系統(tǒng)是關于故宮的管理系統(tǒng)分為兩類用戶，管理員和游客，

22、由于管理員可以對數(shù)據(jù)進行修改，為了保護數(shù)據(jù)，所以管理員登陸需要密碼而游客不需要密碼，管理員有添加景點和路徑、刪除景點和路徑、修改景點信息權限，游客能查詢景點信息、查找到某一景點的最佳路徑和到所有景點的最佳路徑。6測試結(jié)果6.1錄入信息 圖3 錄入信息界面 圖4 錄入信息界面6.2查詢景點模塊 圖5 查詢景點信息界面6.3修改模塊 圖6 修改景點信息界面6.4插入模塊 圖7 添加景點信息界面6.5刪除模塊 圖8 刪除景點信息界面6.6查詢到某景點最佳路徑 圖9 查詢到某景點最佳路徑界面6.7查詢到所有景點的最短路徑。 圖10 查詢到所有景點最佳路徑界面結(jié) 論 本次課程設計“故宮導游咨詢”按照任務

23、書相應的要求成功的完成了任務，由于本課程設計涉及景點和路徑，采用圖的儲存結(jié)構(gòu)和算法比較方便處理數(shù)據(jù)的儲存、查詢、刪除等操作。但圖的操作比較難，比如求某景點到所有景點的最佳路徑問題，需要使用到迪杰斯特拉算法實現(xiàn)。 致 謝 在本次課程設計過程中，首先感謝輔導老師周立章，在數(shù)據(jù)結(jié)構(gòu)課堂上為課程設計需要的前期知識打下了基礎，在課程設計過程中抽出休息時間來做相應的課程設計指導。同時在這次課程設計中，也要感謝許多樂意同學對我不懂的地方的指導和耐心講解。參考文獻 1 嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu).清華大學出版社出版。 2 嚴蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)題集(C語言版) .清華大學出版社.2003年5月。3 楊秀金，數(shù)據(jù)結(jié)構(gòu)(C+版) .高等教育出版社.2009年4月。4 朱戰(zhàn)立.數(shù)據(jù)結(jié)構(gòu)(C+語言描述)（第二版本）.高等出版社出版.2004年4月。5 胡學鋼.數(shù)據(jù)結(jié)構(gòu)(C語言版) .高等教育出版社.2004年8月。6 楊金秀.數(shù)據(jù)結(jié)構(gòu)（C語言版）.西安電子科技大學出版社，2004年8月。