校園導(dǎo)游咨詢系統(tǒng)

1、1-需求分析1、1創(chuàng)建結(jié)點(diǎn)（旅游景點(diǎn)）創(chuàng)建該旅諒景2就是在嘯序表中完成得，在順序表中，首先要?jiǎng)?chuàng)建結(jié)點(diǎn)結(jié)構(gòu)體， 將該結(jié)構(gòu)體命名為SeqList,成員變量有數(shù)組1 ist與s i ze,分別用來表示最大元 素個(gè)數(shù)（即旅游景點(diǎn)得最大個(gè)數(shù)）與順序表中當(dāng)前存儲得數(shù)據(jù)元素個(gè)數(shù)，順序表可 以完成得功能有求當(dāng)前數(shù)據(jù)元素個(gè)數(shù)，插入數(shù)據(jù)元素，刪除數(shù)據(jù)元素，取數(shù)據(jù)元 素.1、2創(chuàng)建圖在構(gòu)造圖得操作中包括結(jié)點(diǎn)得插入（實(shí)參包括AdjMGraph水G, DasTyp v ,n ,Ro wColW e i g ht E ,e）分別表示在該* G得結(jié)構(gòu)體中得Se q li s t Vertices 中插入結(jié)點(diǎn)，在* G得結(jié)構(gòu)

2、體中得edge Ma x V e rtices MaxVer t ices得邊數(shù)組中插入邊信息結(jié)點(diǎn)分別為行下標(biāo)、列下標(biāo)、權(quán)值，該*G得結(jié)構(gòu)體 中numO f Edges,e表示邊得條數(shù)，即將e得值給它。結(jié)點(diǎn)得順序表初始化，在 該函數(shù)中也應(yīng)包括一個(gè)結(jié)構(gòu)體邊信息結(jié)構(gòu)體:成員包括行下標(biāo)、列下標(biāo)、權(quán)值.并 將該結(jié)構(gòu)體命名為RowC o lWe i ght。1、3圖得實(shí)現(xiàn)在該函數(shù)中要使用Se q Li s t頭文件，在該文件中要真正進(jìn)行插入邊與結(jié)點(diǎn)首先 在該函數(shù)中應(yīng)該定義一個(gè)結(jié)構(gòu)體AdjMGraph,在該結(jié)構(gòu)體得成員變量包括存放 結(jié)點(diǎn)得順序表定義為s e q lis t Vertices、存放邊得鄰接矩

3、陣用ed g eMaxV e rtic e s MaxVer t ices表示，邊得條數(shù) n u mOfEd g eSo 初始化 AdjMGraph 中 得成員變量線性表與邊數(shù)及存放邊得鄰接矩陣。然后在順序表中插入結(jié)點(diǎn)，在鄰 接矩陣中插入邊JW除邊，刪除結(jié)點(diǎn)。取序號為V得結(jié)點(diǎn)得第一個(gè)鄰接結(jié)點(diǎn)，取 序號為V 1得鄰接結(jié)點(diǎn)V 2結(jié)點(diǎn)得下一個(gè)鄰接結(jié)點(diǎn)1、4求最短路徑在該函數(shù)中，應(yīng)該有四個(gè)參數(shù)，兩個(gè)位輸入?yún)?shù),分別為帶權(quán)圖G與源點(diǎn)（景點(diǎn)起 點(diǎn)）序號v 0,兩個(gè)為輸出參數(shù),分別為d ist a nce與path , di s tanc e 用來 存放達(dá)到得從源點(diǎn)v0到其余各結(jié)點(diǎn)得最短距離，p a th用

4、來存放最短路徑 得下標(biāo).1、從江西農(nóng)業(yè)大學(xué)得平面地圖中選取岀6個(gè)有代表性得景點(diǎn)。2、為來訪得客人提供圖中任意景點(diǎn)得路徑查詢，即查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間得最短 簡單路徑。當(dāng)用戶輸入正確時(shí)，為用戶輸出任意兩景點(diǎn)得最短路徑;當(dāng)用戶輸入 不合法時(shí)，提示用戶輸入有誤并返回讓用戶重新輸入。3、為來訪客人推薦參觀最短路線.2、概要設(shè)計(jì)1 首先用鄰接矩陣存儲校園圖.2。用數(shù)據(jù)結(jié)構(gòu)知識創(chuàng)建校園圖。3手動(dòng)給校園圖賦上相關(guān)信息（景點(diǎn)名稱、代號、簡介），路徑及路徑長度。4 利用C語言知識編寫查找景點(diǎn)相關(guān)信息得程序。5 利用迪杰斯特拉算法計(jì)算任意兩點(diǎn)之間得最短路徑。6o最后用一個(gè)主函數(shù)m a in輸出各項(xiàng)結(jié)果。1創(chuàng)建校園圖

5、：(1)先定義節(jié)點(diǎn)個(gè)數(shù)N,邊得最大值(Max weig ht),節(jié)點(diǎn)(景點(diǎn)名稱、景點(diǎn)信息)， 鄰接點(diǎn)，邊，頂點(diǎn)向量,當(dāng)前頂點(diǎn)數(shù)與邊數(shù)。(2 )先給一個(gè)節(jié)點(diǎn)賦上其相關(guān)信息，然后再用p = (Node)malloc(sizeof (edge node)語句申請下一結(jié)點(diǎn),再給所申請得節(jié)點(diǎn)賦上相關(guān)信息，直到節(jié)點(diǎn) 數(shù)為N=6為止。(3)讀入道路得起始點(diǎn),為鄰接矩陣得邊賦相應(yīng)得值。時(shí)(4)節(jié)點(diǎn)與邊得相關(guān)信息都弄好了后，校園圖也就創(chuàng)建好了.2.利用函數(shù)Num e給1 0個(gè)節(jié)點(diǎn)賦上相應(yīng)得名稱，利用函數(shù)Informati o n給 各節(jié)點(diǎn)添加相應(yīng)得介紹信息。3 .利用函數(shù)trav g raph來查找景點(diǎn)信息，要

6、查找景點(diǎn)名稱時(shí)調(diào)用Name函數(shù), 要查找景點(diǎn)介紹信息時(shí)調(diào)用I nf o rmati o n函數(shù).4o手動(dòng)創(chuàng)建一個(gè)校園圖AdjMGraph g creat(AdjMGgr p h *G),然后為相應(yīng)得 邊賦上真正得值。5o用distance 數(shù)組來存放任意兩景點(diǎn)之間得最短路徑.6.用ma i n函數(shù)來輸出結(jié)果:用s wi t ch語句分別輸出，要?jiǎng)?chuàng)建校園圖時(shí)調(diào)用 AdjMGra p hgraphc r eat函數(shù);查找景點(diǎn)相關(guān)信息時(shí)調(diào)用s e arc h函數(shù)；要查找任 意兩景點(diǎn)之間得最短路徑時(shí)，先輸入您U前所在得位置，再輸入您得U得地，最后 調(diào)用pa th函數(shù)。3 詳細(xì)設(shè)計(jì)#de f in e

7、N10#d e fine#define#includ eMAXSize2 0圖中頂點(diǎn)數(shù)得最大值MAXedg30/圖中邊數(shù)得最大值s t d i o、h#inclu d e s tring h #inc 1 ude # include t y pede f i nt AdjMGraph MAXSize MAXS i ze;/ 存放鄰接矩陣得 權(quán)值信息ty p ede f structi n t v exs MAXS ize；A d jMGr a p h s； / Matri x _Graph： /圖得鄰接矩陣表示法。ty p e d e f s tr u c t numo fedge/Mnt a

8、dj vex；鄰接矩陣結(jié)點(diǎn)序號int length；定義道路長度ochar in fo10； 定義景點(diǎn)名稱oc h arinfo2l 0 0； 定義景點(diǎn)詳細(xì)信息st r uct n u mofedge * n e xt； 定義指向下一個(gè)結(jié)點(diǎn)得指針 n umof e dg e , *Nod e ； 將該結(jié)構(gòu)體重新命名為*Nodetypedef structchar n a m e 1 0；存儲景點(diǎn)得名稱數(shù)組cha r information 100;/具體得介紹此景點(diǎn)信息數(shù)組s t ruct num o f e d g e次link;指向下一個(gè)景點(diǎn)得指針 vextices；創(chuàng)建景點(diǎn)及其信息結(jié)構(gòu)體

9、typedef str u ct EdgeMnt leng h ；邊得權(quán)值，表示路徑長度、int i vex, jvex：表示兩個(gè)連接得結(jié)點(diǎn)得位置變量os t ruct Edge *next：/指向下一條邊得指針變量 Ed g eT y pe;/邊及其信息、typ e d ef s tmctint num; 結(jié)點(diǎn)編號。ch a r n a me10； 結(jié)點(diǎn)名稱 v e rtex;/ /存放結(jié)點(diǎn)信息結(jié)構(gòu)體typed e f st r u c tover t ex v e x s MAXSize；存放結(jié)點(diǎn)數(shù)組元素信息ointe d ges MA XS i ze MAXSize; /存放邊得鄰接矩陣

10、 adj max, a dj：/表示圖得結(jié)構(gòu)體FILE * f p； 文件得讀取vo i d clrscr () 清屏s ystem (” c 1 s )；void c r e a tgrap h ( v e xtices g, in t *n, E d geType e, a dj m axa dj) /創(chuàng)建校園圖v extice s g 表示存放景點(diǎn)信息數(shù)組,n表示下一個(gè) 景點(diǎn),E dgeT y p e e 表示存放邊得信息數(shù)組，adj max *ad j表示下一條邊得信 息數(shù)組i n t b, i,s,d,l e n;/b代表結(jié)點(diǎn)之間得邊數(shù)s t ruct numof e dge *p,

11、 *q；定義圖得結(jié)構(gòu)體if (fp = fopen (“ “，” r”)= NULL) 打開文件，對文件進(jìn)行讀得操 作oprintf ( ”文件打開錯(cuò)誤!n ” )：get c har ()； 獲取景點(diǎn)信息ex i t (0)；f s canf( f p, ” % d %dn , n,&b)；/ /讀入景點(diǎn)個(gè)數(shù)與邊數(shù)for (i = 1 ; i ve x s i 、n a me, g i、n ame)； / /將景點(diǎn)得名 字賦給圖中得結(jié)點(diǎn)信息。g i 、li n k = NULL;/初始化節(jié)點(diǎn)得下一個(gè)結(jié)點(diǎn)信息 f or (i = 1; i le n g h; / /將各個(gè)邊得長度值記錄下來ad

12、j-ed g es s d = e i、le n gh;為鄰接矩陣中相應(yīng)得邊賦值adj- e d g e sd s = e i、le n g h y / 該矩陣為對稱矩陣故 edges d s = e d g ess d ;dp = (Node)mal 1 oc (sizeof(nuniof e dge) )；/ / 為一個(gè)新得結(jié)點(diǎn)開辟動(dòng)態(tài)空間。p n ext = NULL;/ /初始化開辟空間得下一個(gè)結(jié)點(diǎn)q = (Node) mallo c (sizeof (numofed g e ) ; / /為一個(gè)新得結(jié)點(diǎn)開辟 動(dòng)態(tài)空間q- next= NULL； 初始化開辟空間得下一個(gè)結(jié)點(diǎn)P - a

13、djvex = d;/將邊得列號給結(jié)點(diǎn)信息得結(jié)構(gòu)體中記錄鄰接矩陣得序號成員。p-len gth = len;將邊得長度值給結(jié)點(diǎn)信息得結(jié)構(gòu)體中得道路成員 strcpy (p一i n fo,gd、name)； 為景點(diǎn)賦名稱 st r cpy (p-i n fo2, g d 、info r mati o n); /為景點(diǎn)賦介紹信息dq一adj vex = s；/為景點(diǎn)賦序號，道路長度2 q 1 e n gth =1 en;Wcpy(qinfo,g s 、nam e )；為景點(diǎn)賦名稱2 s t r c p y (qinfo2, gs、information);/為景點(diǎn)賦介紹信息p-ne x t = g

14、 s、link; 使P指針指向第s行得下一行，頭插法建 立鄰接表g s、I in k = p;使p指針指向第s行得下一行得下一行q next= g d、link;/使q指針指向第d列得下一列，頭插法建立鄰接表 g d 、link = q; /使q指針指向第d列得下一列，頭插法建立鄰接表 0printf (”校園旅游圖已經(jīng)建立！ nH);ge t c h ar();voi d Name(int i)swi tch （i） 為景點(diǎn)添加具體得名字地點(diǎn)case 1:M p r intf（n 1:教 n ） ;break；ca s e 2：o p r i n t f （2:二教 n）； break：ca

15、se 3:0 p rintf （” 3:五教n）； b reak;c ase 4 :pr i ntf （ ” 4：新圖書館n”）;b r e ak；ca s e 5 ：pri n tf（5：老圖書館n”）； break;case 6:printf （ 6：北區(qū)食堂 n H）;br e a k；ca s e 7 :prin t f （” 7:南區(qū)食堂n”）； break：case 8：printf （ 8：大學(xué)生活動(dòng)中心n ）； break;case 9：Mpr i n tf（9:圓形報(bào)告廳n ）； bre a k；case 1 0 :printf（” 10：體育館n”）;break;de f

16、ault：o p r int f （景點(diǎn)編號輸入錯(cuò)誤！請輸入1一10得數(shù)字編號！ nnM）； b r e ak； / *N a me*/v oid Informa t ion（i n t i ）/*景點(diǎn)介紹*/swit c h（i）為景點(diǎn)添加介紹信息cas e 1:p r int f （“一教:這就是一棟比較古老得建筑樓，但就是當(dāng)您路過這里， 會聽到朗朗得讀書聲，很勵(lì)志得地方n“）； b reak;c a se 2:op rintf （ ”二教：這棟樓真得很令人不滿意，不瞧平面圖很難找到，其次, 它就就是一個(gè)2得形狀n“）;bre a k：6 c ase 3:p r i n tf（五教：這棟教

17、學(xué)樓應(yīng)該就是新建得，總體瞧上去還令人比較 滿意，周邊環(huán)境也挺好得n）ibreak；ca s e 4：oprintf （”新圖書館:雖然很小，但就是還過得去，學(xué)習(xí)環(huán)境很好，還有自 修室，閱覽室等學(xué)習(xí)場所n“）ibreak；case 5:oprintf （”老圖書館：很少去，聽說藏得書一般就是藝術(shù)類得書籍，建筑學(xué), 美術(shù)還有音樂方面等書籍n ”）； brea k :c a s e 6：print f C北區(qū)食堂：有時(shí)候味道太重，太咸，但就是平時(shí)味道不錯(cuò)，就 是學(xué)生就餐得主要餐廳。nn “）;break；case 7:sprint f （ ”南區(qū)食堂：味道偏清淡，三樓得南昌風(fēng)味得快餐店味道較好n ”

18、 ）； b r ea k ;6 c as e 8 :pr i ntf（”大學(xué)生活動(dòng)中心：在體育館旁邊，舉辦活動(dòng)得主要場所，每次 晚上路過那里都會聽到在舉辦活動(dòng)，很熱鬧n”）； break：cas e 9:沖門ntf （”圓形報(bào)告廳：太小了，如果要求全院得人都參加專業(yè)類得報(bào)告，則會有 很多晚來得人站在后面，沒有足夠得座位n”）； break；Mas e 1 0：pr i nt f （體育館：上體育課得主要場地，比較空曠，平時(shí)會有很多學(xué) 生在那里訓(xùn)練，打羽毛球得時(shí)候與練輪滑得時(shí)候最精彩了n”）；b reak;defaul t :Mpri n t f （”景點(diǎn)編號輸入錯(cuò)誤！請輸入l-】0得數(shù)字編號！

19、 nnH）； break; /* I nformati on*/v oi d s earchgraph（ve x t ice s g jnt m adj ma x adj）/ / 1 查找指定景點(diǎn)信息6i n t i = Lflag = 1 Jen; / / le n存儲要查詢得景點(diǎn)得序號cha r c h；pr i nt f（請輸入您要查詢得景點(diǎn)序號：n”）； /提示用戶輸入景點(diǎn)序號 sea n f （” d”，& 1 en）；getchar （） ;/獲取該序號對應(yīng)得景點(diǎn)名稱與景點(diǎn)信息P r i nt f （”此景點(diǎn)得名稱就是:”）；Name （le n ）；oprintf （”此景點(diǎn)得介

20、紹就是:”）；I n formation（l e n）;ddo oprintf（就是否繼續(xù)？ Y/N”）;Q scan f （n%c n，&ch）;0 g etchar（）；if（c h = Y | I ch = y ） 繼續(xù)。fla g = 1；Q M = 1；6 printf（請輸入您要查詢得景點(diǎn)序號:n）；0s canf （ “ d”,&len）；0 get c h a r （）；printf (”此景點(diǎn)得名稱就是：u ):oName (len)；P rint f (”此景點(diǎn)得介紹就是:“);。1 n f o rmation( 1 en);2 co n t i n u e ；o e 1

21、s eo flag = 0 ；/不繼續(xù)o b r e ak：jwhil e (1)；vo i d cr e at(Mat r ix _Gra p h *G)o i n t i, j；ofor (i= 1 ； i=N； i+) Gvexsi =i； / 初始化，0 號位不用。for (i= 1 ;iv=N； i +)of or ( j =1 ； j s i j =0;/初始值為 0.。G) s 12=2； G) s 1 9 =5； /表示景點(diǎn)一到景點(diǎn)二得距離就 是2。KJ) s 2 1 =2;G s2 3 =5;G s 2 4 =4； G-s2 9=6； /將景點(diǎn)間得距離初始化G-) s 32

22、=5： G-s34 =7;G s 3 7 = 5;G-s 3 9 = 6； G- s 3 1 0 =6；o G-s 4 2 =4； G-s4 6 =7： G-s 4 10=7；G-s 5 6 =4;Gs57=6;G- s 5 8 =8；G- s 64 =7： G-s6 5 =4;G-s6 7=3； Gs 610= 7；oGs 7 6=3； G- s7 8 =4 ； G- s 7 10 =6;G- s 8 5= 8 ； G-s 87=4;G-s 89=9；G-s 9 1=5;Gs 9 2 =6； Gs 9 3j =6； G-) s 9 8 =9； G-s 1 0 3 = 6 ； G-s 1 0

23、4 = 7 ； G-) s 1 0 6 =7 ； G- s 10 7 =6;fo r ( i =1； i s i j =0 )G-) s i j = MAX S i z e;/沒有被重新賦值得，表示兩景點(diǎn)之間/沒有路，用MAX表示無窮大.vo i d Mindistan c e(Matr i x _Grap h *G, i n t s , in t e)M n t i, j , u, c=l,t, v ;Mnt r N+l N+】；/用來存放路徑上得景點(diǎn).MntT N ,flag N, d N；ofor ( i =0； i=N ； i+)f or (j= 0 : jv=N； j +) r L

24、i j= 0 : / 初始值為 0.0 for (i=l ； iv二N;i+)0 T訂=-l； /初始值為一1。0 flagi =1;/初始值為 1。d 訂二MAX Size ；/路徑長度初始值為無窮大，用MAX表示.o flag s = 0 ;/修改標(biāo)識.while (c=N) “ t= MAXSiz e ；0f or( i = 1 ； is s i if(flag j & di +G- s Ti j s T i j ;v=j;0 o if (r v 0! = 1 )0002 oU= 1 ；3 0wh i le(rT 訂u !=0)0000 2 ow o o r v u =r Ti u： u

25、+： dddd 0曲V ll =V；ddddd aw 吐v 0=1;Q aTc = v；dflagv = 0 ;皿 “d c =t；Q回 C+；00 pri n t f ( n nThe pa t h i s:n(%d)”，s);j=l;h ile(re j !=0) 3 printf (n-(%d) r e j) ；j+； /顯示路徑。o pri n tf( n n ”)；i n t main ()/主函數(shù)“ n t i, j;M a tri x _Graph G;c rea t ( &G)；in t n= 0；景點(diǎn)數(shù)目ve x t i c e s g MAX Si z e ；/ 1保存頂點(diǎn)

26、及其信息Ed g eType eMAXedg； /保存邊及其信息a djmax adj; / /保存邊與定點(diǎn)ch a r c ho i c e = x*；wh i I e (1)0 2 c lrscr();prin t f( nntt t *校園導(dǎo)游系統(tǒng)*nn”)； /提示用戶正 確根據(jù)需要輸入數(shù)字Qpr i n tf(n t ttk文件讀入并創(chuàng)建校園圖:nn”);o pH n tf (” t tt2、查詢景點(diǎn)詳細(xì)信息:nn ” );dprintf (”tt t 3、查找兩景點(diǎn)間最短路徑：nn)；p rintf(” tttO、退出nnH);Mpr i nt f (” Please enter

27、you r cho i c e (03) :n H)；choi c e = g etchar ();switc h (ch o ic e )。case 1:Qclrs c r();0c rea t g ra p h (g,& n , e, &adj)；/ /創(chuàng)建圖(景點(diǎn)，景點(diǎn)數(shù)，邊，邊與景點(diǎn))。op rintf ( ”n打開文件錯(cuò)誤n ” );get char();break；2 c ase 2*:0 dclrs c r ()；0se a rchgraph (g, n, adj)； /查詢景點(diǎn)信息wgetc h ar ()；break；6 case 31Qc 1 r scr()；0 Oprin

28、 t f (2您目前得位置就是：n);scan f (” d,& i )；g e tchar ();0 Opri n tfC 2您得目得地就是：n”)；oscanf (%d , & j );o 0 g e tchar ()；6Mindistan c e(&G, i, j );/查找最短路徑Qg e tchar()；cr e at ( &G)；20 d o o Mp r i n tf(” 就是否繼續(xù)? Y/N u )；3叱 h arch；3 Mnt f la g = 1 ;3 s c a n f ( * %c”,&ch ); oooogetc h a r ( )； noif(ch = Y II

29、ch = y *) 就是否繼續(xù)000 Q w f 1 a g = 1；0 doo j = 1 ；6P r int f (”2您目前得位置就是:n )；ogoscanf(” %d”，&i);oowgetchar () ;/獲取輸入得數(shù)字對應(yīng)得地點(diǎn)a pr i ntf ( w 2您得目得地就是：n )；scanf (” d”，& j )；3getch ar ()；0 mM i n d is t a n c e (& G , i,j)； / /查找最短路徑ddge t char()：ere a t (&G)；0 co n ti n ue ；2Q elseoz flag = 0;不繼續(xù)皿 break：

30、while(l )；Q br e ak;6c a se 01d c 1 r scr()；a pr intf(” n * 按任意鍵退出* *)； setc h ar ()；wex i t (0)；wb r e a k ；d e f a u It：a p rintf (n輸入錯(cuò)誤，請重新輸入0-3之間得數(shù)字：n)；g e tchar ();d b r eak;0 g e tcha r ();4調(diào)試分析4、1測試數(shù)據(jù)當(dāng)起點(diǎn)輸入1 1終點(diǎn)輸入10時(shí)，景點(diǎn)不存在，程序提示重新輸入;當(dāng)起點(diǎn)輸入0 （教學(xué)主樓）終點(diǎn)輸入10時(shí)，終點(diǎn)景點(diǎn)不存在，程序提示重新輸入；當(dāng)起點(diǎn)輸入 3 （五教）終點(diǎn)輸入4 （新圖書館）時(shí)，景點(diǎn)都存在，屏幕打印出兩景點(diǎn)最短路徑： 五教一新圖書館，最短路徑約為6當(dāng)輸入1時(shí)，則按景點(diǎn)編號查詢，當(dāng)輸入6 （北區(qū)食堂）時(shí)，屏幕上打印出此景點(diǎn)信息：有時(shí)候味道太重，太咸，但就是