校園導(dǎo)游咨詢程序設(shè)計報告.doc

數(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)過順序，所以先利用迪杰斯特