1、数据结构课程设计数据结构课程设计 一一 问题描述问题描述 用无向网表示*的校园景点平面图， 图中顶点表示主要景点， 存放景点编号、 名称、简介等信息，图中边表示景点间的道路，存放路径长度信息。 程序的主要功能： （1） 查询各景点的相关信息； （2） 查询图中任意两个景点间的最短路径； （3） 查询图中任意两个景点间的所有路径。 *作为一个正在兴起的重点学校， 每年都有很多的领导来参观和学校之间的 交流学习，大多数参观者对学校的景点的相关信息并不是非常了解，所以我们设 计这个校园导游的咨询程序，即*校园导游咨询程序。 二二 数据结构数据结构 1、基本操作： CreateGraph(G):创建图
2、 G。 LocateVertex(G,v):确定顶点 v 在图 g 中的位置，若图 g 中没有顶点 v，则 函数值为“空” 。 GetVertex(G,i):取出图 g 中的第 i 个顶点的值，若 i 大于图 g 中顶点数， 则函数值为“空” 。 FirstAdjVertex（G，v） ：求图 G 顶点 v 的第一个邻接点，若 v 无邻接点或 图 G 中无顶点 v，则函数值为“空” 。 NextAdjVertex（G，v，w） ：已知 w 是图 G 中顶点 v 的某个邻接点，求顶点 v 的下一个邻接点（紧跟在 w 后面） ，若 w 是 v 的最后一个邻接点，则函数值为 “空” 。 Insert
3、Vertex（G，u） ：在图 G 中增加一个顶点 u。 InsertArc（G，v，w） ：在图 G 中增加一条从顶点 v 到顶点 w 的弧。 TraverseGraph（G） ：按照某种次序，对图 G 的每个结点访问一次且仅访问 一次。 2、系统中子程序及功能要求： path(MGraph g,int i,int j,int k)：确定路径上第 k+1 个顶点的序号,k 初始值为 0 apath(MGraph g,int i,int j)：初始化访问标志与路径条数，并调用 path （）函数 cpath(MGraph g,int path1,int i,int v0)：输出最短路径 bpa
4、th(MGraph g,int dist,int path1,int s,int n,int v0,int i)： 由 path1 计算从 v0 到 i 的最短路径 Dijkstra(MGraph g,int v0,int p)：采用迪杰斯特拉算法求从顶点 v0 到顶点 p 的最短路径 chaname(MGraph g)：查询景点的信息 chapath1(MGraph g)：查询两个景点间的所有路径 chapath2(MGraph g)：查询两个景点间的最短路径 3、各程序模块之间的调用关系： 函数的调用关系图 main chaname chapath1 chapath2 apath Dijk
5、stra path bpath path cpath cpath 主函数可调用子程序 子程序可调用子程序 子程序可调用子程序 子程序可调用子程序 子程序可调用子程序 子程序可调用子程序 子程序可调用子程序 子程序可调用子程序 子程序可调用子程序 三三 算法设计思想及流程图算法设计思想及流程图 顶点、边和图的类型： typedef struct int num;/*顶点编号*/ char nameMAXSIZE;/*顶点名称*/ char discriptionMAXLEN;/*顶点信息描述*/ VertexType; typedef struct int edgesMAXVMAXV; int
6、vexnum,arcnum; VertexType vexsMAXV; MGraph; int visitedMAXV; int pMAXV; 创建*地图： int i,j; int b11=1,2,3,4,5,6,7,8,9,10,11; char *c11=/*各个景点名称*/; char *d11=/*字符串指针数组,用来给每个顶点的简介信息进行赋值 */; MGraph g;/*创建一个无向网*/ int A1111=/*景点的相关简介进行赋值*/ ; g.vexnum=顶点个数; g.arcnum=顶点边数; /*建立无向网的邻接矩阵*/ for(i=0;i“,g.vexsv0.name); cpath(g,path1,i,v0); printf(“%s “,g.vexsi
