数据结构-校园导航问题

问题描述：设计一个校园航程序，为来访的客人提供各种信息查询服务。a. 设计大学的校园平面图，所含单位地点不少于十个。以图中各顶点表示校内各单位地点，存放单位名称，代号，简介等信息 ；以边表示路径，存放路径长度等相关信息。b. 为来访客人提供图中任意单位相关信息的查询。c. 为来访客人提供图中任意单位的问路查询，即查询任意两个单位之间的一条最短的路径。 数据结构：用图来描述校园内各个单位，顶点包括名称和简介，边包括两个端点和距离。 结果形式：输入要查询的单位，显示单位简介。输入两个单位，计算两个单位地点间最短距离。 测试数据：校园单位可包括：前门、后门、图书馆、教一楼、教二楼、教三楼、操场、食堂、水房、学一、二、三、四楼等。

 typedef int VRType;
 typedef char InfoType;
 #define MAX_NAME 5 // 顶点字符串的最大长度+1
 #define MAX_INFO 20 // 相关信息字符串的最大长度+1
 typedef char VertexType[MAX_NAME];
 #include“Graph_Matrix.h“
 #include“Graph.h“
 typedef int PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 路径矩阵，二维数组MAX_VERTEX_NUM的定义在Graph_Matrix中
 typedef int ShortPathTable[MAX_VERTEX_NUM]; // 最短距离表，一维数组

 void ShortestPath_DIJ（MGraph Gint v0int v1PathMatrix PShortPathTable D）
 { // 用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]及带权长度
   // D[v]。若P[v][w]为TRUE，则w是从v0到v当前求得最短路径上的顶点。
   // final[v]为TRUE当且仅当v∈S，即已经求得从v0到v的最短路径 算法7.15
   int vwijmin;
   int flag=0;
   Status final[MAX_VERTEX_NUM]; // 辅助矩阵，为真表示该顶点到v0的最短距离已求出，初值为假
   for（v=0;v   {
     final[v]=FALSE; // 设初值
     D[v]=G.arcs[v0][v].adj; // D[]存放v0到v的最短距离，初值为v0到v的直接距离
     for（w=0;w       P[v][w]=FALSE; // 设P[][]初值为FALSE，没有路径
     if（D[v]       P[v][v0]=P[v][v]=TRUE; // 一维数组p[v][]表示源点v0到v最短路径通过的顶点
   }
   D[v0]=0; // v0到v0距离为0
   final[v0]=TRUE; // v0顶点并入S集
   printf（“%s->“G.vexs[v0]）;//经过路径的起始顶点
   for（i=1;i   { // 开始主循环，每次求得v0到某个顶点v的最短路径，并将v并入S集
     min=INFINITY; // 当前所知离v0顶点的最近距离，设初值为∞
     for（w=0;w       if（!final[w]&&D[w]       {
	 v=w;
	 if（v==v1）
		 flag=1;
	 min=D[w];
       }
     final[v]=TRUE; // 将v并入S集
//下面语句输出了经过的路径，剔除了不需要的顶点
	 if（flag==0）
	 printf（“%s->“G.vexs[v]）;
	 else if（v==v1）
		 printf（“%s“G.vexs[v]）;//结束顶点

     for（w=0;w       if（!final[w]&&min       { // w不属于S集且v0→v→w的距离＜目前v0→w的距离
         D[w]=min+G.arcs[v][w].adj; // 更新D[w]
	 for（j=0;j	   P[w][j]=P[v][j];
	 P[w][w]=TRUE;
       }
   }
 }

 void main（）
 {
   int ijv0v1;
   int stopflag=0;
   VertexType ab;
   MGraph g;
   PathMatrix p; // 二维数组，路径矩阵
   ShortPathTable d; // 一维数组，最短距离表   
   printf（“输入顶点信息时使用学校地点的代码：\n“）;
   printf（“v0:前门；v1：后门；v2：图书馆；v3:教一楼\n“）;
   printf（“\n“）;
   printf（“v4:食堂；v5：操场；v6：实验楼；v7:学一楼\n“）;
   printf（“\n“）;
   printf（“v8:水房；v9：学二；va：学三楼；vb:学四楼\n“）;
   printf（“\n“）;
   CreateUDN（g）; // 构造无向网g
   Display（g）; // 输出无向网g
      do
   {
   printf（“输入要查询的两个点（以空格隔开）：\n“）;
   scanf（“%s%s%*c“ab）; //%*c吃掉回车符
  for（i=0;i   {
	   if（strcmp（g.vexs[i]a）==0）
		   v0=i;
	   if（strcmp（g.vexs[i]b）==0）
		   v1=i;
   }
  printf（“经过的路径为：“）;
   ShortestPath_DIJ（gv0v1pd）;//以g中位置为0的顶点为源点，球其到其余各顶点的最短距离。存于d中
   printf（“\n“）;
    printf（“%s到顶点%s的最短路径长度为（若是-1，则表示没有通路）：\n“ab）;
   for（i=0;i     if（i!=0&&strcmp（g.vexs[i]b）==0）
	 {
		 if（d[i]>=INFINITY）
			 d[i]=-1;//若两点间没有通路，用“-1”表示
		 printf（“%s-%s:%d“g.vexs[v0]g.vexs[i]d[i]）;
	 }
	 printf（“\n“）;
	 printf（“输入stopflag‘1‘为结束程序，‘0‘为继续查询：\n“）;
	 stopfla

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件    2223104  2009-04-23 16:58  5-daohang\daohang.ncb

     文件        887  2009-04-15 18:54  5-daohang\daohang.sln

    ..A..H.     18432  2009-04-23 16:58  5-daohang\daohang.suo

     文件      33280  2009-04-23 16:52  5-daohang\Debug\daohang.exe

     文件     335988  2009-04-23 16:52  5-daohang\Debug\daohang.ilk

     文件     510976  2009-04-23 16:52  5-daohang\Debug\daohang.pdb

     文件      31744  2009-04-22 19:08  5-daohang\Debug\tongxin.exe

     文件     330948  2009-04-22 19:08  5-daohang\Debug\tongxin.ilk

     文件     519168  2009-04-22 19:08  5-daohang\Debug\tongxin.pdb

     文件      11772  2009-04-23 16:52  5-daohang\tongxin\Debug\BuildLog.htm

     文件        621  2009-04-23 16:52  5-daohang\tongxin\Debug\daohang.exe.intermediate.manifest

     文件      39892  2009-04-23 16:52  5-daohang\tongxin\Debug\Main.obj

     文件         65  2009-04-23 16:52  5-daohang\tongxin\Debug\mt.dep

     文件        621  2009-04-22 19:08  5-daohang\tongxin\Debug\tongxin.exe.intermediate.manifest

     文件     257024  2009-04-23 16:52  5-daohang\tongxin\Debug\vc90.idb

     文件     217088  2009-04-23 16:52  5-daohang\tongxin\Debug\vc90.pdb

     文件       2290  2009-04-23 14:52  5-daohang\tongxin\Graph.h

     文件        601  2009-04-15 19:09  5-daohang\tongxin\Graph_Matrix.h

     文件       4103  2009-04-23 16:52  5-daohang\tongxin\Main.cpp

     文件       3783  2009-04-22 19:14  5-daohang\tongxin\tongxin.vcproj

     文件       1411  2009-04-23 16:58  5-daohang\tongxin\tongxin.vcproj.Dave-PC.文刀.user

     文件    1174528  2009-04-22 20:22  5-daohang\tongxin.ncb

     文件     122880  2009-05-13 17:07  5-校园导航.doc

     目录          0  2009-04-23 18:10  5-daohang\tongxin\Debug

     目录          0  2009-04-23 18:10  5-daohang\Debug

     目录          0  2009-04-23 18:10  5-daohang\tongxin

     目录          0  2009-04-23 18:10  5-daohang

----------- ---------  ---------- -----  ----

              5841206                    27



............此处省略0个文件信息