课程设计报告
1.问题内容与目的要求
1.1算法产生的背景：
Floyd 算法又称为加点法、插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。该算法名称以创始人之一、1978 年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特 · 弗洛伊德命名。它与 Dijkstra 算法类似，但Dijkstra 算法是基于贪心算法的思想。
1.2题目内容：
基本要求：
针对某大学某校区，设计一个校园导游图系统，为来访的客人提供信息查询服务。要求：
1.在老师提供的“校园景点.txt”文件中，存储了三水校区的景点信息，信息分为两部分 ，二者用一个空行隔开。其中第一部分的每一行，以“编号>名称>简介”道德格式描述了一个景点的信息，“>”起到将不同信息分隔开的作用；第二部分的每一行，以“编号>编号>距离”的格式描述两个景点之间路径的长度，例如0>1>200表示编号为0的景点与编号为1的景点之间的路径长度为200米，“>”还是起到分隔作用。
2.依据“校园景点.txt”提供的信息，将校园景点及景点之间的路径抽象为一个带权无向图，以图中顶点表示景点编号，以边的权值表示两个景点之间路径之长度，在实验报告上绘制这个带权无向图
3.编写程序实现以下功能：
（1）程序读取“校园景点.txt”，依所读取的数据创建上述带权无向图的存储结构，要求存储结构表示了各景点的信息（编号、名称、简介），还表示了景点之间的路径长度。
（2）程序在屏幕上按下述格式，显示所有景点的编号、名称、简介等。
（3）通过景点编号，可检索并显示该景点的全部信息
（4）通过景点名称，可检索并显示该景点的全部信息
（5）为来访客人提供查询任意两个景点之间的一条最短路径，其结果按“1>4>5>8=160”格式显示，表示从1号到8号景点的最短路径依次经过了编号为1、4、5、8的景点，路径长度为160米。
更高要求：
（6）提供校园平面图的编辑功能：增、删景点；增、删道路，修改已有信息等
（7）提供校园导游图的仿真界面—即将上面的第2点，路径的发布与走向尽量画得接近真实情况，并显示到屏幕上。
1.3要实现的目的：
基本：针对某大学某校区，设计一个校园导游图系统，为来访的客人提供信息查询服务。更高：在基本的校园导游系统上，（1）除了给管理员提供查询的服务，再增加上增删改的服务；（2）大致提供校园导游图的仿真界面。
2.总体思路与工程结构
2.1系统功能模块
根据功能分析，系统功能模块图如图1所示：
图1：系统功能模块图
2.2项目结构
2.2.1工程总体结构
建立名为“*********”的工程，整个实验将在其中进行。该小工程包括头文件headPro.h,文件body1.cpp,文件main.cpp。如图2所示：
图2：工程结构
2.2.2 函数之间的调用关系
补充：由于小工程的函数多，画出会很丑陋，这里使用图3的方式的呈现，圆圈的数字与2.2.3函数及功能里的函数的编号，即函数（编号）一一对应。
图3：函数之间的调用关系图
2.2.3 函数及功能
函数（1）：int inputString(char *filename,string str[])
功能：将filename所指文件按行输出到数组str[]中，返回表达式的实际个数。
函数（2）：int f1(string str)
功能：返回str中的数字字符串所对应的整数。
函数（3）：void f2(string str, string &str1, string &str2, string &str3)
功能：将字符串str按'<‘分为三个子字符串 str1, str2, str3。
函数（4）：void createGraph(MGraph &G)
功能：创建无向图G，并将名为“校园景点.txt”的文件数据存储到图的景点、景点之间的关系——道路长所对应的邻接矩阵。
函数（5）：void printDataOfGraph(MGraph G)
功能：打印图G的全部景点的信息。
函数（6）：void searchByNum(MGraph G)
功能：根据用户输入的图G景点的编号，显示图G中该景点的所有信息。
函数（7）：void searchByName(MGraph G)
功能：根据用户输入的图G景点的名称，显示图G中该景点的所有信息。
函数（8）：
/*
* MGraph G: 是无向图
* int **dist: 是指向 dist[][] (存储图的最短路径的邻接矩阵)的指针
* int **path: 是指向 path[][] (记录图的最短路径的景点次序的矩阵)的指针
*/
void floyd(MGraph G, int **dist, int **path)
功能: 使用floyd算法求图G的最短路径的所需的dist[][]，path[][]
函数（9）：
/*
* u 是最短路径的开端景点的编号
* v 是最短路径的末端景点的编号
* int **path: 是指向 path[][] (记录图的最短路径的景点次序的矩阵)的指针
*/
void printPath(int u, int v, int **path)
功能：由于输入需要如1<2<3=160的格式显示，因而使用递归辅助打印最短路径< span=””>
函数（10）：void displayShortestPath(MGraph G)
功能：按格式显示图G任意两个景点u到v(这里的u, v是景点的编号)的最短路径的长度值。
函数（11）：void addNode(MGraph &G)
功能：根据用户所输入的景点的名称、简介，来给图G增加新景点。
函数（12）：void addArc(MGraph &G)
功能：根据用户所输入的两个景点的编号，来给图G增加直达道路。
函数（13）：void updateInformation(MGraph &G)
功能：根据用户所输入的景点的编号和新简介，来修改图G中对应的景点的简介。
函数（14）：void updateName(MGraph &G)
功能：根据用户所输入的景点的编号和新名称，来修改图G中对应的景点的名称。
函数（15）：void updateArc(MGraph &G)
功能：根据用户所输入的两个景点的编号和新的路径长度值，来修改两个景点编号在图G中对应的直达道路的长度值。
函数（16）：void deleteArc(MGraph &G)
功能：根据用户所输入的两个景点的编号，来删除两个景点编号在图G中对应的道路。
函数（17）：void deleteNode(MGraph &G)
功能：根据用户所输入的景点的编号，来删除景点编号在图G中所对应的景点以及跟景点直接相连的道路。
函数（18）：void showMap()
功能：将名为“校园景点.txt”的文件数据存储到图的景点、景点之间的关系——道路长所对应的邻接矩阵之后，大致显示在无向图最初(没有进行增删改的操作)的形状。
函数（19）：void menu1()
功能：显示导游系统的功能菜单。
函数（20）：int main()
功能：主函数(测试函数)，呈现出导游系统的查询界面。
3.主要数据结构、关键问题和算法
3.1数据结构
表1：校园景点表
| 景点编号 | 景点名称 | 景点简介 |
| 0 | 励学楼 | 也称“一教”，是一栋很有文化气息的教学楼，环境幽雅。 |
| 1 | 笃行楼 | 也称“二教”，是一栋很有现代化气息的教学楼，设计巧妙。 |
| 2 | 厚德楼 | 也称“行政楼”，是广东财经大学的行政办事中心。 |
| 3 | 拓新楼 | 也称“实验楼”，是计算机机房，有各类实验设备。 |
| 4 | 图书馆 | 高端大气，藏书丰富，建筑宏伟，环境幽雅。 |
| 5 | 创业园区 | 广财学子开展创新产业实践活动，激发创业意识，培养企业家精神的活动场所。 |
| 6 | 李园 | 宿舍园区，学生职工混住，较为混乱。 |
| 7 | 桃园 | 宿舍园区，环境优美，比较安静。 |
| 8 | 竹园 | 宿舍园区，有许多健身器材，方便广财学子户外娱乐。 |
| 9 | 三饭 | 菜色丰富，环境整洁。 |
| 10 | 学而优 | 方便购买生活必须品，学习用品。 |
| 11 | 灯光球场 | 篮球健儿的摇篮。 |
| 12 | 沁湖 | 美丽校园的缩影，情侣游园的好地方。 |
| 13 | 中心花园 | 场地空旷，马路宽广，正对广东财经大学西门。 |
将校园平面图抽象为图4所示的带权无向图
图4：由校园平面图抽象所得的带权无向图
其中：顶点编号与“表1：校园景点表”中景点编号一一对应，代表相应景点；边上的权值代表两个景点之间的路径长度（单位：米）
数据结构的设计——邻接矩阵：
需要存储的信息有两个方面。一是校园景点表各景点的描述信息；二是各景点之间的联系，即各景点之间的路径信息。为此，一是用一维数组存储校园景点表的信息；二是二维数组表示各景点之间的联系。通过两个数组之间下标的对应关系，使得两方面的信息发生关联。
#include<string> //引用字符串对象
#define MAXVER 50 //邻接矩阵（方阵）的最大行（列）数#define INFINITY 32767 //INFINITY表示极大值、无穷大//这个小工程里的顶点、节点、景点、结点为图的结点,表示为 Vertype,ver,node//这个小工程里的弧、边、道路为图的边（权值边）,表示为 arc//校园景点的定义typedef struct{ int num; //校园景点编号（权值） string name; //校园景点名 string information; //校园景点的描述信息}Vertype;
//图的边的邻接矩阵表示typedef struct{ int arcs[MAXVER][MAXVER]; //邻接矩阵表示弧或边（两点距离长权值） Vertype ver[MAXVER]; //景/顶点表 int vernum; //图的当前景点数 int arcnum; //图的当前边数}MGraph;
思考：接下来执行 MGraph G; 命令，系统会如何给G分配空间，试着画出其示意图，试着把以下两方面信息存储进去：需要存储的信息有两个方面，一是校园景点表各景点的描述信息；二是各景点之间的联系，即各景点之间的路径信息。
3.2关键问题
3.2.1求导游图的任意两个景点的最短路径
那什么是求导游图的任意两个景点的最短路径呢？
答：简言之，就是在导游图已有的景点（顶点）、道路（边），找连接两个景点的最短道路，得到最短道路的长度值（边的权值）、最短道路的经过的景点次序，即从开端景点到中间景点（可能没有，即直达），再到终端景点的次序。
那怎么求导游图的任意两个景点的最短路径呢？
答：
1、通常使用Floyd算法求导游图的任意两个景点的最短路径；大体的关键步骤如下：
1）从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。
2）对于每一对顶点 u 和 v，看看是否存在一个顶点 w （一般称为中间点）使得从 u 到 w 再到 v 比已知的路径更短。如果是，更新它（专业术语为：松弛）。
3）遍历直到结束，这时候存储图的数据结构就得到了多源最短路径。
2、中间涉及两个比较关键数组：
1）二维数组dist[][]是用于存储图的景点之间的最短路径的邻接矩阵，比如dist[i][j] = 150;表示从编号为i的景点到编号为j的景点的最短路径的长度值为150米;比如dist[i][j] = INFINITY (32767)表示从编号为i的景点到编号为j的景点之间没有连通路径，也就是无法直接到达和间接到达。
2）二维数组path[][] 是记录图的最短路径的中间景点次序的矩阵，比如path[m][n] = -1;表示从编号为m的景点到编号为n 的景点是直达的，即没有中间景点；比如path[m][n] = 6; 表示从编号为m的景点到编号为n 的景点是间接到达的，即含有编号为6中间景点（可能还有其它中间景点）；
3.3主要算法说明
3.3.1 Floyd算法
Floyd 算法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。该算法不是那么难且有效，关键的部分是对三道循环的理解。代码大致如下：
//三道循环实现for(v = 0; v < n; ++v) //测试欲加入的节点{ for(i = 0; i < n; ++i) //路径的开端 { for(j = 0; j < n; ++j) //路径的终端 { //判断原来的路径长度值是否大于加入新节点的路径长度值 if(dist[i][j] > dist[i][v] + dist[v][j]) { //松弛边，更新最短路径的长度值 dist[i][j] = dist[i][v] + dist[v][j]; //记录或更新最短路径 path[i][j] = v; } } }}
优点：难度系数不高，可以算出任意两个节点之间的最短距离，代码编写不难。
缺点：时间复杂度比较高，不适合计算大量数据。时间复杂度 O（n^3）,空间复杂度 O（n^2）。
3.3.2 递归算法
那什么是递归算法呢？
答：递归算法是一种直接或者间接调用自身函数或者方法的算法。（俗话就说成“自己调用自己”）递归算法的实质是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法来表示问题的解。递归算法对解决一大类问题很有效，它可以使算法简洁和易于理解。
本小工程主要使用递归算法辅助输出显示两个景点的最短路径，使用于printPath ()函数里面。
4.测试
1、双击.exe 文件 ，显示的界面如图5所示：
图5：测试图1
2、输入y, 进入服务，再输入服务编号2，显示全部景点的信息，如图6所示：
图6：测试图2
3、输入服务编号3或4或5，进入景点信息查询或最短路径查询，如图7所示：
图7：测试图3
4、输入服务编号6，进行增加景点，如图8所示：
图8：测试图4
5、输入服务编号7，进行增加道路，如图9所示：
图9：测试图4
6、输入服务编号9，进行删除道路，再输入服务编号5，进行查询路径做检验，如图10所示：
图10：测试图5
7、输入服务编号8，进行删除景点 ，再输入服务编号2，进行查询检测，如图11所示：
图11：测试图6
8、输入服务编号8，进行删除景点 ，再利用服务编号5进行查询检测，如图12所示：
图12：测试图7
9、输入服务编号10、11，进行修改景点，利用服务编号2进行查询检测，如图13所示：
图13：测试图8
10、还有一些检测措施，如图14所示：
图14：测试图9
5.总结
5.1任务完成情况
5.1.1已经完成的任务
（1）程序读取“校园景点.txt”，依所读取的数据创建带权无向图的存储结构，要求存储结构表示了各景点的信息（编号、名称、简介），还表示了景点之间的路径长度。
（2）程序在屏幕上按下述格式，显示所有景点的编号、名称、简介等。
（3）通过景点编号，可检索并显示该景点的全部信息。
（4）通过景点名称，可检索并显示该景点的全部信息。
（5）为来访客人提供查询任意两个景点之间的一条最短路径，其结果按“1>4>5>8=160”格式显示，表示从1号到8号景点的最短路径依次经过了编号为1、4、5、8的景点，路径长度为160米。
（6）提供校园平面图的编辑功能：增、删景点；增、删道路，修改已有信息等。
（7）提供校园导游图的仿真界面—即将上面的第2点，路径的发布与走向尽量画得接近真实情况，并大致显示到屏幕上，但不牙雅观。
5.1.2尚未完成的任务
无
5.2不足与改进信息
不足之处主要表现在：
1）程序的交互性差，可改进为提供菜单选项，使得每个选项代表用不同的算法来进行搜索；
2）程序运行效率不高，可适当修改算法，进行优化；
3）图的景点之间关系，即图的邻接矩阵空间是有限的、静态定义（可能导致无法增加新的景点），且没有扩容的操作，建议可以使用动态定义或增加扩容操作
4）程序中只知道函数调用涉及栈、new操作涉及堆，了解还是不足，建议可更多地了解底层；
5）程序中对指针和引用的使用不熟，建议更多地了解相关、解析更多更易吸收的书籍或文档。
5.3 自评与诚信声明
自评：** 分
该数据结构课程设计的参考文献资料如后面所列。保证除了参考这些文献资料和与同学讨论之外，没有抄袭某同学的、某文献的，否则甘愿接受记0分的处罚。
附录一 实验环境
Windows 10 + CodeBlocks
附录二 用户手册
1) 在Windows环境下，“校园景点.txt”文件跟.exe文件要放在同一目录，就可以直接打开.exe文件或者利用CodeBlocks编译器打开，这里有打开.exe文件的图片，如图15所示：
图15：使用介绍图1
2）然后双击.exe文件就行，然后会看到导游系统的服务菜单，如图16所示：
图16：使用介绍图2
3) 然后键盘输入英文字母y(yes)进入服务，服务时多看菜单，多参考我那实验测试过程，多使用服务编号2进行全局看景点。当你不要服务时，就输入服务编号0，再按回车键，再按任意键退出校园导游系统。
附录三 源代码
头文件headPro.h如下：
#include<string> //使用字符串类using namespace std; //使用位于名称空间 std 的string类
#define MAXVER 50 //邻接矩阵（方阵）的最大行（列）数#define INFINITY 32767 //INFINITY表示极大值、无穷大//这个小工程里的顶点、节点、景点、结点为图的结点,表示为 Vertype,ver,node//这个小工程里的弧、边、道路为图的边（权值边）,表示为 arc//校园景点的定义typedef struct{ int num; //校园景点编号（权值） string name; //校园景点名 string information; //校园景点的描述信息}Vertype;
//图的边的邻接矩阵表示typedef struct{ int arcs[MAXVER][MAXVER]; //邻接矩阵表示弧或边（两点距离长权值） Vertype ver[MAXVER]; //景/顶点表 int vernum; //图的当前景点数 int arcnum; //图的当前边数}MGraph;
文件body1.cpp如下：
#include”headPro.h”/*#include”header.h”:表明当前文件和”header.h”处于同一工程同一目录*//*#include<header.h>:表明header.h和当前文件不属于同一工程，是外部引用*/
#include<stdlib.h> //使用exit()#include<fstream> //使用输入文件流ifstream#include<iostream> //使用cin(),cout()#include<iomanip> //使用setw()
//1、将filename所指文件按行输出到数组str[]中，返回表达式的实际个数int inputString(char *filename,string str[]){ //功能：定义输入文件流对象infile，打开磁盘filename所指文件，并使filename所指文件与流对象infile关联。 ifstream infile(filename,ios::in); //如果infile关联的文件打开失败，infile返回0 if(!infile) { cout<<“文件打开出错！”< //输出错误信息 exit(1); //异常强行退出exe,读不到会闪现 } int i=0; while(!infile.eof()) //infile关联的文件尚未到文件尾 {
getline(infile,str[i]); //从输入流对象infile所关联的文件读取一行存入str[i] i++; } infile.close(); //关闭infile所关联的磁盘文件 return i – 1; //返回表达式的实际个数}
//2、返回str中的数字字符串所对应的整数int f1(string str){ int result = 0; //for循环遍历字符串 for(unsigned int i = 0; i < str.length(); i++) { if(str[i] >= ‘0’ && str[i] <= ‘9’) { //根据ASCII,00110000~00111001表示’0’~’9’及十进制的规则 result = result * 10 + str[i] – 48; } } //返回字符串所对应的整数 return result;}
//3、将字符串按'<‘分为三个子字符串< span=””>void f2(string str, string &str1, string &str2, string &str3){ //使用string类的find函数分隔字符串 int m = str.find(‘>’); int n = str.find(‘>’, m + 1); //for循环 for(int i = 0; i < str.length(); i++) { if(i < m){str1 += str[i];} //读编号 else if(i > m && i < n){str2 += str[i];} //读景点名称或编号 else if(i > n){str3 += str[i];} //读景点简介或两个景点之间的距离 }}
//4、创建无向图void createGraph(MGraph &G){ //静态定义文件字符串数组 string fileString[50]; //静态定义三个子字符串数组 string subString1[50]; string subString2[50]; string subString3[50];
//将文件读入文件字符串数组,并返回文件里的表达式的个数 //在文件字符串数组的两部分信息的空字符串之后 的第 lines 个元素的下标等于这里的表达式的个数 lines int lines = inputString(“校园景点.txt”,fileString);
//使用for循环将文件字符串数组读入三个子字符串数组 for(int i = 0; i <= lines; i++) { //if条件用于判断文件的两部分信息的空行 if(fileString[i] == “ ”) { //记录文件的两部分信息的空行的下标（即当前图的节点数） G.vernum = i; //记录边的数目 G.arcnum = lines – i; } //调用f2()函数，对读出的字符串数组的元素进行分隔三个字符串 f2(fileString[i], subString1[i], subString2[i], subString3[i]); }
//图的节点的初始化赋值 for(int i = 0; i < G.vernum; i++) { //f1()函数，将字符串转为整数,存为景点的编号 G.ver[i].num = f1(subString1[i]); //将字符串存为景点的名称 G.ver[i].name = subString2[i]; //将字符串存为景点的简介 G.ver[i].information = subString3[i]; }
//初始化邻接矩阵 //这里不使用G.vernum, 而是使用MAXVER的原因:增加景点时,方便dist[][]的初始化赋值 for(int m = 0; m < MAXVER; m++) { for(int n = 0; n < MAXVER; n++) { //将邻接矩阵赋为无穷大 G.arcs[m][n] = INFINITY; } }
//将景点的距离存入邻接矩阵 for(int r = G.vernum + 1; r <= lines; r++) { //由于是无向图,因而路径是双向的 G.arcs[f1(subString1[r])][f1(subString2[r])] = f1(subString3[r]); G.arcs[f1(subString2[r])][f1(subString1[r])] = f1(subString3[r]); }}
//5、打印图的全部景点的信息void printDataOfGraph(MGraph G){ //设置输出格式,向左边靠 cout.setf(ios::left,ios::adjustfield); //使用setw()输出 cout << setw(10) << “编号” << setw(15) << “名称” << “简介” << endl; for(int i = 0; i < G.vernum; i++) { //大致按格式输出景点的编号、名称、简介 cout << setw(10) << G.ver[i].num << setw(15)<< G.ver[i].name << G.ver[i].information << endl; } cout << endl;}
//6、根据景点的编号，输出该景点的所有信息void searchByNum(MGraph G){ int num1; cout << “您好！输入格式：编号(只能是自然数,如0,1,2,3…… )+回车键” << endl; cout << “请您按格式输入您要查询景点的编号：”; cin >> num1; //for循环查询 for(int i = 0;i <= G.vernum; i++) { if (i == num1) //匹配景点的编号 { cout <<“您所查询的景点信息： p=”” style=”mso-spacerun:yes” span=”” lang=”EN-US” cout=”” .num=”” .name=”” .information=”” i=”” void=”” mgraph=”” int=”” if=”” str1=”=” g:=”” dist:=”” path:=”” n=”G.vernum;</span” dist=”” path=”” j=”” v=”” u=””>”; }else { int mid = path[u][v]; //mid用于记录景点u到景点v的路径的中间路径景点(靠u的景点) printPath(u, mid, path); //递归,节点u到节点mid printPath(mid, v, path); //递归,节点mid到节点v }}
//10、显示任意两个景点的最短路径void displayShortestPath(MGraph G){ int num1, num2; bool flag1,flag2; cout << “您好！请您输入要查询最短路径的两个不同的景点的编号！” << endl; cout << “输入格式：编号(必须是自然数,范围：0至” << MAXVER-1 <<“)+回车键” << endl; cout <<“请您输入起点景点的编号：”;< span=””> cin >> num1; cout <<“请您输入终点景点的编号：”;< span=””> cin >> num2;
//第一道检验，提示用户输入的两个景点编号相同 if(num1 == num2) { cout << endl; cout << “对不起！您所输入的两个景点的编号一样，其实指的是同一个景点！” << endl; cout << “请您规范输入，谢谢配合！” << endl; cout << endl; return; }
//判断输入景点是否存在,并且记录下来 for(int i = 0; i < G.vernum; i++) { if(num1 == G.ver[i].num) //匹配第一个景点的编号 { //存在,将flag1 赋值为 true flag1 = true; } if(num2 == G.ver[i].num) //匹配第二个景点的编号 { flag2 = true; } } //第二检验，提示用户输入的两个景点编号不存在 if(!(flag1 || flag2)) { cout << “您好！您所输入的两个景点的编号对应的两个景点都不存在！” << endl; cout << endl; return; }else if(!flag1) { cout << “您好！您所输入的两个景点的编号对应的两个景点中，第一个输入的编号对应的景点不存在！” << endl; cout << endl; return; }else if(!flag2) { cout << “您好！您所输入的两个景点的编号对应的两个景点中，第二个输入的编号对应的景点不存在！” << endl; cout << endl; return; } //n 是记录图的节点的数量 int n = G.vernum; //数组 dist[][] 是存储图的边的邻接矩阵 int **dist = new int *[n]; //数组 path[][] 是记录图的最短路径的节点次序的矩阵 int **path = new int *[n];
for(int j = 0; j < n; j++) { dist[j] = new int[n]; path[j] = new int[n]; } //调用floyd()，给数组 dist, path 赋值 floyd(G,dist,path); //最短路径的长度值赋给length1 int length1 = dist[num1][num2]; //第三道检验，找不到两个景点的可达到路径，则显示查找不到的提示语 if(length1 == INFINITY) { cout << “对不起！您所输入的两个景点没有路径可以到达！” << endl; cout << endl; return; } //调用printPath(),输出最短路径的中间节点 printPath(num1,num2,path); //输出所查询的最短路径的信息 cout << num2 << “=” << length1 << endl; cout << endl; //数组在函数结束时就没了，这里只需释放指针 delete dist; delete path; return;}
//11、增加景点void addNode(MGraph &G){ int n = G.vernum; string name1; string info1; cout << “您好！输入格式：名称+空格+简介+回车键” << endl; cout << “请您按输入格式输入您要增加的景点的名称、简介：” << endl; cin >> name1 >> info1; //判断景点表是否满了 if(n >= MAXVER) { //满了,便显示节点空间不足的提示语 cout << “对不起！景点空间已满，目前暂时无法增加景点！” << endl; cout << endl; return; } //循环将要增加的景点已经存在 for(int i = 0; i < n; i++) { if(name1 == G.ver[i].name) //匹配要新加景点的名称 { //提示用户所输入景点的名称已经存在 cout << “您好！您所输入的要增加的景点的名称已经存在！无法进行增加景点！” << endl; cout << endl; return; }
} //对新增加的景点赋值 G.ver[n].num = n; G.ver[n].name = name1; G.ver[n].information = info1; //景点数加1 G.vernum++; //显示成功增加景点的提示语 cout << “您好！您已成功增加景点！” << endl; cout << endl; return;}
//12、增加道路void addArc(MGraph &G){ int num1, num2, arc1; bool flag1, flag2; //标志变量,默认值为 false cout << “您好！输入格式：第一个景点编号+空格+第二个景点编号+空格+道路的长度(只能是正整数)+回车键” << endl; cout << “景点的编号必须是自然数,范围：0至” << MAXVER-1 << endl; cout << “请您按 输入格式 输入您要增加的景点道路：”; cin >> num1 >> num2 >> arc1;
if(arc1 < 0) { cout << “您好！道路的长度只能是正整数！请规范输入，谢谢配合！” << endl; cout << endl; return; } //提示用户输入的两个景点编号相同 if(num1 == num2) { cout << endl; cout << “对不起！您所输入的两个景点的编号一样，其实指的是同一个景点！” << endl; cout << “请您规范输入，谢谢配合！” << endl; cout << endl; return; } for(int i = 0; i < G.vernum; i++) { if(num1 == G.ver[i].num) //匹配第一个景点的编号 { flag1 = true; } if(num2 == G.ver[i].num) //匹配第二个景点的编号 { flag2 = true; } } //检查两个景点都存在 if(!(flag1 || flag2)) { cout << “您好！您所输入的两个景点的编号对应的两个景点都不存在, 无法增加道路！” << endl; cout << endl; return; }else if(!flag1) { cout << “您好！您所输入的两个景点的编号对应的两个景点中，第一个输入的编号对应的景点不存在，无法增加道路！” << endl; cout << endl; return; }else if(!flag2) { cout << “您好！您所输入的两个景点的编号对应的两个景点中，第二个输入的编号对应的景点不存在，无法增加道路！” << endl; cout << endl; return; }
//检查两个景点之间不存在道路,才能进行增加道路(路径长) if(G.arcs[num1][num2] == INFINITY) { //在无向图的邻接矩阵里增加道路 G.arcs[num1][num2] = arc1; G.arcs[num2][num1] = arc1; //道路数目加1 G.arcnum++; cout << “您好！您已成功增加道路！” << endl; cout << endl; return; }else { cout << “您好！您所输入的两个景点的编号对应的两个景点已存在，且两个景点之间存在道路,无法进行增加道路！” << endl; cout << endl; return; }}
//13、修改景点的简介void updateInformation(MGraph &G){ int num1; string info1; bool flag1; //标志变量 cout << “您好！编号的输入格式：编号+回车键” << endl; cout << “景点的编号必须是自然数,范围：0至” << MAXVER-1 << endl; cout << “请您按编号的输入格式输入您要修改的景点的编号：”; cin >> num1; cout << “您好！名称的输入格式：简介+回车键” << endl; cout << “请您按名称的输入格式输入您要修改的景点的新简介：”; cin >> info1;
int i = 0; for(; i < G.vernum; i++) { if(num1 == G.ver[i].num) //匹配要修改景点的编号 { //标志变量赋值为 true flag1 = true; //匹配到就跳出循环 break; } } if(flag1) { //修改景点的简介 G.ver[i].information = info1; //显示修改成功的提示语 cout << “您好！您已成功修改您所输入的景点的简介！” << endl; cout << endl; return; }else { //显示无法修改成功的提示语 cout << “对不起！您所输入的景点的编号对应的景点不存在,无法进行修改景点的简介！” << endl; cout << endl; return; }}
//14、修改景点的名称void updateName(MGraph &G){ int num1; string name1; bool flag1; //标志变量 cout << “您好！编号的输入格式：编号+回车键” << endl; cout << “景点的编号必须是自然数,范围：0至” << MAXVER-1 << endl; cout << “请您按编号的输入格式输入您要修改的景点的编号：”; cin >> num1; cout << “您好！名称的输入格式：简介+回车键” << endl; cout << “请您按名称的输入格式输入您要修改的景点的新名称：”; cin >> name1;
int i = 0; for(; i < G.vernum; i++) { if(num1 == G.ver[i].num) //匹配要修改景点的编号 { //标志变量赋值为 true flag1 = true; //匹配到就跳出循环 break; } } if(flag1) { //修改景点的简介 G.ver[i].name = name1; //显示修改成功的提示语 cout << “您好！您已成功修改您所输入的景点的名称！” << endl; cout << endl; return; }else { //显示无法修改成功的提示语 cout << “对不起！您所输入的景点的编号对应的景点不存在,无法进行修改景点的名称！” << endl; cout << endl; return; }}
//15、修改道路的长度值void updateArc(MGraph &G){ int num1, num2, arc1; bool flag1, flag2; //标志变量,默认值为 false cout << “您好！输入格式：第一个景点编号+空格+第二个景点编号+回车键” << endl; cout << “景点的编号必须是自然数,范围：0至” << MAXVER-1 << endl; cout << “请您按 输入格式 输入您要修改的道路所对应的两个景点：”; cin >> num1 >> num2; cout << “道路的长度(只能是正整数)+回车键” << endl; cout << “请您按 输入格式 输入您要修改的道路的长度值：”; cin >> arc1;
if(arc1 < 0) { cout << “您好！道路的长度只能是正整数！请规范输入，谢谢配合！” << endl; cout << endl; return; } //提示用户输入的两个景点编号相同 if(num1 == num2) { cout << endl; cout << “对不起！您所输入的两个景点的编号一样，其实指的是同一个景点！” << endl; cout << “请您规范输入，谢谢配合！” << endl; cout << endl; return; } for(int i = 0; i < G.vernum; i++) { if(num1 == G.ver[i].num) //匹配第一个景点的编号 { flag1 = true; } if(num2 == G.ver[i].num) //匹配第二个景点的编号 { flag2 = true; } } //检查两个景点都存在 if(!(flag1 || flag2)) { cout << “您好！您所输入的两个景点的编号对应的两个景点都不存在, 无法修改道路的长度值！” << endl; cout << endl; return; }else if(!flag1) { cout << “您好！您所输入的两个景点的编号对应的两个景点中，第一个输入的编号对应的景点不存在，无法修改道路的长度值！” << endl; cout << endl; return; }else if(!flag2) { cout << “您好！您所输入的两个景点的编号对应的两个景点中，第二个输入的编号对应的景点不存在，无法修改道路的长度值！” << endl; cout << endl; return; }
//在无向图的邻接矩阵里修改道路 G.arcs[num1][num2] = arc1; G.arcs[num2][num1] = arc1; cout << “您好！您已成功增加道路！” << endl; cout << endl; return;}
//16、删除道路void deleteArc(MGraph &G){ int num1, num2; bool flag1, flag2; //标志变量，默认值为 false cout << “您好！输入格式：第一个景点编号+空格+第二个景点编号+回车键” << endl; cout << “景点的编号必须是自然数,范围：0至” << MAXVER-1 << endl; cout << “请您按输入格式输入您要删除的景点道路所对应的两个编号：”; cin >> num1 >> num2;
//第一道检验，提示用户输入的两个景点编号相同 if(num1 == num2) { cout << endl; cout << “对不起！您所输入的两个景点的编号一样，其实指的是同一个景点！” << endl; cout << “请您规范输入，谢谢配合！” << endl; cout << endl; return; } for(int i = 0; i < G.vernum; i++) { if(num1 == G.ver[i].num) //匹配第一个景点的编号 { flag1 = true; } if(num2 == G.ver[i].num) //匹配第二个景点的编号 { flag2 = true; } }
if(flag1 && flag2) { if(G.arcs[num1][num2] != INFINITY) //两个景点都存在&两个景点之间存在道路,才能进行删除道路(路径长) { //在邻接矩阵里删除道路,赋值为无穷大 G.arcs[num1][num2] = INFINITY; G.arcs[num2][num1] = INFINITY; //道路的数目减去1 G.arcnum–; //显示成功删除道路的提示语 cout << “您好！您已成功删除道路！” << endl; cout << endl; return; }else { cout << “您好！您所输入的两个景点的编号对应的两个景点存在，但两个景点之间不存在道路，无法进行删除道路！” << endl; cout << endl; return; } }else if(!(flag1 || flag2)) { cout << “您好！您所输入的两个景点的编号对应的两个景点都不存在！” << endl; cout << endl; return; }else if(!flag1) { cout << “您好！您所输入的两个景点的编号对应的两个景点中，第一个输入的编号对应的景点不存在,无法进行删除道路！” << endl; cout << endl; return; }else { cout << “您好！您所输入的两个景点的编号对应的两个景点中，第二个输入的编号对应的景点不存在,无法进行删除道路！” << endl; cout << endl; return; }}
//17、删除景点void deleteNode(MGraph &G){ int num1; int k = G.vernum; //图的景点数目赋值给k bool flag; //标志变量 cout << “输入格式：编号(必须是自然数,范围：0至” << MAXVER-1 <<“)+回车键” << endl; cout << “请您按输入格式输入您要删除的景点的编号：”; cin >> num1; int i = 0; for(; i < k; i++) { if(num1 == G.ver[i].num) { //找到则设置标志变量为true flag = true; //找到，则跳出循环 break; } }
if(flag) { //在被删除的景点之后的景点数组的景点,应向前移动一位 for(int j = i; j < k – 1; j++) { //通过覆盖数据实现移动 G.ver[j].name = G.ver[j+1].name; G.ver[j].information = G.ver[j+1].information; } //将最后一个景点”清除” G.ver[k-1].num = -2; G.ver[k-1].name = “”; G.ver[k-1].information = “”;
/* *删除景点的同时顺便把道路给删除了(没了景点留着道路没什么意义) *实现：把图的边对应的邻接矩阵（有实际的意义那部分）从 N×N 变为 (N-1)×(N-1) */ //for查找要删除的景点的编号,在边的邻接矩阵相关的元素,再减少图的边数目 for(int a = 0; a < G.vernum; a++) { //由于是无向图,因而只需处理行 if(G.arcs[i][a] != INFINITY) { G.arcnum–; } } //将图的边对应的邻接矩阵,从删除的景点的编号开始按行上移 for(int m = i; m < k – 1; m++) { for(int n = 0; n < G.vernum; n++) { //从要删除的景点开始，其所对应的边的邻接矩阵按行上移 G.arcs[m][n] = G.arcs[m + 1][n]; } } //将图的边对应的邻接矩阵,从删除的景点的编号开始按列左移 for(int r = i; r < k – 1; r++) { for(int s = 0; s < G.vernum; s++) { //在按行上移的基础上，再让边的邻接矩阵按列左移 G.arcs[s][r] = G.arcs[s][r + 1]; } } //将图的边对应的邻接矩阵，最右一行、最下一行的元素赋值为无穷大 for(int t = 0; t < G.vernum; t++) { G.arcs[k – 1][t] = INFINITY; G.arcs[t][k – 1] = INFINITY; } //景点的数目减去1 G.vernum–; //显示成功删除道路的提示语 cout << “您好！您已成功删除景点！” << endl; cout << endl; return; }else { //显示无法删除景点的提示语 cout << “您好！您所输入的景点的编号对应的景点不存在，无法进行删除景点！” << endl; cout << endl; return; }}
文件main.cpp如下：
#include”headPro.h”/*#include”header.h”:表明当前文件和”header.h”处于同一工程同一目录*//*#include<header.h>:表明header.h和当前文件不属于同一工程，是外部引用*/
#include<iostream> //使用cin(),cout()#include<stdio.h> //使用printf(),scanf()/*extern: 实现C++代码跨文件调用函数*/extern int inputString(char *filename,string str[]);extern int f1(string str);extern void f2(string str, string &str1, string &str2, string &str3);extern void createGraph(MGraph &G);extern void printDataOfGraph(MGraph G);extern void searchByNum(MGraph G);extern void searchByName(MGraph G);extern void floyd(MGraph G, int **dist, int **path);extern void printPath(int u, int v, int **path);extern void displayShortestPath(MGraph G);extern void addNode(MGraph &G);extern void addArc(MGraph &G);extern void updateInformation(MGraph &G);extern void updateName(MGraph &G);extern void updateArc(MGraph &G);extern void deleteArc(MGraph &G);extern void deleteNode(MGraph &G);
//18、大致显示无向图最初的形状void showMap(){ printf(“tt|————————————————————————|n”); printf(“tt| |n”); printf(“tt| |——-| [350] |n”); printf(“tt| [800] | 7桃园 |———————-| |n”); printf(“tt| |——————–|——-| |——| |n”); printf(“tt| |————| [350] | | |12沁湖| |n”); printf(“tt| |10学而优超市| [180] | | |——| |n”); printf(“tt| |————|———|—–| | | |n”); printf(“tt| | ——|6李园| |[370] | |n”); printf(“tt| | | |—–| | |[100] |n”); printf(“tt| | [130]| | | | |n”); printf(“tt| [180]| | [90]| | | |n”); printf(“tt| | | | | | |n”); printf(“tt| | | |———| [100] |——–| |n”); printf(“tt| | | | 0励学楼 |———————|5 创业 | |n”); printf(“tt| |———-| | |（一教） | |———-|—–| 园区 | |n”); printf(“tt| |11灯光球场| | |———| | 3 拓新楼 |[170]|——–| |n”); printf(“tt| |———-| | | | | |（实验楼）| | |n”); printf(“tt| | | | [120]| | | |———-|—–| | |n”); printf(“tt| | | | | | |[200] &nbs
