数据结构课程设计-校园导游咨询(11页).doc

《数据结构课程设计-校园导游咨询(11页).doc》由会员分享，可在线阅读，更多相关《数据结构课程设计-校园导游咨询(11页).doc（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-数据结构课程设计-校园导游咨询学 号武 汉 科 技 大 学 城 市 学 院课 程 设 计 报 告 课程名称 数据结构课程设计 题 目 校园导游咨询 学 部 专 业 班 级 姓 名 指导教师 2016年6月12日-第 5 页数据结构课程设计任务书课程设计名称：校园导游咨询课程设计开发平台与工具：Microsoft Visual C+ 6.01.课程设计任务设计学校的校园平面图，所含景点不少于10个。以图中顶点表示学校各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。 为来访客人提供图中

2、任意景点相关信息的查询。 2.课程设计功能说明（1）输入数据：景点个数，景点信息结构（包含名称、代号、简介等信息）（2）输入约束：景点个数为整形；校园景点平面图用图的形式存储; （3）实现以下功能：a) 查询校园地图；b) 查询单个景点的相关信息如名称或简介等；c) 查询从某个景点到其他所有景点最短路径长度即最短距离和途中要经历的景点；d) 查询学校里任意两个景点之间的最短距离和途经点。3. 设计内容及步骤（1）分析问题，给出数学模型，设计相应的数据结构。a) 分析问题的特点，用数学表达式或其它形式描述其数学模型。b) 选择能够体现问题本身特点的逻辑结构。c) 在逻辑结构确定的情况下，为算法的

3、设计选择相应的存储结构，顺序存储结构和链式存储结构的不同存储方式，其对应的算法也不同。（2）在已经选择好数据结构的前提下，为解决的问题设计算法。a) 确定所需要的模块b) 对于稍复杂的问题，要充分利用模块化程序设计方法，自顶向下，逐步细化，在整体思路确定的情况下，考虑所需模块数，各模块完成功能以及模块之间的数据联系和调用关系。c) 各子模块功能描述：给出主要模块的算法描述，用流程图或伪代码表示。d) 模块之间的调用关系：给出算法各模块之间的关系图示。（3） 编写程序为了提高工作效率，要求学生充分利用上机调试程序的时间。（4）用测试数据去验证算法及程序的正确性（5）算法分析：分析算法的时间复杂度

4、和空间复杂度。 目 录一 需求分析2二 概要设计4三 详细设计5四 测试分析6五 小结6参考文献7课设计评分表81 需求分析1.1需求分析 来访我校的游客可能刚到学校不了解学校里的景点，为了给游客提供一条最短的游览路径，结合对校园平面图的分析，将其转化为数据并保存在系统中，使顾客可以找到游玩景点最省市，最高效的路径。1.2功能需求描述设计学校的校园平面图，所含景点10个。为来访的客人提供图中任意景点相关信息的查询。为来访客人提供任意景点的问路查询。即查询任意两个景点之间的一个最短的简单路径，并提示出个经典之间的防卫关系，行走方向。2 概要设计2.1抽象数据类型定义#include #inclu

5、de/*定义符号常量*/#define INT_MAX 10000#define n 10/*定义全局变量*/int costnn;/* 边的值*/int shortestnn;/* 两点间的最短距离*/int pathnn;/* 经过的景点*/开始2.2模块结构显示查询信息 加入文字文件读取显示最短路径退出图2.2 模块图2.3函数的详细调用处理流程 当游客选择了要查找景点的信息的介绍这一项功能的时候，程序就会调用DisIntroduction(G);函数进入到查找景点的介绍的界面，当游客输入了需要查找的景点的名称的时候，程序利用for();循环语句来查找是否有这个景点for(inti=0;

6、iG.vexnum;i+)intm=strcmp(G.vexsi.name,n1);if(m=0)v1=i;count1=count1+1;找到将它的编号返回，并输出它的介绍，没有找到这输出错误提示，提醒游客进行相关的操作进入正确的操作过程当中。 当游客选择了要查找两个景点之间的最短距离这一项功能的时候，程序就会调用DisPath(G)；函数进入到查找两个景点之间的最短距离的操作界面当中，当游客输入了两个景点的名称过后，程序会调用strcmp();函数查看是否有这两个景点，如果有则返回他们各自的编号，并调用ShortPath_DIJ(G,v1,v2);函数进入到查找最短路径问题的程序当中。fo

7、r(v=0;vG.vexnum;v+)/各对节点之间初始已知路径及距离finalv=FALSE;/从V出发的最短路径的空集合Dv=G.arcsv0v;/从V出发到图上其余各个定点v0可能到达的最短路径的初始值for(w=0;wG.vexnum;w+)Pvw=FALSE;/设空路径if(DvMAXNUM)Pvv0=TRUE;Pvv=TRUE;Dv0=0;finalv0=TRUE;inta20;for(i=0;iG.vexnum;i+)/对Pathij进行初始化，使其值全部为1000，便于后期的判断for(j=0;jG.vexnum;j+)Pathij=1000;for(i=0;iG.vexnum

8、;i+)/对数组进行初始化，以便对Pathij进行描述ai=1;for(v=0;vG.vexnum;v+)/各条路线的初始节点为v0Pathv0=v0;/开始主循环，每次求解得到v0到某个v顶点的最短路径，并加入到S集合中for(i=1;iG.vexnum;i+)/其余G.vexnum-1个顶点m=MAXNUM;/当前所知的离v0最近的距离for(w=0;wG.vexnum;w+)if(!finalw)/w顶点在V-S中if(Dwm)/w顶点离v0顶点更近v=w;m=Dw;Pathvav=v;/离v0顶点最近的v加入s集合finalv=TRUE;for(w=0;wG.vexnum;w+)/更新

9、当前最短路径及距离if(!finalw)&(m+G.arcsvwDw)Dw=m+G.arcsvw;/修改当前的最短路径的值intk0=1;aw=1;while(Pathvk0!=1000)/如果上述条件成立，Pathw路径需要改变，因为从v0到w的路径显然经过了v0和v之间的所有的点（包括v）Pathwk0=Pathvk0;k0+;aw+;cout两个景点之间的最短路径为:t;intk=0;while(Pathv2k!=1000)intm=Pathv2k;coutG.vexsm.namet;k+;coutendl;cout两个景点之间的最短距离为:Dv2Mendl;cout请选择要进行的操作(

10、I:查询景点信息，P:查询两个景点之间的最短路径，Q:退出)endl; (1)假设用带权的邻接矩阵arcs来表示带权的有向图，arcsij表示弧（vi,vj）上的权值。若(vi,vj)不存在，则置arcsij为无穷大。S为已找到从v出发的最短路径的终点集合，它的初始状态为空集。那么，从v出发到图上其余各个定点vi可能到达的最短路径长度的初始值为：Di=arcsvi; (2)选择vj,使得Dj=MinDi|viVSvj就是当前求得的一条从v出发的最短路径的终点。令S=Sj; (3)修改从v出发到集合VS上任意顶点vk可到达的最短路径的长度。如果Dj+arcsjkDk则修改Dk为Dk=Dj+arc

11、sjk; (4)重复操作(2)、(3)共n1次，由此求得从v到图上其余各个顶点的最短路径是依路径长度递增的序列。从而求得了从一个景点到另一个景点的最短路径的问题。3详细设计3.1 数据结构存储定义1.邻接矩阵typedefintAdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;定义一个邻接矩阵，用邻接矩阵来定义和储存边的相关信息。2.顶点的结构体typedefstructVertex/定义图中顶点的数据类型intnum;/景点编号charname14;/景点名称charintroduction100;/景点介绍Vertex;定义一个顶点的结构体，用来储存景点的编号、景

12、点得名称和景点的介绍等关于景点的信息。3.无向图的结构体typedefstruct/定义图的数据类型VertexvexsMAX_VERTEX_NUM;/顶点的结构体AdjMatrixarcs;/边的邻接矩阵intvexnum,arcnum;/顶点的个数，边的个数MGraph;定义一个图的结构体，用来储存顶点的信息、边的信息、顶点的个数和边的个数等相关的信息便于我们以后在用的时候能够方便快捷的调用。定义好这些结构体后，当我们以后需要调用的时候，我们就能够方便快捷的调用这些结构体，从而使得我们在运行程序的时候能够更加的快速能够提高我们的程序的运行效率，大大的节省了我们的时间还使得程序变得更加的简单

13、3.2算法设计void floyed()/*用floyed算法求两个景点的最短路径*/ int i,j,k; for(i=1;i=n;i+) for(j=1;j=n;j+) shortestij=costij; pathij=0; for(k=1;k=n;k+) for(i=1;i=n;i+) for(j=1;j(shortestik+shortestkj) /*用path记录从i到j的最短路径上点j的前驱景点的序号*/ shortestij=shortestik+shortestkj; pathij=k; pathji=k;3.3 界面设计 3.3.1主界面图3.1 主界面3.3.2 查询图

14、3.2 查询界面 3.3.3 查找最短路径图3.3 查找最短路径界面 3.3.4 退出图3.4 退出4测试分析调试过程中难免会遇到这样或者那样的问题，一个很低级的错误就是在字符串的赋值上居然还会出错，本来是不可以像int型数据那样直接用等号赋值的，可是刚开始由于食物却犯了这样低级的错误结果导致出现一百多个错误，当时还莫名其妙，仔细看了几遍后才把问题想明白，字符串赋值必须用strcpy函数。看来基本功还是相当重要的。5 小结 在本次的实验过程当中，虽然有各种各样的问题在困扰着我，但是好在我的身边总会有人在这个时候出现为我解决这些问题，而他们就我的老师和同学们，一个人做事的时候总是会遇到问题的，有

15、问题并不可怕只要我们相信我们不是一个人在战斗而是有很多的同学和老师与我们站在一起的样我们就能够战胜各种困难，感谢我的老师和我的同学们。是他们在我遇到问题的时候给我指明了解决的方法，从而克服了一个又一个的问题最终解决了所有的问题实现了程序所需要的功能，感谢我的同学们，不论是上课还是下课，只要是遇到了困难找到他们的时候只要是能够解决的他们会义不容辞的献出自己的力量。感谢老师们的谆谆教诲，他们不辞辛劳为了我们能够顺利的解决问题无时刻不在我们的身边，当我们一遇到问题的时候他就会出现，从没有半点怨言。最后还要感谢学校感谢给我们提供了良好的实验环境，使我们能够安心轻松的在好的额环境当中完成我们的实验。参考

16、文献1 严蔚敏,吴伟民.数据结构（C语言版）.清华大学出版社,2011. 2 刘振安,刘燕君.C程序设计课程设计M.北京: 机械工业出版社,2004. 3 谭浩强.C程序设计（第三版）.清华大学出版社,2010.4 吴文虎.程序设计基础.清华大学出版社,2010.5 严蔚敏,陈文博.数据结构及应用算法教程.清华大学出版社,2004. 课设计评分表评分标准：1. 学生是否严格遵守课程设计纪律，按照规定时间完成设计任务(占30%)2. 程序设计的质量与规范：(占40%)(1)选题难度：ACM题目（A级或B级）、传统题目(2)是否采用了良好的设计方法，独立完成程序设计(3)程序界面设计是否合理、美观(4)程序是否运行正常，未见运行错误3. 课程设计报告书的质量与规范 (占30%)教师评分：1.学生出勤得分： A， B， C， D2.程序设计得分： A， B， C， D3.设计报告得分： A， B， C， D 教师评语： 根据该生在课程设计期间，是否严格遵守课程设计纪律，按照规定时间完成设计任务，完成的程序设计的质量与规范，提交的课程设计报告书的质量与规范等多方面的评分，该生本次课程设计的评分为：_ 教师签名：杨艳霞 日期： 2016 年 6 月 15 日