数据结构 - DEVMAX

【数据结构】基本术语与概念

由若干数据项组成。包括数据元素的表示和关系的表示。一个含抽象数据类型的软件模块应包含三部分：定义、表示、实现。抽象数据类型有三种：原子类型：原子类型的变量的值是不可分解的固定聚合类型：值由确定数目的成分按某种结构组成可变聚合类型：值的成分的数目不确定算法：对特定问题求解步骤的一种描述。

【数据结构】：AVL树

左单旋:右单旋:左右双旋:右左双旋:注意：上图中，我们并不能确定插入的是L节点或是R节点，所以需要分情况讨论其平衡因子的变化。

陈越《数据结构》第四讲树中

4.1二叉搜索树4.1.1定义与抽象数据类型的基本操作1.定义：一棵二叉树，可以为空；如果不为空，满足以下性质：1.非空左子树的所有键值小于其根结点的键值。

【数据结构】线性结构——判空

如何判断栈和队列是否为空？只需判断他们的指针位置。这将是数据结构总结篇幅最短的一篇博客…）顺序存储（一）栈（二）队列链式存储（一）栈（二）队列小结写这篇博客的目的，是让大家知道数据结构的运算代码没想象中的难…

【数据结构】线性结构——初始化

初始化，通过指把变量赋为初始值，把某对象设为默认状态。对线性结构的初始化，无论是顺序存储还是线性存储，都是指将线性结构的某种具体表示初始设为空。顺序存储由于顺序结构自身的特性，因此初始化只需将各指针位置设置为0。（一）栈（二）队列小结通过对比总结，我们可以发现，线性结构的定义与运算的代码很有规律，只要我们能正确画出示意图，代码自然可以写出来。

以下为treap的基本操作，各种在这上面扩展出的其他的操作这里就不细讲了Build我们可以发现一棵treap同时也是一棵迪笛卡尔树，那么建树就可以O解决了，用一个栈即可，Splittreap当然离不开Split操作啦，这个点操作的作用是把treap两棵treap，一半为前si个，另一半就是剩下的，具体的操作是：判断断开的位置是在左子树还是右子树，再递归求解，Merge合并就简单了，直接把较大的那个放到这个位置即可

【数据结构】：二叉搜索树

二叉搜索树，也称有序二叉树,排序二叉树，是指一棵空树或者具有下列性质的二叉树：若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；任意节点的左、右子树也分别为二叉查找树。如图所示就是一棵二叉搜索树：中序遍历结果为：0123456789需要注意的是：二叉搜索树在进行删除和插入操作后都需要再次进行调整，新得到的树也应该是二叉搜索树。

【数据结构】链式存储——定义

实例1.线性表2.栈3.队列异同点（一）同：通过上面实例的代码，我们可以发现，线性表链式存储的定义可分为两部分：结构数据结构的类型名（二）异：链式存储和顺序存储有很多类似的地方，这里就不再细说，请参见顺序存储——定义。在这里，小编想要强调的是，为什么单链表和链栈的结构是一部分，二链队列的结构是两部分？

【数据结构】顺序存储——定义

通过以上三种数据结构顺序存储的示意图，我们不难发现，代码中的不同之处正是图的不同之处，线性表强调实际长度，栈强调栈顶位置，队列强调首指针和尾指针。代码中另一个不同点体现在数据结构的类型名，顺序的英文为“sequence”，因此类型名以“seq”开始，紧接，表是“list”，栈是“stack”，队列是“queue”。小结-代码的学习要与图进行结合-学习过程中我们需要将类似的知识点进行归纳总结，对比它们的相同点和不同点-最终的结果就是抽象

【数据结构】4.串

6.字符在串中的序号称为该字符在串中的位置，子串在串中的位置由它的第一个字符位置表示一、定长顺序存储二、堆动态分配存储三、串的块链存储一、常用的匹配算法二、KMP的模式匹配算法1.上面的算法一旦在比较出现不匹配的时候，就回到模式串的起始位置重新进行比较。