恰同学少年的博客

原创 数据结构与算法C++之更多和最短路径相关的问题

原创 数据结构与算法C++之单源最短路径算法 Bellman-Ford

实现程序如下#include <iostream>#include "SparseGraph.h"#include "ReadGraph.h"#include "BellmanFord.h"using namespace std;int main() { string filename = "testG2.txt"; //string fi...

原创 数据结构与算法C++之单源最短路径算法 dijkstra

单源最短路径算法 dijkstra（1）从起始节点0开始，与0连接的节点有1,2,3，将它们的权重存入右表中，可以看出最小的权重是边0-2，权重为2，那么在图中不能有负权边的前提下，0-2的最短路径就是边0-2（2）接下来，以节点2为出发点，考察与2连接的节点1,4,3，边2-1的权重为1，那么0-2-1的耗费为3，比上图表中0-1的耗费5要小，所以将1位置的5替换为3；边2-4权...

原创 数据结构与算法C++之最小生成树问题总结

原创 数据结构与算法C++之最小生成树问题 Kruskal

下面是 Kruskal 算法实现最小生成树（1）下面是有权无向图，初始边的连接如下图（2）对上图的权重按照从小到大排序，如下图（3）按照权重从小到大寻找边，只要不形成环该权重边就符合要求，如下图前5个标为红色的都没有形成环，而边1-3会形成环，舍弃，1-5也会形成环，舍弃，4-5不会形成环，保留，边2-6不会形成环，保留，下图标红的形成最小生成树使用堆实现权重排序#include...

原创 数据结构与算法C++之最小生成树问题 Prim

上篇博客中使用Lazy Prim实现的最小生成树算法复杂度为 O(ElogE)O(ElogE)O(ElogE)下面使用Prim实现最小生成树，算法复杂度为 O(ElogV)O(ElogV)O(ElogV)使用最小索引堆实现Prim（1）将与节点0相连接的节点的权值放入数组中，节点7的权重最小，那么边0-7属于最小生成树（2）下面开始考察与节点7相连接的节点，对于节点1来说，数组中没有，...

原创 数据结构与算法C++之最小生成树问题

最小生成树算法 Lazy Prim

原创 数据结构与算法C++之带权图

带权图 Weighted Graph程序实现如下#include <iostream>#include <iomanip>#include "DenseGraph.h"#include "SparseGraph.h"#include "ReadGraph.h"using namespace std;int main() { string ...

原创 数据结构与算法C++之图的广度优先遍历

原创 数据结构与算法C++之图的获得两点之间的一条路径

使用深度优先遍历即可获得两点间的一条路径定义 Path.h 实现获取路径 #include <stack> #include <iostream> #include <cassert> using namespace std;template <typename Graph>class Path{private: Gr...

原创 数据结构与算法C++之图的遍历（深度优先遍历）

图的遍历：深度优先遍历（1）首先遍历节点0，与0连接的节点有1,2,5,6，那么先遍历节点1，下面再看与节点1相连的是节点0，节点0已经遍历过了，那么继续遍历节点2，与2连接的节点是0，节点0已经遍历过了，那么开始遍历节点5，（2）与5连接的节点有0,3,4，节点0已经遍历过了，那么开始遍历节点3，3没有被遍历过，记录下3，与节点3连接的节点是4和5，首先4没有被遍历过，记录下4，继续查看...

原创 数据结构与算法C++之txt中读入图

建立一个ReadGraph.h文件读入txt中存储的图#include <iostream>#include <ctime>#include <cstdlib>#include "SparseGraph.h"#include "DenseGraph.h"#include "ReadGraph.h"using namespace std;int..

原创 数据结构与算法C++之图的遍历

图的遍历：遍历邻边下面是程序的实现#include <iostream>#include <ctime>#include <cstdlib>#include "SparseGraph.h"#include "DenseGraph.h"using namespace std;int main(){ int N = 20; //顶点个...

原创 数据结构与算法C++之图的表示

图的表示：邻接矩阵、

原创 数据结构与算法C++之图论

下面这三个连通的，可以是三个图，也可以是一个图

原创 数据结构与算法C++之并查集 路径压缩

前几篇博客都是对并查集的union进行优化，其实并查集的find也可以优化，之前进行find操作时，如下图，查找4的根节点需要4->3->2->1->0，当根节点数目特别多时，这样是很耗时的，可以通过路径压缩来优化当寻找4的根节点时，首先发现4的父节点3不是根节点，那么继续找3的父节点2是不是根节点这里根据路径压缩，当发现4的父节点3不是根节点时，不再查找3，此时...

原创 数据结构与算法C++之并查集 基于rank的优化

上一篇博客中，选择根节点数目少的节点指向根节点数目多的节点，这种策略一般是没有问题的，但是如果是下图的情况，要合并4和2根据根节点数目少的指向根节点数目多的，4的根节点数目为3，2的根节点数目为6，那么需要将4的根节点8指向2的根节点7，但是这样树的高度变为4而如果将2的根节点7指向4的根节点8，那么这样树的高度变为3，因此需要根据树的高度来判断谁指向谁根据树的高度判断指向，称为基于r...

原创 数据结构与算法C++之并查集的优化

上篇中实现的union操作中合并两个元素是无序的，一般将第一个元素指向第二个元素，如下图中，是将4的根节点指向9，但是这样造成树总的高度为4，如果将9指向4的话，树的高度为3，树的高度减少后会很节省后面的查找花费的时间，因此需要先判断一下两个节点的根节点的数目，选择根节点数目少的节点指向根节点数目多的节点下面是程序实现#include <iostream>#include &l...

原创 数据结构与算法C++之并查集2

上篇博客实现的并查集是使用quick find实现的，这其中，尽管实现find比较快，但是实现 并union 却比较慢，现在看一下另外一种实现思路如果两个元素相连接，就把一个元素指向另一个元素，如下图，如果3和2连接，就将3指向2，成2为3的父节点，2只指向自己，如果父节点5也要指向节点2，就把5指向2，那么5下面的6和7的父节点都变为了2...

原创 数据结构与算法C++之并查集

并查集 Union Find可以解决连接问题和路径问题下图中使用id表示数组，第一行表示其索引，第二行表示元素值，为0的元素表示是互相连接在一起的，同样为1的元素表示互相连接在一起的下面是测试一个并查集 Union 操作的计算复杂度#include <iostream>#include <cassert>#include "UnionFindTestHel...

原创 数据结构与算法C++之二分搜索树的局限性

为此，有人提出了平衡二叉树，其中一个很著名的平衡二叉树是红黑树

原创 数据结构与算法C++之二分搜索树的顺序性

二分搜索树可以查找最小值 minimum 和最大值 maximum可以找到一个元素的前驱（successor），后继（predecessor），floor，和 ceil当该元素在树中时，前驱后继和floor，ceil是相同的当该元素不在树中时，前驱和后继就不再起作用了，而floor和ceil还是可以使用的...

原创 数据结构与算法C++之二分搜索树的删除节点，删除任意节点

上篇博客介绍了怎样删除二分搜索树的最大值和最小值节点，下面介绍怎样删除树的任意一个节点上篇删除最大值节点的操作，其实删除的节点要么没有左右子节点，要么只可能有左节点，同样，删除最小值节点的操作，其实删除的节点要么没有左右子节点，要么只可能有右节点（1）删除只有左节点的节点，如删除节点58，只需要将58删除掉，然后将其左节点50替换其位置即可（2）删除只有右节点的节点，如删除节点58，只需...

原创 数据结构与算法C++之二分搜索树的删除最大值和最小值节点

前两篇介绍了二分搜索树以及二分搜索树的遍历，下面介绍二分搜索树删除最大值和最小值节点（1）根据二叉树的定义，只要从根节点的左节点一直寻找，直到某一个左节点不再有左节点，那么该节点就是最小值（2）只要从根节点的右节点一直寻找，直到某一个右节点不再有右节点，那么该节点就是最大值删除二分搜索树的最小值（1）如果删除的节点没有右子节点，那么直接删除掉就可以，如下图的最小节点13（2）如果删除...

原创 数据结构与算法C++之二分搜索树的遍历

二分搜索树的遍历分为三种，前序遍历，中序遍历，后序遍历前面介绍的前中后序遍历都是深度优先遍历下面介绍一种广度优先遍历，二叉树中称为层序遍历所谓层序遍历就是一层层遍历树的元素，下图中遍历顺序为28->16->30->13->22->29->42（1）具体实现步骤为，首先将根节点28推入队列中，front表示队首（2）然后进行一次循环，只要队列中...

原创 数据结构与算法C++之二分搜索树

二分搜索树的优势（1）查找表的实现-字典数据结构（2）算法复杂度比普通数组，顺序数组低总结如下下面是二分搜索树（是棵二叉树）的定义插入新节点 insert（1）插入新元素60时，60比41大，60继续与41的右节点58比，60比58大，那么继续将60与58的右节点比，58没有右节点，那么就将60插入58的右节点位置处（2）插入28，首先28比41小，那么28与41的左节点...

原创 数据结构与算法C++之二分查找法

二叉搜索树一个很广泛的应用是查找问题解决查找问题的一个基本解法是二分查找法 Binary Search对于有序数列，才能使用二分查找法如上图所示，首先找到数列的中间元素，如果等于要查找的元素，查找就停止，如果不等于，判断是大于中间元素还是小于中间元素，大于的话就对右边数列继续切分查找，如果小于就对左边数列继续切分查找，直到中间位置的元素等于查找元素位置下面是程序实现#include...

原创 数据结构与算法C++之索引堆

前几篇博客介绍了数据结构堆以及堆排序，但是前面用到的堆有以下不足（1）在构建堆时，需要首先将数组元素放入堆中，然后通过交换操作（ShiftDown）将合适的元素放入合适的位置，以满足堆的性质，当数组元素是整数之类比较简单的数据类型时，没什么问题，但是当数组元素特别复杂时，如每一个元素都是一个含有十万字文章的字符串时，交换操作就会消耗很大的资源，但是这种也可以通过计算机强大的软硬件能力来解决。（...

原创 数据结构与算法C++之排序算法总结

原创 数据结构与算法C++之原地堆排序

上一篇博客中的堆排序需要先将数组中的元素放入堆中，然后再从堆中取出来，整个操作开辟了n个额外元素的堆，其实也可以将数组看做是一个堆，如下图（1）最大堆的第一个元素 vvv 是最大值，根据排序需要将最大元素放入数组中的最后一个位置 www 处，因此交换 vvv 和 www 的位置（2）此时已经将 vvv 放到排好序的位置，但是左边的橙色部分就不是个最大堆了（3）需要将其恢复为最大堆，使用上篇...

原创 数据结构与算法C++之堆排序

首先需要介绍一下一个新的数据结构：堆堆使用了优先队列普通队列：先进先出，后进后出优先队列：出队顺序与入队顺序无关，与优先级有关，一般取出优先级最高的元素，堆入队出队的算法复杂度都为O(nlogn)最常使用的是二叉堆（Binary Heap）如上图所示，62称为41和30的父节点，41称为左节点，30称为右节点，以此类推，41又是28和16的父节点，等等，二叉堆有如下性质：父节点大于...

原创 python seaborn 基础操作

Seaborn其实是在matplotlib的基础上进行了更高级的API封装，从而使得作图更加容易，在大多数情况下使用seaborn就能做出很具有吸引力的图，而使用matplotlib就能制作具有更多特色的图。应该把Seaborn视为matplotlib的补充，而不是替代物。seaborn 有五种风格，分别为"darkgrid", “whitegrid”, “dark”, “white”, "ti...

原创 python plt 画图

使用csv数据文件在百度网盘import pandas as pdunrate = pd.read_csv('unrate.csv')# pd.to_datetime() 转换成日期格式，即由 1948/1/1 转换为 1948-01-01 unrate['DATE'] = pd.to_datetime(unrate['DATE']) print(unrate.head(12)) ...

原创 python pandas 基本操作

pandas 是基于 Numpy 构建的含有更高级数据结构和工具的数据分析包类似于 Numpy 的核心是 ndarray，pandas 也是围绕着 Series 和 DataFrame 两个核心数据结构展开的 。Series 和 DataFrame 分别对应于一维的序列和二维的表结构。pandas 约定俗成的导入方法如下：import pandas as pd读取csv文件，打印变量类型和...

原创 数据结构与算法C++之三路快速排序

前两篇博客介绍了快速排序算法以及对快速排序算法的两种改进，下面开始介绍三路快速排序算法，之所以称为三路快速排序算法，是因为其考虑了三个部分（如下图），分别为大于 vvv 的部分， 小于 vvv 的部分， 等于 vvv 的部分。如上图所示，随机选择一个元素 vvv 作为参考元素，并与最左边元素交换位置，交换后参考元素 vvv 的索引为 lll . 然后定义...

原创 数据结构与算法C++之快速排序（续）

上一篇博客数据结构与算法C++之快速排序介绍了快速排序算法。但是上面实现的快速排序有两个缺点：（一）对于近乎有序的数组，算法的计算复杂度由O(nlogn)退化到O(n2)（二）如果数组中存在大量重复的元素，那么算法的计算复杂度也会退化到O(n2)（一）对于近乎有序的数组，算法的计算复杂度由O(nlogn)退化到O(n2)使用上篇博客里的快速排序算法做测试，测试程序为int main()...

原创 数据结构与算法C++之快速排序

快速排序是一种比归并排序还要快的排序算法，具体原理如下图所示对上图所示的数组，首先随机选取一个参照元素，一般选取最左边的元素4为参照元素，然后将数组排序成以4为分界点，左边都是小于4的元素，右边都是大于4的元素，按照这种方式进行不断递归，就可实现整个数组的排序。上图显示的是程序的实现过程，首先指定最左边的元素 vvv 为参照元素，索引为 lll，小于元素 vvv的 最后一个元素的索引为 j...

原创 python numpy 基本操作

首先导入import模块import numpy as np创建list和matrixvector = np.array([5, 10, 15, 20]) # listmatrix = np.array([[5, 10, 15], [20, 25, 30], [35, 40, 45]]) # matrixprint vectorprint matrix#打印输出[ 5 10 15...

原创 数据结构与算法C++之归并排序（续）

上一篇博客中实现的是自上以下的归并排序，自上而下需要先不断将数组进行对半拆分（递归实现），然后再合并排序其实也可以自下而上实现归并排序，这样使用for循环就可以实现，省掉了递归的操作首先对数组的每一个元素进行两两归并（相邻的两个元素合并成一个有序数组），然后将合并好的两个元素的有序数组再进行合并，合并成包含四个元素的有序数组，然后在此基础上，再合并成包含八个有序数组的元素，以此类推程序实现为...

原创 数据结构与算法C++之归并排序

上两篇博客使用的选择排序和插入排序的算法复杂度都是O(n2)，这在数组元素比较多的时候和一些算法复杂度为O(nlogn)的快速排序算法相比，差距还是很明显的，如下图当有10万个元素的时候，快速排序算法比普通的选择排序算法要快了6000倍，本篇博客介绍的是快速排序算法中的归并排序归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略（分治法将问题分成一些小的问题然后递归求解，而治的...