数据结构与算法大作业

课程设计说明书课程名称：数据结构与算法设计题目：校园导游程序院系：计算机科学与信息工程学院学生姓名：丁守亮学号：201003030007专业班级：10级软件工程一班指导教师：闫怀平2012年6月15日课程设计任务书设计题目校园导游程序学生姓名丁守亮所在院系计算机科学与信息工程学院专业、年级、班10级软件工程一班设计要求：应用无向网表示学校的校园景点平面图（1）建图以图中顶点表示主要景点，并存放景点的编号、名称、简介等信息；图中的边表示景点间的道路，存放路径长度等信息。（2）查询该系统可以查询景点的信息；查询图中任意两个景点间的最短路径；查询图中任意两个景点间的所有路径。（3）更新可以进行景点的更新，如去除、增添景点和路径，可以随时对景点间路径长度的更新。学生应完成的工作：根据设计要求，我们需完成如下工作：程序编写方面：（1）建立无向图，保存景点信息和路径信息；（2）景点相关信息查询函数；（3）查询图中任意两个景点间最短路径函数；（4）查询图中任意两个景点间的所有路径函数；（5）更新景点信息函数，需要完成对以下函数的调用1）增加景点的信息函数；2）增加道路的信息函数；3）删除景点的信息函数；4）删除道路的信息函数；5）更新道路权值的信息函数。（6）建立校园景点平面图；（7）对（2）、（3）、（4）、（5）、（6）功能函数调用函数。其他方面：（1）对编写完成的程序进行上机调试；（2）运行程序；（3）对运行结果进行分析；（4）撰写课程设计说明书（5）完成设计答辩。参考文献阅读：[1]严蔚敏、吴伟民.据结构（c语言版）.北京：清华大学出版社.2009[2]谭浩强.C程序设计（第四版）.北京：清华大学出版社.2010[3]严蔚敏、吴伟民.据结构题集.北京：清华大学出版社.2009工作计划：本次课程设计时间为2011—2012学年度第二学期的第17、18周1、第一周的第一天：小组布置设计题目；说明进度安排。2、第一周的第二天：小组审题，查阅资料，进行设计前的必要资料准备。3、第一周的第三天、第四天、第五天：程序编写、上机调试4、第二周的第一天至第三天：上机调试程序、结果分析。5、第二周的第四天：撰写设计报告。6、第二周的第五天：设计答辩及成绩评定。任务下达日期：2012年6月4日任务完成日期：2012年6月15日指导教师（签名）：学生（签名）：校园导游程序摘要：随着现代旅游业的快速发展,图文声像导游方式和实地口语导游方式都已经不能满足现阶段旅游者的需求,信息化的飞速发展造就了地理信息系统(GIS)和全球定位系统(GPS),促使消费者更多的选择自助游和自驾游等方式出行。而近年来高等院校的发展使得高校也成为了一个景点。如何让游客以最短的时间到达旅游目的地就是本文所寻求解决的问题。文章通过最短路径算法,并结合实际情况以高等院校为例采集所需要的数据,理论上使得游客可以轻松的寻找到最适合自己的旅游线路,并以此为依据合理安排自己的行程。关键词：数据结构图结点边权景点路径距离目录1.设计背景…………………………………………………………11.1课程设计目的……………………………………………11.2题目要求…………………………………………………12.设计方案………………………………………………………22.1功能构思…………………………………………………22.2方法实现…………………………………………………33.方案实施………………………………………………………43.1基本操作…………………………………………………43.2各步操作函数模块………………………………………44.结果和结论……………………………………………………174.1运行结果…………………………………………………174.2结论………………………………………………………255.收获和致谢……………………………………………………266.参考文献………………………………………………………277.附件……………………………………………………………28-1-1.设计背景1.1课程设计目的数据结构是计算机程序设计的重要理论技术基础，它不仅是计算机科学的核心课程，而且已成为其他理工专业的热门选修课。从课程性质上讲，数据结构是一门专业技术基础课。它的教学要求是：学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当地逻辑结构，存储结构和其相应的算法，并初步掌握算法的时间分析和空间分析的技术。另一方面，本课程的学习也是复杂程序的设计的训练过程，要求学生编写的程序结构清楚和正确易读，符合软件工程的规范。如果说高级语言程序设计的训练过程，要进行结构化的程序设计的初步训练的话，那么数据结构就要培养我们的数据抽象能力。本次课程设计的目的就是培养学生运用数据结构中基本算法进行处理现实中的问题的能力。通过本次课程设计，可以让学生更好地掌握数据结构中的各类基本算法，并运用C语言完成简单的编程，为以后更好的学习高级编程语言打下基础。1.2题目要求本次设计要求两人合作共同完成：1.景点信息和路径信息保存在文本文件，景点个数不少于20个2.查询各景点的相关信息；3.查询图中任意两个景点间的最短路径。4.查询图中任意两个景点间的所有路径。5.增加、删除、更新有关景点和道路的信息。-2-2.设计方案2.1功能构思2.1.1问题的分析和结构的设计思路1）在安阳工学院校内选取具有代表性的景点，把这些景点看作无向带权图的各个结点，景点间的路径看作无向图的边，两景点之间的距离以各对应边上的权值表示。2）校园咨询程序要为用户提供最佳路径查询，根据用户提供的起始景点和终端景点输出最佳的路径，此时，可以运用弗洛伊德算法函数完成最短路径的输出。3）校园咨询程序可以用迪杰斯特拉算法完成在游客只提供起始景点的情况下，告知游客到校园内其余景点的最短路径。4）景点信息的更新则可以在无向图中以添加、删除结点，添加、删除边以及改变各边权值表示。2.1.2校园导游咨询程序的算法思想及设计1）由校园各景点建立起的无向带权图，采用邻接矩阵的形式进行存储，其中点信息的存储形式如“strcpy(c.vexs[0].name,南门);strcpy(c.vexs[0].introduction,安阳工学院正门)”所示，各边以及路径长度的则以c.arcs[i][j].adj=Infinity表示（其中i,j表示景点的编号）。2）校园任意两景点间的最短路径问题则可以用弗洛伊德算法实现，3）显示校园其中一个景点到其余各景点的最短路径的过程用迪杰斯特拉算法求一个结点到其余各结点的最短路径像似，因此我们可以采用迪杰斯特拉算法实现。4）校园景点的更新，我们则可以在无向图中做出相应的表示。2.1.3校园导游咨询程序的设计流程图:校园导游程序初始化无向图创建校园平面图查找两景点间最短路径查询一个景点到其余各景点最短路径图形更新插入和删除结点插入和删除边更新边的权值查询两景点间的所有路径-3-2.2方法实现2.2.1基本操作函数实现1.建立无向图的初始化mgraphinitgraph()2.查找景点在图中的序号intlocatevex(mgraphc,intv)3.求序号为m,n景点间的长度不超过8个景点的路径voidpath(mgraphc,intm,intn,intk)4.打印两景点间的景点个数不超过8的所有路径。调用2intallpath(mgraphc)5.用迪杰斯特拉算法，求出一个景点到其他景点间的最短路径，并打印voidshortestpath_dij(mgraphc)6.构造图的邻接矩阵intcreatgragh(mgraph&c)7.建图、更新信息、删除、增加结点和边intnewgraph(mgraph&c)//新建图intenarc(mgraph&c)//增加边intenvex(mgraph&c)//增加结点intdelvex(mgraph&c)//删除结点intdelarc(mgraph&c)//删除边8.使用FLOYD算法查询两景点间的最短路径voidshortestpath_floyd(mgraphc)-4-3.方案实施3.1基本操作3.1.1完成图的各个模块以及各模块之间的调用3.2各步操作函数模块3.2.1定义边、点、图结构体以及整形变量typedefstructarcell{//边结构体intadj;}arcell,adjmatrix[MaxVertexNum][MaxVertexNum];typedefstructvexsinfo{//点信息结构体intposition;charname[32];charintroduction[256];}vexsinfo;typedefstructmgraph{//图结构体vexsinfovexs[MaxVertexNum];adjmatrixarcs;intvexnum,arcnum;Main（）browsecompus（）shortestpath_dij（）shortestpath_floyd（）Seeabout（）Changegraph（）Allpath（）Printmatrix（）Printfmap（）Creatgraghdelvexdelarcenvexenarcnewgraph-5-}mgraph;3.2.2无向图的邻接矩阵存储mgraphinitgraph()//对图初始化{inti=0,j=0;mgraphc;c.vexnum=21;c.arcnum=36;for(i=0;ic.vexnum;i++)c.vexs[i].position=i;strcpy(c.vexs[0].name,南门);//依次输入顶点信息strcpy(c.vexs[0].introduction,安阳工学院正门);strcpy(c.vexs[1].name,报告厅);strcpy(c.vexs[1].introduction,学生聆听名人演讲的地方);strcpy(c.vexs[2].name,行政楼);strcpy(c.vexs[2].introduction,教务后勤办公处);strcpy(c.vexs[3].name,主教楼);strcpy(c.vexs[3].introduction,考研学生的自习室);strcpy(c.vexs[4].name,明德湖);strcpy(c.vexs[4].introduction,学生早读之处);strcpy(c.vexs[5].name,求索广场);strcpy(c.vexs[5].introduction,因有八卦图故名求索);strcpy(c.vexs[6].name,网球场);strcpy(c.vexs[6].introduction,网球运动绝佳圣地);strcpy(c.vexs[7].name,足球场);strcpy(c.vexs[7].introduction,每年大学生春季运动会在这里举办);strcpy(c.vexs[8].name,宿舍楼);strcpy(c.vexs[8].introduction,校内女生宿舍，离餐厅很近);strcpy(c.vexs[9].name,餐厅);strcpy(c.vexs[9].introduction,校内学生在这里就餐);strcpy(c.vexs[10].name,羽毛球场);strcpy(c.vexs[10].introduction,学生运动好去处);strcpy(c.vexs[11].name,工行取款机);strcpy(c.vexs[11].introduction,方便学生取钱的地方);strcpy(c.vexs[12].name,医务室);strcpy(c.vexs[12].introduction,小病，可以轻松治愈);strcpy(c.vexs[13].name,外语学院);strcpy(c.vexs[13].introduction,在这里你可以进行英语交流);strcpy(c.vexs[14].name,艺术楼);strcpy(c.vexs[14].introduction,每年