本文共 6331 字，大约阅读时间需要 21 分钟。

4、校园导游咨询（图的应用）

[问题描述]

设计一个校园导游程序，为来访的客人提供各种信息查询服务。

（1）设计学校的校园平面图，所含景点不少于10个，以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息；

（2）提供基本信息的修改功能；

（3）为来访客人提供图中任意景点相关信息的查询；

（4）为来访客人提供景点的问路查询，即已知一个景点，查询到某景点之间的一条最短路径及长度。

一、算法设计

    本次程序设计中对于图的存储采用的是邻接矩阵，其实就是二维数组。查询路径采用的则是弗洛伊德算法，其中对于所求的路径地点名采用的是三元组的形式，第一个数表示始点，第二个表示终点，第三个表示中间经过的点的下标。查询和修改功能都是按照景点的编号来进行查询的，修改可以更改对景点的简介。

    各个函数的调用关系如下图所示：

2.本程序中包含6个模块

(1)主函数：int main()；

(2)主界面函数：mainjiemian()；

(3)显示地图信息：map()；

(4)求取最短路径的算法：ShortestPath()；

(5)修改景点信息：xiugai()；

(6)退出函数：exit()；

3.元素类型、结点类型和指针类型

    #define MX65535            //最大值 无穷

    #defineNUM  10             //最大顶点个数

    typedef intadjmatrix[NUM][NUM];

    typedef intpath[NUM][NUM][NUM];

    typedefstruct

    {   int vex;              /*顶点号*/

         string name;          /*景点名字*/

         string jieshao;       /*景点简介*/

     }Vertex;

二、实验测试

源代码：

#pragma warning(disable:4996)#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  using namespace std;#define MX 65535 //最大值 无穷#define NUM 10 //最大顶点个数typedef int adjmatrix[NUM][NUM];typedef int path[NUM][NUM][NUM];typedef struct{ int vex; /*顶点号*/ string name; /*景点名字*/ string jieshao; /*景点简介*/}Vertex;Vertex node[10] ={ { 1, "国际教育学院教学楼", "此栋教学楼为中工国际教育学院专属教学楼，与国外合作办学。同时内设考研自习室，提供了良好的学习氛围。" }, { 2, "北苑篮球场", "它是北苑学生休闲活动的场所之一，除篮球场外还设有排球与网球场地，但因其地势低洼，故又被称做“北大坑”。" }, { 3, "北苑餐厅", "北苑餐厅共设有三层，提供了来自全国各地的美食，价格设置合理，饭菜管饱，满足了广大师生的需求。" }, { 4, "大学生活动中心", "活动中心共有五层，内设有乒乓球，篮球，羽毛球等场地，方便休闲，同时也是重大典礼举办的场所，能够容纳数万人，雄伟壮观。" }, { 5, "中心操场", "中心操场设有塑胶跑道与露天网球场，常有同学来此晨练，此外校庆汇演等重大活动也在此开展，有着“中心操场”的美誉。" }, { 6, "图书馆", "图书馆收纳了各个专业的相关书籍，是名副其实的“书的海洋”，提供了丰富的学习资源，也是中工最宏伟的建筑，没有之一。" }, { 7, "紫薇广场", "紫薇广场是社团活动与招聘会的举办点，每当节日，紫薇广场上必定热闹非凡，是各大社团的活动场所。" }, { 8, "教学楼群", "它聚集了8，9，10，11号教学楼，是各大学院的办公场所所在地，同时也是各个实验室的汇聚之地，学术氛围浓厚。" }, { 9, "南苑操场", "南苑操场供生活在南苑的学子们活动的场所，同时设有锻炼器材与篮球场，极大地方便了同学们的生活。" }, { 10, "工业实训基地", "基地位于中工的最南面，提供各大机床以便学生实训，是学生们实践实训的绝佳场所。" }};/*采用邻接矩阵存储地图*/int arcs[NUM][NUM] ={ { 0, 10, 10, 40, 40, MX, MX, MX, MX, MX }, { 10, 0, 15, 30, MX, MX, MX, MX, MX, MX }, { 10, 15, 0, MX, 30, MX, MX, MX, MX, MX }, { 40, 30, MX, 0, 2, MX, MX, MX, MX, MX }, { 40, MX, 30, 2, 0, 20, MX, MX, MX, MX }, { MX, MX, MX, MX, 20, 0, 25, 30, MX, MX }, { MX, MX, MX, MX, MX, 25, 0, 20, MX, MX }, { MX, MX, MX, MX, MX, 30, 20, 0, 15, 30 }, { MX, MX, MX, MX, MX, MX, MX, 15, 0, 20 }, { MX, MX, MX, MX, MX, MX, MX, 30, 20, 0 }};void Floeyd(adjmatrix G, adjmatrix D, path P)/*弗洛伊德算法*/{ //利用弗洛伊德算法求图GA中每对顶点间的最短长度，对应存于二维数组A中 for (int v = 0; v
                  
                    end*/{ adjmatrix D; //D[i,j]表示从i到j的最短距离； path P; //P[i,j]表示从i到j的最短路径上j的父节点 Floeyd(GA, D, P); cout << D[a][b] * 10 << endl; cout << "路径为："; if (judge == 1) { for (int u = a; u
                   
                    "; a = u; } } cout << node[b].name << endl; } else if (judge == 0) { int i = 0; int t[NUM] = { 0 }; for (int u = a; u
                    1; i--) { cout << node[t[i] - 1].name << "->"; } cout << node[t[1] - 1].name << endl; }}void ShortestPath()/*求取最短路径*/{ int start = 5; int end = 5; cout << "输入出发点和目的地编号 (1~10 空格分隔)" << endl; cin >> start >> end; if (start>0 && start<18 && end>0 && end<18) { cout << "从" << node[start - 1].name; cout << "到" << node[end - 1].name; cout << "的最短路径长度 ："; if (start <= end) guide(arcs, start - 1, end - 1, 1); else guide(arcs, end - 1, start - 1, 0); } else cout << "没有这个地方！" << endl;}/*--------------------------------------------------------------*/void find()/*查询功能*/{ int a; cout << "请输入想要查询的顶点编号" << endl; cin >> a; if (a >= 1 && a <= 10) { cout << "查询结果如下:\n" << endl; cout << "[" << node[a - 1].vex << "]" << ":"; cout << node[a - 1].name << endl; cout << "信息简介：" << node[a - 1].jieshao << endl; } else { cout << "当前并无该景点" << endl; }}void xiugai()/*修改功能，修改景点基本介绍*/{ int a; cout << "请输入想要修改的顶点编号" << endl; cin >> a; if (a <= 10 && a >= 1) { cout << endl; cout << "[" << node[a - 1].vex << "]" << ":"; cout << node[a - 1].name << endl; cout << "信息简介：" << node[a - 1].jieshao << endl; cout << endl; cout << "景点简介:" << endl; string b; cin >> b; node[a - 1].jieshao = b; cout << "修改成功!" << endl; } else { cout << "当前并无该景点" << endl; }}/*----------------------------------------------------------------------------*/void mainjiemian(){ cout << " ★-----★---------★---------★-----★" << endl; cout << " 中工导游系统 " << endl; cout << " ☆ ☆" << endl; cout << " 1 中工一览 " << endl; cout << " ☆ 2 查询路径 ☆" << endl; cout << " 3 查询景点 " << endl; cout << " ☆ 4 修改信息 ☆" << endl; cout << " 5 退出系统 " << endl; cout << " ☆ ☆" << endl; cout << " 中工师生欢迎您 " << endl; cout << " ★-----★---------★---------★-----★" << endl; cout << endl; cout << endl; cout << "请选择数字命令：";}void exit(){ cout << " ★-----★---------★---------★-----★" << endl; cout << endl; cout << " ☆ 感谢您的使用！ ☆" << endl; cout << endl; cout << " ★-----★---------★---------★-----★" << endl; cout << endl;}void map(){ cout << endl; cout << " ★---------★---------★---------★---------★---------★---------★" << endl; cout << " 【1】国际教育学院教学楼" << endl; cout << " ☆ | ☆" << endl; cout << " 【2】北苑篮球场<-----------|-------------------->【3】北苑餐厅 " << endl; cout << " ☆ | ☆" << endl; cout << " | " << endl; cout << " ☆【4】大学生活动中心<-----【5】中心操场 ☆" << endl; cout << " | " << endl; cout << " ☆ | ☆" << endl; cout << " 【6】图书馆 " << endl; cout << " ☆ | ☆" << endl; cout << " |-------------------->【7】紫薇广场 " << endl; cout << " ☆ 南 | ☆" << endl; cout << " | 【8】教学楼群 " << endl; cout << " ☆ 西<---|--->东 | ☆" << endl; cout << " | |-------------------->【9】南苑操场 " << endl; cout << " ☆ 西 | ☆" << endl; cout << " 【10】工业实训基地 " << endl; cout << " ★---------★---------★---------★---------★---------★---------★" << endl;}int main(){ system("color 57"); char*end;/*末端指针*/ string order; mainjiemian(); while (cin >> order) { int a_order = static_cast
                     
                      (strtol(order.c_str(), &end, 10));/*将输入进来的值转化为int类型*/ switch (a_order + 48) { case'1': { system("cls"); map(); system("pause"); system("cls"); mainjiemian(); break; } case'2': { system("cls"); ShortestPath(); map(); system("pause"); system("cls"); mainjiemian(); break; } case'3': { system("cls"); find(); system("pause"); system("cls"); mainjiemian(); break; } case'4': { system("cls"); xiugai(); system("pause"); system("cls"); mainjiemian(); break; } case'5': { system("cls"); exit(); return 0; } default: { cin.clear(); cin.sync(); cout << "输入错误，重新返回主界面。" << endl; system("pause"); system("cls"); mainjiemian(); break; } } }}