南通大学校园导航系统.doc

南通大学计算机学院上机实验报告课程名称: 算法设计与分析班级: 学号: 姓名: 指导老师: 一、题目与要求题目: 设计并开发南通大学校园导航系统(1 )使用最短路径算法: Dijkstra 算法( 2 )可组队完成(最多 5 人一组) ,但需明确分工(3 )编程语言不限、最简单就是实现算法,最复杂可以引入地图 功能要求 1. 不同的功能使用不同的函数实现(模块化) ,对每个函数的功能和调用接口要注释清楚。对程序其它部分也进行必要的注释。 2 .对系统进行功能模块分析、画出总流程图和各模块流程图。 3. 用户界面要求使用方便、简洁明了、美观大方、格式统一。所有功能可以反复使用,最好使用菜单。 。 。 设计内容: ,方便用户走访学校。 2. 登录模块。该模块在进入主界面之前先执行, 用于对进入系统的用户进行身份验证,若用户输入正确的用户名及用户密码,则进入主界面,否则输入超过 3 次错误则退出程序。处理方法:用户名及用户密码可保存在一文件中,校验时从文件中读入数据进行校验。在系统中应增加一个用户管理模块,在其中可新增用户,修改用户信息等。 3. 系统帮助。显示开发者姓名、班级、开发完成日期、版本号和指导老师等信息。二、分析 设计基础:要掌握最短路径的实现方式。 分析设计课题的要求,要求编程实现以下功能: (1) 退出系统(2) 进入南通大学导航系统(3) 新增用户信息(0) 修改密码 主控菜单设计为实现导航的操作功能,首先设计一个含有多个菜单项的主控菜单程序,然后再为这些菜单项配上相应的功能。程序运行后,给出菜单项的内容和输入提示,如下: 1 显示场所编号 2 计算路径长度及找出最短路径 3 退出 设计课题已明确要求,有关的定义如下: void insert(); #define N10 int n=1; #define Max 32767 #define NUM 16 typedef struct ell {int adj; //相邻接的景点之间的路程 char *info; }ell; //定义边的类型 typedef struct VertexType {int number; //景点编号 char *sight; //景点名称 char *description; //景点描述}VertexType; //定义顶点的类型 typedef struct {VertexType vex[NUM]; //图中的顶点,即为景点 ell arcs[NUM][NUM]; //图中的边,即为景点间的距离 int vexnum,um; //顶点数,边数}MGraph; //定义图的类型 MGraph G;//把图定义为全局变量 int P[NUM][NUM]; // long int D[NUM]; //辅助变量存储最短路径长度 void CreateUDN(int v,int a); //创建图的函数 void pingmu(); //屏幕输出函数 void ShortestPath(int num); //最短路径函数 void output(int sight1,int sight2); //输出函数 void PrintMGraph(); char Menu(); //主菜单 void mainn(); 逻辑设计: 按所设想的功能,把程序化分为几个模块,各模块的名称和其数据类型如下: (1)Main 主函数调用各函数,实现课程设计的目标。其中包含三个功能,一个是直接进入导航系统,利用主函数中已有的数据,进行查询:一个是进行创建数据,本程序中初始数据为通大的导航数据,如果需要也可以自己建立一个;最后一个是退出功能。(2)Menu 菜单函数该函数用于显示初页面,列出两个功能的选择。一个是进入通大导航系统, 一个是进行自己创建一个导航系统。(3)dijkstra 建立最小生成树这是本程序的中心,在众多路径中选出最短路径。基于对 dijkstra 求最小生成树方法的应用。使整个程序显得极为简便。课本中的 dijkstra 函数只是输入一个结点,然后输出从该结点出发到各结点的最短路径,为了使它更适用于本课程设计,我将它改为“输入两个结点,输出这两点的最短路径”。 程序调试的实验截图?用户登陆界面首先加载“ ”文件,该文件包含初始用户名和密码。程序加载该文件: 按回车后,需输入初始用户名和密码(用户名: zjw ,密码 111111 ): ?用户登陆界面成功?新增用户信息此时打开“ ”,我们会看到: 下次重新运行该程序时就