JSON标准及语法介绍

JSON 标准规范 Json 有两个标准规范:RFC8259 和 ECMA-404。这两个标准规范在核心语法上完全相同,区别在于: 发行机构不同 RFC8259 由 IETF(互联网工程任务组)发布,是互联网标准文档(Request for Comments)。它于2017年12月发布...

阅读更多

ABNF-扩展巴斯克范式

ABNF ABNF 是一种用于定义互联网规范的语法,它基于 BNF (Backus-Naur Form,巴克斯-瑙尔范式),被称作扩充巴克斯-瑙尔范式。RFC5234 中定义了 ABNF 及它的规则。 ABNF的规则定义 ABNF规则命名 ABNF 的名称就是一系列字符序列,它以字符开始,后接字符,数字或...

阅读更多

B树

B 树 当数据在磁盘中存储时,磁盘相对于内存读取是非常缓慢的,因此在读取磁盘上的数据时,要尽量减少磁盘IO。 磁盘上的数据是以页为单位存储的,每个磁盘页一般为 4 K。磁盘在某一页上读取数据时,读取 1B 的数据与读取 4K 的数据时间差不了太多,它的时间主要花费在了磁盘寻道与机械运动上。因此,我们需要一种数据...

阅读更多

AVL 树

AVL 树 当要构造二叉树的原有元素序列接近有序时,构造的二叉树会退化成一棵单支树,此二叉树的查找效率也接近于 O(n),这就失去了构造二叉树的意义(如图1)。为了解决这一问题,苏联科学家 Adelson-Velskii 和 Landis 发明了一种自平衡二叉树,即 AVL 树。 图1 AVL 树是一棵具...

阅读更多

抽象数据类型(ADT)-二叉搜索树

二叉搜索树 二叉搜索树是一种特殊的二叉树,对于树中的每个结点 X,它左子树上的每个结点的值都小于 X 的值,它右子树上的每个结点的值都大于 X 的值。 二叉搜索树的实现 二叉搜索树上的结点都是有序的,因此不同于普通二叉树,二叉搜索树可以按照元素的大小,向特定的分支去查找,因此二叉搜索树有自己的插入、删除、查...

阅读更多

二叉树的四种遍历方法

二叉树有四种遍历方式,先序遍历,中序遍历,后序遍历以及层次遍历。 先序遍历 二叉树的先序,中序,后序遍历表示访问二叉树中结点的先后顺序,先序表示先访问结点,中序表示中间访问结点,后序表示最后访问结点。 先序遍历二叉树的顺序: 访问根结点。 先序遍历左子树。 先序遍历右子树。 采用递归的方式...

阅读更多

抽象数据类型(ADT)-二叉树

二叉树定义 二叉树是一种特殊的树,对于树中的每一个结点,最多只有两个儿子的树称为二叉树。如图: 二叉树的实现 因为二叉树的每个结点只有两个儿子,因此可以把在每个结点中记录下儿子的指针,为了方便查找,还可以记录下每个结点的父结点指针。 数据结构定义: #define ELEMENT_TYPE int ...

阅读更多

抽象数据类型(ADT)-树

表、栈、队列都是线性数据结构,这次我们讲一个非线性数据结构 - 树。 树定义及相关概念 树可以用多种方式定义,用递归的方式定义是一种自然的方式。树是一些结点的集合,集合可以为空,若非空,则树由一个被称为根结点的 r 和零个或多个非空子树 T0, T1, ……, Tn 组成,这些子树的每一棵的根都由来自 r 的...

阅读更多