C++数据结构 交通咨询系统设计（一）
C++数据结构 交通咨询系统设计（一）文件读取&画图部分
C++数据结构 交通咨询系统设计（一）
记录一下自己做这个课程设计图论部分题目的一些流程思路
一、题目描述
设计一个交通咨询系统，通过读取全国城市距离图（http://pan.baidu.com/s/1jIauHSE，请在程序运行时动态加载到内存，可将excel转成csv方便读取），实现：
问题1：请验证全国其他省会城市（不包括港澳和两个宝岛台北和海口）到武汉中间不超过2个省（省会城市）是否成立？（正是因为武汉处于全国的中心位置，此次疫情才传播的如此广）
问题2：允许用户查询从任一个城市到另一个城市之间的最短路径（两种算法均要实现，界面上可自行选择）以及所有不重复的可行路径（可限制最多经过10个节点），并利用快速排序对所有路径方案依据总长度进行排序输出（输出到文件），每一条结果均需包含路径信息及总长度，试比较排序后的结果与迪杰斯特拉算法和费洛伊德算法输出的结果
问题3：假设在求解2个城市间最短路径时需要绕过某个特定的城市（用户输入或者选择，例如武汉），请问应该如何实现？
问题4：不基于功能2遍历的结果如何直接求解两个城市间的前第K短的路径，例如，武汉到北京之间第3短的路径。
二、文件读取
在网盘上下载的是一份包含了两个矩阵的Excel文件，将它们分成单独两份保存成csv文件。
文件1：省会城市距离矩阵.csv
（是一个三角矩阵, 里面记录了任意两个城市之间的距离，不管这两个城市之间是否邻接）
文件2：省会城市邻接矩阵.csv
（正儿八经的邻接矩阵，0 表示行城市和列城市不相邻，1 则表示它们相邻）
有了这两份csv文件之后，就可以分别去读取它们，从而建立两个关键的矩阵（二维数组）
① 省会城市距离矩阵，② 省会城市邻接矩阵
PS：题目中的城市数量是确定的（34个），也不用对这个矩阵做任何插入或者删除的操作，所以构建二维数组时图方便的话可以不用动态new方法去构建而是考虑直接 int Edge[34][34] 粗暴解决。
构建带权值的邻接矩阵Edge
① Edge[i][j] = 0 → i = j
② Edge[i][j] = ∞ → Vi 和 Vj 不相邻， 即 EdgeMatrix[i][j] = 0
③ Edge[i][j] = DistanceMatrix[i][j] → Vi 和 Vj 相邻， 即 EdgeMatrix[i][j] = 1
注释：DistanceMatrix是读取文件1的距离矩阵，EdgeMatrix是读取文件2的邻接矩阵
-
先把刚刚读文件的部分整合成函数:
ReadCSV(string Filename, int Martix[34][34]);
分别调用两次填充制作得到城市距离矩阵 DistanceMatrix 和城市邻接矩阵 EdgeMatrix
然后读取这两个矩阵，汇总制作出真正用于后面题目的带权值的邻接矩阵 Edge -
读取文件这一部分可以说几乎完全是独立于后面要写的功能或者界面的，就是不管下面用啥界面做读取的思路应该和我自己整的这个差不了多少，如果想用非控制台来做界面的话，这一部分其实可以另外新开一个控制台去测试，测好了再把这部分移入到要做的界面当中。
三、框架设计
题目中要求做界面，我自己也只会用 MFC 和控制台两种，在这里就考虑用 MFC 来做框架了
（一）画图部分的类设计
想到图论的应用，特别是像这一题需要看城市之间的路径的题目，一般来说可视化要求是将整幅图展示在界面上面，同时对于每一个功能，都应该用不同的形式展示在刚刚画出的整幅图中（例如我把城市图用黑色画在对话框上，那么找到的路径就可以换一种颜色，如蓝色标记出来）
如图所示：
黑色是初始化图：
蓝色则标记处一条题目要求的路径（如寻找乌鲁木齐到长沙的最短路径）：
（红色结点表示出起点城市和终点城市，那么绿色结点就可以用来表示绕过某个城市）
如在上图的基础上，强行绕过西宁之后，乌鲁木齐到长沙的最短路径变成：
（可以看到这样的可视化画图界面较为直观易懂）
为了比较容易地实现这样的作图效果，需要定义以下的内容：
① 结点类，必须内置单个结点的画图函数
② 线类，必须内置这一条线（两个邻接结点之间）的画图函数，同时还得标记出这两个结点之间的权值
③ 路径类，含有从起点到终点的所有连线，必须内置单条路径的画图函数
④ 画出初始化图的函数
下面就开始逐个解决这些部分的设计。
1. 结点类（MapPoint）
这道题中，每一个结点代表一个城市，数据成员肯定得有一个能够打印到界面的 CString 类变量CityName 来表示城市名称。为了画图，这个结点类必须包含有MFC点类 CPoint 的指针 ptr，同时为了方便城市名称与其对应下标关系（存在邻接矩阵 Edge[i][j] ,必须知道 i 行到底是啥城市），还需要一个 int 变量 Mark 来标记，再加上记录坐标的 double 型变量 x ，y，那么这一个MapPoint 类的数据成员就可以基本上确定下来了。
声明部分如下：
class MapPoint
{
public:
//数据成员
CString CityName; //城市名称
int Mark; //标记，类似于下标，Vi 结点的 Mark 就是 i
double x, y; //x, y 坐标
CPoint* ptr; //ptr 指针，用于画图
//默认构造函数
MapPoint() :
CityName(_T("")),
Mark(-1), x(0), y(0), ptr(NULL) {}
//含参构造函数
MapPoint(CString name, int mark, double xPoint, double yPoint) :
CityName(name),
Mark(mark),
x(xPoint),
y(yPoint)
{
//根据输入的坐标写入到 CPoint 指针中
ptr = new CPoint(x, y);
}
//画图函数
bool DrawPoint(CDC* pDC, double Radius = 10);
};
结点的画图函数 DrawPoint ，只需要获取 CDC指针，和用户给定的半径就可以绘图。其中 CDC 指针 pDC 相当于控制着画笔的颜色，色号大小，笔头🖊的类型。
-
这三部分内容实际上是整合在MFC画笔类 CPen 中的
（如：CPen blackPen(PS_SOLID, 2, RGB(0,0,0))）
而 CDC 指针就可以在每一次需要画图时选择对应需要的画笔就可以达到控制上面三要素的目的：
（如： pDC->SelectObject(&blackPen);）
然后把这个pDC传给画图函数，画出来的点/线就是符合要求的啦 -
所以画图函数自己只需要解决画什么东西就可。对于点的画图函数而言，就只需要画圆和打印出城市名称即可
点画图函数代码部分如下：
//绘制点函数
bool MapPoint::DrawPoint(CDC* pDC, double Radius)
{
//以圆代替点
pDC->Ellipse(ptr->x - Radius, ptr->y - Radius, ptr->x + Radius, ptr->y + Radius);
//打印出城市名称
pDC->TextOutW(ptr->x, ptr->y, CityName);
return true;
}
2. 线类（MapLine）
有了前面点类的铺垫，线类就比较好展开啦。
数据成员包括：
① 两个端点类 MapPoint 的指针 startPtr，endPtr
② 权值（即两邻接城市的距离）lineDistance 以及用于输出的 CString 形式 Distance
③ 用于在两点中间打印权值必须得有的 CPoint 类指针 midPoint
声明部分如下：
//地图线类
class MapLine
{
public:
//数据成员
MapPoint * startPtr, * endPtr; //起点和终点
int lineDistance; //点权值（两城市实际距离）
CPoint * midPoint; //终点（用于将权值数据标出）画图时用到
CString Distance; //距离（用于画图）
//成员函数
MapLine(); //构造函数（默认）
MapLine(MapPoint* pStart, MapPoint* pEnd, int dist); //构造函数（两点构造）
MapLine(const MapLine& otherLine); //拷贝构造函数
bool DrawLine(CDC* pDC); //画线函数
bool operator!=(const MapLine& otherLine); //不同边的判定
};
- 画线函数 DrawLine 主要任务就是画线和在中点标出权值
线画图函数代码部分如下：
//画线函数
bool MapLine::DrawLine(CDC* pDC)
{
//标定起点和终点，连线
pDC->MoveTo(startPtr->ptr->x, startPtr->ptr->y);
pDC->LineTo(endPtr->ptr->x, endPtr->ptr->y);
//在中点的位置打印权值数据，其中将坐标稍稍偏离一点，避免数据和线重合在一起太难看
pDC->TextOutW(midPoint->x - 10, midPoint->y - 10, Distance);
return true;
}
3. 路径类（MapLine）
一条路径就是一组从起点出发到终点的所有边的集合。在存储上直接使用边的数组会比较方便，直观上看这个数组类似于下图，每一个元素存一条边 MapLine 类元素。
利用这个数组，通过遍历的方法就能把路径画出或者拼接成字符串输出，同时也可计算某一条路径总的权值数。
声明部分如下：
//路径类
class LinesPath
{
public:
//数据成员
int TotalWeight; //路径总权值
vector<MapLine> PathArray; //路径数组，每个元素就是一条边
CString PathArrayStr; //用于最后输出的路径字符串
//成员函数
LinesPath(); //构造函数（默认）
LinesPath(const LinesPath& otherPath);
LinesPath(int Edge[34][34], MapPoint Points[34], int Path[]); //构造函数（利用做好的变化数组）
LinesPath(vector<int> Arr,int Edge[34][34],MapPoint Points[34]);
bool DrawPath(CDC* pDC); //画路径函数
};
路径画图函数代码部分如下：
bool LinesPath::DrawPath(CDC* pDC)
{
for (int i = 0; i < PathArray.size(); ++i)
{
//将每一条边逐一画出即可
PathArray[i].DrawLine(pDC);
}
return true;
}
（二）画图部分的城市坐标设计
手工画出城市图，需要给出每一个城市的具体坐标。一个一个自己标定显然是不可取的，比较可行的办法是套用经纬度坐标，将它们修改和放大。
具体来说，先去外面拿到每个城市的经纬度坐标，整合到前面的点类，创建出一个仅用于画图使用的点数组。
创建格式为： 城市名称 + 城市下标代号 + 经度坐标 + 纬度坐标
经纬度数据问百度问出来的，就不发链接了
//图结点数组
MapPoint Points[34] = {
MapPoint(_T("北京"),0,116.4666667,39.9), //北京,116.4666667,39.9
MapPoint(_T("上海"),1,121.4833333,31.23333333), //上海,121.4833333,31.23333333
MapPoint(_T("天津"),2,117.1833333,39.15), //天津,117.1833333,39.15
MapPoint(_T("重庆"),3,106.5333333,29.53333333), //重庆,106.5333333,29.53333333
MapPoint(_T("哈尔滨"),4,126.6833333,45.75), //哈尔滨,126.6833333,45.75
MapPoint(_T("长春"),5,125.3166667,43.86666667), //长春,125.3166667,43.86666667
MapPoint(_T("沈阳"),6,123.4,41.83333333), //沈阳,123.4,41.83333333
MapPoint(_T("呼和浩特"),7,111.8,40.81666667), //呼和浩特,111.8,40.81666667
MapPoint(_T("石家庄"),8,114.4666667,38.03333333),//石家庄,114.4666667,38.03333333
MapPoint(_T("太原"),9,112.5666667,37.86666667), //太原,112.5666667,37.86666667
MapPoint(_T("济南"),10,117,36.63333333), //济南,117,36.63333333
MapPoint(_T("郑州"),11,113.7,34.8), //郑州,113.7,34.8
MapPoint(_T("西安"),12,108.9,34.26666667), //西安,108.9,34.26666667
MapPoint(_T("兰州"),13,103.8166667,36.05), //兰州,103.8166667,36.05
MapPoint(_T("银川"),14,106.2666667,38.33333333), //银川,106.2666667,38.33333333
MapPoint(_T("西宁"),15,101.75,36.63333333), //西宁,101.75,36.63333333
MapPoint(_T("乌鲁木齐"),16,87.6,43.8), //乌鲁木齐,87.6,43.8
MapPoint(_T("合肥"),17,117.3,31.85), //合肥,117.3,31.85
MapPoint(_T("南京"),18,118.8333333,32.03333333), //南京,118.8333333,32.03333333
MapPoint(_T("杭州"),19,120.15,30.23333333), //杭州,120.15,30.23333333
MapPoint(_T("长沙"),20,113,28.18333333), //长沙,113,28.18333333
MapPoint(_T("南昌"),21,115.8666667,28.68333333), //南昌,115.8666667,28.68333333
MapPoint(_T("武汉"),22,114.35,30.61666667), //武汉,114.35,30.61666667
MapPoint(_T("成都"),23,104.0833333,30.65), //成都,104.0833333,30.65
MapPoint(_T("贵阳"),24,106.7,26.58333333), //贵阳,106.7,26.58333333
MapPoint(_T("福州"),25,119.3,26.08333333), //福州,119.3,26.08333333
MapPoint(_T("台北"),26,121.5166667,25.05), //台北,121.5166667,25.05
MapPoint(_T("广州"),27,113.25,23.13333333), //广州,113.25,23.13333333
MapPoint(_T("海口"),28,110.3333333,20.03333333), //海口,110.3333333,20.03333333
MapPoint(_T("南宁"),29,108.3333333,22.8), //南宁,108.3333333,22.8
MapPoint(_T("昆明"),30,102.6833333,25), //昆明,102.6833333,25
MapPoint(_T("拉萨"),31,91.16666667,29.66666667), //拉萨,91.16666667,29.66666667
MapPoint(_T("香港"),32,114.1666667,22.3), //香港,114.1666667,22.3
MapPoint(_T("澳门"),33,113.5,22.2), //澳门,113.5,22.2
};
显然，只依赖这套数据是没办法画图的，因为每个城市间经纬度差异在数值上太小，而且没有一个确切的“中心”来画图。
所以下面需要解决的问题就是：
- 维度数据是从下到上变大的，但是MFC画图中 y 轴坐标是从上到下的，必须先转换 y 轴坐标
- 找一个城市，把它当作“坐标原点”
- 将其它城市的坐标修改为以改原点为中心的直角坐标系的标准坐标
- 在对话框中，确定坐标原点的具体的 x0 ，y0 坐标
- 其余城市的标准坐标都在此基础上加上 x0 ，y0 的偏移量
- 再将现在其它城市的坐标做适当的放大处理
方便叙述，先规定以下的符号：
某一个城市 i 的理论坐标为（x，y），实际在画布上的坐标为： （Xi，Yi）
PS：原点 O 的理论坐标为（0，0），但实际上在画布的坐标为：（X0，Y0）
1. 转换 y 轴坐标
整个对话框的画布（作图区域）可以看成这样：
可以看到，维度变化是和MFC作图的 y 轴变化刚好相反，所以先要对每一个城市的纵坐标 Y 做调整。
调整方式是取一个上限值减去所有城市的维度值：
即：
y = Y l i m i t − y . \ {y} = {Y}_{limit} - y. y=Ylimit−y.
在这里我就取了极限值为 50，即拿 50 减去每一个城市的 y
for (int i = 0; i < 34; ++i)
{
Points[i].ptr->y = 50- Points[i].ptr->y;
}
2. 坐标原点划定 & 求“标准坐标”
在整个中国城市图中，需要选出一个城市，作为整个图的“原点”，这个原点可以是任何一个城市，方便设计在这里就取武汉作为坐标原点 O
武汉现在的城市数据：
- i = 22 （代号）
- X = 114.35 ≈ 114
- Y = 50 - 30.61666667 ≈ 20
现在只需要把所有城市的 x，y 数据全部减去武汉的 x 和 y 数据，就能得到所有城市相对于武汉的直角坐标数据（或者说其它城市距离武汉的 x，y 偏移量）
- x = x − x w u h a n {x} = x - {x}_{wuhan} x=x−xwuhan
- y = y − y w u h a n {y} = y - {y}_{wuhan} y=y−ywuhan
//武汉,114.35,30.61666667为 基准坐标
int x0 = Points[22].ptr->x, y0 = Points[22].ptr->y;
for (int i = 0; i < 34; ++i)
{
Points[i].ptr->x = (Points[i].ptr->x - x0);
Points[i].ptr->y = (Points[i].ptr->y - y0);
Points[i].x = Points[i].ptr->x;
Points[i].y =Points[i].ptr->y;
}
3. 确定原点实际坐标 & 调整偏移量 & 放大系数
前面两步完成之后，如果直接画图，画的结果大致如下：
所有点都会落在红色的矩形区域内，且有一大部分甚至都会落到对话框外面画不出来。原因是当前武汉作为坐标原点，它的实际坐标是（0，0）而（0，0）就在对话框的左上角位置，所以才会出现这种情况，解决办法就是先给武汉找到合适的位置（即先找到原点应该落位在哪）：
然后再把其它城市的坐标也相对应的加上这一个偏移量，让它们也移动到中间来：
但是此时画出来的图，所有的点都挤在一起了，这是因为所有城市离武汉的经纬度距离在数值上显得太小，需要对这个数据进行放大，在图上的效果是这样的：
所以综上所述，对于每一个城市结点而言，在这一步调整的公式为：
1.设定武汉（坐标原点）在对话框的实际坐标
即： X w u h a n = 800 {X}_{wuhan} = 800 Xwuhan=800 ； Y w u h a n = 400 {Y}_{wuhan} = 400 Ywuhan=400
2.确定放大系数： n = 20 {n} = 20 n=20（放大 20 倍）
3.对于每一个城市 i 而言：
X i = X w u h a n + X ∗ n ; Y i = Y w u h a n + Y ∗ n {X}_{i} = {X}_{wuhan} + {X} * n;{Y}_{i} = {Y}_{wuhan} + {Y} * n Xi=Xwuhan+X∗n;Yi=Ywuhan+Y∗n
//设定武汉在画布中的实际位置
int X_wuhan = 800, Y_wuhan = 400;
for (int i = 0; i < 34; ++i)
{
Points[i].ptr->x = X_wuhan + (Points[i].ptr->x * n);
Points[i].ptr->y = Y_wuhan + (Points[i].ptr->y * n);
}
综上所述，整一个调整坐标的流程都可以整合到初始化的部分，代码如下：
//初始化按钮
void CMFCTrafficSystemDlg::OnBnClickedButtonSetup()
{
//放大倍数 n 定为 20 倍
int n = 20;
for (int i = 0; i < 34; ++i)
{
Points[i].ptr->y = 50- Points[i].ptr->y;
}
//武汉,114.35,30.61666667 为 基准坐标
int x0 = Points[22].ptr->x, y0 = Points[22].ptr->y;
for (int i = 0; i < 34; ++i)
{
Points[i].ptr->x = (Points[i].ptr->x - x0);
Points[i].ptr->y = (Points[i].ptr->y - y0);
Points[i].x = Points[i].ptr->x;
Points[i].y =Points[i].ptr->y;
}
//设定武汉在画布中的实际位置
int X_wuhan = 800, Y_wuhan = 400;
for (int i = 0; i < 34; ++i)
{
Points[i].ptr->x = X_wuhan + (Points[i].ptr->x * n);
Points[i].ptr->y = Y_wuhan + (Points[i].ptr->y * n);
}
//作图函数
PaintAll();
//阶段数清空
Stage = -1;
MessageBox(_T("初始化完成"));
}
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
9
0- 0
已为社区贡献1条内容
所有评论(0)