简单数据结构实现.zip

##图 [TOC] 这里不做术语介绍，详细请查阅[wiki链接](https://zh.wikipedia.org/wiki/%E5%9B%BE_(%E6%95%B0%E5%AD%A6)) 实现功能 1. 创建、销毁 2. 添加结点 3. 重置结点 4. 分别为有、无向图设置邻接矩阵 5. 打印邻接矩阵 6. 深度优先遍历 7. 广度优先遍历 8. 普利姆最小生成树 9. 克鲁斯卡尔最小生成树 ```bash # 编译各个demo所需要的cpp g++ demo.cpp CMap.cpp Node.cpp -o demo g++ demo2.cpp CMap.cpp Node.cpp Edge.cpp -o demo2 ``` ### 搜索 假设我们要构造如下的图。 这里采取的办法是使用邻接矩阵。有值的地方表示存在连接，没有值的地方表示不存在连接，所以上面的图就可以转换成下面这个矩阵。这里值可以理解为边的权值，方便起见我们设置为１。同样为了方便起见，我们使用无向图进行说明。无向图在邻接矩阵上的体现为**[对称矩阵](https://baike.baidu.com/item/%E5%AF%B9%E7%A7%B0%E7%9F%A9%E9%98%B5)**，简单来说就是$a_{ij}=a_{ji}$。 深度优先（优先向深走），用的数据结构为栈，主要用递归实现 广度优先（优先向近走），用的数据结构为队列，主要用迭代实现 ```bash 图例： A / \ B D / \ / \ C F G-H \ / E A B C D E F G H A 1 1 B 1 1 1 C 1 1 1 D 1 1 1 E 1 F 1 1 G 1 1 H 1 1 输出： 深度优先遍历 A B C E F D G H 广度优先遍历 A B D C F G H E ``` #### 深度优先搜索 从顶点出发，访问与其连接的点（未被访问过），接下来继续进行上面的过程，如果当前点的所有连接点都被访问过，那么就回退到当前点的上一个节点重复上面的过程。最终直到所有的节点都被访问过。 按照给的案例，路线就应该是： 我们约定当前点有多条连接点时选择其最左侧顶点。这里要注意的是，Ｆ、Ｇ之间没有连接，Ｆ、Ｄ也没有，图上可能显示有点歧义，可以从邻接矩阵中看出。 所以我们从Ａ点出发，一路前进到Ｆ。 Ａ->B->C->E->F 接下来，Ｆ访问Ｂ，但是Ｂ已经被访问过了，所以回退到Ｅ。Ｅ同Ｆ的情况，进行回退，一直回退到Ａ。则从Ａ开始访问Ｄ。 Ｄ->G->H Ｈ访问Ｄ，但是Ｄ已经被返回过了，所以回退，一直回退到Ａ。发现所有的点都被访问过了，所以结束搜索。 综上，总的路程应该是Ａ->B->C->E->F->Ｄ->G->H。 根据思路，代码应该使用递归的思想来完成。这里可参考`CMap.p`的`depthFirstTraverse`部分。 #### 广度优先搜索 不同于深度优先搜索，广度优先搜索从理解上，会比深度优先搜索更好理解。 从顶点出发，访问它的所有连接的点。接下来，再分别以它所有连接点为顶点进行访问，即访问连接点的连接点。这里要注意的是，不能访问已经被访问过的点。 按照给的案例，路线应该是： 同样我们约定有多个连接点的时候，选择最左侧的点。 从Ａ出发，访问Ａ的连接点Ｂ、Ｄ A->B->D 接下来分别访问Ｂ、Ｄ的连接点 C->F、G->H 接下来，访问Ｃ、Ｆ、Ｇ、Ｈ的连接点 Ｅ Ｃ向下只有一个连接点，Ｆ向下的连接点Ｅ被访问过了，Ｇ、Ｈ向下无连接点。 所以，综上总的路程应该是A->B->D->C->F->G->H->Ｅ 其实直观来看，广度优先搜索就是按层搜索，一层一层的进行搜索。 这里用代码实现就是使用循环来完成。这里可参考`CMap.p`的`breadthFirstTraverse`部分 ### 最小生成树 下面说明两种最小生成树的算法。分别是**普利姆**算法和**克鲁斯卡尔**算法。我们以下面的图为案例进行说明。同样，这张图也是无向图，但是边具有权值。我们一样使用上面的邻接矩阵进行转换。邻接矩阵可以用代码生成。在这里，我们主要说明算法过程。 ```bash A / | \ B--F--E \/ \/ C---D A B C D E F 0 1 2 3 4 5 A-B 6 B-C 3 C-D 7 D-E 2 E-F 9 A-E 5 B-F 2 C-F 8 D-F 4 A-F 1 输出 普利姆最小生成树 起始点: A 0----5 1 F 5----1 2 B 1----2 3 C 5----3 4 D 3----4 2 E 克鲁斯卡尔最小生成树 0--5 1 1--5 2 3--4 2 1--2 3 3--5 4 ``` #### 普利姆最小生成树 从顶点出发，遍历所有的连接边的权值，选最小权值的边，加入边集合，之后将边连接的点加入点集合。以边连接的另一个点作为顶点，重复上述过程。直到完成最小生成树（最小生成树的边数等于顶点数减１）。 初始化，点集合{A}，边集合{} 这里我们从顶点Ａ出发，有三条连接边，Ａ-Ｂ，Ａ-Ｅ，Ａ-Ｆ。发现Ａ－Ｆ最小，所以此边加入边集合。点集合{A,F}，边集合{A-F} 从顶点Ｆ出发，有五条连接边，F-A，F-B，F-C，F-D，F-E。F-A被选择过了，所以排除F-A。在剩下的边中F-B最小，所以加入集合。点集合{A,F,B}，边集合{A-F, F-B} 所以下面从顶点Ｂ出发，B-C最小。点集合{A,F,B,C}，边集合{A-F,F-B,B-C} 接下来从顶点Ｃ出发，Ｃ-D最小。点集合{A,F,B,C,D}，边集合{A-F,F-B,B-C,C-D} 接下来从顶点Ｄ出发，D-E最小。点集合{A,F,B,C,D,E}，边集合{A-F,F-B,B-C,C-D,D-E} 此时，边数＝顶点数－１。所以结束，最小生成树构造完成。 代码部分，可参考`CMap.p`的`primTree`部分。 #### 克鲁斯卡尔最小生成树 首先，初始化一个二维数组，用于存放点。需要确保不构成回路，所以需要二维数组。接着初始化一个边集合，存放边，作用同普利姆算法的边集合。 第二步，构造一个集合，里面存放了所有的边。取出里面权值最小的边。 所以取出A-F，加入边集合，对应的点加入点集合。 点集合{{A},{F}}，边集合{A-F} 接下来继续取出权值最小的边B-F。（权值为２的有两条边，根据遍历规则先取出的是B-F） 此时，点Ｆ已经在二维数组中，所以将另一个点B，放入F集合中。 点集合{{A},{F,B}}，边集合{A-F,B-F} 继续D-E。点集合{{A},{F,B},{D},{E}}，边集合{A-F,B-F,D-E 继续B-C。此时B已经在点集合中的某个集合里了，所以将C放入对应的集合。点集合{{A},{F,B,C},{D},{E}},边集合{A-F,B-F,D-E,B-C} 继续D-F。此时D和Ｆ都在点集合中，但是位于不同位置。合并这两个集合。点集合{{A},{F,B,C,D},{E}},边集合{A-F,B-F,D-E,B-C,D-F} 此时最小生成树的边数＝顶点数－１。所以结束。同普利姆算法的终止条件。 代码部分，可参考`CMap.p`的`kruskalTree　`部分。 ### 最短路径问题 在一个图中，找出任意点到其他点的最短路径问题。这里主要介绍**迪杰斯特拉（Dijkstra）算法**和**弗洛伊德（Floyd）**算法。这里以下图为例子进行说明。  具体如何插入到数据结构的方法可以见`demo3.cpp`，这里不做介绍。值得一提的是**Dijkstra**的时间复杂度为$O(n^2)$,**Floyd**的时间复杂度为$o(n^3)$。但是前者比后者更难以实现。 #### 迪杰斯特拉（Dijkstra） 1. 构造一个点集合，初始时里面只有起始点 2. 构造一个数组，里面是从起始点到其他点（包括本身）的距离。（如果不存在，则这两点距离初始化为无穷大） 3. 从上面的数组中选取最小的点，放到点集合中。 4. 接下来以新放入的这个点为起始点，重新构造步骤2中的数组。比较两次的距离，比如A->C可能有两条路径A->C或者A->B->C，在此步骤中进行比较。选取较小的值为最短路径 5. 重复2-4步，直到所有点都在点集合中 以上图为例 1. 点集合中包含{A}，A->A=0。构造数组[A->B=6,A->C=3