Data Structures | 数据结构

  
Data Structures：
线性(Linear) （即常说的线性表）
          顺序表/数组（Array）
          链表（Linked List）
                    单向链表/单链表(Singly Linked List)
                              循环链表(Circular Linked List)
                    双向链表（Doubly Linked List）
          栈（Stack）
          队列（Queue）
非线性(Non-Linear)
          树（Tree）
                    二叉树
                              完全二叉树
                                        满二叉树
                                        堆（Heap）
                              霍夫曼树(Huffman Tree) 亦称最优二叉树
                              二叉查找树（Binary Search Tree） 亦称二叉排序树（Binary Sort Tree）
                                        自平衡二叉查找树(Self-balancing Binary Search Tree)（如红黑树(Red-black Tree)、AVL树）
                              平衡二叉树（Balanced Binary Tree）
          图（Graph）
          集合（Set）
          Table
          散列表（Hash Table）


可视化的数据结构和算法：
http://www.cs.usfca.edu/~galles/visualization/Algorithms.html
Algorithms, 4th Edition：
http://algs4.cs.princeton.edu/home/



重要点说明：
树：

引用

节点的度：结点所含子树的个数。  树的度是树内各节点的度的最大值

完全二叉树：

引用

若一棵二叉树至多只有最下面的两层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。

满二叉树：

引用

最后一层全为叶子节点，其他层上的所有结点都有两个子结点（度数都为2）的二叉树称为满二叉树。

霍夫曼树：

引用

树节点的权（值）：若为树中结点赋予一个有某种含义的数值，则这个数值称为该结点的权
结点的带权路径长度：从根结点到该结点之间的路径长度与该结点的权的乘积。
树的带权路径长度：所有叶子结点的带权路径长度之和，记为WPL。
WPL最小的二叉树称为霍夫曼树。

二叉查找树：

引用

或者是一棵空树，或者是具有下列性质的二叉树：① 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；② 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；③ 它的左、右子树也分别为二叉查找树。
按中序遍历二叉查找树得到的中序序列是一个递增有序序列。

平衡二叉树：

引用

或者是一棵空树，或者是具有下列性质的二叉树：① 左右两个子树的深度之差的绝对值<=1 ② 它的左、右子树也分别为平衡二叉树。
一般情况下在二叉查找树中查询指定结点时的查询复杂度是跟目标结点到树根的距离（即深度，或树的高度）有关，因此当结点的深度普遍较大时，查询的均摊复杂度会上升，为了更高效的查询，平衡树应运而生了。这里的“平衡”指所有叶子的深度趋于平衡，更广义的是指在树上所有可能查找的均摊复杂度偏低。

堆：

引用

对任一节点其值总是大于或等于（小于或等于）任何一个子节点的值的完全二叉树称为最大堆（最小堆）。

红黑树：

引用

是一种自平衡二叉查找树。红黑树确保从根节点到所有叶子节点的路径中，最长路径不大于最短路径的两倍，因而是接近平衡的。

散列表/哈希表（Hash Table）：
http://student.zjzk.cn/course_ware/data_structure/web/chazhao/chazhao9.4.3.2.htm    看动画演示！
定义：根据设定的哈希函数H(key)和处理冲突的方法将一组关键字映像到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表称为散列表/哈希表或散列桶(hash buckets)，这一映像过程称为哈希造表或散列，所得存储位置称为哈希地址或散列地址。
哈希函数的构造：方法有直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法等。好的哈希函数应该满足：简单和均匀。

引用

除留余数法：
取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址：
H(key)=key MOD p (p<=m)

冲突及解决：对不同的关键字可能得到同一哈希地址（函数值），即关键字K1≠K2，但H（K1）= H（K2），这种现象称为冲突。具有相同函数值的关键字对该哈希函数来说称做同义词。解决冲突的方法有Open addressing（开放定址法）、Separate chaining(中文俗称链地址法、拉链法)、再哈希法、Bucket Hashing（中文俗称桶哈希法或建立公共溢出区）等。

引用

Open addressing：
插入时当关键字经由哈希函数的散列映射过程出现与不同关键字的冲突时，使用某种探查(亦称探测)技术在散列表中形成一个探查(测)序列，沿此序列逐个单元地查找，直到碰到与当前关键字等值的关键字(此时的处理可以是放弃插入，也可以是替换原等值关键字)，或者碰到一个开放的哈希地址(即该哈希地址为空)，则将当前关键字存入该哈希地址。通用表达式为：
    Hi=( H(key) + di) MOD m  0<i≤m-1
    H(hey)：哈希函数  ；  m：哈希表表长  ；  di：增量序列
按照形成探查序列的方法不同(即di的不同)，又可将开放定址法细分为线性探查法(Linear probing)、二次探查法(Quadratic probing)、双散列探查法(Double hashing)、随机探查法等。
Linear probing：di = 1,2,3,..,m-1
Quadratic probing：di = 1^2,-1^2,2^2,-2^2,....,k^2,-k^2 （k<=m/2）
Separate chaining：
将所有关键字为同义词的记录存储在同一单链表中；哈希表长为m，设置一个由m个指针分量组成的一维数组 ST[m], 凡哈希地址为 i 的关键字都插入到头指针为 ST[i] 的单链表中。一般保证单链表是按关键字有序的，这样可以减少比较的次数，提高性能。

哈希表的查找：
在哈希表上进行查找的过程和哈希造表的过程基本一致。给定的关键字，根据造表时设定的哈希函数求得哈希地址，若表中此位置上没有记录，则查找不成功；否则比较关键字，若和给定关键字相等，则查找成功；否则根据造表时设定的处理冲突的方法找“下一地址”，直至哈希表中的某个位置为“空”或者表中所填记录的关键字等于给定关键字时为止。

引用

查找时，决定平均查找长度的一个很重要的因素是填充因子（Load factor）：
      填充因子 a = 表中填入的记录数/哈希表的长度
通过数学推导可以计算出，哈希表的平均查找长度是填充因子的函数，而与哈希表中的记录数 n 无任何关系。由此，不管 n 多大，我们总可以选择一个合适的填充因子以便将平均查找长度限定在一个范围内。