画布 1
数据结构（Data Structure）
  线性表（Linear List）是由n（n≥0）个数据元素（结点）a[0]，a[1]，a[2]…，a[n-1]组成的有限序列。存在一个唯一的没有前驱的（头）数据元素；存在一个唯一的没有后继的（尾）数据元素；此外，每一个数据元素均有一个直接前驱和一个直接后继数据元素。
    队列（Queue）是先进先出（FIFO, First-In-First-Out）的线性表。队列只允许在队尾（tail）进行入队操作（enqueue），在对头（head）进行出队操作（dequeue）。
    堆栈（Stack）只能允许在链接串列或阵列的一端（称为栈顶：top）进行加入数据（push）和输出数据（pop）的运算。即后进先出（LIFO, Last In First Out）
    顺序表（Sequential List）是在计算机内存中以数组的形式保存的线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构。
    链表（Linked list）不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。
      单向链表（Singly linked list）：链表中最简单的一种是单向链表，它包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。
      双向链表（Doubly linked list）：每个节点有两个连接：一个指向前一个节点，（当此“连接”为第一个“连接”时，指向空值或者空列表）；而另一个指向下一个节点，（当此“连接”为最后一个“连接”时，指向空值或者空列表）
      循环链表（Circular Linked list）首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可实现。要转换一个循环链表，你开始于任意一个节点然后沿着列表的任一方向直到返回开始的节点。
    可用数组或链表实现
  散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。
    散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快定位。
      直接定址法：取关键字或关键字的某个线性函数值为散列地址。即 hash(k)=k或 hash(k)=a* k+b，其中 a,b为常数（这种散列函数叫做自身函数）
      数字分析法：假设关键字是以r为基的数，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。
      平方取中法：取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况，取其中的哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。
      折叠法：将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。
      随机数法
      除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 hash(k)=k mod p, p <= m。不仅可以对关键字直接取模，也可在折叠法、平方取中法等运算之后取模。对p的选择很重要，一般取素数或m，若p选择不好，容易产生冲突。
    处理冲突
      开放定址法
        线性探测(Linear Probing)
        平方探测(Quadratic Probing)
        伪随机探测
      单独链表法：将散列到同一个存储位置的所有元素保存在一个链表中。实现时，一种策略是散列表同一位置的所有冲突结果都是用栈存放的，新元素被插入到表的前端还是后端完全取决于怎样方便。
      双散列
      再散列： 即在上次散列计算发生冲突时，利用该次冲突的散列函数地址产生新的散列函数地址，直到冲突不再发生。这种方法不易产生“聚集”（Cluster），但增加了计算时间。
      建立一个公共溢出区
      查找效率
        散列函数是否均匀
        如何处理冲突
        载荷因子（也叫装填因子）：α = 填入表中的元素个数 / 散列表的长度
  树（tree）用来模拟具有树状结构性质的数据集合。它是由n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
    特性
      每个节点有零个或多个子节点
      没有父节点的节点称为根节点
      每一个非根节点有且只有一个父节点
      除了根节点外，每个子节点可以分为多个不相交的子树
    术语
      节点的度：一个节点含有的子树的个数称为该节点的度
      树的度：一棵树中，最大的节点的度称为树的度
      叶节点或终端节点：度为零的节点
      非终端节点或分支节点：度不为零的节点
      父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点
      子节点：一个节点含有的子树的根节点称为该节点的子节点；
      兄弟节点：具有相同父节点的节点互称为兄弟节点
      堂兄弟节点：父节点在同一层的节点互为堂兄弟
      节点的祖先：从根到该节点所经分支上的所有节点
      子孙：以某节点为根的子树中任一节点都称为该节点的子孙
      节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推
      深度：对于任意节点n,n的深度为从根到n的唯一路径长，根的深度为0
        从根到n
      高度：对于任意节点n,n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0
        从n到叶
      森林：由m（m>=0）棵互不相交的树的集合称为森林
      度
      节点间关系
      节点描述
    分类
      无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树
      有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树
        二叉树：每个节点最多含有两个子树的树称为二叉树
          分类
            完全二叉树：对于一颗二叉树，假设其深度为d（d>1）。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树；
              满二叉树：所有叶节点都在最底层的完全二叉树
            二叉查找树：若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；左、右子树也分别为二叉排序树；
              自平衡二叉查找树
                高度平衡树（AVL树）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树
                红黑树：一棵n个结点是红黑树始终保持了logn的高度，查找、插入、删除的时间复杂度最坏为O(log n)
                  C++ STL中的Set等使用红黑树
                  特征
                    1.节点是红色或黑色；
                    2.根节点是黑色；
                    3.每个叶节点（NIL节点，空节点）是黑色的；
                    4.每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)；
                    5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
                伸展树（Splay Tree）：每次查找之后对树进行调整，把被查找的条目搬移到树根。
            霍夫曼树：带权路径最短的二叉树称为霍夫曼树或最优二叉树
              用于数据压缩
            笛卡尔树：树的每个节点有两个值，一个为key，一个为value。光看key的话，笛卡尔树是一棵二叉搜索树，每个节点的左子树的key都比它小，右子树都比它大；光看value的话，笛卡尔树有点类似堆，根节点的value是最小（或者最大）的，每个节点的value都比它的子树要小（或者大）。
            二叉堆：任意节点小于（或大于）它的所有后裔，最小元（或最大元）在堆的根上（堆序性）。堆总是一棵完全树。即除了最底层，其他层的节点都被元素填满，且最底层尽可能地从左到右填入。
          存储
            顺序存储：如果某个节点的索引为i，（假设根节点的索引为0）则在它左子节点的索引会是2i+1，以及右子节点会是2i+2；而它的父节点（如果有）索引则为 (i-1)/2向下取整。
            二叉链表存储：两个指针域指向两个子节点
            三叉链表存储：改进于二叉链表，增加父节点的指引
          遍历
            先序DLR
            中序LDR
            后序LRD
            广度优先遍历：二叉树的广度优先遍历又称按层次遍历。算法借助队列实现。
            L、D、R分别表示遍历左子树、访问根结点和遍历右子树
        B树：是一种自平衡的非二叉的查找树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。
          一棵m阶的B树的特征
            1.根结点至少有两个子女。
            2.每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m
            3.每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m
            4.所有的叶子结点都位于同一层。
            5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。
          简单说一种为了减少磁盘IO操作尽量变得矮胖的树，多用于文件系统和数据库系统。
        B+树
          特征
            1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
            2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
            3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。
          优势
            1.单一节点存储更多的元素，使得查询的IO次数更少。
            2.所有查询都要查找到叶子节点，查询性能稳定。
            3.所有叶子节点形成有序链表，便于范围查询。
        字典树（Trie）：用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。
  图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
    分类
      有向图，点对有序
        有向无圈图（DAG）
          拓扑排序：如果存在一条从Vi到Vj的路径，那么在排序中Vj在Vi的后面
            简单算法：先找出任意一个没有入边的顶点。然后我们显示出该顶点，并把该顶点和它的边一并删除。然后对图的其余部分应用同样的方法。
        强连通：连通的有向图为强连通
        弱连通：去掉方向的基础图连通为弱连通
      无向图，点对无序
        连通的：每一个顶点到每个其他顶点都有路径
          最小生成树：当图连通时，链接图中所有顶点的边所构成的树，且其总价值最低
            用最少的电线给房子安装电路就是在解决最小生成树问题
            Prime算法：每一步都把一个节点当做根并往上加边，这样就把相关联的顶点加到增长中的树上。
            Kruskal算法：贪婪的按照最小的权选择边，并且当所选的边不产生圈时就把它作为取定的边。
    构成
      点
      点对（边，或弧）
        边可以带权（weight）或值（cost）
      路径是一个顶点序列
        简单路径，其上所有顶点都是互异的，但第一个顶点和最后一个顶点可能相同
        环(loop)：如果图包含一条从一个顶点到它自身的边(v,v)，那么路径(v,v)有时候也叫做一个环
        圈（circle）w1=wn 且长度至少为1的路径
    表示
      邻接矩阵：使用二维数组表示，对于一条边(u,v)，置A[u][v] = 1或权值
      邻接表：对每一个顶点，我们使用一个表存放所有邻接的顶点
      十字链表
      邻接多重表
    最短路径
      无权最短路径
      Dijkstra算法