搜索
数据结构（C++）课程设计题目:校园导游咨询*姓名：学号：院系：专业年级：2014年7月8日《校园导游咨询*》设计报告—1—目录一、设计题目..........................................................................................................2二、需求分析..........................................................................................................2三、概要设计..........................................................................................................6四、详细设计........................................................................................................11五、调试分析........................................................................................................14六、测试结果........................................................................................................14七、附录：程序设计源代码................................................................................21《校园导游咨询*》设计报告—2—一、设计题目校园导游咨询*二、需求分析1)运行环境（软、硬件环境）电脑型号X64兼容台式电脑处理器英特尔第二代酷睿i5-2310@2.90GHz四核主板华硕P8H61-MLX(英特尔H61芯片组)内存8GB(威刚DDR31333MHz)主硬盘西数WDCWD10EALX-009BA0(1TB/7200转/分)显卡ATIRadeonHD6700Series(512MB/ATI)显示器SGW5600PL2208HD(21.7英寸)光驱华硕DRW-24D1STaDVD刻录机声卡瑞昱ALC887@英特尔6SeriesChipset高保真音频网卡瑞昱RTL8168EPCI-EGigabitEthernetNIC/华硕操作系统：Windows7Ultimate(x86)sp1编程环境：MicrosoftVisualStudio20122)输入的形式和输入值的范围内容形式范围景点代号int自然数景点名称string所有字符景点简介string所有字符X坐标int正整数Y坐标int正整数3)输出的形式描述内容形式范围景点代号int自然数《校园导游咨询*》设计报告—3—景点名称string所有字符景点简介string所有字符X坐标int正整数Y坐标int正整数最短路径图像jpg4)功能描述以我校南汇校区部分景点、进行抽象化，生成了具有15个顶点、18条边的图，以邻接表与邻接矩阵复合形式储存在内存中，主要有以下功能：a.查询景点的信息，包括基本信息和拓展的周围节点信息；b.景点导航，给出起点、终点，规划出最短路径和风景最佳路径；c.修改景点，道路信息，包括添加景点、添加道路、修改景点功能；d.开发人员工具，包括邻接表、邻接矩阵的查看DFS深度优先遍历、BFS广度优先遍历e.显示地图，打开预制的地图文件查看5)测试数据初始地图信息：《校园导游咨询*》设计报告—4—景点编号景点名称景点介绍X坐标Y坐标0北校门学校的北入口2141北图书馆学校北侧图书馆12142崇德楼经管学院楼26143奋进楼公共机房12284北运动场具有足球场、篮球场、健身房等26285行政楼计算机学院楼及其他行政办公12326教师活动中心又称H楼，具有桌球、乒乓球、会议室、舞厅等12397雕塑校园雕塑26398南校门学校南入口2509至诚楼办理学生事务处125010大礼堂学校大型文艺演出、讲座场所265011南图书馆学校南侧的图书馆125212大学生文化活动中心团委、学生会、社联所在处121213风帆广场绿地广场，景色优美265814南运动场具有足球场、篮球场、羽毛球场等1270比例尺：1:9.15（即：坐标与实际地理单位相差9.15倍）距离邻接矩阵：《校园导游咨询*》设计报告—5—0《校园导游咨询*》设计报告—6—三、概要设计1)抽象数据类型定义描述（对各类的成员及成员函数进行抽象描述，参见书或ppt及实验）Site类Data：编号Code景点名称SiteName景点介绍Introduction景点X坐标景点Y坐标Operation：构造函数输入：编号，名称，介绍，X坐标，Y坐标前置条件：无动作：初始化Site类元素输出：无后置条件：无SetSite输入：编号，名称，介绍，X坐标，Y坐标前置条件：无动作：赋值Site类元素输出：无后置条件：无ArcNode类Data：邻接点下标值Adjvx指向下一个边结点的指针*nextarc;风景等级sceneLevel;距离distance;Operation：构造函数输入：Adjvx,*nextarc,sceneLevel;前置条件：无动作：初始化ArcNode类输出：无后置条件：无《校园导游咨询*》设计报告—7—VertexNode类Data：节点内容vex节点首指针*firstarcOperation：无Road类Data：Site型节点1，节点2距离Distance风景等级Bool型是否是机动车道carAviliable;Operation：SetRoad构造函数输入：节点1，节点2，风景等级前置条件：存在Site对象动作：初始化Road类输出：无后置条件：无BGraph类Data：邻接表adjlist[]Int距离矩阵Int风景值矩阵Operation：构造函数输入：前置条件：动作：输出：后置条件：无addSite函数输入：景点名称，景点信息，景点X坐标，景点Y坐标前置条件：顶点表已建立动作：添加邻接表顶点、修改邻接矩阵《校园导游咨询*》设计报告—8—输出：无后置条件：无addRoad函数输入：景点1名称，景点2名称，风景等级前置条件：顶点表已建立动作：添加邻接表的边表，修改邻接矩阵输出：无后置条件：无ShowInfo函数输入：无前置条件：函数已初始化动作：输出当前图信息输出：顶点数、边数后置条件：无pGraph函数输入：无前置条件：函数已初始化动作：输出邻接表输出：邻接表后置条件：无pMatrix输入：无前置条件：函数已初始化动作：输出邻接矩阵输出：邻接矩阵后置条件：无searchByName输入：景点名称前置条件：图已初始化动作：搜索符合名称的节点输出：节点site型后置条件：无DFSTraverse函数输入：无《校园导游咨询*》设计报告—9—前置条件：图已初始化动作：深度优先遍历输出：遍历路径后置条件：无BFSTraverse函数输入：无前置条件：图已初始化动作：广度优先遍历输出：遍历路径后置条件：无FindPath函数输入：节点1，节点2前置条件：图已初始化动作：计算最短路径输出：路径经过点、路径产长度、每一步的方向后置条件：无2)功能模块设计（如主程序模块设计）1.主程序模块：连接各种功能子模块，使用循环等待用户操作，完成程序的基本操作实现功能。2.菜单显示模块：生成每个菜单的显示界面，使程序更简单清晰3.用户操作功能模块，由主程序直接调用的函数模块，将功能具象化4.系统工具函数模块，提供如判断字符串是否为纯数字、计算两点之间距离等功能，将常用功能独立化，方便重复使用《校园导游咨询*》设计报告—10—3)模块层次调用关系图开始欢迎画面选择界面1.查询景点信息2.景点导航3.修改景点或道路界面4.开发人员工具5.显示地图0.退出系统构造初始数据3.修改景点信息2.添加道路1.添加景点3.DFS2.查看邻接矩阵1.查看邻接表4.BFS0.返回上级菜单0.返回上级菜单结束结束画面《校园导游咨询*》设计报告—11—四、详细设计实现概要设计中定义的所有的类的定义及类中成员函数，并对主要的模块写出伪码算法。BGraph::构造函数(传入Sitea[],Roadb[],intn,inte)//传入顶点类数组a，边类数组b，顶点数、边数{顶点数=n;边数=e;A[]赋值给Adjlist[]成员变量vex插入边a[i][j]插入边a[j][i]//初始化距离矩阵新建整形二维数组dis[][]，长度、宽度均为MAXSIZE，全部赋值为UR循环次数为（边表数目）{当(下一个指针存在){将E的权值放入矩阵中制定位置指针后移}//初始化风景矩阵新建整形二维数组scn[][]，长度、宽度均为MAXSIZE，全部赋值为0循环次数为（边表数目）{当(下一个指针存在){将E的权值放入矩阵中制定位置指针后移}顶点数自增}voidBGraph::添加景点{bool旗标=false;《校园导游咨询*》设计报告—12—整形数据下标1，下标2，风景等级String型数据temp景点型数据n如果顶点数目到达最大值提示用户否则{输入需要添加的景点名调用通过景点名返回景点型变量函数，赋值给n输入景点信息输入景点坐标修改距离邻接矩阵、风景邻接矩阵}voidBGraph::添加边(){输入节点1，节点2查询节点1、节点2的下标advx在adjlist[]中节点1、节点2互相添加一条到对方的边修改邻接距离矩阵修改邻接风景矩阵边数自增}SiteBGraph::通过景点名称查找景点(stringname){声明int型指针num_s，num_e，num_d输入景点名在adjlist[]中查找是否有景点名为name的景点若不存在输出不存在否则返回该adjlist[]的vex}voidBGraph::导航(){{用户输入导航原则若导航原则为距离优先t1=最短路程距离;t2=m;《校园导游咨询*》设计报告—13—将距离邻接矩阵二维数组复制给临时变量数组temp[][]若导航原则为风景优先t1=最优风景总值;t2=;将风景等级邻接矩阵二维数组复制给临时变量数组temp[][]输出请输入起点输入给name1;查询name1对应下标值，赋值给num_s输出请输入终点输入给name2;查询name2对应下标值，赋值给num_d动态生成num_e声明一个长宽为maxsize的二维数组D声明一个长宽为maxsize的二维数组path循环赋值{将权值数组temp[][]赋值给D[][]将权值存在的元素在path数组中对应位置设置为i不存在的设置为-1若path中存在比当前路径更小的路径更新为新的路径}输出起点当path中还存在下一个点{输出当前指向顶点名称计算当前点与前一点的位置关系，存到t计算当前点与前一个点的距离，存到d输出【向t走d*比例尺米】-;}不存在了的话输出-结束Path指针后移一位}《校园导游咨询*》设计报告—14—五、调试分析（包括调试过程中遇到的问题及解决的方法、算法的时间空间复杂性分析、经验体会。）在本次设计中，对于求两点之间的最短路径方法花费了最多时间，之前对于迪杰斯特拉算法和弗洛伊德算法的不熟料导致在运用上不能非常得心应手，产生了诸多问题。在计算的时间、空间复杂度上，在尽可能减少占用空间和所需时间上，努力减少了循环层数，编写析构函数及时释放了空间。通过本次试验，我较好的掌握了C++编写技术、数据结构中图的各类应用及VS2012界面、操作、调试技术，为未来的工作学习打下了更好的基础。六、测试结果《校园导游咨询*》设计报告—15—《校园导游咨询*》设计报告—16—《校园导游咨询*