xxxxxxxxxxx姓名-芝罘區(qū)主要景點公交車查詢

1、魯東大學 數學與信息學院20092010學年第1學期數據結構專題設計課程論文課程號：2102791任課教師陳軍成績號學 -級班二二二二二二二二業(yè)專下以線此在寫字文將須生學 線封密論文題目：（可指定題目，也可說明題目范圍。）從給出的參考選題中選（或自選）一個能體現數據結構課程特點的課題， 用C語言（TC/VC+）編程實現所述功能，用論文形式描述整個工作。詳見數 據結構專題設計課程任務和要求文檔。論文要求：（對論文題目、內容、行文、字數等作出判分規(guī)定）按右邊給定的模板要求寫作，字數4000字以上（不含附錄）。評分采用五級制：優(yōu)秀、良好、中等、及格、不及格。評分依據包括題目難易程度、程序運行情況、數

2、據結構和算法設計合理與 否、算法注釋的清晰程度；論文的規(guī)范程度、撰寫質量（條理清晰，內容充實, 文字通順，圖表恰當）；總結的深刻程度、工作量和創(chuàng)新性；交作業(yè)的及時程度、 獨立完成情況，以及其它參考因素。不同同學可以選擇同類題目，但在具體功能、程序代碼、論文寫作上都要 有所不同，若發(fā)現雷同，均判為不及格。教師評語：-教師簽字：I T2009年11月2日芝果區(qū)主要景點公交車查場1、引言隨著新學期的開始，魯東大學又迎來了新一屆同學。為了大一新生能夠迅速熟悉 煙臺芝策區(qū)，適應煙臺生活，本文在所學圖論知識的基礎上建立了一個芝策區(qū)主要景 點公交查詢程序。因為主要是為魯東大學的同學服務，公交路線的起始點都是

3、魯東大 學。并給出了相關景點的粗略信息，以及從魯東大學到景點的站點數。新同學可以通 過此程序查詢芝策區(qū)主要景點信息及可以乘坐哪路公交車、及到達該景點經過車站數 最少的公交車。2、需求分析根據學生平日出游參觀景點的特點，主要選取了芝策區(qū)六個主要景點區(qū)。此外 考慮經過魯東大學的公交車主要有33路、46路、50路、52路公交車，將各路公交 車在魯東大學的起點及六個主要景區(qū)的代表景點，抽象成一個無向帶權圖。圖中分別 頂點表示33路、46路、50路、52路公交車在魯東大學東門、南門或是西門起始站 點；并且頂點存放起始站點和景點的編號、名稱、簡介等信息，圖中的邊表示分別從 起始站點到所去景點乘不同公交車經

4、過的站點數，并作為路徑長度。本程序的目的是為來魯東大學新生提供煙臺芝策區(qū)主要景點相關信息及公交 車的查詢，通過程序可以查詢：從魯東大學到某一景點所需要乘坐的公交車，及經過的站點數。查詢各個景點的信息。到達某一景點最優(yōu)公交線路。查詢經過魯東大學的不同公交車的公交線路。3經過魯東大學的公交路線及主要景點圖如下。魯東大學46路公交車52路公交車50路公交車3、概要設計3.1抽象數據類型圖的定義本論文的程序設計，主要是在圖論知識的基礎上進行設計，因此首先給出抽象類 型圖的定義，以便結合實際情況進行圖的構造。ADT Graph 數據對象V： V是具有相同特性的數據元素的集合，稱為頂點集。數據關系R：R=

5、VRVR=( (v, w) | v, wEV, (v, w)表示v和w之間存在路徑基本操作P：CreatGraph (&G, V, VR)初始條件：V是圖的頂點集，VR是圖中邊的集合。操作結果：按V和VR的定義構造圖G。DestroyGraph(&G)初始條件：圖G存在。操作結果：銷毀圖G。Locate Vex (G, u)初始條件：圖G存在，u和G中頂點有相同特征。操作結果：若G中存在頂點u,則返回該頂點在圖中位置；否則返回其 它信息。Get Vex (G, v)初始條件：圖G存在，v是G中某個頂點。操作結果：返回v的信息。FirstEdge (G, v)初始條件：圖G存在，v是G中某個頂點

6、。操作結果：返回依附于v的第一條邊。若該頂點在G中沒有鄰接點，則 返回“空。NextEdge (G, v, w)初始條件：圖G存在，v是G中某個頂點，w是v的鄰接頂點。操作結果：返回依附于V的(相對于W的)下一條邊。若不存在，則返 回“空”。InsertVex(&G, v)初始條件：圖G存在，v和圖中頂點有相同特征。操作結果：在圖G中增添新頂點V。DeleteVex(&G, v)初始條件：圖G存在，v是G中某個頂點。操作結果：刪除G中頂點v及其相關的邊。InsertEdge (&G, v, w)初始條件：圖G存在，v和w是G中兩個頂點。操作結果：在G中增添邊(v, w) oDeleteEdge

7、 (&G, v, w)初始條件：圖G存在，v和w是G中兩個頂點。操作結果：在G中刪除邊(v, w) oGetShortestPath (G, st, nd, &Path)初始條件：圖G存在，st和nd是G中兩個頂點。操作結果：若st和nd之間存在路徑，則以Path返回兩點之間一條最 短路徑，否則返回其它信息。 ADT Graph3. 2模塊設計2. 1本程序包含的模塊主程序模塊void main ()初始化;do 接受命令(輸入景點信息或輸出公交路線)；處理命令； while (命令”！=退出)；景點信息模塊；將經過魯東大學的公交車50路、52路、33路、46路公交車分別編號為0、1、2、3。

8、對景點進行編號，構成無向圖的頂點，并將起始站點和景點的編號、名稱、 簡介等信息存放在頂點。將兩景點之間公交車所經過的站點數作為邊的賦權值。景點公交路線選擇模塊約定兩景點之間公交車經過的車站數越少，兩景點之間越近。根據圖的最短 路徑算法，求出兩景點之間的最少車站數。如果兩景點之間不能通過經過魯東大學的 公交車到達，為方便編程，不考慮乘坐其他公交車，而且根據學生的出游特點，到達 某一景點時不考慮步行所經過的路程只考慮公交車經過的車站數。輸出模塊輸出符合查詢的條件的公交路線或是景點信息。3.2.2程序流程圖主程序景點公交路無向圖的定義景點信息模塊線選擇模 輸出模塊塊4、詳細設計及實現4. 1主程序模

9、塊void main () do ck=Menu ();switch(ck) case r :Path ();break;case 2 :search ();break;，o5case 3 :narrate ();case 4 :ShortestPath ();break;4. 2景點信息模塊構造無向圖：頂點、邊和圖的類型如下： typedef struct ArcCell int adj;ArcCell:typedef struct VertexTypeint number:char *sight;char description:VertexType;typedef structVerte

10、xType vexNUM:ArcCell arcsNUMNUM: int vexnum, arcnum;MGraph;4. 3景點公交路線選擇模塊/相鄰接的景點之間的站點數/定義邊的類型景點編號景點名稱景點描述定義頂點的類型圖中的頂點，即為景點圖中的邊，即為景點間的站點數頂點數，邊數/定義圖的類型迪杰斯特拉偽碼算法：Void shortestPath (int num)迪杰斯特拉算法最短路徑函數num為入口點的編號for (v=0;vNUM;v+) finalv=0:Dv=G. arcsnumv. adj;for(w=0;wNUM;w+)Pv w=0;if (Dv20000) P v num=

11、l:Pv v = l;D num=0;finalnum=l:for(i=0;iNUM;+i) min二Max;for(w=0;wNUM;+w)if (!finalw)if(Dwmin) v=w;min=Dw;finalv=l:for(w=0;wNUM;+w)if (!finalw&(min+G. arcsvw. adj)Dw)/不在s集合，并且比以前所找到的路徑都短就更新當前路徑Dw=min+G. arcsvw. adj;for(t=0;tNUM;t+)Pw t=Pv t:pw w = l;4.4公交路線輸出模塊利用switch函數、及調用滿足查詢條件的各個函數，輸出公交路線或是景點信 息。例

12、如：當查詢經過魯東大學主要有哪些公交路線時，輸出函數如下所示。void display()printf （/zttt主要有以下公交路線：）；printf（/zn 50路公交路線：魯東大學東門-一煙臺汽車站一-火車站-一虹口賓館 山東工冏學院;n）；printf（/z52路公交路線：魯東大學一-中心廣場 -一建設銀行-一山東工商學院;n）；printf （41路公交路線:魯東大學煙臺汽車站；n）；printf （33路公交路線:魯東大學南門-山東工商學院;n）；printf （46路公交路線：魯東大學 煙臺毓璜頂醫(yī)院-濱海廣場。n）；5、調試分析5. 1調試分析本題主要是在圖論知識的基礎上進行設

13、計，由于在學習圖論知識時，只掌握了 圖論的理論知識，了解圖論的有關算法思想而對算法的實現未進行上機實際操作，因 此在進行本程序設計過程當中走了很多彎路。對例如混淆了 ”和的用法， 在初始化景點的信息時，導致了大量錯誤。在對景點進行初始化建立抽象無向圖時，由于頂點的選擇失誤，導致最后結 果很不符合實際情況。經過多次操作實驗最確定了將不同公交車起始站點也進行編號 的方法，解決從魯東大學出發(fā)到同一景點不同公交車到達經過的景點的車站數不同的 問題。在解決從魯東大學出發(fā)到同一景點公交路線問題時，由于將不同路公交車分 別設置成了不同頂點，因此從魯東大學大學出發(fā)到某一景點的經過車站數是一個定 值，沒有了最優(yōu)

14、公交路線比較意義。經過調試和改進，最終加上了最優(yōu)公交路線模塊, 但具體算法過于繁瑣。4在調用函數時，出現問題基礎知識錯誤，函數未進行定義。因此函數的基本 知識掌握還不夠扎實，有待進一步提周。5. 2調試結果調試結果用圖表?。?.初始界面如圖1所示。歡迎使用芝累區(qū)主要景點公交車咨詢要車車車車站S:學：頂 主交交交交車：場 公公公公洱站廣工廣毓 路路跳路臺東山臺 駕斗呻ffi有以下查詢方式:查查景經退 1,2,3,4,5詢詢點過出點公交線路優(yōu)路線的查詢 東大學公交路線信輸入您的選:2查詢景點公交線路。例如 查50路是否經過煙臺汽車站、中心廣場。查詢結果如圖2、3所示。歡迎使用芝琴區(qū)主要景點公交車咨

15、詢要車車車車站5:學：頂 主交交交交車：場商場瑞 公公公公洱站廣工廣毓 路路路路臺蕾東心臺 5052碧叫灘 公交車v： 0請選擇景點編號: 4從5。路公交車到煙臺汽車站的公交路線是所需車站數為4.50路公交車一煙臺汽車站請按回車鍵繼續(xù).圖2從魯東大學坐50路可到煙臺汽車站。歡迎使用芝策區(qū)主要景點公交車咨詢-6院B醫(yī) 軍車車車站S:學：頂 交交交交車公公公公誨站廣工廣毓 路路路路臺WK東、隊臺 駕46呻沸 公交車0請選擇景點編號（49）: 8從5。路公交車到中心廣場的公交路線是所需車站數為20000. 5路公交車請按回車鍵繼續(xù)一一一圖3從魯東大學坐50路不能到中心廣場歡迎使用芝栗區(qū)主要景點公交車

16、咨詢好主要景點名稱的編號列表:F0路公交車：0嚙2露公交車：1”46路公交車：233路公交車：3犧臺汽車站：4L火車站：5T賓海廣場：61山東工商學院：?呻心廣場：8煙臺毓璜頂醫(yī)院：?主要有以下公交路線：線線線線線路路路路路交交交交交.4m#.4.k路路路路路0 2 13 65 5 4 3 4山東工商學院;魯東大學東門一期臺汽車站-一火車站一-虹口賓館魯東大學中心產場建設銀行山東工商學院;膏東大生_堆臺汽王站；毒轉曹舀矗M矗：濱海廣場.請按回車鍵繼續(xù).圖4經過路東大學的主要公交路線6、結論及體會1）考慮到只為魯東大學新生熟悉煙臺地區(qū)環(huán)境的目的，加上編寫時間有限，本 論文所設計的公交查詢系統涉及

17、的站點較少，且只考慮了經過路東大學的公交車輛, 因此相對于實際情況程序設計所取數據較少。但本文涉及到的算法思想有很大應用價 值。2）通過此次公交查詢論文設計，進一步加深了相關圖論的知識，將所學的理論 知識結合實際問題進行了應用。對于圖的頂點定義，邊的賦權值有了進一步的理解。3）由于自己所學圖論知識過少，該方面上機動手操作能力不強，在本課題設 計過程中出現了很多問題。但正是通過解決這些問題使自己的程序編寫及調試識錯能 力有了很大提周。4）在程序調試過程中，同學給與了很大幫助，提高了同學之間的團結合作能力。參考文獻嚴蔚敏，吳偉民.數據結構題集（C語言版）.北京：清華大學出版社，1999.徐孝凱.數

18、據結構課程實驗.北京：清華大學出版社，2002. 公園導游圖-數據結構課程設計源代碼，2009年06月15日，星期一 17:54博 客.附錄#include string.h#include stdio.h#include malloc.hinclude stdlib.h#define Max 20000#define NUM 10typedef struct ArcCell int adj; ArcCell;typedef struct fertexType int number;char * sight;char * description;VertexType;typedef struc

19、t VertexType vexNUM;ArcCell arcs NUM NUM;離int vexnum,arcnum;MGraph;MGraph G;int PNUMNUM;long int DNUM;int x9=0;void CreateUDN(int v,int a);void narrate();void ShortestPath(int num);void output(int sight 1,int sight2);char Menu();void search();char SearchMenu();void better();相鄰接的景點之間的路程定義邊的類型景點編號景點名稱

20、景點描述定義頂點的類型圖中的頂點，即為景點圖中的邊，即為景點間的距頂點數，邊數定義圖的類型把圖定義為全局變量/助變量存儲最短路徑長度造圖函數說明函數/最短路徑函數俺俞出函數主菜單/查詢景點信息查詢子菜單哈密爾頓圖的遍歷/顯示遍歷結果void NextValue(int);voiddisplay ();void main()主函數int v0,vl;char ck;system(color 3A);/CreateUDN(NUM,ll);do ck=Menu();switch(ck) case T:system(cls);narrate();printf(nnttt 公交車號(03):);scan

21、f(%d,&v0);printf(ttt請選擇景點編號(49)：);scanf(%d,&vl);ShortestPath(vO);output(vO,vl);計算兩個景點之間的最短路徑俺俞出結果printf(nntttt 請按回車鍵繼續(xù).An”);getchar();getchar();break;case 2:search。；break;case 3:system(cls);narrate();x0=l;/ HaMiTonian(l);better();printf(nntttt 請按回車鍵繼續(xù).An”);break;case 4:system(cls);narrate();xO=l;/ H

22、aMiT onian(l);display ();printf(nntttt 請按回車鍵繼續(xù).An”);getchar();getchar();break;；while(ck!=e);/mainchar Menu()主菜單char c;int flag;do Aag=l;system(cls);narrate();printf(tt有以下查詢方式printf(nttt |1 n);printf(ttt | n); TOC o 1-5 h z printf(ttt |1、查詢景點公交線路In，printf(ttt |2、查詢景點信息|n);printf(ttt |3、景點最優(yōu)路線的查詢In，pr

23、intf(ttt |4、經過魯東大學公交路線|n);printf(ttt | e、退出| n);printf(ttt |n);printf(ttt 11n);printf(tttt請輸入您的選擇：， scanf(%c,&c);if(c=Tllc=2llc=3llc=4llc=8)flag=O;while(flag);return c;/Menuchar SearchMenu()查詢子菜單char c;int flag;do Aag=l;system(cls);narrate();pnntf( nttt |1 n);printf(ttt |1 n);printf(ttt |1、按照景點編號查詢I

24、 n);printf(ttt |2、按照景點名稱查詢| n);printf(ttt |e、返回I n);printf(ttt |1 n);printf(ttt 11 n);printf(tttt請輸入您的選擇：， scanf(%c,&c);if(c=Tllc=2llc=)flag=O;while(flag);return c;/SearchMenuvoid search()查詢景點信息int num;int i;char c;char name 20;do system(cls);c=SearchMenu();switch (c)case 1:system(cls);narrate();pri

25、ntf(nntt請輸入您要查找的景點編號：， scanf(%d,&num);for(i=0;ivNUM;i+)if(num=G vex i .number) printf(niittt您要查找景點信息如下:)； printf(nnttt%-25 snn ,Gvex i .description); printf(nttt 按回車鍵返回.”)； getchar();getchar(); break;if(i=NUM) printf(nnttt 沒有找到！ ”)；printf(nnttt 按回車鍵返回.”)； getchar();getchar();break;case 2:system(cls)

26、;narrate();printf(nntt請輸入您要查找的景點名稱：)； scanf(%s,name);for(i=0;ivNUM;i+)if(! strcmp(name,Gvexi .sight) printf(niittt您要查找景點信息如下:)； printf(nnttt%-25 snn ,Gvex i .description); printf(nttt 按回車鍵返回.”)； getchar();getchar();break;if(i=NUM)printf(nnttt 沒有找到！ ”)；printf(nnttt 按回車鍵返回 getchar();getchar();break;wh

27、ile(c!=e);/searchvoid CreateUDN(int v,int a)造圖函數int i,j;初始化結構中的景點數和邊數Gvexnum=v;Garcnum=a;for(i=0;iGvexnum;+i) G.vexi.number=i;初始化每一個景點的編號/*J始景點名 景點才苗*/Gvex0.sight=50 路公交車”；G vex 0 .description=魯東大學東門”；Gvexl.sight=52 路公交車”；Gvexl.description=#東大學西門，南門，東門乘車均可；Gvex2.sight=46 路公交車”；Gvex 2 .description魯東大

28、學東門乘車”；Gvex3.sight=33 路公交車”；Gvex 3 .description=魯東大學南門乘車；Gvex4.sight=ffi 臺汽車站;Gvex 4 .description= 途汽車站,三站科技市場，購物；Gvex5.sights火車站”；Gvex5.description=煙臺火車站，附近有北馬路汽車站Gvex6.sight=濱海廣場；Gvex6.description=50路虹口賓館,52路建設銀行下車”;Gvex 7. sights山東工商學院；Gvex7 .description=附近還有煙臺大學，濱州醫(yī)學院；Gvex8.sights中心廣場”；Gvex8 .de

29、scription= 近有沃爾瑪，大潤發(fā)超市；購物;Gvex9.sight=ffi臺毓璜頂醫(yī)院；Gvex9 .description=看病，治療”；/*這里把所有的邊假定為20000,含義是這兩個景點之間是不可到達/ /for(i=0;iGvexnum;+i)for(j=0;j Gvexnum ;+j)Garcsij.adj=Max;Garcs0 4. adj=4;Garcs05.adj=6;Garcs06.adj=12;Garcs07.adj=23;Garcsl6.adj=10;G arcs 1 7. adj=24;Garcsl8.adj=6;G arcs 2 6. adj=21;Garcs

30、29.adj=16;Garcs37.adj=17;/CreateUDN void narrate()說明函數int i,k=0;printf(”nt*歡迎使用芝策區(qū)主要景點公交車咨詢* *Yq） printf（tiT）:printf（tttt主要景點名稱的編號列表:n，printf（ ttt4% 050 路公交車:0n）;printf（ ttt4% 1 52 路公交車：ln）;printf（ ttt4% 246 路公交車:2 n）;printf（ ttt4% 333 路公交車：3 n）;printf（ ttt4% 4煙臺汽車站：4n）;printf（ ttt4% 5火車站：5n）;printf

31、（ ttt4% 6濱海廣場：6n）;printf（ ttt4% 7山東工商學院:7n）;printf（ ttt4% 8中心廣場：8n）;printf（ ttt4% 9煙臺毓璜頂醫(yī)院：9n）;printf（ tn）;/narratevoid ShortestPath（int num）迪杰斯特拉算法最短路徑函數int v,w,i,t;int final NUM;int min;for（v=0;vNUM;v+） final v=0;Dv=Garcs num v .adj;for（w=0;wNUM;w+） Pvw=0;num為入口點的編號i、w和v為計數變量假設從頂點num到頂點v沒有最短路徑將與之相關的權值放入D中存放/設置為空路徑if（Dv 20000）Pv num=l; Pvv=l;存在路徑存在標志置為一自身到自身Dnum=O;final num=1;初始化num頂點屬于S集合/*開始主循環(huán)，每一次求得num到某個頂點的最短路徑，并將其加入到S集合 */其余Gvexnum-1個頂點當前所知離頂點num的最近距離w頂點在v-s中/w頂點離num頂點更近/M num頂點更近的v加入到s集合更新當前最短路