校园导游资讯系统课程设计报告

湖南涉外经济学院课程设计报告课程名称：数据结构报告题目：校园导游咨询系统学生姓名：余甜、童英俊、杨胜玉、薛志明所在学院：信息科学与工程学院专业班级：软件工程1402班学生学号：144300234、33、31、39指导教师：李春庭老师2014年12月25日课程设计任务书报告题目校园导游咨询系统完成时间2周学生姓名余甜专业班级软工1402指导教师李春庭职称讲师总体设计要求和主要功能设计湖南涉外经济学院的校园平面图，所含景点不少于10个和20条边。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。查找任意景点的信息，找出从任意景点到达另一景点的最佳路径（最短路径）功能要求如下：1．首先创建一个包含10个以上景点名称、代号、简介等信息的数据文件作为数据输入，另外建一个文件包含20条边（道路）及权值（长度）的文件，程序运行时自动载入并读取数据创建无向网。。2．菜单功能：显示顶点序列（景点名称及相应代号），根据代号查询景点（信息），任意两个景点（代号）间的最短路径，退出系统。。工作内容及时间进度安排第17周：周1---周2：立题、论证方案设计周3---周5：系统设计和程序编码第18周：周1---周3：程序调试周4---周5：验收答辩摘要随着现代社会生活节奏的加快，人们外出旅游以寻求放松的时间越来越多。开发本系统的目的在于为来访我校的游客提供一条最短游览路径。本系统的设计基于图的结构，创建一个无向图，针对游客的实际需求，将湖南涉外经济学院的景点编号、名称、介绍等信息放入到图的顶点当中并保存在景点文本文件当中，将两个景点的编号和它们之间的距离当作权值也保存到权值文本文件当中，利用迪杰斯特拉算法来求从一个景点到另一个景点的最短距离，利用，函数来查找景点，并显示出它的信息，从而解决了要查找的景点信息和景点之间的最短路径的问题，最后按照提示进行相关的操作。关键词：无向图、邻接表、最短路径、校园导游咨询目录一、需求分析................................................................................................................51．问题描述.......................................................52．输入输出需求...................................................5二、概要设计................................................................................................................51．总体设计图.....................................................52．数据结构设计...................................................63．算法设计.......................................................64．主要模块及模块之间的关系.......................................6三、详细设计...............................................................................................................61．结构体设计.....................................................62．主要模块实现的流程图...........................................83．各模块的算法实现...............................................8四、测试运行................................................................................................................91．运行说明.......................................................92．运行效果图.....................................................9五、总结报告..............................................................................................................111．总体评价......................................................112．我所做的工作及体会............................................12六、程序附录..............................................................................................................12七、参考文献.............................................................................................................235一、需求分析1．问题描述依据课程设计的要求，利用一个无向图的结构，将景点当作图的顶点，将景点之间的距离当作权值来存储，然后根据游客自己的需求，按照显示屏上的提示来进行查找景点介绍，查找两个景点之间的最短距离，退出程序等基本操作。2．输入输出需求初始数据通过编辑两个文本文件产生，每个文件数据包含了10条以上记录，每条记录包含景点名称、景点介绍，然后定义一个邻接矩阵结构体来储存边的信息，最后定义一个无向图类型的结构体来储存顶点的信息、边的信息、顶点的个数、边的个数。最后游客按照提示来进行相关的操作。二、概要设计1．总体设计图如图1所示，依据无向图的操作通过查找函数来查找景点的信息，通过迪杰斯特拉函数来查找最短距离，开始时首先从文件中读取景点代号、景点名称、景点简介以及两个景点之间边的距离即权值，然后将其加入到邻接表当中，之后进入主菜单界面，根据用户的选择执行相应的操作，最后调用退出函数实现系统退出功能。图1主界面显示顶点序列根据代号查询景点任意两个景点间的最短路径退出系统景点名称查询景点代号查询显示各边信息62．数据结构设计数据采用结构体方式存储，逻辑结构为邻接表，存储结构为顺序存储结构，系统操作的数据元素主要是设计一个图的结构体来存取模拟的各个景点结构组成，景点的个数和各景点之间的路径分别存储在两个文本文件中，系统主要操作一个表如下：名称变量名数据类型长度描述表头向量datachar[]100景点名称*fistarcarcnode100景点简介顶点数目vexnumint10景点个数边数目arcnumint20各景点之间路径数图矩阵arcsint100图的矩阵形式3．算法设计本系统主要用到的算法有迪杰斯特拉算法、邻接矩阵创建算法、顺序查找算法、矩阵创建算法、数据打印算法等。由于系统只有主界面没有登录界面，因此执行完主菜单和二级菜单后返回的是主界面，而不是退出程序。4．主要模块及模块之间的关系程序没有登录界面，主界面菜单模块提供显示菜单并供用户选择；只有通主界面的菜单选项才能进入二级菜单，景点信息显示模块显示的是每个景点的代号、名称和简介；查询模块提供任一景点信息的查询功能，边信息显示模块显示具体的每条边和边的长度；最后一个模块提供任意两个景点（代号）间的最短路径；主界面中的各个模块都是独立运行，通过相应的函数调用实现。从主界面可以直接选择退出菜单而实现退出整个系统。三、详细设计1．结构体设计本程序一共由四个结构体构成，邻接表结构体，包括表头信息，邻接矩阵，图的顶点数和边数，其中表头、边、顶点又是一个结构体类型。typedefstruct{//邻接表adjlistbiaot;//邻接表表头向量intarc[10][10];//矩阵intvexnum;//图的当前顶点数intarcnum;//图的当前边数}algraph;表头结构体：7typedefstructdnode{//顶点结点typedata;//顶点(景点)信息arcnode*firstarc;//链表头的第一条指针}adjlist[max_vexnum];边结构体：typedefstructarcnode{//边结点intadjvex;//顶点的位置floatcost;//权值即路径长度structarcnode*nextarc;//指向顶点的下一条弧的指针}arcnode;顶点结构体：typedefstructtype{//顶点类型charvex;charname[100],jianjie[100];}type;2．主要模块实现的流程图用户直接进入的是主菜单界面，用菜单的形式实现，输入1到5有效，否则返回到主界面等待用户输入。具体模块流程图如图2所示8图23．各模块的算法实现邻接表创建算法实现描述：建立一个无向图的结构体包括顶点、边，对图中每个顶点建立一个单链表,第i个单链表中的结点表示依附于顶点vi的边(对有向图是以顶点vi为尾的弧)。每个结点含三个域:邻接点域(adjvex)指示与顶点vi邻接的点在图中的位置,链域(nextarc)指示下一条边或弧的结点;数据域如权值等。景点信息打印函数实现描述：查找邻接表的每一景点，把每个景点的代号、名称、简介都输出到屏幕。5?是否否否否否是是是是2？1？代号查询名称查询3？回上一级是是是否否开始否结束9查询模块算法描述如下：进入二级菜单选择景点代号查询或景点名称查询，如：用户输入所要查询景点的代号或景点名称，运用一个循环语句依次与图中每一个景点的代号或名称作比较，若找到相同的，则退出循环显示此景点的信息。景点各边打印算法描述如下：如景点信息打印函数原理一样，把邻接表从头跑到尾，将每条边和边的长度打印到屏幕。最短路径算法描述：求任意两景点之间的最短距离，运用迪杰斯特拉算法，设置两个顶点的集合S和T=V-S，集合S中存放已找到最短路径的顶点，集合T存放当前还未找到最短路径的顶点。初始状态时，集合S中只包含源点v0，然后不断从集合T中选取到顶点v0路径长度最短的顶点u加入到集合S中，集合S每加入一个新的顶点u，都要修改顶点v0到集合T中剩余顶点的最短路径长度值，集合T中各顶点新的最短路径长度值为原来的最短路径长度值与顶点u的最短路径长度值加上u到该顶点的路径长度值中的较小值。此过程不断重复，直到集合T的顶点全部加入到S中为止。四、测试运行1．主界面运行效果图2．运行说明在主菜单界面，为了实现操作过程，需要预先编辑两个带有景点信息和路径的文本文件。用以构建一个有具体数据的无向图。103．运行效果图11表学生情况统计表序号姓名性别出生日期学号专业联系电话备注1余甜女1997.06.12144300234软件工程18807429572编写程序2童英俊女1997.08.17144300233软件工程15700740195查找资料3杨胜玉女1996.11.27144300231软件工程18821853179撰写报告4薛志明男1996.05.26144300239软件工程18973797988打印报告五、结论与心得1．总体评价从12月21日到12月29日这9天的时间里组长负责写程序代码，组员负责查找资料，编辑测试数据文件，我们一起合作完成了这个校园导游咨询系