daoyou.cpp

利用数据结构的平衡二叉树实现的简单的校园导游程序

//头文件
#include <iostream.h>
#include "conio.h"
#include "stdlib.h"

//预处理，定义一个最大的数字
#define max 32767

//声明两常量，保证能在数组中使用
const int Vex=10;       //声明图中顶点个数
const int Edge=45;      //声明图中边的个数

//构造图的邻接矩阵，是个11X11的矩阵，不需要下标为0的元素
int arcs[Vex+1][Vex+1]={
0,2,4,6,7,8,4,4,7,3,6,
2,0,6,2,1,6,1,3,2,1,9,
4,6,0,1,4,8,2,9,7,4,6,
6,2,1,0,5,2,1,7,2,5,8,
7,1,4,5,0,4,1,6,2,6,5,
8,6,8,2,4,0,1,4,4,2,7,             
4,1,2,1,1,1,0,3,6,7,9,
4,3,9,7,6,4,3,0,9,3,8,
7,2,7,2,2,4,6,9,0,2,4,
3,1,4,5,6,2,7,3,2,0,6,
6,9,6,8,5,7,9,8,4,6,0  };       //是个对称矩阵

//声明图的结构体
struct Graph
{
 int Distance[Vex+1];           //存放源点到各顶点的最短路径
 int PreviousVertex[Vex+1];     //存放在最短路径上该顶点的前一顶点号
 int MarkedVertex[Vex+1];       //已求得的在最短路径上的顶点的顶点号
};

//求最短路径的函数
void theShortestPath(struct Graph &G,  int V,int End)   //V是起始顶点
{                                               //后面的算法即是迪杰斯特拉算法的略微修改
 for(int i=1; i<=Vex; i++)                      
 { G.Distance[i]=arcs[V][i]; 
   G.MarkedVertex[i]=0;
   if((i!=V)&&(G.Distance[i]<max))
	   G.PreviousVertex[i]=V;
   else G.PreviousVertex[i]=0;
 }

   G.MarkedVertex[V]=1; 
   G.Distance[V]=0;
 
 for( i=1; i<Vex; i++)
 {
   int min=max;  
   int u=V;

   for(int j=1; j<=Vex; j++)
   if(!G.MarkedVertex[j]&&G.Distance[j]<min)
   {   u=j;min=G.Distance[j]; }
       G.MarkedVertex[u]=1;

   for(int w=1; w<=Vex;w++)
    if(!G.MarkedVertex[w]&&arcs[u][w]<max&&G.Distance[u]+arcs[u][w]<G.Distance[w])
	{ G.Distance[w]=G.Distance[u]+arcs[u][w];
	  G.PreviousVertex[w]=u;
	}
 }                             //中心算法结束
 
  //打印结果
 //for(i=1; i<=Vex; i++)         //依次打印从V点到所有点的最短路径
// {
  //if(i!=V)                     //如果两个点一样，距离即是0，没必要打印
     int ie=End;
	  int VexCopy=Vex;
      int VerPath[Vex+1]={0};
      cout<<"从 "<<V<<" 到 "<<ie<<"  的最短距离为：   "<<G.Distance[ie]<<" ; 路径为  "<<V<<"-->";
   
   int preVer=G.PreviousVertex[ie];  //如下打印最短路径依次经过的点
   
   while(preVer!=0)                     //依次求出经过的点，保存在数组中
   { 
	   VerPath[VexCopy]=preVer;
	   VexCopy--;
	   preVer=G.PreviousVertex[preVer];
	   
   }

   for(int k=VexCopy+1;k<=Vex;k++)     //依次打印经过的点
   {
	  if (V==VerPath[k]) continue;
      cout<<VerPath[k]<<"-->";
   }
   cout<<ie<<endl;
   
   cout<<endl;
  //}
 //}

}

//主函数
void main()
{
	while(true){
 struct Graph G;
 int S,E;
 /*for(int count=1;count<=10;count++)                //依次打印每个点到别的9个点的最短路径
 {  
	 cout<<"第 "<<count<<"个点到别的各个点的最短路径为  "<<endl<<endl;
	 theShortestPath(G,count);
     cout<<endl;
 }*/

  cout<<"             **********谢谢使用!**********";
  cout<<endl;
  cout<<"请输入起始点：";
  cin>>S;
  cout<<"请输入终点：";
  cin>>E;
  theShortestPath(G,S,E);
  getch();
	}
}