xxxxxxxxxxx姓名-芝罘区主要景点公交车查询

1、鲁东大学 数学与信息学院20092010学年第1学期数据结构专题设计课程论文课程号：2102791任课教师陈军成绩号学 -级班二二二二二二二二业专下以线此在写字文将须生学 线封密论文题目：（可指定题目，也可说明题目范围。）从给出的参考选题中选（或自选）一个能体现数据结构课程特点的课题， 用C语言（TC/VC+）编程实现所述功能，用论文形式描述整个工作。详见数 据结构专题设计课程任务和要求文档。论文要求：（对论文题目、内容、行文、字数等作出判分规定）按右边给定的模板要求写作，字数4000字以上（不含附录）。评分采用五级制：优秀、良好、中等、及格、不及格。评分依据包括题目难易程度、程序运行情况、数

2、据结构和算法设计合理与 否、算法注释的清晰程度；论文的规范程度、撰写质量（条理清晰，内容充实, 文字通顺，图表恰当）；总结的深刻程度、工作量和创新性；交作业的及时程度、 独立完成情况，以及其它参考因素。不同同学可以选择同类题目，但在具体功能、程序代码、论文写作上都要 有所不同，若发现雷同，均判为不及格。教师评语：-教师签字：I T2009年11月2日芝果区主要景点公交车查场1、引言随着新学期的开始，鲁东大学又迎来了新一届同学。为了大一新生能够迅速熟悉 烟台芝策区，适应烟台生活，本文在所学图论知识的基础上建立了一个芝策区主要景 点公交查询程序。因为主要是为鲁东大学的同学服务，公交路线的起始点都是

3、鲁东大 学。并给出了相关景点的粗略信息，以及从鲁东大学到景点的站点数。新同学可以通 过此程序查询芝策区主要景点信息及可以乘坐哪路公交车、及到达该景点经过车站数 最少的公交车。2、需求分析根据学生平日出游参观景点的特点，主要选取了芝策区六个主要景点区。此外 考虑经过鲁东大学的公交车主要有33路、46路、50路、52路公交车，将各路公交 车在鲁东大学的起点及六个主要景区的代表景点，抽象成一个无向带权图。图中分别 顶点表示33路、46路、50路、52路公交车在鲁东大学东门、南门或是西门起始站 点；并且顶点存放起始站点和景点的编号、名称、简介等信息，图中的边表示分别从 起始站点到所去景点乘不同公交车经

4、过的站点数，并作为路径长度。本程序的目的是为来鲁东大学新生提供烟台芝策区主要景点相关信息及公交 车的查询，通过程序可以查询：从鲁东大学到某一景点所需要乘坐的公交车，及经过的站点数。查询各个景点的信息。到达某一景点最优公交线路。查询经过鲁东大学的不同公交车的公交线路。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路公交路线：鲁东大学 烟台毓璜顶医院-滨海广场。n）；5、调试分析5. 1调试分析本题主要是在图论知识的基础上进行设

13、计，由于在学习图论知识时，只掌握了 图论的理论知识，了解图论的有关算法思想而对算法的实现未进行上机实际操作，因 此在进行本程序设计过程当中走了很多弯路。对例如混淆了 ”和的用法， 在初始化景点的信息时，导致了大量错误。在对景点进行初始化建立抽象无向图时，由于顶点的选择失误，导致最后结 果很不符合实际情况。经过多次操作实验最确定了将不同公交车起始站点也进行编号 的方法，解决从鲁东大学出发到同一景点不同公交车到达经过的景点的车站数不同的 问题。在解决从鲁东大学出发到同一景点公交路线问题时，由于将不同路公交车分 别设置成了不同顶点，因此从鲁东大学大学出发到某一景点的经过车站数是一个定 值，没有了最优

14、公交路线比较意义。经过调试和改进，最终加上了最优公交路线模块, 但具体算法过于繁琐。4在调用函数时，出现问题基础知识错误，函数未进行定义。因此函数的基本 知识掌握还不够扎实，有待进一步提周。5. 2调试结果调试结果用图表小：1.初始界面如图1所示。欢迎使用芝累区主要景点公交车咨询要车车车车站S:学：顶 主交交交交车：场 公公公公洱站广工广毓 路路跳路台东山台 驾斗呻ffi有以下查询方式:查查景经退 1,2,3,4,5询询点过出点公交线路优路线的查询 东大学公交路线信输入您的选:2查询景点公交线路。例如 查50路是否经过烟台汽车站、中心广场。查询结果如图2、3所示。欢迎使用芝琴区主要景点公交车咨

15、询要车车车车站5:学：顶 主交交交交车：场商场瑞 公公公公洱站广工广毓 路路路路台蕾东心台 5052碧叫滩 公交车v： 0请选择景点编号: 4从5。路公交车到烟台汽车站的公交路线是所需车站数为4.50路公交车一烟台汽车站请按回车键继续.图2从鲁东大学坐50路可到烟台汽车站。欢迎使用芝策区主要景点公交车咨询-6院B医 军车车车站S:学：顶 交交交交车公公公公诲站广工广毓 路路路路台WK东、队台 驾46呻沸 公交车0请选择景点编号（49）: 8从5。路公交车到中心广场的公交路线是所需车站数为20000. 5路公交车请按回车键继续一一一图3从鲁东大学坐50路不能到中心广场欢迎使用芝栗区主要景点公交车

16、咨询好主要景点名称的编号列表:F0路公交车：0啮2露公交车：1”46路公交车：233路公交车：3牺台汽车站：4L火车站：5T宾海广场：61山东工商学院：?呻心广场：8烟台毓璜顶医院：?主要有以下公交路线：线线线线线路路路路路交交交交交.4m#.4.k路路路路路0 2 13 65 5 4 3 4山东工商学院;鲁东大学东门一期台汽车站-一火车站一-虹口宾馆鲁东大学中心产场建设银行山东工商学院;膏东大生_堆台汽王站；毒转曹舀矗M矗：滨海广场.请按回车键继续.图4经过路东大学的主要公交路线6、结论及体会1）考虑到只为鲁东大学新生熟悉烟台地区环境的目的，加上编写时间有限，本 论文所设计的公交查询系统涉及

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 请按回车键继续.An”);getchar();getchar();break;case 2:search。；break;case 3:system(cls);narrate();x0=l;/ HaMiTonian(l);better();printf(nntttt 请按回车键继续.An”);break;case 4:system(cls);narrate();xO=l;/ H

22、aMiT onian(l);display ();printf(nntttt 请按回车键继续.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、景点最优路线的查询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=附近还有烟台大学，滨州医学院；Gvex8.sights中心广场”；Gvex8 .de

29、scription= 近有沃尔玛，大润发超市；购物;Gvex9.sight=ffi台毓璜顶医院；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*欢迎使用芝策区主要景点公交车咨询* *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烟台毓璜顶医院：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集合/*开始主循环，每一次求得num到某个顶点的最短路径，并将其加入到S集合 */其余Gvexnum-1个顶点当前所知离顶点num的最近距离w顶点在v-s中/w顶点离num顶点更近/M num顶点更近的v加入到s集合更新当前最短路