a校园导游图.cpp

校园导游图

#include < iostream.h >
#include < limits.h >

#define	ERROR 0
#define OK 1
#define FALSE 0
#define TRUE 1
#define INFINITY INT_MAX
#define MAX_VERTEX_NUM  30


typedef unsigned int VRType;
typedef char VertexType;
typedef char VertexInfo;
typedef int Status ;
typedef int PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct ArcCell
{
   VRType weight;
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct VexNode
{
	VertexType data;
	VertexInfo* maininfo;
	VertexInfo* info;
}VexNode, VexArray[MAX_VERTEX_NUM];

typedef struct
{
  VexArray Vexs;   
  AdjMatrix  arcs;
  int vexnum, arcnum;
}MGraph;

typedef  int ShortPathTable[MAX_VERTEX_NUM];

int LocateVex( MGraph G, VertexType v1 )
{
	for ( int i = 0; i < G.vexnum; i++ )
		if ( G.Vexs[i].data == v1 )
			return i;

	return ERROR;
}

Status CreateGraph( MGraph & G )
{
  G.vexnum = 10;
  G.arcnum = 18;
  char * ch = "abcdefghij";

  for ( int i = 0; i < G.vexnum; i++ )
  {
    G.Vexs[i].data = ch[i];
  }
  G.Vexs[0].maininfo = "科技楼";
  G.Vexs[1].maininfo = "中心广场";
  G.Vexs[2].maininfo = "图书馆";
  G.Vexs[3].maininfo = "教学楼"; 
  G.Vexs[4].maininfo = "实验楼";
  G.Vexs[5].maininfo = "B楼";
  G.Vexs[6].maininfo = "行政楼";
  G.Vexs[7].maininfo = "A楼";
  G.Vexs[8].maininfo = "蝴蝶湖";
  G.Vexs[9].maininfo = "校门口";

  G.Vexs[0].info = " 科技楼，功能:由实验室，机房，课室组成。主要用来上课，供学生做物理实验和进行上机操作。";
  G.Vexs[1].info = " 中心广场，功能：主要用来开大型会议或举行文艺活动，例如十大歌手，国庆晚会等";
  G.Vexs[2].info = " 图书馆，功能：有五层，一楼主要用于展览，二楼用于租借书籍，三楼主要用于藏书,四楼有大量杂志，五楼是图书馆工作人员办公室。每层的教室还能供同学们自修使用。";
  G.Vexs[3].info = " 教学楼，功能：主要由课室，电教室和多媒体教室组成，是学校上课的主要地方。";
  G.Vexs[4].info = " 实验楼，功能：由实验室，养殖室和温室组成，是水院和农院同学做实验的主要地方。";
  G.Vexs[5].info = " B楼，功能：由课室组成，用于上课。";
  G.Vexs[6].info = " 行政楼，功能：是学校领导办公的主要地方。";
  G.Vexs[7].info = " A楼，功能：由教室和语音室组成，主要用于外语学院上课和听力课。";
  G.Vexs[8].info = " 蝴蝶湖，功能：学校的景点之一，是学生们聊天，饭后散步的好地方。";
  G.Vexs[9].info = " 校门口，功能：由此进入校园。";

  for ( i = 0; i < G.vexnum; i++ )
	for ( int j = 0; j < G.vexnum; j++ )
      G.arcs[i][j].weight = INFINITY;

  G.arcs[0][1].weight = 3;
  G.arcs[0][2].weight = 6;
  G.arcs[0][9].weight = 25;
  G.arcs[1][2].weight = 2;
  G.arcs[1][3].weight = 4;
  G.arcs[1][0].weight = 3;
  G.arcs[2][0].weight = 6;
  G.arcs[2][1].weight = 2;
  G.arcs[2][3].weight = 4;
  G.arcs[2][5].weight = 8;
  G.arcs[3][1].weight = 4;
  G.arcs[3][2].weight = 4;
  G.arcs[3][4].weight = 3;
  G.arcs[3][6].weight = 10;
  G.arcs[4][3].weight = 3;
  G.arcs[4][5].weight = 3;
  G.arcs[4][6].weight = 6;
  G.arcs[5][2].weight = 8;
  G.arcs[5][4].weight = 3;
  G.arcs[5][6].weight = 5;
  G.arcs[5][7].weight = 3;
  G.arcs[6][3].weight = 10;
  G.arcs[6][4].weight = 6; 
  G.arcs[6][5].weight = 5; 
  G.arcs[6][7].weight = 4;
  G.arcs[6][8].weight = 4;
  G.arcs[6][9].weight = 8;
  G.arcs[7][5].weight = 3;
  G.arcs[7][6].weight = 4;
  G.arcs[7][8].weight = 3;
  G.arcs[8][6].weight =	4;
  G.arcs[8][7].weight = 3;
  G.arcs[8][9].weight = 3; 
  G.arcs[9][8].weight = 3;
  G.arcs[9][6].weight = 8; 
  G.arcs[9][0].weight = 25;
	  
  return OK;
}

void ShortesPath_DIJ( MGraph G, char v0, PathMatrix &P, ShortPathTable &D )
//用Dijdstra算法求有向网G的V0顶点到其余顶点v的最短路径P[v][w]及其带权长度D[v].
//若P[v][w]为TRUE，则w是从v0到v当前求得最短路径上的顶点
//final[v]为TRUE当且仅当v<s,即已经求得从v0到v的最短路径
{
  int r;
  int min;
  int Final[MAX_VERTEX_NUM];
  int i = LocateVex( G, v0 );

  for ( int j = 0; j < G.vexnum; j++ )// 初始化D[j]、P[j][k]、Final[j]
  {
    Final[j] = FALSE;
	D[j] = G.arcs[i][j].weight;

	for ( int k = 0; k < G.vexnum; k++ )
	  P[j][k] = FALSE;

	  if ( D[j] < INFINITY )
	  {
		P[j][i] =TRUE;
		P[j][j] = TRUE;
	  }
  }
  
  D[i] = 0;
  Final[i] = TRUE;//初始化，v0顶点属于S集

  //开始主循环,每次求得v0到某个v顶点的最短路径,并加v到s集 
  for (  j = 1; j < G.vexnum; j++ )//其余G.vexnum-1个顶点
  {
	min = INFINITY;//目前所知离v0顶点的最近距离
    for ( int  k = 0; k < G.vexnum; k++ )//计算离v0顶点最近的顶点r
	  if ( !Final[k] )//w 顶点 在V-S中
		if( D[k] < min )
		{
		  r = k;
		  min = D[k];
		}

	Final[r] = TRUE;//离v0顶点最近的r加入S中
	 
	for (  k = 0; k < G.vexnum; k++ )//表示v0--r--其它顶点k权值与v0直接到其它顶点k权值比较,其它顶点在V-S集中
	{  
	  if ( !Final[k] && ( (min + G.arcs[r][k].weight) < D[k] ))
	  {
		D[k] = min + G.arcs[r][k].weight;//D[k]表示从i到k的最短权值

		for ( int n = 0; n < G.vexnum; n++ )
		  P[k][n] = P[r][n];

		  P[k][k] = TRUE;
	  }//if
	}//for
  }	//for
}//ShortesPath_DIJ

void ShowPath( MGraph G, char v0, char v1, PathMatrix P, ShortPathTable D )
{
  int min, r, k, e, i,count;
  count = 0;                 //计算经过多少个顶点
  int a[10];                 //存放经过顶点的下标  
  k = LocateVex( G, v0);
  e = LocateVex( G, v1);
	
  for ( int j = 0; j < G.vexnum; j++ )//初始化
    a[j] = INFINITY;

  for ( i = 0, j = 0; i < G.vexnum && j < G.vexnum; i++, j++ )
  //P若P[v][w]为TRUE，则w是从v0到v当前求得最短路径上的顶点
  {
    if ( P[e][i] ) //k到e最短路径经过i,保存i到a[j]     
	{
	  a[j] = i;count++;
	}
  }
  if ( count == 2 )
  {
	cout<<G.Vexs[k].maininfo<<"到"<<G.Vexs[e].maininfo<<"是直接到达的"<<endl;
	cout<<"它的长度是 "<<D[e]<<endl;//D[e]保存了k到e点的最短长度
	return ;
  }
	
  cout<<"从"<<G.Vexs[k].maininfo<<"到"<<G.Vexs[e].maininfo<<"它经过"<<(count - 2)<<"个点，分别是"<<endl;
  
  a[k] = INFINITY;
  a[e] = INFINITY;
   
  for (  j = 0; j < count ; j++ )
  {
	min  = INFINITY;//初始化
	 
	for ( int k = 0; k < G.vexnum; k++ )
	{
	  if ( a[k] != INFINITY && min > D[a[k]] )
	  {
		min = D[a[k]];       //在经过顶点上寻找权值小的为先经过
		r = a[k];            //记住最小点的位置
	  }
	}
	if ( a[r] != INFINITY )cout<<G.Vexs[r].maininfo<<endl;
      a[r] = INFINITY;         //表示
  }
  cout<<"它的长度是 "<<D[e]<<endl;
}
			  
void main()
{

  char v0;
  char v1;
  char ch, ding;
  int n;
  int min = INFINITY;
  MGraph G;
  CreateGraph(G );
  PathMatrix P;
  ShortPathTable D;
    
  cout << " a代表科技楼 " << "b代表中心广场 " << "c代表图书馆 " << endl;
  cout << " d代表教学楼 " << "e代表实验楼 " << "f代表B楼 " << endl;
  cout << " g代表行政楼 " << "h代表A楼 " << "i代表蝴蝶湖 " << "j代表校门口 " << endl;
  cout <<" 如果你想查询某个顶点的信息请按 u 键" << endl;
  cout <<" 如果你想查询两个地点的最短路径请按 p 键"<< endl; 
  cin >> ch;
  do		
  {
	while ( ch == 'u' )
	{
	  cout << "请你输入一 个顶点" << endl;
	  cin >> ding;
      n = LocateVex( G, ding );
	  cout << G.Vexs[n].info << endl << endl;
	  cout << "如果你还想继续查询某个顶点的信息请按 u 键，但如果你想查询两个地点" << endl;
	  cout << "的最短路径请按 p 键，如果想退出请按其它键" << endl;
	  cin >> ch;
	}
	while ( ch == 'p' )
	{
	  cout << " a代表科技楼 " << "b代表中心广场 " << "c代表图书馆 " << endl;
	  cout << " d代表教学楼 " << "e代表实验楼 " << "f代表B楼 " << endl;
	  cout << " g代表行政楼 " << "h代表A楼 " << "i代表蝴蝶湖 " << "j代表校门口 " << endl;
	  cout << "请输入两个顶点字符" << endl;
      cin >> v0 >> v1;
      ShortesPath_DIJ( G, v0, P, D );
	  ShowPath( G, v0, v1, P, D);
      cout << endl;
	  cout << "如果你还想继续查询两个地点的最短路径请按 p 键, 但如果你想查询" << endl;
	  cout << "某个顶点的信息请按 u 键,如果想退出请按其它键" << endl;
	  cin >> ch;
	}
  }while ( ch == 'u' || ch == 'p' );
    
}