文档介绍：计算机科学与工程学院
数据结构课程设计报告
2014—2015 学年 第二学期
小组成员
学生姓名 专业班级 学号
_黄 煜_ _计算机132_ __
_范文浩_ _计算机132_ __
指导教师：张沛露
计算机科学与工程学院
2015 年 6 月
一、课程设计题目和要求
题目：校园导游图
要求：用无向网表示本学校校园景点平面图，选取若干个有代表性的景点抽象成无向带权图，图中顶点表示校内各顶点，边上权值表示路径长度。能够：
（1）为来访客人查询各景点的相关信息；
（2）为来访客人查询图中任意两个景点间的最短路径
（3）为来访客人查询图中任意两个景点间的所有路径
（4）为来访客人修改图中顶点和边的信息
（5）为来访客人增加景点和路径
（6）为来访客人删除景点和路径
（7）为来访客人输出对应编号景点的信息
二、 开发平台
处 理 器：Intel Core i5
物理内存：2048M
操作系统：Microsoft Windows 7
开发环境：Microsoft VC
三、自定义数据结构 n
数据对象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
六、使用说明
（输出各景点信息）：
应输出所