校園導(dǎo)游咨詢程序設(shè)計報告.doc_第1頁
校園導(dǎo)游咨詢程序設(shè)計報告.doc_第2頁
校園導(dǎo)游咨詢程序設(shè)計報告.doc_第3頁
校園導(dǎo)游咨詢程序設(shè)計報告.doc_第4頁
校園導(dǎo)游咨詢程序設(shè)計報告.doc_第5頁
已閱讀5頁,還剩9頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計設(shè)計題目: 校園導(dǎo)游咨詢 學(xué) 院: 信息學(xué)院 班 級: 計算機(jī)1008班 姓 名: 學(xué) 號: 20101221180 日期: 2012 年 3 月校園導(dǎo)航問題問題描述設(shè)計一個校園導(dǎo)游程序,為來訪的客人提供各種信息查詢服務(wù)?;疽螅?)設(shè)計所在學(xué)校的校園平面圖,所含景點(diǎn)不少于十個。以圖中頂點(diǎn)表示校內(nèi)各景點(diǎn),存放景點(diǎn)名稱、代號、簡介等信息;以邊表示路徑,存放路徑長度等信息。(2)為來訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢。(3)為來訪客人提供圖中任意景點(diǎn)的問路查詢,即查詢?nèi)我鈨蓚€頂點(diǎn)之間的一條最短的簡單路徑。(4)校園導(dǎo)游圖的景點(diǎn)和道路的修改擴(kuò)充功能。(5)擴(kuò)充道路信息,如道路類別(車道、人行道),以致可按客人所需分別查詢?nèi)诵新窂交蜍囆新窂?。?)擴(kuò)充每個景點(diǎn)的林潔景點(diǎn)的方向等信息,使得路徑查詢結(jié)果能提供詳盡的導(dǎo)向信息。(7)實現(xiàn)校園導(dǎo)游的仿真界面。一、 概要設(shè)計4二、 詳細(xì)設(shè)計6三、 調(diào)試分析12四、 調(diào)用關(guān)系12五、用戶操作指南13測試數(shù)據(jù)1、 概要設(shè)計1. 數(shù)據(jù)類型#define V_MAX 20#define E_MAX 200typedef struct char name10;/名字/char code10;/代碼char info20;/信息,簡介int x,y;/坐標(biāo)VType;/頂點(diǎn)類型typedef struct int live;/標(biāo)記是否存在,如果被刪除則為0,存在為1char name10;/ 路名int length;/路的長度char ivex10,jvex10;/路(邊)連接的兩個頂點(diǎn)的名字int type;/表示道路類型,0表示兩個都是,1表示人行道,2表示行車道EdgeType;/邊類型typedef struct AdjNodeint length;/ 弧的長度char name10;/關(guān)聯(lián)的頂點(diǎn)的名字struct AdjNode *next;/下一條弧AdjNode;/弧結(jié)點(diǎn)typedef struct int live;/標(biāo)記是否存在,如果被刪除則為0,存在為1int flag;/標(biāo)記是否被訪問過VType data;/頂點(diǎn)的信息 AdjNode *first_adj;/指向該頂點(diǎn)的第一條弧VNode;/景點(diǎn)(頂點(diǎn))結(jié)點(diǎn)typedef struct VNode vexV_MAX;/頂點(diǎn)數(shù)組EdgeType edgeE_MAX;/邊的數(shù)組int v_num,e_num;Graph;/圖類型/Graph G;AdjNode *p;2.基本函數(shù)/void creatGraph(Graph &G);/創(chuàng)建校園圖void load(Graph &G);/從文件中讀取數(shù)據(jù)void save(Graph &G);/保存數(shù)據(jù)入文件int find_v(Graph G,char name10);/通過輸入景點(diǎn)名字,返回該景點(diǎn)在vex數(shù)組里的下標(biāo)void print_Graph(Graph G);/以鄰接矩陣的形式輸出圖信息int direction(Graph G,char bname10,char fname10);/用于判斷并輸出一個景點(diǎn)在另外一個景點(diǎn)的方位信息void search_view(Graph G);/查詢并輸出景點(diǎn)的所有信息void del_v(Graph &G);/刪除景點(diǎn)void add_v(Graph &G);/增加景點(diǎn)void add_e(Graph &G)/增加道路void modify_v(Graph &G);/修改景點(diǎn)信息void del_e(Graph &G);/刪除道路2、 詳細(xì)設(shè)計本程序由m.cpp、head.h、Menu.h、dijie.h4個文件構(gòu)成。1、 m.cpp主要用于調(diào)用菜單函數(shù)#include #include #include #include #include head.h#include dijie.h#include allpath.h#include Menu.hvoid main() load(G);/while(1)menu();2. Menu.h存放用于顯示系統(tǒng)仿真界面的函數(shù)void mobifyMenu()while(1)system(cls);int choose;printf(-);printf(n);printf( 校園導(dǎo)游系統(tǒng) );printf(n);printf(-);printf(n);printf( 景點(diǎn)或者道路信息的修改擴(kuò)充 );printf(n);printf(n);printf(-);printf(n);printf(1. 增加新景點(diǎn)n);printf(2. 刪除景點(diǎn)n);printf(3. 修改景點(diǎn)n);printf(4. 增加新道路n);printf(5. 重新構(gòu)建校園景點(diǎn)和路徑信息n);printf(0. 返回上一個菜單n);printf(請輸入操作代碼:);scanf(%d,&choose);getchar();system(cls);switch(choose)case 1:add_v(G);break;case 2:del_v(G);break;case 3:modify_v(G);break;case 4:add_e(G);break;case 5:creatGraph(G);break;case 0:return;void menu()int choose;printf(-);printf(n);printf( 校園導(dǎo)游系統(tǒng) );printf(n);printf(-);printf(n);printf( 景點(diǎn)預(yù)覽 );printf(n);for(int i=0;iG.v_num;i+) printf( %s ,G.);if(i+1)%2=0) printf(n);printf(n);/print_Graph(G);printf(-);printf(n);printf(1. 景點(diǎn)或者道路信息的修改擴(kuò)充n);printf(2. 查詢景點(diǎn)信息n);printf(3. 查詢最佳觀光路徑n);printf(0. 退出系統(tǒng)n);printf(請輸入操作代碼:);scanf(%d,&choose);getchar();system(cls);switch(choose)case 1:mobifyMenu();break;case 2:search_view(G);getchar();break;case 3:FDijkstra(G);getchar();break;case 0:exit(0);break;system(cls);3. head.h本文件用于存放基本操作函數(shù),在此不做詳細(xì)介紹4. dijie.h本文件用于查詢并輸出兩個景點(diǎn)間的最佳路徑并輸出const int maxnum = 20;const int maxint = 10000;int cmaxnummaxnum;/圖的鄰接矩陣int P maxnum maxnum;/標(biāo)明最短路徑經(jīng)過哪個點(diǎn)bool finalmaxnum;/標(biāo)明從原點(diǎn)到某個點(diǎn)的最短路徑已經(jīng)找到int Dmaxnum;/記錄最短路徑的長度int pathmaxnum,jishu=0;/path用于按順序存放已找到最短路徑的頂點(diǎn),path1為第二個已經(jīng)找到的/需要注意的是,如果圖中有9個頂點(diǎn),其中有兩個無法到達(dá),則path的最后面3個就是重復(fù)的/要注意區(qū)分開/ 用迪杰斯特拉算法找出最短路徑void DIJ(Graph G,int v0,int P maxnum maxnum,int Dmaxnum)jishu=0;int min;for(int v=0;vG.v_num;v+)finalv=false; Dv=cv0v;for(int w=0;wG.v_num;+w) Pvw=0;if(Dvmaxint) Pvv0=1;Pvv=1;Dv0=0;finalv0=true;pathjishu=v0;jishu+;for(int i=1;iG.v_num;+i)min=maxint;for(int w=0;wG.v_num;+w) if(!finalw) if (Dwmin) v=w;min=Dw; finalv=true;pathjishu=v;jishu+;for(w=0;wG.v_num;+w)if(!finalw&(min+cvwDw)Dw=min+cvw;/Pw=Pv;for(int j=0;jG.v_num;j+)Pwj=Pvj;Pww=1;/糾正jishufor(jishu=1,i=1;i1000) printf(沒有能夠到達(dá)的路徑n);return ;int shortPathV_MAX,count=0;/count指最短路徑里到底有幾個點(diǎn)/ shortPath里面是正確連續(xù)的最短路徑/若果shortPath=0,4,3,5,則最短路徑為0-4-3-5shortPath0=b_v;for(int i=1;ijishu;i+)if(Pf_vpathi=1) / 問題出在pathi上,由于有兩個景點(diǎn)是無法到達(dá)的/ 所以pathi后面三個元素都是重復(fù)的,導(dǎo)致count數(shù)多了2個count+;shortPathcount=pathi;/puts(G.);/ 通過shortPath輸出路線信息int roadV_MAX;/road0記錄的是從shortPath0到shortPath1要走的路for(i=0;icount;i+) /i指向兩個鄰接點(diǎn)的起點(diǎn),i+1表示終點(diǎn)for(int j=0;jG.e_num;j+) /找連接這兩個頂點(diǎn)的邊,j指向邊 if(strcmp(G.edgej.ivex,G.vexshortP)=0&strcmp(G.edgej.jvex,G.vexshortPathi+1.)=0) roadi=j;break; if(strcmp(G.edgej.jvex,G.vexshortP)=0&strcmp(G.edgej.ivex,G.vexshortPathi+1.)=0) roadi=j;break; printf(從 );for(i=0;icount;i+)printf(%sn,G.vexshortP);printf(往);direction(G,G.vexshortP,G.vexshortPathi+1.); printf( 沿著%s路走 %d 米到n,G.,G.edgeroadi.length);puts(G.vexf_);/ 查詢兩個景點(diǎn)間最短路徑函數(shù)void FDijkstra(Graph G)int vi,vj;char begin_p10,final_p10;int b_v,f_v; for(int g=0;gG.v_num;g+) for(int h=0;hG.v_num;h+) cgh=maxint;for(int h=0;hV_MAX;h+)for(g=0;gV_MAX;g+)Pgh=0;for( h=0;hV_MAX;h+)finalh=false;for(h=0;hV_MAX;h+)Dh=10000;for(h=0;hV_MAX;h+)pathh=0;jishu=0;int t;printf(選擇道路類型(人行道1/行車道2/兩者都行0):);scanf(%d,&t);getchar();/ 構(gòu)建鄰接矩陣for(int i=0;iG.e_num;i+)if(G.edgei.type=t|G.edgei.type=0) vi=find_v(G,G.edgei.ivex); vj=find_v(G,G.edgei.jvex); cvivj=G.edgei.length; cvjvi=G.edgei.length;printf(請輸入起點(diǎn):);while(1)gets(begin_p); if(find_v(G,begin_p)=100) printf(不存在該景點(diǎn),請重新輸入:);continue;break;b_v=find_v(G,begin_p);printf(請輸入終點(diǎn):);while(1)gets(final_p); if(find_v(G,final_p)=100) printf(不存在該景點(diǎn),請重新輸入:);continue;break;f_v=find_v(G,final_p); DIJ(G,b_v,P,D);print_path(G,b_v,f_v);3、 調(diào)試分析數(shù)據(jù)結(jié)構(gòu)書中的迪杰斯特拉算法只能求出最短路徑中有哪個景點(diǎn),但無法求出這幾個景點(diǎn)的經(jīng)過順序,所以先利用迪杰斯特

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論