魯東大學到附近主要休閑場所的公交車查詢.doc

學院_專業(yè)_班級_本專 學號_姓名_ 密封線 學生須將文字寫在此線以下魯東大學 數(shù)學與信息學院 20102011學年第1學期數(shù)據(jù)結構專題設計課程論文課程號：2102791 任課教師 成績 論文題目：（可指定題目，也可說明題目范圍。）從給出的參考選題中選（或自選）一個能體現(xiàn)數(shù)據(jù)結構課程特點的課題，用C語言（TC或VC+）編程實現(xiàn)所述功能，用論文形式描述整個工作。詳見數(shù)據(jù)結構專題設計 課程任務和要求文檔。論文要求：（對論文題目、內(nèi)容、行文、字數(shù)等作出判分規(guī)定。）按右邊給定的模板要求寫作，字數(shù)4000字以上（不含附錄）。評分采用五級制：優(yōu)秀、良好、中等、及格、不及格。評分依據(jù)包括題目難易程度、程序運行情況、數(shù)據(jù)結構和算法設計合理與否、算法注釋的清晰程度；論文的規(guī)范程度、撰寫質(zhì)量（條理清晰，內(nèi)容充實，文字通順，圖表恰當）；總結的深刻程度、工作量和創(chuàng)新性；交作業(yè)的及時程度、獨立完成情況，以及其它參考因素。不同同學可以選擇同類題目，但在具體功能、程序代碼、論文寫作上都要有所不同，若發(fā)現(xiàn)雷同，均判為不及格。教師評語： 教師簽字： 2010 年 11 月 2 日魯東大學到附近主要休閑場所的公交車查詢1、引言當初剛上大一的時候，什么也不知道，出門坐車得問個千遍萬遍，才敢坐車。那種無助的感覺到現(xiàn)在還記憶猶新。新學期的開始，魯東大學又迎來了新一屆同學。為了減少學弟學妹們的不適感，我利用學習過的數(shù)據(jù)結構知識，在本文中建立了一個芝罘區(qū)主要休閑場所查詢程序并給出了相關場所的粗略信息，以及從魯東大學到其地點的站點數(shù)。新同學可以通過此程序查詢芝罘區(qū)主要休閑場所信息及可以乘坐哪路公交車、及到達該場所經(jīng)過車站數(shù)最少的公交車。2、需求分析1.經(jīng)過一定的調(diào)查詢問得知同學們平日所到之處大致相同，考慮到經(jīng)過魯東大學的公交車主要有33路、41路、46路、50路、52路公交車，將各路公交車在魯東大學的起點及主要休閑場所的代表地點，抽象成一個無向帶權圖。圖中分別頂點表示33路、41路、46路、50路、52路公交車在魯東大學東門、南門或是西門起始站點；并且頂點存放起始站點和各場所的編號、名稱、簡介等信息，圖中的邊表示分別從起始站點到所去地點乘不同公交車經(jīng)過的站點數(shù)，并作為路徑長度。輸入相應選擇后，會得到自己所需要乘坐的的公交車，站點等等2.本程序的目的是為魯東大學新生提供煙臺芝罘區(qū)主要休閑場所相關信息及公交車的查詢，通過程序可以查詢： （1）從魯東大學到某一娛樂場所所需要乘坐的公交車，及經(jīng)過的站點數(shù)。（2）查詢各個地點的信息。（3）到達某一娛樂場所最優(yōu)公交線路。（4）查詢經(jīng)過魯東大學的不同公交車的公交線路。3. 經(jīng)過魯東大學的公交路線及主要休閑場所圖如下：3、概要設計（或總體設計）3.1數(shù)據(jù)結構描述本論文的程序設計，主要是在圖論知識的基礎上進行設計，因此首先給出抽象類型圖的定義，以便結合實際情況進行圖的構造。以下是查詢的有關抽象類型圖的定義：ADT Graph 數(shù)據(jù)對象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點集。 數(shù)據(jù)關系R： R=VR VR=(v,w)|v，wV,(v,w)表示v和w之間存在路徑 基本操作P： CreatGraph(&G,V,VR) 初始條件：V是圖的頂點集，VR是圖中邊的集合。 操作結果：按V和VR的定義構造圖G。 DestroyGraph(&G) 初始條件：圖G存在。 操作結果：銷毀圖G。 LocateVex(G,u) 初始條件：圖G存在，u和G中頂點有相同特征。 操作結果：若G中存在頂點u，則返回該頂點在圖中位置；否則返回其它信息。 GetVex(G,v) 初始條件：圖G存在，v是G中某個頂點。 操作結果：返回v的信息。 FirstEdge(G,v) 初始條件：圖G存在，v是G中某個頂點。 操作結果：返回依附于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)。 DeleteEdge(&G,v,w) 初始條件：圖G存在，v和w是G中兩個頂點。 操作結果：在G中刪除邊(v,w)。 GetShortestPath(G,st,nd,&Path) 初始條件：圖G存在，st和nd是G中兩個頂點。 操作結果：若st和nd之間存在路徑，則以Path返回兩點之間一條最短路徑，否則返回其它信息。 ADT Graph3.2模塊設計3.2.1本程序包含的模塊(1)主程序模塊void main( ) 初始化； do 接受命令（輸入休閑場所信息或輸出公交路線）； 處理命令； while(“命令”!=”退出”); (2)各場所信息模塊 將經(jīng)過魯東大學的公交車50路、52路、46路、33路、41路公交車分別編號為0、1、2、3、4。對各休閑場所進行編號5-11，構成無向圖的頂點，并將起始站點和各場所的編號、名稱、簡介等信息存放在頂點。將兩地之間公交車所經(jīng)過的站點數(shù)作為邊的賦權值。(3)休閑場所公交路線選擇模塊 約定兩地點之間公交車經(jīng)過的車站數(shù)越少，兩地點之間距離越近。根據(jù)圖的最短路徑算法，求出兩地之間的最少車站數(shù)。如果兩地之間不能通過經(jīng)過魯東大學的公交車到達，為方便編程，不考慮再乘坐其他公交車的情況，而且根據(jù)大多數(shù)學生的出游特點，到達某一場所時不考慮步行所經(jīng)過的路程只考慮公交車經(jīng)過的車站數(shù)。(4)輸出模塊 輸出符合查詢的條件的公交路線或是景點信息。3.2.2程序流程圖3.2.3程序操作流程圖4、詳細設計及實現(xiàn)4.1主程序模塊void main()/主函數(shù) do ck=Menu();switch(ck) case 1:narrate();ShortestPath(v0); /計算兩地點之間的最短路徑getchar();getchar();break;case 2:search();break; case 3:narrate(); better();getchar();getchar();break;case 4:system(cls);narrate(); display();getchar();getchar();break;while(ck!=e); /main4.2休閑場所信息模塊構造無向圖： 頂點、邊和圖的類型如下： typedef struct ArcCell int adj;/相鄰接的地點之間的站點數(shù)ArcCell;/定義邊的類型typedef struct VertexType int number;/地點編號 char *sight;/場所名稱 char *description;/地點描述VertexType;/定義頂點的類型typedef struct VertexType vexNUM;/圖中的頂點，即為休閑場所 ArcCell arcsNUMNUM;/圖中的邊，即為休閑場所間的站點數(shù) int vexnum,arcnum;/頂點數(shù)，邊數(shù)MGraph;/定義圖的類型4.3各休閑場所公交路線選擇模塊迪杰斯特拉偽碼算法：Void shortestPath(int num)/迪杰斯特拉算法最短路徑函數(shù)num為入口點的編號for(v=0;vNUM;v+) finalv=0;Dv=G.arcsnumv.adj;for(w=0;wNUM;w+)Pvw=0;if(Dv20000) Pvnum=1;Pvv=1; Dnum=0;finalnum=1; for(i=0;iNUM;+i) min=Max;for(w=0;wNUM;+w)if(!finalw)if(Dwmin) v=w;min=Dw; finalv=1;for(w=0;wNUM;+w)if(!finalw&(min+G.arcsvw.adj)Dw)/不在s集合，并且比以前所找到的路徑都短就更新當前路徑Dw=min+G.arcsvw.adj;for(t=0;tNUM;t+)Pwt=Pvt;Pww=1; 4.4公交路線輸出模塊利用switch函數(shù)、及調(diào)用滿足查詢條件的各個函數(shù)，輸出公交路線或是休閑場所信息。 例如：當查詢經(jīng)過魯東大學主要公交路線的最優(yōu)路線時，輸出函數(shù)如下所示。void better() printf( ttt最優(yōu)公交路線:);printf(n 到山東工商學院及附近高校坐33路公交到山東工商學院站點下車（約經(jīng)過10個站點）;n);printf( 到濱海廣場坐52路公交到建設銀行站點下車（約經(jīng)過17個站點）;n);5、調(diào)試分析5.1調(diào)試分析1.在建立抽象無向圖時，由于對無向圖的知識很不了解，查閱了大量資料，也做了很多無用功，而且由于頂點的選擇失誤，導致最后結果很不符合實際情況。經(jīng)過多次操作實驗最確定了將不同公交車起始站點也進行編號的方法，解決從魯東大學出發(fā)到同一景點不同公交車到達經(jīng)過的景點的車站數(shù)不同的問題。在最終總體調(diào)試程序時曾出現(xiàn)以下簡單錯誤：2.原因是：符號c使用之前未進行定義；3.原因是：程序中定義了i，多余；4.運行程序后，選擇3號查詢方式，并未出現(xiàn)所要查詢的結果。原因是：在編寫case 1，3，4時忘記引用函數(shù)：getchar()來輸出字符；5.2調(diào)試結果1.初始界面如下圖所示：2. 查詢休閑場所公交路線圖： 例如 查33路是否能到達山東工商學院，煙大等學校，查詢結果如下圖所示：3.最優(yōu)路線查詢結果如下圖所示：6、結論及體會1) 因為編寫程序時只考慮了新一屆魯大學子不熟悉芝罘區(qū)主要休閑場所的情況。再者，編寫時間有限，本論文所設計的公交查詢系統(tǒng)涉及的站點很少，而且只涉及了經(jīng)過魯東大學的幾輛公交車。另外，同學們?nèi)サ牡胤讲⒉皇呛芏?，本論文只是選取了比較常去是的幾個地方。雖然程序簡單，涉及實際數(shù)據(jù)較少，但也有其實用價值。有了這個程序，新生們可以大體的了解魯大周圍的幾個常去地點，而且不至于坐錯公交車。本文涉及的算法思想也有比較大的可取價值。 2) 通過此次公交查詢論文的設計，我進一步加深了無向帶權圖的知識，將所學的理論知識結合實際問題進行了應用，活學活用，對于圖的頂點定義，邊的賦權值有了進一步的理解。對于數(shù)據(jù)結構的程序設計也有了進一步的了解，并不是初學時的得過且過，朦朦朧朧。 3） 由于自己所學圖論知識過少，程序代碼方面并不是很精通，上機動手操作能力不強，在本課題設計過程中出現(xiàn)了很多問題。但正是通過解決這些問題使自己的程序編寫及調(diào)試識錯能力有了很大提高。對代碼的認識也不再是僅止于英文字母，學會了基本的程序編寫。增強了動手解決問題的能力。4）在程序調(diào)試過程中，曾出現(xiàn)幾個錯誤問題，有代碼寫錯的，也有直接忘記寫的，同學給與了很大幫助，提高了同學之間的團結合作能力。參考文獻1 嚴蔚敏，吳偉民數(shù)據(jù)結構題集（C語言版）北京：清華大學出版社，1999.2 徐孝凱. 數(shù)據(jù)結構課程實驗. 北京：清華大學出版社，2002. 3 20092010學年第1學期xxxxxxxxxxx姓名-芝罘區(qū)主要景點公交車查詢.doc附錄#include string.h #include stdio.h #include malloc.h#include stdlib.h#define Max 20000#define NUM 12typedef struct ArcCell int adj;/相鄰接的場所之間的路程ArcCell;/定義邊的類型typedef struct VertexType int number;/休閑場所編號char *sight;/地點名稱char *description;/地點描述VertexType;/定義頂點的類型typedef struct VertexType vexNUM;/圖中的頂點，即為休閑場所ArcCell arcsNUMNUM; /圖中的邊，即為場所間的距離int vexnum,arcnum;/頂點數(shù)，邊數(shù)MGraph;/定義圖的類型MGraph G;/把圖定義為全局變量int PNUMNUM;long int DNUM;/輔助變量存儲最短路徑長度int x11=0; void CreateUDN(int v,int a); /造圖函數(shù)void narrate();/說明函數(shù)void ShortestPath(int num);/最短路徑函數(shù)void output(int sight1,int sight2); /輸出函數(shù)char Menu();/主菜單void search();/查詢休閑場所信息char SearchMenu();/查詢子菜單void better();/哈密爾頓圖的遍歷void NextValue(int); void display();/顯示遍歷結果void main()/主函數(shù) int v0,v1;char ck;CreateUDN(NUM,12);do ck=Menu();switch(ck) case 1:system(cls);narrate();printf(nnttt公交車號(04)：);scanf(%d,&v0);printf(ttt請選擇景點編號（512）：);scanf(%d,&v1);ShortestPath(v0); /計算兩個地點之間的最短路徑output(v0,v1);/輸出結果printf(nntttt請按回車鍵繼續(xù).n);getchar();getchar();break;case 2:search();break; case 3: system(cls);narrate();x0=1; /HaMiTonian(1); better();printf(nntttt請按回車鍵繼續(xù).n);getchar();getchar();break;case 4:system(cls);narrate();x0=1; /HaMiTonian(1); display(); printf(nntttt請按回車鍵繼續(xù).n);getchar();getchar();break;while(ck!=e); /mainchar Menu()/主菜單char c;int flag;do flag=1;system(cls);narrate();printf( tt有以下查詢方式:);printf(nttt n);printf(ttt n);printf(ttt 1、查詢休閑場所公交線路 n);printf(ttt 2、查詢休閑場所信息 n);printf(ttt 3、各地點最優(yōu)路線的查詢 n);printf(ttt 4、經(jīng)過魯東大學公交路線 n);printf(ttt e、退出 n);printf(ttt n);printf(ttt n);printf(tttt請輸入您的選擇：);scanf(%c,&c);if(c=1|c=2|c=3|c=4|c=e)flag=0;while(flag);return c;/Menuchar SearchMenu()/查詢子菜單char c;int flag;do flag=1;system(cls);narrate();printf(nttt n);printf(ttt n);printf(ttt 1、按照休閑場所編號查詢 n);printf(ttt 2、按照休閑場所名稱查詢 n);printf(ttt e、返回 n);printf(ttt n);printf(ttt n);printf(tttt請輸入您的選擇：);scanf(%c,&c);if(c=1|c=2|c=e)flag=0;while(flag);return c;/SearchMenuvoid search() /查詢休閑場所信息int num;int i;char c;char name20;do system(cls);c=SearchMenu();switch (c) case 1: system(cls);narrate();printf(nntt請輸入您要查找的地點編號：);scanf(%d,&num);for(i=0;iNUM;i+) if(num=G.vexi.number) printf(nnttt您要查找地點信息如下:);printf(nnttt%-25snn,G.vexi.description);printf(nttt按回車鍵返回.);getchar();getchar();break;if(i=NUM) printf(nnttt沒有找到！);printf(nnttt按回車鍵返回.);getchar();getchar();break;case 2:system(cls);narrate();printf(nntt請輸入您要查找的地點名稱：);scanf(%s,name);for(i=0;iNUM;i+) if(!strcmp(name,G.vexi.sight) printf(nnttt您要查找地點信息如下:);printf(nnttt%-25snn,G.vexi.description);printf(nttt按回車鍵返回.);getchar();getchar();break;if(i=NUM) printf(nnttt沒有找到！);printf(nnttt按回車鍵返回.);getchar();getchar();break;while(c!=e);/searchvoid CreateUDN(int v,int a) /造圖函數(shù)int i,j;G.vexnum=v;/初始化結構中的休閑場所數(shù)和邊數(shù)G.arcnum=a;for(i=0;iG.vexnum;+i) G.vexi.number=i; /初始化每一個地點的編號/*初始化每一個地點名及其信息描述*/G.vex0.sight=50路公交車;G.vex0.description=魯東大學東門;G.vex1.sight=52路公交車;G.vex1.description=魯東大學西門,南門,東門乘車均可;G.vex2.sight=46路公交車;G.vex2.description=魯東大學東門乘車;G.vex3.sight=33路公交車;G.vex3.description=魯東大學南門乘車; G.vex4.sight=41路公交車; G.vex4.description=魯東大學東門乘車;G.vex5.sight=煙臺汽車站;G.vex5.description=長途汽車站;G.vex6.sight=火車站;G.vex6.description=煙臺火車站，附近有北馬路汽車站，三站;G.vex7.sight=濱海廣場;G.vex7.description=50路虹口賓館,52路建設銀行下車,景色優(yōu)美，適合觀景;G.vex8.sight=山東工商學院;G.vex8.description=附近還有煙臺大學，濱州醫(yī)學院;G.vex9.sight=中心廣場;G.vex9.description=附近有沃爾瑪，大潤發(fā)，也能步行去三站;G.vex10.sight=煙臺毓璜頂醫(yī)院;G.vex10.description=看病，治療; G.vex11.sight=三站;G.vex11.description=離大潤發(fā)超市很近，有服裝市場，電子用品賣場等;/*這里把所有的邊假定為20000，含義是這兩地點之間是不可到達*/for(i=0;iG.vexnum;+i)for(j=0;jG.vexnum;+j) G.arcsij.adj=Max;G.arcs05.adj=4;G.arcs06.adj=6;G.arcs07.adj=12; G.arcs08.adj=23; G.arcs17.adj=10;G.arcs18.adj=24;G.arcs19.adj=6; G.arcs110.adj=4; G.arcs111.adj=4;G.arcs27.adj=21;G.arcs210.adj=16;G.arcs38.adj=17;G.arcs45.adj=4; G.arcs46.adj=5;G.arcs411.adj=3;/CreateUDNvoid narrate()/說明函數(shù)int k=0;printf(nt*歡迎使用魯東大學附近主要休閑場所公交車咨詢*n);printf( t_n);printf(tttt主要休閑場所名稱的編號列表:n); printf( ttt4% 050路公交車: 0n);printf( ttt4% 152路公交車: 1n);printf( ttt4% 246路公交車: 2 n);printf( ttt4% 333路公交車: 3 n); printf( ttt4% 441路公交車: 4 n);printf( ttt4% 5煙臺汽車站: 5n);printf( ttt4% 6火車站: 6n);printf( ttt4% 7濱海廣場: 7n);printf( ttt4% 8山東工商學院: 8n);printf( ttt4% 9中心廣場: 9n); printf( ttt4% 10煙臺毓璜頂醫(yī)院: 10n); printf( ttt4% 11三站: 11n); printf( t_ n);/narratevoid ShortestPath(int num)/迪杰斯特拉算法最短路徑函數(shù) num為入口點的編號 int v,w,i,t;/i、w和v為計數(shù)變量int finalNUM;int min;for(v=0;vNUM;v+) finalv=0;/假設從頂點num到頂點v沒有最短路徑Dv=G.arcsnumv.adj;/將與之相關的權值放入D中存放for(w=0;wNUM;w+)/設置為空路徑Pvw=0;if(Dv20000)/存在路徑Pvnum=1;/存在標志置為一Pvv=1;/自身到自身Dnum=0;finalnum=1;/初始化num頂點屬于S集合/*開始主循環(huán)，每一次求得num到某個頂點的最短路徑，并將其加入到S集合*/for(i=0;iNUM;+i)/其余G.vexnum-1個頂點 min=Max;/當前所知離頂點num的最近距離for(w=0;wNUM;+w)if(!finalw)/w頂點在v-s中if(Dwmin)/w頂點離num頂點更近 v=w;min=Dw; finalv=1;/離num頂點更近的v加入到s集合for(w=0;wNUM;+w)/更新當前最短路徑極其距離if(!finalw&(min+G.arcsvw.adj)Dw)/不在s集合，并且比以前所找到的路徑都短就更新當前路徑Dw=min+G.arcsvw.adj;for(t=0;tNUM;t+)Pwt=Pvt;Pww=1; /Shorte