校园导游图.doc

计算机科学与工程学院 数据结构课程设计报告 2014—2015 学年 第二学期 小组成员 学生姓名 专业班级 学号 _黄 煜_ _计算机132_ _201311243_ _范文浩_ _计算机132_ _201313463_ 指导教师：张沛露 计算机科学与工程学院 2015 年 6 月 一、课程设计题目和要求 题目：校园导游图 要求：用无向网表示本学校校园景点平面图，选取若干个有代表性的景点抽象成无向带权图，图中顶点表示校内各顶点，边上权值表示路径长度。能够： （1）为来访客人查询各景点的相关信息； （2）为来访客人查询图中任意两个景点间的最短路径 （3）为来访客人查询图中任意两个景点间的所有路径 （4）为来访客人修改图中顶点和边的信息 （5）为来访客人增加景点和路径 （6）为来访客人删除景点和路径 （7）为来访客人输出对应编号景点的信息 二、 开发平台 处 理 器：Intel Core i5 物理内存：2048M 操作系统：Microsoft Windows 7 开发环境：Microsoft VC 6.0 三、自定义数据结构 ? 数据对象V：V具有相同特性的数组元素的集合，称为顶点集 数据关系R：R={VR} VR={x,y|P(x,y)^(x,y属于V)} ADT Graph{ 数据对象V：一个集合，该集合中的所有元素具有相同的特性 数据关系R：R={VR} VR={x,y|P(x,y)^(x,y属于V)} 基本操作： （1）????initgraph(G)； （2）?? creatgraph(mgraph G)??； （3）?? DeleteplanArc(mgraph G) ；?? （4）???DeleteVertex(mgraph G)； （5）? enarc(mgraph G)；?? （6）? enverx(mgraph G)?； }ADT Graph 基本操作： 1、void displaycampus(mgraph g)输出所有顶点信息（即将展示校园全景图） 2、void seaabout(mgraph G)根据输入编号用来查询各个景点信息 3、void shortestpath_Floyd(mgragh *g)用弗洛伊德阿算法求两个景点间最短路径 4、void Allpaths(mgragh *g)显示输入两个顶点间的所有路径 5、int changegraph(mgraph G) 更改图的信息 6、int locatevex(mgraph c,int v)景点的定位 7、void creatgraph(mgraph G) 创建图的邻接矩阵 8、void printmatrix(mgraph G) 打印图的邻接矩阵； 9、int DeleteplanArc(mgraph G) 删除图一条边； 10、int DeleteVertex(mgraph G) 删除景点 11、int enarc(mgraph G) 增加路径 12、int enverx(mgraph G) 增加结点 13、int newgraph(mgraph G) 更新景点的信息 14、int initgraph(mgraph G) 校园导游图的初始化 15、void main( )主函数，可以调用子函数 16、exit(0) 退出程序 各程序模块之间的调用关系 主函数可调用子程序：1，2，3，4，5，8，14，16 子程序5可调用子程序:,7,8，9,10,11,12,13 子程序9,10,11,12,13可调用子程序:6 四、算法描述 Floyd算法 通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。 从图的带权邻接矩阵A=[a(i,j)] n×n开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；……；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。 五、详细代码 见附录2 六、使用说明 1.校园导游图景点介绍（输出各景点信息）： 应输出所有景点的信息，如下： 景点编号（position） 景点名称(name) 景点介绍(intoduction) 0 土木教学楼 吉林建筑大学特色建筑，楼高5层 1 逸