鲁东大学到附近主要休闲场所的公交车查询.doc

学院_专业_班级_本专 学号_姓名_ 密封线 学生须将文字写在此线以下鲁东大学 数学与信息学院 20102011学年第1学期数据结构专题设计课程论文课程号：2102791 任课教师 成绩 论文题目：（可指定题目，也可说明题目范围。）从给出的参考选题中选（或自选）一个能体现数据结构课程特点的课题，用C语言（TC或VC+）编程实现所述功能，用论文形式描述整个工作。详见数据结构专题设计 课程任务和要求文档。论文要求：（对论文题目、内容、行文、字数等作出判分规定。）按右边给定的模板要求写作，字数4000字以上（不含附录）。评分采用五级制：优秀、良好、中等、及格、不及格。评分依据包括题目难易程度、程序运行情况、数据结构和算法设计合理与否、算法注释的清晰程度；论文的规范程度、撰写质量（条理清晰，内容充实，文字通顺，图表恰当）；总结的深刻程度、工作量和创新性；交作业的及时程度、独立完成情况，以及其它参考因素。不同同学可以选择同类题目，但在具体功能、程序代码、论文写作上都要有所不同，若发现雷同，均判为不及格。教师评语： 教师签字： 2010 年 11 月 2 日鲁东大学到附近主要休闲场所的公交车查询1、引言当初刚上大一的时候，什么也不知道，出门坐车得问个千遍万遍，才敢坐车。那种无助的感觉到现在还记忆犹新。新学期的开始，鲁东大学又迎来了新一届同学。为了减少学弟学妹们的不适感，我利用学习过的数据结构知识，在本文中建立了一个芝罘区主要休闲场所查询程序并给出了相关场所的粗略信息，以及从鲁东大学到其地点的站点数。新同学可以通过此程序查询芝罘区主要休闲场所信息及可以乘坐哪路公交车、及到达该场所经过车站数最少的公交车。2、需求分析1.经过一定的调查询问得知同学们平日所到之处大致相同，考虑到经过鲁东大学的公交车主要有33路、41路、46路、50路、52路公交车，将各路公交车在鲁东大学的起点及主要休闲场所的代表地点，抽象成一个无向带权图。图中分别顶点表示33路、41路、46路、50路、52路公交车在鲁东大学东门、南门或是西门起始站点；并且顶点存放起始站点和各场所的编号、名称、简介等信息，图中的边表示分别从起始站点到所去地点乘不同公交车经过的站点数，并作为路径长度。输入相应选择后，会得到自己所需要乘坐的的公交车，站点等等2.本程序的目的是为鲁东大学新生提供烟台芝罘区主要休闲场所相关信息及公交车的查询，通过程序可以查询： （1）从鲁东大学到某一娱乐场所所需要乘坐的公交车，及经过的站点数。（2）查询各个地点的信息。（3）到达某一娱乐场所最优公交线路。（4）查询经过鲁东大学的不同公交车的公交线路。3. 经过鲁东大学的公交路线及主要休闲场所图如下：3、概要设计（或总体设计）3.1数据结构描述本论文的程序设计，主要是在图论知识的基础上进行设计，因此首先给出抽象类型图的定义，以便结合实际情况进行图的构造。以下是查询的有关抽象类型图的定义：ADT Graph 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系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)各场所信息模块 将经过鲁东大学的公交车50路、52路、46路、33路、41路公交车分别编号为0、1、2、3、4。对各休闲场所进行编号5-11，构成无向图的顶点，并将起始站点和各场所的编号、名称、简介等信息存放在顶点。将两地之间公交车所经过的站点数作为边的赋权值。(3)休闲场所公交路线选择模块 约定两地点之间公交车经过的车站数越少，两地点之间距离越近。根据图的最短路径算法，求出两地之间的最少车站数。如果两地之间不能通过经过鲁东大学的公交车到达，为方便编程，不考虑再乘坐其他公交车的情况，而且根据大多数学生的出游特点，到达某一场所时不考虑步行所经过的路程只考虑公交车经过的车站数。(4)输出模块 输出符合查询的条件的公交路线或是景点信息。3.2.2程序流程图3.2.3程序操作流程图4、详细设计及实现4.1主程序模块void main()/主函数 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;/相邻接的地点之间的站点数ArcCell;/定义边的类型typedef struct VertexType int number;/地点编号 char *sight;/场所名称 char *description;/地点描述VertexType;/定义顶点的类型typedef struct VertexType 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+)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函数、及调用满足查询条件的各个函数，输出公交路线或是休闲场所信息。 例如：当查询经过鲁东大学主要公交路线的最优路线时，输出函数如下所示。void better() printf( ttt最优公交路线:);printf(n 到山东工商学院及附近高校坐33路公交到山东工商学院站点下车（约经过10个站点）;n);printf( 到滨海广场坐52路公交到建设银行站点下车（约经过17个站点）;n);5、调试分析5.1调试分析1.在建立抽象无向图时，由于对无向图的知识很不了解，查阅了大量资料，也做了很多无用功，而且由于顶点的选择失误，导致最后结果很不符合实际情况。经过多次操作实验最确定了将不同公交车起始站点也进行编号的方法，解决从鲁东大学出发到同一景点不同公交车到达经过的景点的车站数不同的问题。在最终总体调试程序时曾出现以下简单错误：2.原因是：符号c使用之前未进行定义；3.原因是：程序中定义了i，多余；4.运行程序后，选择3号查询方式，并未出现所要查询的结果。原因是：在编写case 1，3，4时忘记引用函数：getchar()来输出字符；5.2调试结果1.初始界面如下图所示：2. 查询休闲场所公交路线图： 例如 查33路是否能到达山东工商学院，烟大等学校，查询结果如下图所示：3.最优路线查询结果如下图所示：6、结论及体会1) 因为编写程序时只考虑了新一届鲁大学子不熟悉芝罘区主要休闲场所的情况。再者，编写时间有限，本论文所设计的公交查询系统涉及的站点很少，而且只涉及了经过鲁东大学的几辆公交车。另外，同学们去的地方并不是很多，本论文只是选取了比较常去是的几个地方。虽然程序简单，涉及实际数据较少，但也有其实用价值。有了这个程序，新生们可以大体的了解鲁大周围的几个常去地点，而且不至于坐错公交车。本文涉及的算法思想也有比较大的可取价值。 2) 通过此次公交查询论文的设计，我进一步加深了无向带权图的知识，将所学的理论知识结合实际问题进行了应用，活学活用，对于图的顶点定义，边的赋权值有了进一步的理解。对于数据结构的程序设计也有了进一步的了解，并不是初学时的得过且过，朦朦胧胧。 3） 由于自己所学图论知识过少，程序代码方面并不是很精通，上机动手操作能力不强，在本课题设计过程中出现了很多问题。但正是通过解决这些问题使自己的程序编写及调试识错能力有了很大提高。对代码的认识也不再是仅止于英文字母，学会了基本的程序编写。增强了动手解决问题的能力。4）在程序调试过程中，曾出现几个错误问题，有代码写错的，也有直接忘记写的，同学给与了很大帮助，提高了同学之间的团结合作能力。参考文献1 严蔚敏，吴伟民数据结构题集（C语言版）北京：清华大学出版社，1999.2 徐孝凯. 数据结构课程实验. 北京：清华大学出版社，2002. 3 20092010学年第1学期xxxxxxxxxxx姓名-芝罘区主要景点公交车查询.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;/顶点数，边数MGraph;/定义图的类型MGraph G;/把图定义为全局变量int PNUMNUM;long int DNUM;/辅助变量存储最短路径长度int x11=0; void CreateUDN(int v,int a); /造图函数void narrate();/说明函数void ShortestPath(int num);/最短路径函数void output(int sight1,int sight2); /输出函数char Menu();/主菜单void search();/查询休闲场所信息char SearchMenu();/查询子菜单void better();/哈密尔顿图的遍历void NextValue(int); void display();/显示遍历结果void main()/主函数 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请按回车键继续.n);getchar();getchar();break;case 2:search();break; case 3: system(cls);narrate();x0=1; /HaMiTonian(1); better();printf(nntttt请按回车键继续.n);getchar();getchar();break;case 4:system(cls);narrate();x0=1; /HaMiTonian(1); display(); printf(nntttt请按回车键继续.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、各地点最优路线的查询 n);printf(ttt 4、经过鲁东大学公交路线 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) /造图函数int i,j;G.vexnum=v;/初始化结构中的休闲场所数和边数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路建设银行下车,景色优美，适合观景;G.vex8.sight=山东工商学院;G.vex8.description=附近还有烟台大学，滨州医学院;G.vex9.sight=中心广场;G.vex9.description=附近有沃尔玛，大润发，也能步行去三站;G.vex10.sight=烟台毓璜顶医院;G.vex10.description=看病，治疗; G.vex11.sight=三站;G.vex11.description=离大润发超市很近，有服装市场，电子用品卖场等;/*这里把所有的边假定为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()/说明函数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烟台毓璜顶医院: 10n); printf( ttt4% 11三站: 11n); printf( t_ n);/narratevoid ShortestPath(int num)/迪杰斯特拉算法最短路径函数 num为入口点的编号 int v,w,i,t;/i、w和v为计数变量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集合/*开始主循环，每一次求得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