线性表
线性表（linear list）是 n 个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况...
博客
17 篇数据结构
跳表
skiplist 是一种随机化的数据结构，基于并联的链表，实现简单，插入、删除、查找的复杂度均为 O(logN)（大多数情况下，因为是实现上是概率问题），因为其性能匹敌红黑树且实现较为简单，因此在很多著名项目都用 skiplist 来代替红黑树，例如 LevelDB、RocksDB、Redis 中的有序集合 zset 的底层存储结构就是用的 skiplist。 目前常用的 keyva...
红黑树
我们这里只实现红黑树的插入和删除，了解他们的底层即可，而后面我们在介绍 map 以及 set 的模拟实现的时候，我们就会进一步将红黑树进行改造！ 红黑树是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是 Red 或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。（接近平衡不代表是平衡的，...
Ⅰ. 最小生成树
连通图中的每一棵生成树，都是原图的一个极大无环子图，即：从其中删去任何一条边，生成树就不再连通；反之，在其中引入任何一条新边，都会形成一条回路。 若连通图由 n 个顶点组成，则其生成树必含 n 个顶点和 n1 条边。因此构造最小生成树的准则有三条： 1. 只能使用图中的边来构造最小生成树 2. 只能使用恰好 n1 条边来连接图中的 n 个顶点 3. 选用的 n1 条边不能构成回路 构造最小生成...
Ⅰ. 排序的概念及其运用
排序： 所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。 稳定性： 若经过排序，这些记录的序列的相对次序保持不变，即在原序列中，r[i] r[j] ，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。 内部排序： 数据元素全部放在内存中的排序。 外部排序： 数据元素太多不...
Ⅰ. 并查集原理
在一些应用问题中，需要将 n 个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集合，然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为 并查集 (unionfindset)。 比如：某公司今年校招全国总共招生10人，西安招4人，成都招3人，武汉招3人，10个人来自不同的学校，起先互不相识...
图的最短路径
最短路径问题：从在带权有向图 G 中的某一顶点出发，找出一条通往另一顶点的最短路径，最短也就是沿路径各边的权值总和达到最小。 单源最短路径问题：给定一个图 G(V，E)，求源结点 s∈V 到图中每个结点 v∈V 的最短路径。Dijkstra 算法就适用于解决带权重的有向图上的单源最短路径问题，同时算法要求图中所有边的权重非负。一般在求解最短路径的时候都是已知一个起点和一个终点，所以使用 ...
Ⅰ. 图的基本概念
图是由顶点集合及顶点间的关系组成的一种数据结构： G (V, E)，其中： 顶点集合 V {x x属于某个数据对象集 } 是有穷非空集合； E { (x,y) x,y属于V } 或者 E { <x, y x,y属于V && Path(x, y) } 是顶点间关系的有穷集合，也叫做边的集合。 (x, y) 表示 x 到 y 的一条双向通路，即 (x, y) 是无方向...
Ⅰ. unordered 系列关联式容器
在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到 $log2 n$，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered 系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，本文中只对unor...
哈夫曼树的构造
这里就不仔细讲哈夫曼树的原理了，资料很多，网上和书籍都是有的，主要讲一下如何实现构建哈夫曼树和编码译码的操作！ 做这个实验也是花了半天的功夫，等到做完发现其实最难的不是实现，而是难在你要选用什么数据结构去搭建这个哈夫曼树以及编码译码，这个流程下来这个选用的数据结构是很重要的，决定着你的算法是如何的！ 我用的是 C++ 实现的，数据结构方面选用了 string、vect...