课程设计总结报告模板.docx

课程编号:B080109010数据结构课程设计总结报告姓名刘德政学号20142883班级软件1401指导教师李昕实验名称数据结构课程设计开设学期2016-2017第一学期开设时间第10周——第12周报告日期评定成绩评定人评定日期2016-11-28东北大学软件学院第一章需求分析文档名称景区景点浏览、、线路推荐及道路规划解决方案项目概要这是一个为该景区设计的软件系统。能够对该景区的景点进行浏览。游客可根据自己感兴趣的景点进行关键字查询。本系统能够将各个景点按受欢迎程度、设施完善程度等特点进行排序,并能够为游客和导游提供游览整个景区的合理的路线,也可提供任意两个景点间最方便到达的路径,给客户提供最良好的体验。为了方便广大游客前来参观,景区特意设置了停车场,分为私家车停车场和旅游巴士停车场,给游客(及游客团队)提供最优质的停车服务。同时,景区一期工程的道路建设方案也在此展示,旨在最大程度上节省资金。用户类型景区官方工作人员参观景区的客户、向导问题的定义(功能需求):分别通过图的邻接表和邻接矩阵的定义来实现,其中,在定义邻接表时,录入所有顶点信息和所有边的信息(文件或数据库表),再利用这些信息来构造图的邻接矩阵定义,最后输出。创建导游线路图:首先对整个图进行深度优先遍历,可用递归法和非递归法。以此查看遍历结果中相邻的点,如果这两点之间存在边,则直接分别加入导游图和一个栈中,否则依次查看这两点中的前一个点和栈顶元素之间是否有边,如果没有,将这些栈顶依次加入导游路线图,否则继续考察深度优先遍历结果的序列。输出导游路线图及其图中的回路部分:找到导游线路图中重复的部分,分别判断返回的点和这些重复的店之间是否有边,如果没有,则当前重复的点属于回路中的一个点,否则该重复的点是该回路中的最后一个点,将这些点统计起来,方可构成一个回路。输出两个景点之间最短路径和最短距离:运用迪杰斯特拉最短路径算法计算图中任意两点间的最短距离,本系统采用图的邻接表定义来计算。输出道路修建规划图:运用prim最小生成树算法,本系统采用图的邻接矩阵定义来实现。查找及排序:利用查找字符串子串的算法来查找相关景点;按照景点的相关属性排序(如受欢迎度等),本系统采取快排、插入排序和冒泡排序法。输出车辆的进出信息:借助两个栈和一个队列进行实现。问题的研究意义分析图的邻接矩阵和邻接表定义(ADT)及其相关操作。掌握最短路径算法和最小生成树算法。掌握排序算法,并掌握时间、空间复杂度分析。:图结点中景点的定义:structVertex{ intid;//景点标识 StringspotName;//景点名称 StringspotBriefIntro;//景点简介 doublelevelOfAppeal;//受欢迎度 boolhasRestArea;//是否有休息区 boolhasToliet;//是否有卫生间};边的信息的定义:structEdge{ doubletimeCost;//花费的时间 doubledistance;//距离 Stringdest;//终点名称(终点的景点名称) intdest_id;/终点标识};存储边信息的链表的结点定义:structVNode{ Edge*edge;//数据域为一个边的信息(动态分配内存) VNode*next;//指针域为链表的下一个结点(的地址)};图结点的定义:ode{ Vertex*vertex;//一个景点信息(动态分配内存) VNode*adj;//邻接链表};(5)图结点代理类的定义(用于计算最短路径算法)structArcShortestPathProxy:ode{ doublefee;//从起始结点到该节点的代价 intlast_node;//上一跳结点 boolvisited;//该结点是否已加入 ode*arc;//父类的指针};(6)图的邻接表定义:structGraph{ unsignedintnum_of_vertex;//图顶点个数 Array<ode*>node_table;//存放结点的数组//递归法深度优先遍历 voiddfs(); voiddfs(intver,Array<bool>&visit);//迭代法深度优先遍历 Array<int>dfs_non