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

精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)學(xué)與計(jì)算機(jī)學(xué)院課程設(shè)計(jì)說明書課 程 名 稱: 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì) 課 程 代 碼: 題 目: 故宮導(dǎo)游咨詢 年級(jí)/專業(yè)/班: 學(xué) 生 姓 名: 學(xué) 號(hào): 開 始 時(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)教師簽名： 年 月 日專心-專注-專業(yè)目錄摘 要隨著計(jì)算機(jī)的普及，涉及計(jì)算機(jī)相關(guān)的科目也越來越普遍，其中數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)重要的專業(yè)基礎(chǔ)課程與核心課程之一，為適應(yīng)我國計(jì)算機(jī)科學(xué)技術(shù)的發(fā)展和應(yīng)用，學(xué)好數(shù)據(jù)結(jié)構(gòu)非常必要，然而要掌握數(shù)據(jù)結(jié)構(gòu)的知識(shí)非常難，所以對(duì)“數(shù)據(jù)結(jié)構(gòu)”的課程設(shè)計(jì)比不可少。本說明書是對(duì)“故宮導(dǎo)游咨詢”課程設(shè)計(jì)的說明。首先是對(duì)需求分析的簡(jiǎn)要闡述，說明系統(tǒng)要完成的任務(wù)和相應(yīng)的分析，并給出測(cè)試數(shù)據(jù)。其次是概要設(shè)計(jì)，說明所有抽象數(shù)據(jù)類型的定義、主程序的流程以及各程序模塊之間的層次關(guān)系，以及ADT描述。然后是詳細(xì)設(shè)計(jì)，描述實(shí)現(xiàn)概要設(shè)計(jì)中定義的基本功操作和所有數(shù)據(jù)類型，以及函數(shù)的功能及代碼實(shí)現(xiàn)。再次是對(duì)系統(tǒng)的調(diào)試分析說明，以及遇到的問題和解決問題的方法。然后是用戶使用說明書的闡述，然后是測(cè)試的數(shù)據(jù)和結(jié)果的分析，最后是對(duì)本次課程設(shè)計(jì)的結(jié)論。關(guān)鍵詞：計(jì)算機(jī)、課程設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu) 引 言 數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)重要的專業(yè)基礎(chǔ)課程與核心課程之一，在計(jì)算機(jī)領(lǐng)域應(yīng)用廣泛，計(jì)算機(jī)離不開數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)為了能使我們掌握所學(xué)習(xí)的知識(shí)并有應(yīng)用到實(shí)際的設(shè)計(jì)中的能力，對(duì)于掌握這門課程的學(xué)習(xí)方法有極大的意義。本課程設(shè)計(jì)的題目為“故宮導(dǎo)游咨詢”，完成相應(yīng)的錄入信息、查找、修改、刪除、計(jì)算功能等等。本課程設(shè)計(jì)采用的編程環(huán)境為Microsoft Visual Stdio 6.0。1、需求分析 游客游覽某一景點(diǎn)時(shí)，對(duì)景點(diǎn)都不熟悉。特別是對(duì)于象故宮這樣的大型景點(diǎn)，如果隨便參觀的話，可能會(huì)錯(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)要完成對(duì)故宮景點(diǎn)信息的儲(chǔ)存、修改、刪除、添加和查詢最短路線，因?yàn)樯婕暗阶疃搪肪€問題，所以數(shù)據(jù)結(jié)構(gòu)優(yōu)先考慮采用圖的鄰接矩陣儲(chǔ)存結(jié)構(gòu)，景點(diǎn)和旅游線路可以構(gòu)成圖狀結(jié)構(gòu)，景點(diǎn)作為圖的頂點(diǎn)，旅游線路作為圖的邊，邊上的權(quán)值作為景點(diǎn)間的距離。此結(jié)構(gòu)便于完成任務(wù)的各種操作。1.2測(cè)試數(shù)據(jù) 圖1 測(cè)試數(shù)據(jù)2 概要設(shè)計(jì) 2.1 ADT描述 ADT Graph數(shù)據(jù)對(duì)象：D故宮景點(diǎn)和路徑數(shù)據(jù)關(guān)系：RVRVR=<v,w>|v,wV，<v,w>表示頂點(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 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)和路徑的信息，并儲(chǔ)存。查詢景點(diǎn)模塊:void select()查找某景點(diǎn)的信息。修改模塊:void xiugai()修改某景點(diǎn)的信息。插入模塊:void insert()插入新的景點(diǎn)和路徑信息。刪除模塊:void delet()刪除景點(diǎn)和路徑信息。查詢到某景點(diǎn)最佳路徑:void shortpath1()：查詢到某景點(diǎn)的最短路徑。查詢到查詢到所有景點(diǎn)的最短路徑:void shortpath2()查詢到所有景點(diǎn)的最短路徑3詳細(xì)設(shè)計(jì)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;i<MAXVertices;i+) Verticesi.dingdian="0" for(i=0;i<MAXVertices;i+) for(int j=0;j<MAXVertices;j+)if(i=j)Edgeij=0;elseEdgeij=MAXweight;numE=0;numV=0;3.3 插入操作插入路徑和景點(diǎn)信息： void Graph:insert() int i,vi,vj,w,x,y; cout<<"輸入添加路徑的條數(shù)和景點(diǎn)數(shù)：" cin>>x>>y; cout<<"輸入添加景點(diǎn)名稱:"<<endl; for(i=0;i<y;i+) cout<<numV+i+1<<":"cin>>VerticesnumV+i.dingdian;cout<<" "<<"景點(diǎn)信息:"cin>>VerticesnumV+i.xinxi;cout<<"添加成功!"<<endl; for(i=0;i<x;i+) cout<<"輸入添加景點(diǎn)到景點(diǎn)的路徑的長度(vi,vj,length):" cin>>vi>>vj>>w; 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; cout<<"輸入路徑的條數(shù)數(shù)和景點(diǎn)數(shù)：" cin>>numE>>numV; cout<<"輸入景點(diǎn)名稱:"<<endl; for(i=0;i<numV;i+) cout<<i+1<<":"cin>>Verticesi.dingdian;cout<<"景點(diǎn)信息:"cin>>Verticesi.xinxi; for(i=0;i<numE;i+) cout<<"輸入景點(diǎn)到景點(diǎn)的路徑的長度(vi,vj,length):" cin>>vi>>vj>>w; Edgevi-1vj-1=w; Edgevj-1vi-1=w; 3.5修改操作void Graph:xiugai() string a,c; int b=0; cout<<"請(qǐng)輸入要修改的景點(diǎn):" cin>>a; for(int i=0;i<numV;i+) if(Verticesi.dingdian=a) cout<<"請(qǐng)重新輸入景點(diǎn)信息:"cin>>c;Verticesi.xinxi=c;b+;cout<<"修改成功!"<<endl;if(b=0)cout<<"不存在該景點(diǎn)！"<<endl;3.6查詢操作void Graph:select() string a; int b=0; cout<<"請(qǐng)輸入要查詢的景點(diǎn):" cin>>a; for(int i=0;i<numV;i+)if(Verticesi.dingdian=a)cout<<Verticesi.xinxi<<endl;b+;if(b=0)cout<<"不存在該景點(diǎn)！"<<endl;3.7刪除操作void Graph:delet() int x,y,z,k,v; cout<<"請(qǐng)你輸入要撤銷景點(diǎn)數(shù)和路線條數(shù):" cin>>k>>z; for(int j=0;j<k;j+) cout<<"請(qǐng)輸入要撤銷的景點(diǎn)編號(hào):" cin>>v; for(int i=0;i<numV;i+) if(i!=v-1) Edgev-1i=MAXweight;Edgeiv-1=MAXweight; cout<<"撤銷成功!"<<endl; for(int i=0;i<z;i+) cout<<"請(qǐng)輸入要撤銷的旅游路線的景點(diǎn)編號(hào)(vi,vj):" cin>>x>>y; 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; cout<<"輸入你所在的景點(diǎn):" cin>>b; cout<<"輸入你所要去的景點(diǎn):" cin>>c; for(int i=0;i<numV;i+)if(Verticesi.dingdian=b)v=i; for( i=0;i<numV;i+)if(Verticesi.dingdian=c)v1=i; for( i=0;i<numV;i+) disti=Edgevi;si=0;if(i!=v&&disti<MAXweight)pathi=v;elsepathi=-1; sv=1; distv=0; for(i=0;i<numV;i+) float min=MAXweight;int u=v;for(int j=0;j<numV;j+)if(!sj&&distj<min)u=j;min=distj;su=1;for(int w=0;w<numV;w+) if(!sw&&Edgeuw<MAXweight&&distu+Edgeuw<distw)distw=distu+Edgeuw;pathw=u; for( i=0;i<numV;i+) if(i!=v&&i=v1&&disti!=MAXweight) string c10; int j=0; int k=i; cout<<"從"<<b<<"到"<<Verticesi.dingdian<<"的" cout<<"最佳路徑長度為:" cout<<disti<<"米"<<" " cout<<"大約需要走"<<disti/100<<"分鐘"<<" " cout<<"路徑為:" doj+; cj=Verticesk.dingdian; k=pathk; while(k!=v); j+; cj=Verticesk.dingdian; for(int n=j;n>=1;n-) cout<<cn; if(n!=1) cout<<"->" cout<<endl; 3.9求到所有景點(diǎn)的路徑void Graph:shortpath2() int v; string b; cout<<"輸入你所在的景點(diǎn):" cin>>b; for(int i=0;i<numV;i+)if(Verticesi.dingdian=b)v=i; for( i=0;i<numV;i+) disti=Edgevi;si=0;if(i!=v&&disti<MAXweight)pathi=v;elsepathi=-1; sv=1; distv=0; for(i=0;i<numV;i+) float min=MAXweight;int u=v;for(int j=0;j<numV;j+)if(!sj&&distj<min)u=j;min=distj;su=1;for(int w=0;w<numV;w+) if(!sw&&Edgeuw<MAXweight&&distu+Edgeuw<distw)distw=distu+Edgeuw;pathw=u; for( i=0;i<numV;i+) if(i!=v&&disti!=MAXweight) string c10; int j=0; int k=i; cout<<"從"<<b<<"到"<<Verticesi.dingdian<<"的" cout<<"最佳路徑長度為:" cout<<disti<<"米"<<" " cout<<"大約需要走"<<disti/100<<"分鐘"<<" " cout<<"路徑為:" doj+; cj=Verticesk.dingdian; k=pathk; while(k!=v); j+; cj=Verticesk.dingdian; for(int n=j;n>=1;n-) cout<<cn; if(n!=1) cout<<"->" cout<<endl; 3.10求到所有景點(diǎn)的路徑void Graph:shortpath2() int v; string b; cout<<"輸入你所在的景點(diǎn):" cin>>b; for(int i=0;i<numV;i+) if(Verticesi.dingdian=b) v=i; for( i=0;i<numV;i+) disti=Edgevi; si=0; if(i!=v&&disti<MAXweight) pathi=v; elsepathi=-1; sv=1; distv=0; for(i=0;i<numV;i+) float min=MAXweight;int u=v;for(int j=0;j<numV;j+)if(!sj&&distj<min)u=j;min=distj;su=1;for(int w=0;w<numV;w+)if(!sw&&Edgeuw<MAXweight&&distu+Edgeuw<distw)distw=distu+Edgeuw;pathw=u; for( i=0;i<numV;i+) if(i!=v&&disti!=MAXweight) string c10; int j=0; int k=i; cout<<"從"<<b<<"到"<<Verticesi.dingdian<<"的" cout<<"最佳路徑長度為:" cout<<disti<<"米"<<" " cout<<"大約需要走"<<disti/100<<"分鐘"<<" " cout<<"路徑為:" doj+; cj=Verticesk.dingdian; k=pathk; while(k!=v); j+; cj=Verticesk.dingdian; for(int n=j;n>=1;n-) cout<<cn; if(n!=1) cout<<"->" cout<<endl; 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<<"* 請(qǐng)選擇(A、B、C)*"<<endl; cout<<"*"<<endl; cin>>c; if(c=A) int d;char b;cout<<"請(qǐng)輸入密碼:"cin>>d;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<<"* 請(qǐng)選擇(A、B、C、D、E) *"<<endl;cout<<"*"<<endl;cin>>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<<"密碼錯(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<<"* C、查詢到所有景點(diǎn)的最佳路徑 *"<<endl; cout<<"* D、退出 *"<<endl;cout<<"* 請(qǐng)選擇(A、B、C、D) *"<<endl;cout<<"*"<<endl;cin>>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測(cè)試數(shù)據(jù)測(cè)試數(shù)據(jù)見圖1.4.2調(diào)試問題 在調(diào)試過程中遇到輸出路徑算法有錯(cuò)誤，當(dāng)刪除一條路徑時(shí)時(shí)不能正確輸出相應(yīng)路徑，然后對(duì)輸出路徑的條件進(jìn)行改進(jìn)，增加了條件，測(cè)試成功。 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)和路徑為x，y時(shí)，若x>=y時(shí)間復(fù)雜度為O(x)反之為O(y);刪除景點(diǎn)和路徑: 當(dāng)刪除的景點(diǎn)和路徑為x，y時(shí)，若x>=y時(shí)間復(fù)雜度為O(x)反之為O(y);查詢到某景點(diǎn)最佳路徑；此算法為迪杰斯特拉算法時(shí)間復(fù)雜度為O(n*n);查詢到所有景點(diǎn)的最短路徑: 此算法為迪杰斯特拉算法時(shí)間復(fù)雜度為O(n*n);4.4經(jīng)驗(yàn)和體會(huì)在本次課程設(shè)計(jì)中主要是對(duì)圖的數(shù)據(jù)結(jié)構(gòu)操作，所有剛開始對(duì)知識(shí)不是很熟悉操作起來有一定難度，容易在程序的關(guān)鍵地方但經(jīng)過翻閱教材能較好的解決問題。5用戶使用說明本系統(tǒng)是關(guān)于故宮的管理系統(tǒng)分為兩類用戶，管理員和游客，由于管理員可以對(duì)數(shù)據(jù)進(jìn)行修改，為了保護(hù)數(shù)據(jù)，所以管理員登陸需要密碼而游客不需要密碼，管理員有添加景點(diǎn)和路徑、刪除景點(diǎn)和路徑、修改景點(diǎn)信息權(quán)限，游客能查詢景點(diǎn)信息、查找到某一景點(diǎn)的最佳路徑和到所有景點(diǎn)的最佳路徑。6測(cè)試結(jié)果6.1錄入信息 圖3 錄入信息界面 圖4 錄入信息界面6.2查詢景點(diǎn)模塊 圖5 查詢景點(diǎn)信息界面6.3修改模塊 圖6 修改景點(diǎn)信息界面6.4插入模塊 圖7 添加景點(diǎn)信息界面6.5刪除模塊 圖8 刪除景點(diǎn)信息界面6.6查詢到某景點(diǎn)最佳路徑 圖9 查詢到某景點(diǎn)最佳路徑界面6.7查詢到所有景點(diǎn)的最短路徑。 圖10 查詢到所有景點(diǎn)最佳路徑界面結(jié) 論 本次課程設(shè)計(jì)“故宮導(dǎo)游咨詢”按照任務(wù)書相應(yīng)的要求成功的完成了任務(wù)，由于本課程設(shè)計(jì)涉及景點(diǎn)和路徑，采用圖的儲(chǔ)存結(jié)構(gòu)和算法比較方便處理數(shù)據(jù)的儲(chǔ)存、查詢、刪除等操作。但圖的操作比較難，比如求某景點(diǎn)到所有景點(diǎn)的最佳路徑問題，需要使用到迪杰斯特拉算法實(shí)現(xiàn)。 致 謝 在本次課程設(shè)計(jì)過程中，首先感謝輔導(dǎo)老師周立章，在數(shù)據(jù)結(jié)構(gòu)課堂上為課程設(shè)計(jì)需要的前期知識(shí)打下了基礎(chǔ)，在課程設(shè)計(jì)過程中抽出休息時(shí)間來做相應(yīng)的課程設(shè)計(jì)指導(dǎo)。同時(shí)在這次課程設(shè)計(jì)中，也要感謝許多樂意同學(xué)對(duì)我不懂的地方的指導(dǎo)和耐心講解。參考文獻(xiàn) 1 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu).清華大學(xué)出版社出版。 2 嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)題集(C語言版) .清華大學(xué)出版社.2003年5月。3 楊秀金，數(shù)據(jù)結(jié)構(gòu)(C+版) .高等教育出版社.2009年4月。4 朱戰(zhàn)立.數(shù)據(jù)結(jié)構(gòu)(C+語言描述)（第二版本）.高等出版社出版.2004年4月。5 胡學(xué)鋼.數(shù)據(jù)結(jié)構(gòu)(C語言版) .高等教育出版社.2004年8月。6 楊金秀.數(shù)據(jù)結(jié)構(gòu)（C語言版）.西安電子科技大學(xué)出版社，2004年8月。