石家庄经济学院 本科生课程设计报告书 题 目 校园导游咨询系统 姓 名 颜建学 学 号 410109070321 学 院 信息工程学院 专 业 计算机方向 指导教师 XXXXXX 完成日期： 2012-07-5 1 校园导游咨询系统 1 需求分析 本程序的主要目的是为了提供本学校的景点的路径咨询和来访客人以及刚来报到的新生提供一个快捷方便的路径咨询，快速有效的提高了用户的熟悉度。。满足用户查询的需要： 1、从石家庄经济学院的平面地图中选取出10个有代表性的景点。 2、为来访的客人提供图中任意景点相关信息的查询。当用户输入正确时，为用户输出景点的相关信息；当用户输入不合法时，提示用户输入有误并返回让用户重新输入。 3、为来访的客人提供图中任意景点的路径查询，即查询任意两个景点之间的最短简单路径。当用户输入正确时，为用户输出任意两景点的最短路径；当用户输入不合法时，提示用户输入有误并返回让用户重新输入。 4、为来访客人推荐参观路线。 2 概要设计 1、抽象数据类型图的定义如下： ADT Graph{ 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R： R={VR} VR={(v,w)|v,w∈V,(v,w)表示v和w之间存在路径} 基本操作P： CreatGraph70321(&G,V,VR) 初始条件：V是图的顶点集，VR是图中边的集合。 操作结果：按V和VR的定义构造图G。 DestroyGraph70321(&G) 初始条件：图G存在。 操作结果：销毁图G。 LocateVex70321(G,u) 初始条件：图G存在，u和G中顶点有相同特征。 操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其他信息。 GetVex70321(G,v) 初始条件：图G存在，v是G中某个顶点。 操作结果：返回v的信息。 FirstEdge70321(G,v) 初始条件：图G存在，v是G中某个顶点。 操作结果：返回依附于v的第一条边。若该顶点在G中没有邻接点，则返回“空”。 NextEdge70321(G,v,w) 2 初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。 操作结果：返回依附于v的（相对于w的）下一条边。若不存在，则返回“空”。 InsertVex70321(&G,v) 初始条件：图G存在，v和图中顶点有相同特征。 操作结果：在图中增添新顶点v。 DeleteVex70321(&G,v) 初始条件：图G存在，v是G中某个顶点。 操作结果：删除G中顶点v及其相关的边。 InsertEdge70321(&G,v,w) 初始条件：图G存在，v和w是G中两个顶点。 操作结果：在G中增添边(v,w). DeleteEdge70321(&G,v,w) 初始条件：图G存在，v和w是G中两个顶点。 操作结果：在G中删除边(v,w)。 GetShortestPath70321(G,st,nd,&Path) 初始条件：图G存在，st和nd是G中两个顶点。 操作结果：若st和nd之间存在路径，则以Path返回两点之间一条最短路径，否则返回其他信息。 }ADT Graph 主程序 void main() {初始化； do{ 接受命令（输入景点信息或输出最短路径）； 处理命令； }while（“命令”！=“退出”）； ｝ 2、 调用的函数有如下： void CreateUDN70321(int v,int a); /* 造图函数 */ void narrate70321(); /*说明函数*/ void ShortestPath70321(int num); /*最短路径函数*/ void output70321(int sight1,int sight2); /*输出函数*/ char Menu70321(); /* 主菜单 */ void search70321(); /* 查询景点信息 */ char SearchMenu70321(); /* 查询子菜单 */ void HaMiTonian70321(int); /* 哈密尔顿图的遍历 */ void NextValue70321(int); void display70321(); /* 显示遍历结果 */ 3