qt.h

校园导游程序,可以检索和求最短路径,界面友好 可以改成自己学校的~

/******************************************************
  Copyright (c), 2007, xiaohan, swust.
  FileName: QT.h
  Author: xiaohan   Version:1.0  Date:2007.01.03
  Discrition: 实现校园导游模拟
  History: 无
  <author>     <time>     <version>       <desc>
  xiaohan    2007/01/03      1.0       实现模拟的有关函数
*******************************************************/

struct RowColWeight
{
	int row;                          //景点代码-1
	int col;                          //景点代码-1
	int weight;                       //两个景点的路径长度(权)
}
rcw[22] = {{0, 1, 300}, {1, 0, 300}, {0, 3, 200}, {3, 0, 200},{0, 2, 150}, 
{2, 0, 150}, {2, 4, 200}, {4, 2, 200}, {3, 4, 400}, {4, 3, 400},{2, 5, 600}, 
{5, 2, 600}, {5, 6, 700}, {6, 5, 700}, {6, 7, 50},{7, 6, 50}, {7, 8, 30}, 
{8, 7, 30}, {5, 8, 650}, {8, 5, 650},{8,9,150},{9,8,150}};

void initialization1()                //初始化用户界面
{
	cout << "****************************************" 
		<< "****************************************" << endl;
		cout << "                    (代码)                   景点名称" 
			<< endl << endl;
}

void initialization2()                //初始化用户界面
{
	cout << "请选择一项：" 
		<< "              (Y或y)浏览景点介绍" << endl 
		<< "                          (N或n)查询任意两个景点间的最短路径 " 
		<< endl <<"                          (E或e)退出" << endl;
}

/*************************************************
  函数名称:      Print
  函数功能:      打印景点及代码
  Called:        无
  Called By:     Welcome
  输入参数:      item    
  输出参数:      无
  返回值:        无
  其它说明:      无  
*************************************************/
void Print(Sight item)                   //输出菜单(景点及其代码)
{
	cout << "                     (" << item.Num 
		<< ")                     " 
		<< item.Name << endl;
}

/*************************************************
  函数名称:      Welcome
  函数功能:      打印欢迎用户界面
  Called:        Print
  Called By:     main Function
  输入参数:      g    
  输出参数:      无
  返回值:        无
  其它说明:      无  
*************************************************/
void Welcome(AdjMWGraph &g)                             
{
	cout << "                         您好!欢迎光临西南科技大学" << 
		endl << endl;
	cout << "下面是我校景点及代码: " << endl;
	cout << "****************************************" 
		<< "****************************************" <<endl;
	cout << "                    (代码)                   景点名称" 
		<< endl << endl;
    
	for(int l = 0; l < 10; l++)
	{
		Print(g.GetValue(l));
	}    //for语句结束

	cout << endl;
	cout << "****************************************" 
		<< "****************************************" << endl;
	initialization2();
}

/*************************************************
  函数名称:      GreatGraph
  函数功能:      建立图
  Called:        InsertVertex  InsertEdge
  Called By:     InsertG
  输入参数:      n  e  g  V[]  E[]
  输出参数:      无
  返回值:        无
  其它说明:      无  
*************************************************/
void CreatGraph(AdjMWGraph &G, DataType V[], int n, RowColWeight E[], int e)
{
	for(int i = 0; i < n; i++)        //向图G中插入n个结点
	{
		G.InsertVertex(V[i]);
	}   //for语句结束
	for(int k = 0; k < e; k++)        //向图G中插入e条边
	{
		G.InsertEdge(E[k].row, E[k].col, E[k].weight);
	}   //for语句结束
}

/*************************************************
  函数名称:      InsertG
  函数功能:      插入校园图
  Called:        CreatGrap
  Called By:     main Function
  输入参数:      g
  输出参数:      无
  返回值:        无
  其它说明:      无  
*************************************************/
void InsertG(AdjMWGraph &g)            
{
	int n = 10, e = 22;               //景点数10，有向边条数22
	CreatGraph(g, W, n, rcw, e);
}

/*************************************************
  函数名称:      SinghtMessage
  函数功能:      打印景点信息
  Called:        无
  Called By:     Run
  输入参数:      无
  输出参数:      无
  返回值:        无
  其它说明:      无  
*************************************************/
void SightMessage()                   //景点信息
{
	int t;
	cin >> t;
	cout << "**********************************" 
		<< "**********************************************" << endl;
	switch(t - 1)
	{
	case 0:cout << "柳池:" << endl << endl << "小荷才露尖尖角，早有蜻" 
			   << "蜓立上头。这是一个谈情说爱的好地方!" << endl; break;
	case 1:cout << "北山体育场:" << endl << endl << "有篮球场和网球场。" 
			   << "是一个学生进行体育锻炼的好地方!" << endl; break;
	case 2:cout << "龙山体育场:" << endl << endl << "一个足球场。" 
			   << "历史悠久，有居高临下之感。" << endl; break;
	case 3:cout << "老区图书馆:" << endl << endl << "这是工学图书馆，" 
			   << "热爱学习的学生都能在这里找到真理。" << endl; break;
	case 4:cout << "西科花园:" << endl << endl << "学校内部的一个花园，" 
			   << "绿树成荫，夏天旁晚有很多游客在这里散步。" << endl; break;
	case 5:cout << "科技中心:" << endl << endl << "2006年建成，" 
			   << "理学院当家做主，是学校的象征。" << endl; break;
	case 6:cout << "行政楼:" << endl << endl << "学校行政中心，" 
			   << "许多会议等都在这里举行。" << endl; break;
	case 7:cout << "九洲湖:" << endl << endl << "不光是有许多学生在" 
			   << "这里背书，连鱼儿也会露出湖面凑热闹。" << endl;break;
	case 8:cout << "逸夫图书信息中心:" << endl << endl << "这是综合" 
			   << "图书馆，在这里，读万卷书，行万里路 "<< endl;break;
	case 9:cout << "新区运动场:" << endl << endl << "这是一个综合运动场，" 
			   << "是举行大型运动会的场所，2006年全国大学生足球联赛南区决赛" 
			   << "在此举行" << endl;break;
	default:cout << "你输入的景点不存在!" << endl;
	}    //switch语句结束
	cout << "**********************************" 
		<< "**********************************************" << endl;
}

/*************************************************
  函数名称:      Dijkstra
  函数功能:      计算一个顶点到其它顶点的最短路径
                 长度即目标景点的前一景点下标
  Called:        NumOfVertices  GetWeight  
  Called By:     Run
  输入参数:      G  v0    
  输出参数:      distance[]  path[]
  返回值:        distance[]  path[]
  其它说明:      无  
*************************************************/
void Dijkstra(AdjMWGraph &G, int v0, int distance[], int path[])  
{
	int n = G.NumOfVertices();
	int *s = new int[n];
	int minDis, i, j, u;

	//初始化
	for(i = 0; i < n; i++)
	{
		distance[i] = G.GetWeight(v0, i);            //取v0到其它景点的距离存在数组中
		s[i] = 0;
		if(i != v0 && distance[i] < MaxWeight) path[i] = v0;
		else path[i] = -1;
	}       //for语句结束
	s[v0] = 1;                            //标记结点v0已从集合T加入到集合S中

	//在当前还未找到最短路径的结点集中选取具有最短距离的结点u
	for(i = 1; i < n; i++)
	{
		minDis = MaxWeight;
		for(j = 0; j <= n; j++)
		{
			if(s[j] == 0 && distance[j] < minDis)
			{
				u = j;
				minDis = distance[j];
			}   //if语句结束
		}      //for语句结束
		
		//当已不再存在路径时算法结束；此语句对非连通图是必要的
		if(minDis == MaxWeight)return;

		s[u] = 1;                         //标记结点u已从集合T加入到集合S中
		//修改从v0到其它结点的最短距离和最短路径
		for(j = 0; j < n; j++)
		{
			if(s[j] == 0 && G.GetWeight(u, j) < MaxWeight && 
				distance[u] + G.GetWeight(u, j) < distance[j])
			{
				//结点v0经结点u到其他结点的最短距离和最短路径
				distance[j] = distance[u] + G.GetWeight(u, j);
				path[j] = u;
				
			}   //if语句结束
		}     //for语句结束
	}     //for语句结束
}

/*************************************************
  函数名称:      Run
  函数功能:      实现景点信息及最短路径的输出
  Called:        GetValue  Print  initialization1()
                 SightMessage()  NumOfVertices()
                 Dijkstra  Insert  ListSize  GetData
                 initialization2()
  Called By:     main Funtion
  输入参数:      cmd  g    
  输出参数:      无
  返回值:        无
  其它说明:      无  
*************************************************/
void run(char cmd,AdjMWGraph &g)                           //运行函数
{
	cout << endl;
	
	if(cmd != 'Y' && cmd != 'y' && cmd != 'N' && 
		cmd != 'n' && cmd != 'E' && cmd != 'e')
		cout << "输入错误!请重新输入:";
	
	initialization1();
	for(int l = 0; l < 10; l++)Print(g.GetValue(l));
	cout << endl;
		
	switch(cmd)
	{
	case 'Y':                                             //浏览景点简介
	case 'y':
		cout << "请选择景点代码: ";
		
		SightMessage();
		
		initialization2();
		break;
	case 'N':                                              //求路径长度
	case 'n':
		int m = g.NumOfVertices();
		int *distance = new int[m];
		int *path = new int[m];
		int v1, v2;
		
		cout << "请输入要查询的两个景点的代号(用空格键隔开):";
		cin >> v1 >> v2;
		
		while(v1 < 1 || v1 > 10 || v2 < 1 || v2 > 10)      //输入景点不存在时继续输入
		{
			cout << "输入错误!请重新输入：";
			cin >> v1 >> v2;
		}                //while语句结束
	 
		v1 = v1 - 1;
		Dijkstra(g, v1, distance, path);                   
		
		cout << "****************************************" 
			<< "****************************************" << endl;
		
		//以下为求最短路径长度
		cout << "从景点“" << g.GetValue(v1).Name << "”到景点“" 
			<< g.GetValue(v2 - 1).Name << "”的最短路径长度是:"
			<< distance[v2 - 1] << "米" << endl;
		cout << endl << "最短路线是:" << endl;
		 
		int i = v2 - 1;                                    //以下为求最短路线
		SeqList list;
		while(i != v1)
		{
			if(path[i] != -1)
			{
				list.Insert(g.GetValue(path[i]),list.ListSize());
				i = path[i];
			}    //if语句结束
		}       //while语句结束
			
		for(int c = list.ListSize() - 1;c >= 0;c--)
		{
			cout << list.GetData(c).Name << "——>";
		}    //for语句结束
			
		cout << g.GetValue(v2 - 1).Name << endl;
		cout << endl;
		cout << "****************************************"
			<< "****************************************" << endl;
		
		delete []distance;                                  //清空
		delete []path;
		
		initialization2();
		break;
	}     //switch语句结束
}