《数据结构课程设计之校园导航系统》由会员分享，可在线阅读，更多相关《数据结构课程设计之校园导航系统（23页珍藏版）》请在金锄头文库上搜索。
1、#大学数据结构课程设计报告题目： 校园导航系统院（系）：计算机工程学院 学生姓名: 班级： 学号: 起迄日期: 2011.6.19-6.30指导教师: 指导教师评语： 成绩： 签名： 年 月 日20XX20XX年度 第 2 学期 一、需求分析 1.问题描述：从理工大学的平面图中选取10个有代表性的景点，抽象成一个无向带权图。以图中顶点表示景点，边上的权值表示两地之间的距离，求取任意两点间最短路径。 2.基本功能 本程序主要实现的功能是为用户提供路径咨询。根据用户指定的始点和终点输出相应路径（用到output（）函数），或者根据用户指定的景点输出景点的信息（用到search（）函数）。 3.输入
2、输出 本程序主要输入输出信息是景点编号和景点名称，以字符串的形式输入输出。二、 概要设计1.设计思路： 本程序是校园导航系统，即求两点间的最短路径。其主要算法是迪杰斯特拉算法，在此基础上再加上菜单函数输出函数造图函数查找函数即可。 2.数据结构设计： 抽象数据类型图的定义如下：ADT Graph 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R： R=VR VR=(v,w)|v,w V,(v,w）表示v和w之间存在路径 基本操作p： CreatGraph（&G，V，VR） 初始条件：V是图的顶点集，VR是图中边的集合。 操作结构：按V和VR的定义构造图G。 Destroy
3、Graph（&G） 初始条件：图G存在。 操作结果:销毁图G。 LocateVex（G，u） 初始条件：图G存在，u和G中顶点有相同特征。 操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其他信息。 GetVex（G，v） 初始条件：图G存在，v是G中某个顶点。 操作结果：返回v的信息。 FirstEdge（G，v） 初始条件：图G存在，v是G中某个顶点。 操作结果：返回依附于v的第一条边。若该顶点在G中没有邻接点，则返回“空”。 NextEdge（G，v，w） 初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。 操作结果:返回依附于v的（相对于w的）下一条边。若不存在，则返
4、回“空”。 InsertVex（&G,v） 初始条件:图G存在，v和图中顶点有相同特征。 操作结果：在图G中增添新顶点v。 DeleteVex（&G,v） 初始条件：图G存在，v是G中某个顶点。 操作结果：删除G中顶点v及其相关的边。 GetShortestPath（G，st，nd，&Path） 初始条件：图G存在，st和nd是G中的两个顶点。 操作结果：若st和nd之间存在路径，则以Path返回两点之间一条最短路径，否 则返回其他信息。3.软件结构设计： void CreatUDN（int v，int a） 造图函数 void narrate（） 说明函数 void ShortestPath
5、（int num） 最短路径函数 void output（int sight1，int sight2）输出函数 void search（） 查询函数 char Menu（） 主菜单 char SearchMenu（） 查询子菜单函数 主程序模块 带权无向图模块三、 详细设计 1. 边 顶点和图类型 #define Max 20000 #define NUM 10 typedef struct ArcCell int adj; /* 相邻接的景点之间的路程 */ ArcCell; /* 定义边的类型 */ typedef struct VertexType int number; char* s
6、ight; char* info; VertexType; /* 定义顶点的类型 */ typedef struct MGraph VertexType vexNUM; /* 图中的顶点，即为景点 */ ArcCell arcsNUMNUM; /* 图中的边，即为景点间的距离 */ int vexnum,arcnum; MGraph; /* 定义图的类型 */2.void main() /* 主函数 */int v0,v1;char ck;CreateUDN(NUM,11);do ck=Menu(); switch(ck) case 1: system(cls); narrate(); /*
7、输出景点列表 */ printf(nnttt请选择起点景点（09）：); scanf(%d,&v0); printf(ttt请选择终点景点（09）：); scanf(%d,&v1); ShortestPath(v0); /* 计算两个景点之间的最短路径 */ output(v0,v1); /* 输出结果 */ printf(nntttt请按任意键继续.n); getchar(); getchar(); break; case 2:search(); break; ;while(ck!=e); char Menu() /* 主菜单 */char c;int flag;do flag=1; sys
8、tem(cls); narrate(); /* 输出景点列表 */ printf(ntttn); printf(ttt n); printf(ttt 1、查询景点路径 n); printf(ttt 2、查询景点信息 n); printf(ttt e、退出 n); printf(ttt n); printf(tttn); printf(tttt请输入您的选择：); scanf(%c,&c); if(c=1|c=2|c=e) flag=0;while(flag);return c; char SearchMenu() /* 查询子菜单 */char c;int flag;do flag=1; sy
9、stem(cls); narrate(); /* 输出景点列表 */ printf(ntttn); printf(ttt n); printf(ttt 1、按照景点编号查询 n); printf(ttt 2、按照景点名称查询 n); printf(ttt e、返回 n); printf(ttt n); printf(tttn); printf(tttt请输入您的选择：); scanf(%c,&c); if(c=1|c=2|c=e) flag=0;while(flag);return c; void search() /* 查询景点信息 */int num;int i;char c;char name20;do system(cls); c=SearchMenu(); switch (c) case 1: system(cls); narrate(); /* 输出景点列表 */ printf(nntt请输入您要查找的景点编号：); scanf(%d,&num); for(i=0;iNUM;i+) if(num=G.vexi.number) printf(nnttt您要查找景点信息如下:); printf(nnttt%-25snn,G.vexi.inf
