Estom的博客

队列1 简介概念 队列可以定义为有序列表。在一端执行插入操作rear，删除操作在另一端执行，称为front。 队列被称为先进先出列表。 应用 单个共享资源(如打印机，磁盘，CPU)的等待列表。 异步数据传输。管道，文件IO，套接字。 缓冲区. 操作系统中处理中断。 时间复杂度 时间复杂性 访问 搜索 插入 删除 平均情况 θ(n) θ(n) θ(1) θ(1) 最坏情况 θ(n) θ(n) θ(1) θ(1) 2 队列的操作基本操作 创建 遍历（显示第一个元素） 插入 删除 3 队列的实现队列的数组实现123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103#include<stdio.h> #in...

Hash 表的查找要点哈希表和哈希函数在记录的存储位置和它的关键字之间是建立一个确定的对应关系（映射函数），使每个关键字和一个存储位置能唯一对应。这个映射函数称为哈希函数，根据这个原则建立的表称为哈希表(Hash Table)，也叫散列表。 以上描述，如果通过数学形式来描述就是： 若查找关键字为 key，则其值存放在 f(key) 的存储位置上。由此，不需比较便可直接取得所查记录。 注：哈希查找与线性表查找和树表查找最大的区别在于，不用数值比较。 冲突若 key1 ≠ key2 ，而 f(key1) = f(key2)，这种情况称为冲突(Collision)。 根据哈希函数f(key)和处理冲突的方法将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这一映射过程称为构造哈希表。 构造哈希表这个场景就像汽车找停车位，如果车位被人占了，只能找空的地方停。 构造哈希表由以上内容可知，哈希查找本身其实不费吹灰之力，问题的关键在于如何构造哈希表和处理冲突。 常见的构造哈希表的方法有 5 种： 直接定址法说白了，就是小学时学...

二叉树 树>二叉树 1 二叉树简介概念 二叉树是一种特殊类型的通用树，它的每个节点最多可以有两个子节点。 二叉树通常被划分为三个不相交的子集。 节点的根 左二叉树 右二叉树 性质 二叉树第 i 层上的结点数目最多为 2i-1 (i≥1)。 深度为 k 的二叉树至多有 2k-1 个结点(k≥1)。 包含 n 个结点的二叉树的高度至少为 log2(n+1)。 在任意一棵二叉树中，若终端结点的个数为 n0，度为 2 的结点数为 n2，则 n0=n2+1。 2 二叉树分类严格二叉树 在严格二叉树中，每个非叶节点包含非空的左和右子树。 换句话说，每个非叶节点的等级将始终为2。具有n个叶子的严格二叉树将具有(2n-1)个节点。 完全二叉树 如果所有叶子都位于相同的水平d，则称二元树是完全二叉树。完全二叉树是二叉树，在0级和d级之间的每个级别包含正好$2^d$个节点。 具有深度d的完全二叉树中的节点总数是$2^{(d+1)}-1$，其中叶节点是$2^d$,非叶节点是$2^d-1$。 3 二叉树的操作——遍历搜索遍历搜索方法 深度优先搜索（DFS） 在这个策...

树 树 0 简介定义树是一种抽象数据类型或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由 n（n>0）个有限节点组成一个具有层次关系的集合。 树是一种递归数据结构，包含一个或多个数据节点的集合，其中一个节点被指定为树的根，而其余节点被称为根的子节点。 除根节点之外的节点被划分为非空集，其中每个节点将被称为子树。 树的节点要么保持它们之间的父子关系，要么它们是姐妹节点。 在通用树中，一个节点可以具有任意数量的子节点，但它只能有一个父节点。 特点 每个节点都只有有限个子节点或无子节点。 树有且仅有一个根节点。 根节点没有父节点；非根节点有且仅有一个父节点。 每个非根节点可以分为多个不相交的子树。 树里面没有环路。 术语 祖先节点： 节点的祖先是从根到该节点的路径上的任何前节点。根节点没有祖先节点。 父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 子节点：一个节点含有的子树的根节点称为该节点的子节点； 根节点： 根节点是树层次结构中的最顶层节点。 换句话说，根节点是没有任何父节点的节点. 叶子节点或终端节点：度为零的...

(注：切勿简单的认为一棵m阶的B树是m叉树，虽然存在四叉树，八叉树，KD树，及vp/R树/R*树/R+树/X树/M树/线段树/希尔伯特R树/优先R树等空间划分树，但与B树完全不等同)

B树1 简介概念 B 树又叫平衡多路查找树。一棵m阶的B树定义如下： B树中的每个节点最多包含m个子节点。最多包含m-1个键。 除根节点和叶节点外，B树中的每个节点至少包含[m/2]（向上取整）个子节点。 根节点要么是空、要么是独自的根、要么必须至少有2个子节点。 有k个子节点的节点必有k-1个键。每个键按顺序升序排序。 所有叶节点必须处于同一层（水平）。 4阶B树如下 应用 大规模数据存储中，二叉树节点存储的元素数量是有限的（如果元素数量非常多的话，查找就退化成节点内部的线性查找了），这样导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下 如何减少树的深度，一个基本的想法就是：采用多叉树结构（由于树节点元素数量是有限的，自然该节点的子树数量也就是有限的）。 多路查找树。根据平衡二叉树的启发，使用平衡多路查找树结构，也就是这篇文章所要阐述的第一个Btree。 分类 B树 B+树 B*树 2 操作基础操作 创建 遍历和搜索 插入 删除 分裂 合并 创建搜索 B树中搜索类似于二叉搜索树中的搜索 将数据项49与...

图1 简介概念 图可以定义为用于顶点和边的组合。 图可以看作是循环树，图中顶点(节点)维持它们之间的任何复杂关系，而不是简单的父子关系。 图G 可以定义为有序集G(V，E)，其中V(G)表示顶点集，E(G)表示用于连接这些顶点的边集。 图G(V，E)有5个顶点(A，B，C，D，E)和6个边((A，B)，(B，C)，(C，E)，(E，D)， (D，B)，(D，A))如下图所示。 术语 阶（Order） - 图 G 中点集 V 的大小称作图 G 的阶。 子图（Sub-Graph） - 当图 G’=(V’,E’)其中 V‘包含于 V，E’包含于 E，则 G’称作图 G=(V,E)的子图。每个图都是本身的子图。 生成子图（Spanning Sub-Graph） - 指满足条件 V(G’) = V(G)的 G 的子图 G’。 导出子图（Induced Subgraph） - 以图 G 的顶点集 V 的非空子集V1 为顶点集，以两端点均在 V1 中的全体边为边集的 G 的子图，称为 V1 导出的导出子图；以图 G 的边集 E 的非空子集 E1 为边集，以 E...

跳表跳表的基本概念 经典实现：Redis 的 Sorted Set、JDK 的 ConcurrentSkipListMap 和 ConcurrentSkipListSet 都是基于跳表实现。 只需要对链表稍加改造，就可以支持类似“二分”的查找算法。我们把改造之后的数据结构叫作跳表（Skip list）。 跳表是一种各方面性能都比较优秀的动态数据结构，可以支持快速的插入、删除、查找操作，写起来也不复杂，甚至可以替代红黑树（Red-black tree）。 在一个单链表中查询某个数据的时间复杂度是 O(n)。 在一个具有多级索引的跳表中，第一级索引的结点个数大约就是 n/2，第二级索引的结点个数大约就是 n/4，第三级索引的结点个数大约就是 n/8，依次类推，也就是说，第 k 级索引的结点个数是第 k-1 级索引的结点个数的 1/2，那第 k 级索引结点的个数就是 $n/(2^k)$ 跳表的原理跳表的结构 跳表的特点，可以概括如下。根据以下原则构建跳表。 跳表是多层（level）链表结构；跳表中的每一层都是一个有序链表，并且按照...

算法代码模板 算法代码模板即算法的常见套路。熟练记忆，活学活用。 递归12345678910111213141516public void recursion(int level, int param1, int param2, ...) { // 递归终止条件 if (level > MAX_LEVEL) { // print return; } // 当前处理逻辑 processData(level, param1, param2, ...); // 递归 recursion(level + 1, param1, param2, ...); // 如有必要，还原状态 reverseState(level, data);} DFS12345678910Set<Node> visited = new HashSet<>();public void dfs(Node node, Set<Node> visited) ...

主要是利用位运算解决一些巧妙的问题。 1 基础位运算基础 符号 说明 特性 & 按位与 只要有0，返回0 | 按位或 只要有1，返回1 ^ 按位异或 相同返回0。不同返回1 ~ 按位取反 全部反转。不重复的数字 >> 右移 << 左移 负数在计算机中使用补码表示，主要目标就是实现了最小值到最大值之间，位运算的连续性。 在字面数字运算中，-2 加1为-1，-1 加1为0，0+1为1。是连续计算的。在二级制补码计算中。也满足上述的计算规则。1111表示-1，加一通过溢出一位，变为0000，成为0. 实际上-1是按位绝对值最大的数，即1111。 特殊性质 操作 性质 n & (n - 1) n中的最后一个1变成0。 n & (~n + 1) n&(n^(n-1)) lowbit()运算，n中最后一个1保留。 (~n) + 1== -n 计算机中补码表示的-n。位运算取反 n/2 等价于 右移一位 n >> 1 n*2 等价...