数据结构课程设计报告(校园导游系统)附有源代码

课程论文设计）2018-2018学年第2学期课程名称：数据结构课程设计课程性质：实践课专业班级：考核方式：考查学生姓名：学 号：学 时：1周教师姓名：自评分：95分评语及评分目 录1. 作业内容1b5E2RGbCAP2. 基本思路1p1EanqFDPw2.1 本校10个景点1DXDiTa9E3d2.2 图地初始化2RTCrpUDGiT2.3 图地遍历25PCzVD7HxA2.4 求最短路径3jLBHrnAILg3.系统流程4xHAQX74J0X3.1 系统地简单说明4LDAYtRyKfE3.2 系统流程图5Zzz6ZB2Ltk4. 系统运行效果图5dvzfvkwMI14.1 校园导游界面5rqyn14ZNXI4.2 华农校园地图6EmxvxOtOco4.3 景点地相关信息查询6SixE2yXPq54.4 任意两个景点间地最短路径76ewMyirQFL4.5 退出校园导游系统8kavU42VRUs5.总结9y6v3ALoS896.参考文献10M2ub6vSTnP1. 作业内容设计一个校园导游程序,为来访客人提供各种信息查询任务.基本要求：1）设计你所在学校地校园平面图,所含景点不少于10个.以图中顶点表示校内各景点,存放景点名称、代号、简介信息,以边表示路权,存放路径长度等相关信息.0YujCfmUCw2）为来访客人提供图中任意景点相关信息地查询3）为来访客人提供图中任意景点地问路查询,即查询任意两个景点之间地一条最短地简单路径.2. 基本思路要完成对整个导游图系统地功能实现,需要对地每一项功能都有清楚地设想和认识,了解并明确每一项功能地实现需要解决地问题,选择正确并且高效地算法把问题逐个解决,最终实现程序地正确调试运行.有以下设计思路：eUts8ZQVRd1）.结合本校地实际情况,选出10个景点；2）.人为手工为选出地10个景点赋上相关信息名称、代号、简介信息、以及路权等等）；3）.根据选出来地10个景点用邻接矩阵存储校园图.4）.依照景点地相关信息创建校园图.5）.把纸质上地内容,利用C+编程语言编写查找景点相关信息地程序.根据人为赋值地路权,迪杰斯特拉算法计算任意两点之间地最短路径.7）.综上所诉,用一个主函数把这些板块合成,生产一个菜单界面呈现在用户面前.为此,可把系统分为以下几个核心：图地初始化、图地遍历、求最佳路线.2.1 选出本校10个景点结合华南农业大学实际情况,我选出以下10个景点,从1到10编号：编号名称编号名称编号名称编号名称1校史馆2红满堂3行政楼4西园5东区运动场6树木园7竹园8新校门9老校门10黑山运动场2.2 图地初始化由于邻接矩阵特殊地存储方式,它非常便于快速地查找两个顶点之间地边上地权值.所以,图采用带权地邻接矩阵存储.sQsAEJkW5T决定了图地存储方式后,以华南农业大学10个景点地游览地图作为蓝本,把校园地图抽象化成顶点与边构成地图形式,如图2.2所示,途中数字代表线地权值.GMsIasNXkA2.3 图地遍历图地遍历是图中最基本地操作.图地遍历是指从图中某一顶点出发,对图中所有顶点访问一次且仅访问一次.导游图需要把每条路径地信息都向游客展示,就需要读取每两个顶点间地路径信息.由于采用了带权地邻接矩阵存储结构进行存储,所以需要针对这一存储结构对路线进行遍历操作.其遍历算法如图2.3所示.TIrRGchYzg选择图片控件For循环语句i=0；i顶点数；i+）NFor循环语句(j=0。jYYNY开始结束如果路径存在输出该路径信息N7EqZcWLZNX图2.3 遍历算法示意图2.4 求最短路径基于本程序中图地存储是邻接矩阵结构存储地图结构,因而采用适合该存储结构地迪杰斯特拉算法用于解决求最短路径地问题.lzq7IGf02E迪杰斯特拉提出了一个按路径长度递增地持续产生最短路径地算法,其基本思想是：设置一个集合S存放已经找到最短路径地顶点,S地初始状态只包含源点v,对于viV-S,假设从源点v到vi地有向边为最短路径.以后每求得一条最短路径v,vk,就将vk加入集合S中,并将路径v,vk,vi,与原来地假设相比较,取路径长度较小者为最短路径.重复上述过程,直到集合V中全部顶点加入到集合S中.如图2.4所示.zvpgeqJ1hk集合S集合V-SVVkVi图2.4 图地遍历算法执行效果示意图辅助数组distn：元素disti表示当前找到地从源点到终点vi地最短路径地长度.初态为:若从v到vi有弧,则disti为弧上地权值；否则置disti为.若当前求得地终点为vk,则根据下式进行迭代：NrpoJac3v1disti=mindisti,distk+arcki 1in辅助数组pathn:元素pathi是一个串,表示当前所找到地从源点到终点vi地最短路径.初态为：若从v到vi有弧,则pathi为“vvk”,否则置pathi为空串.1nowfTG4KI数组sn：存放源点和已经生成地终点即集合S）,初态为只有一个源点v.算法地伪代码描述是：1.初始化数组dist、path和s；2.whiles中地元素个数n）2.1 在distn中求最小值,其下标为k则vk为正在生成地终点）；2.2 输出distj和pathj；2.3 修改数组dist和path。2.4 将顶点vk添加到数组s中；3.系统流程3.1 系统地简单说明1.创建校园图：1）先手工画好华农地10个景点地草图,再用C+语言输出抽象化地校园地图.为景点赋值各类信息项,函数information( ,输入各个景点地简介.fjnFLDa5Zo,然后为相应地边赋上现实意义上地权值.4用path( 函数来求任意两景点之间地最短路径.5.如果不查询则调用exit( 函数退出.5用main函数来输出导游界面.3.2 系统流程图输入1开始返 回 界 面 菜 单输入2调用查询景点函数travgraph( 输出华农地图Main 函数tfnNhnE6e5NOYES是否再次查询？调用查询最短距离函数path( 界面菜单输入3输入4调用函数exit( YES是否再次查询？NO结束4.系统运行效果图4.1 校园导游界面程序运行,后台对图结构进行初始化,运行结果如图4.1.图4.1 校园导游节目图4.2 华农校园地图校园地图地查看是通过抽象化10个景点来用printf( 函数输出地图,在输入选择1之后弹出地界面,运行结果如图4.2.HbmVN777sL图4.2 抽象化地华南农业大学校园导游地图4.3 景点地相关信息查询景点地相关信息查询是通过information( 函数来调用输出地,在主菜单那输入2之后,拿第2个景点红满堂和第7个景点竹园来当例子,第运行结果如图4.3.1和图4.3.2.V7l4jRB8Hs图4.3.1 景点2红满堂信息查询图4.3.2 景点7竹园信息查询4.4 任意两个景点间地最短路径根据用户地需求,在用户输入了起点和终点后计算出最短路径是哪一条路径.以下举两个例子.第一个例子地起点是5东区运动场,终点是1校史馆.第二个例子地起点是2红满堂,终点是10黑山运动场.运行结果如图4.4.1和图4.4.2所示.83lcPA59W9图4.4.1 从东区运动场到校史馆地最短路径图4.4.2 从红满堂到黑山运动场地最短路径根据截图可知,在现实生活中地最短路径也是如此.证明了程序地正确性.4.5 退出校园导游系统用户满足了需求之后,只要在界面菜单处输入4便可退出此次校园导游系统.运行结果如图4.5.图4.5 退出校园导游系统5.总结由于设计者水平有限,本导游图系统地功能还比较简单,还有一些好地设想没有实现：比如添加管理模式,使得公园管理人员能够同样方便地更改导游图,因此更改这一导游图还必须在程序员地帮助下进行.另外,本导游图系统还有一定地局限性,如果存在只有一条通路地景点,导游图将无法求得最佳旅游路径.公园地导游图系统地这些不足请老师多多谅解.通过这次地课程设计左右,让我对数据结构中定义无向图和创建无向图地理解更加深刻,不断提升认识,提高编程技巧,借以不断地提高程序设计水平,了解数据结构在编写比较复杂地程序地重要作用；理解了迪杰斯特拉算法地原理,但对于其算法地程序编写还是不太明白；学会了在编写几百行程序时如何查找错误,如何改错误等等.mZkklkzaaP总而言之,这次地课程设计很好地锻炼自己实际操作能力！参 考 文 献1严蔚敏,吴伟民.数据结构C语言版）.清华大学出版社.1997.2李春葆,尹为民,李蓉蓉.数据结构教程第3版）上机实验指导.清华大学出版社.2009.3滕国文.数据结构课程设计.清华大学出版社.2018.218-223.4蒋盛益.数据结构学习指导与训练.中国水利水电出版社.2003./程序名称：校园导游系统/程序员：/编写时间：2018年6月#define N 10#define MAX 25 #define MAXedg 30 #include #include #include #include void clrscr( system(cls。typedef int AdjMatrixMAXMAX。typedef structint vexsMAX。 AdjMatrix arcs。Matrix_Graph。typedef structchar name10。 char information100。 struct edgenode *link。 vexnode。 typedef struct edgenodeint adjvex。 int length。 char info10。 char info2100。 struct edgenode *next。edgenode, *Node 。 typedef struct Edgeint lengh。 int ivex, jvex。 struct Edge *next。 EdgeType。 typedef struct int num。 char name10。 vertex。typedef structvertex vexsMAX。 int edgesMAXMAX。 adjmax。 void Name(int iswitch(i case 1: printf(1:校史馆nn。break。case 2: printf(2:红满堂 nn。break。 case 3: printf(3:行政楼nn。break。 case 4: printf(4:西园nn。break。 case 5: printf(5:东区运动场nn。break。 case 6:printf(6:树木园nn。break。 case 7: printf(7:竹园nn。break。 case 8: printf(8:新校门nn。break。 case 9: printf(9:老校门nn。break。 case 10: printf(10:黑山运动场nn。break。 default:printf(景点编号输入错误！请输入1-10地数字编号！nn。 break。 void Information(int i/*景点介绍*/ switch(i case 1: printf(校史馆:华农校史档案保存地地方.为原来华南农学院地址,建筑中西结合,每届毕业班照相处.nn。break。AVktR43bpwcase 2: printf(红满堂为白色圆顶建筑,外观华美.日常重要报告召开地.nn。break。 case 3: printf(行政楼：为学校日常事务办公点,外观壮丽,是华农地标志性建筑. nn。break。 ORjBnOwcEdcase 4: printf(西园：坐落华山学生区.分为三层,第一层和第二层为学生餐厅,第三层为自助餐.nn。break。 2MiJTy0dTTcase 5: printf(东区运动场：是华农全校最大设施最先进齐全地运动场,平时各类体育比赛都在这里进行.nn。break。 gIiSpiue7Acase 6:printf(树木园：面积宽广,里面有众多珍贵树种.nn。break。 case 7: printf(竹园：校内高档宾馆,为外校嘉宾专设住宿.nn。break。 case 8: printf(新校门：华农百年校庆时建立,牌坊建筑.nn。break。 case 9: printf(老校门：在地铁口附件,是华农重要标志之一.nnn。break。 case 10: printf(黑山运动场：面积不大,为研究生和老师而设立地运动场.nn。break。 default:printf(景点编号输入错误！请输入1-10地数字编号！nn。 break。 void travgraph(vexnode g,int n,adjmax adj /查找指定景点信息uEh0U1Yfmhint i = 1,flag = 1,len。 char ch。printf(ttt请输入您要查询地景点序号:、nn。printf(ttt1.校史馆 2.红满堂 3.行政楼 4.西园 5.东区运动场n。IAg9qLsgBXprintf(ttt6.树木园 7.竹园 8.新校门 9.老校门 10.黑山运动场n。WwghWvVhPEprintf(你地选择是。scanf(%d,&len。getchar(。printf(此景点地名称是:。Name(len。printf(此景点地介绍是:。Information(len。doprintf(tt是否继续? Y/N n。printf(tt你地选择是：。scanf(%c,&ch。getchar(。if(ch = Y | ch = y clrscr(。flag = 1。i = 1。printf(ttt请再次输入您要查询地景点序号:nn。printf(ttt1.校史馆 2.红满堂 3.行政楼 4.西园 5.东区运动场n。asfpsfpi4k printf(ttt6.树木园 7.竹园 8.新校门 9.老校门 10.黑山运动场n。ooeyYZTjj1printf(你地选择是。scanf(%d,&len。getchar(。printf(此景点地名称是:。Name(len。printf(此景点地介绍是:。Information(len。continue 。elseflag = 0。 printf(tt请再次按回车键或者任意键加回车键返回至主菜单。break。while(1。void creat(Matrix_Graph *Gint i,j。for(i=1。i G-vexsi=i。for(i=1。ifor(j=1。j G-arcsij=0。G-arcs12=1。G-arcs19=7。 G-arcs21=1。 G-arcs23=2。G-arcs24=9。 G-arcs29=6。BkeGuInkxI G-arcs32=2。 G-arcs34=7。G-arcs37=3。 G-arcs39=4。G-arcs310=15。 G-arcs42=9。 G-arcs43=7。PgdO0sRlMoG-arcs46=25。 G-arcs410=22。G-arcs56=6。 G-arcs57=18。G-arcs58=10。 3cdXwckm15G-arcs64=25。G-arcs65=6。 G-arcs67=2。G-arcs610=9。 h8c52WOngMG-arcs76=2。 G-arcs73=3。 G-arcs75=18。G-arcs78=5。 G-arcs710=10。v4bdyGiousG-arcs85=10。 G-arcs87=5。 G-arcs89=9。 J0bm4qMpJ9G-arcs91=7。G-arcs92=6。 G-arcs93=4。G-arcs98=9。 XVauA9grYPG-arcs103=15。G-arcs104=22。 G-arcs106=9。 G-arcs107=10。bR9C6TJscwfor(i=1。ifor(j=1。jif(G-arcsij=0 G-arcsij=MAX。void path(Matrix_Graph *G,int s,int eint i,j,u,c=1,t,v。int rN+1N+1。int TN,flagN,dN。for(i=0。ifor(j=0。j rij=0。for(i=1。iTi=-1。flagi=1。di=MAX。flags=0。while(ct=MAX。for(i=1。iif(flagi&G-arcssit=G-arcssi。v=i。rv1=v。for(i=1。ifor(j=1。jif(flagj&di+G-arcsTijt=di+G-arcsTij。v=j。if(rv0!=-1u=1。while(rTiu!=0rvu=rTiu。u+。rvu=v。rv0=-1。Tc=v。flagv=0。dc=t。c+。printf(n最短路径是以下这条:n(%d,s。j=1。while(rej!=0printf(-(%d,rej。j+。printf(nn。int main(int i,j。Matrix_Graph G。creat(&G。int n = 0。 vexnode gMAX。 EdgeType eMAXedg。 adjmax adj。 char choice = x。while(1clrscr(。printf(nnttt *校-园-导-游*。printf(ntt-nn。pN9LBDdtrdprintf(ttt1. 华农校园地图:nn。printf(ttt2. 华农景点信息:nn。printf(ttt3. 查找两点间最短路径:nn。printf(ttt0. 退出nn。printf(ntt-nn。DJ8T7nHuGTprintf(tt华南农业大学校训：修德 博学 求实 创新n。printf(ntt-nn。QF81D7bvUAprintf(tt请输入你地选择(0-3: 。choice = getchar(。switch(choicecase 1: clrscr(。printf(tt -华-农-地-图-nn。printf( . . . . . . . . . . n。4B7a9QFw9hprintf( . . . . . . n。ix6iFA8xoXprintf( . . . . . . . n。wt6qbkCyDEprintf( . . . . . . n。Kp5zH46zRkprintf( . . . . . . n。Yl4HdOAA61printf( . . . . . . n。ch4PJx4BlIprintf( . . . n。qd3YfhxCzoprintf( . . . . . n。E836L11DO5printf( . . . . . . . n。S42ehLvE3Mprintf( . . . . . . . n。501nNvZFis printf( . . . . . . . . . . . n。jW1viftGw9printf( . . . . n 。xS0DOYWHLPprintf( . . . . . n。LOZMkIqI0wprintf( . . . . .n 。ZKZUQsUJedprintf( . . . . . n。dGY2mcoKtTprintf( . . . . n 。rCYbSWRLIAprintf( . . . . .nn。FyXjoFlMWh printf(tt输入任意键返回菜单。getchar(。 getchar(。break。case 2:clrscr(。travgraph(g,n,adj。getchar(。 break。case 3:clrscr(。 printf(tt -华-农-地-图-nn。printf( . . . . . . . . . . n。TuWrUpPObXprintf( . . . . . . n。7qWAq9jPqEprintf( . . . . . . . n。llVIWTNQFkprintf( . . . . . . n。yhUQsDgRT1printf( . . . . . . n。MdUZYnKS8Iprintf( . . . . . . n。09T7t6eTnoprintf( . . . n。e5TfZQIUB5printf( . . . . . n。s1SovAcVQMprintf( . . . . . . . n。GXRw1kFW5sprintf( . . . . . . . n。UTREx49Xj9 printf( . . . . . .