跳表基于链表 提取节点，建立多级索引 跳表会否浪费内存 实际的软件开发中，原始链表中存储的有可能是很大的对象，而索引结点只需要存储关键值和几个指针，并不需要存储对象，所以当对象比索引结点大很多时，那索引占用的额外空间就可以忽略了。 高效的动态插入和删除 跳表支持查找，及高效的动态的插入、删除操作，时间复杂度都是 O(logn) 索引动态更新 作为一种动态数据结构，需要某种手段来维护索引与原始链表大小之间的平衡...
本文以MySQL数据库为研究对象，讨论与数据库索引相关的一些话题。特别需要说明的是，MySQL支持诸多存储引擎，而各种存储引擎对索引的支持也各不相同，因此MySQL数据库支持多种索引类型，如BTree索引，哈希索引，全文索引等等。为了避免混乱，本文将只关注于BTree索引，因为这是平常使用MySQL时主要打交道的索引，至于哈希索引和全文索引本文暂不讨论。文章主要内容分为三个部分。 第一部分主要从数据结构及算法理论层面讨论MySQL数...
摘要 本文以MySQL数据库为研究对象，讨论与数据库索引相关的一些话题。特别需要说明的是，MySQL支持诸多存储引擎，而各种存储引擎对索引的支持也各不相同，因此MySQL数据库支持多种索引类型，如BTree索引，哈希索引，全文索引等等。为了避免混乱，本文将只关注于BTree索引，因为这是平常使用MySQL时主要打交道的索引，至于哈希索引和全文索引本文暂不讨论。 文章主要内容分为三个部分。 第一部分主要从数据结构及算法理论层面讨论M...
原创 底层软件架构 2019-07-12 22:40:12 Linux内核(源代码的链接在github) 1.链表、双向链表、无锁链表。 2.B+ 树，这是一些你无法在教科书上找到的说明。一个相对简单的B+树的实现。我把它作为一个学习练习来帮助理解B+树是如何工作的。这同样也被证明是有用的。 ... 一个在教科书中并不常见的技巧。最小的值在右侧而不是在左侧。所有在一个节点里用到的槽都在左侧，所有没有用到的槽包含了空值(NUL)。大多数操作只简单地遍历所有...
知乎链接：https://zhuanlan.zhihu.com/p/58087261 Linux内核代码中广泛使用了数据结构和算法，其中最常用的两个是链表和红黑树。 链表 Linux内核代码大量使用了链表这种数据结构。链表是在解决数组不能动态扩展这个缺陷而产生的一种数据结构。链表所包含的元素可以动态创建并插入和删除。链表的每个元素都是离散存放的，因此不需要占用连续的内存。链表通常由若干节点组成，每个节点的结构都是一样的，由有效数据区和指针区两部分...
一. 基本介绍 选择式排序也属于内部排序法， 是从欲排序的数据中， 按指定的规则选出某一元素， 再依规定交换位置后达到 排序的目的。 二. 思路介绍三. 代码实现 public class SelectSort {public static void main(String[] args) {int arr[] = {3, 9, -1, 0, 10};selectSort(arr);System.out.println(Arrays.toString(arr));}private static void selectSort(int[] arr) {for (int i = 0; i < arr.length; i++) {int minIndex = ...
目录 二叉树先，中，后序遍历【1710真题】 计算二叉树的高度 P106 【1704真题】 以二叉链表作存储的结构，试编写求二叉树叶子结点个数的算法：P225 【1904真题】【1810真题】【1404真题】 设计算法求二叉树的结点的个数 设计算法按先序次序打印二叉树T中叶子结点的值 树的存储结构采用孩子兄弟链表，请编写树的按层次遍历算法二叉树先，中，后序遍历【1710真题】 void preorder (BinTree bt) {if(bt!=NULL){visit(bt); ...
我的公众号是【CodeAllen】，程序员技术交流①群：736386324,转载请注明出处上一篇说的临接矩阵是不错的图存储结构，但是对于边数相对顶点较少的图，这种结构是存在对存储空间极大浪费的 因此可以考虑另外一种存储结构：比如把数组和链表结合一起来存储 临接表无向图的处理方法：1.图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便 2.图中每个顶点Vi的所有邻接点构成一...
4.29 数据结构 二叉树 手动输入节点值，二叉树的前序、中序、后序遍历及销毁 并计算二叉树的节点数 运行结果截图: 代码： /*许沐 20760204 4.28 二叉树 */#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<string.h> #include<iostream> #include<stdlib.h> using namespace std; #define MAXSIZE 100typedef int SqBiTree[MAXSIZE]; SqBiTree bt;typedef struct BTNode {int data;struct BTNode* lChild;struct BT...
本篇文章主要是用代码记录二叉树的一些常用方法，如建立BST、前中后序遍历二叉树等，持续补充，方便自己之后复习。package dataStruct.tree;import java.util.Random;class BinaryTree{//节点类class TreeNode{//成员变量：一个树节点you数据域和两个儿子指针组成int val;TreeNode left;TreeNode right;//节点的构造函数TreeNode(int val){this(val,null,null);}TreeNode(int val,TreeNode left,TreeNode right){this.val = val;th...
运行结果：源文件： #include "邻接表宽度优先遍历的queue.h" //邻接表的初始化 Status Init(LGraph* lg, int nSize) {int i;lg->numofDot = nSize;lg->numofEdge = 0;lg->a = (ENode**)malloc(nSize * sizeof(ENode*));if (!lg->a){return ERROR;}else{for (i = 0; i < lg->numofDot; i++)lg->a[i] = NULL;return OK;} }//邻接表的撤销 void Destroy(LGraph* lg) {int i;ENode* p, * q;for (i = 0; i < lg->numofDot; i++){p = lg...
## 二叉树 说明：这是个人笔记，欢迎大家指正，互相学习。感谢大家！ 节点的度：一个节点含有的子树个数称为该节点的度；叶节点：度为0的节点称为叶节点根节点：没有父节点的节点双亲节点或者父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点孩子节点或子节点：一个节点含有的子节点成为这个节点的孩子节点兄弟节点：具有相同父节点的节点之间互为兄弟节点树的度：一棵树中，最大的节点度称为树的度树的高度和深度...
1.先序遍历 遍历过程如下：访问根节点（可以是print或其他的操作） 先序遍历其左子树 先序遍历其右子树很显然这里可以利用递归程序进行实现，大致的代码如下def pre_order_traversal(root):if root:print(root.val)pre_order_traversal(root.left)pre_order_traversal(root.right) 图 先序遍历示意图 2.中序遍历 遍历过程：中序遍历其左子树 访问根结点 中序遍历其右子树 def in_order_traversal(root):if root:in_order_tr...
1.二叉树的定义 二叉树T：一个又穷的结点集合。 这个结点集合可以为空，若不为空则则它是由根节点及称为其左子树TL和右子树TR的两个不相交的二叉树组成。那么也就是说二叉树具有五种基本形态，如下图所示。 图 二叉树的五种基本形态 二叉树与一般的度为2的树是有区别的：二叉树的子树有左右之分。 2.几种特殊的二叉树 ①斜二叉树(skewed binary tree) 相当于链表，已经是一个线性结构了。 ②完美二叉树(perfect binary...
1.堆是一颗完全二叉树。 2.建立大根堆进行排序步骤 1）从第一个非叶子点开始堆化，一直到根节点 2）每次将根节点（最大值）放到最后面 重新堆化/*** @Description:堆排* @Author: cckong* @Date:*/ public class heapsort {public static void main(String[] args) {int[] arr = {5, 3, 2, 6, 7, 8, 9, 10, 1, 12, 4, 21};int len=arr.length;//从第一个非叶子节点开始堆化 一直到根节点for(int i=len/2-1;i>=0;i--){heapif...