数据结构复习

一、线性表

线性表的特点：
（1）只有唯一一个首元素和末元素
（2）只有唯一一个前驱和后继
实现方式：顺序表示和链式表示

顺序表示：使用一组地址连续的存储单元依次存储线性表的元素
数组
特点：查找快，增删慢
时间复杂度：
查找：O(1)
增删：O(n)

链式表示：可以用任意的存储单元来存储数据，每个元素需要存储本身的信息外还要存储一个指示其后继的信息
链表
特点：查找慢，增删快
时间复杂度：
查找：O(n)
增删：O(1)

二、栈和队列

栈：先进后出
队列：先进先出

三、树和二叉树

树：结点拥有的子树称为结点的度，度为0的结点称为叶子，度不为0的结点称为分支。结点子树的根被称为结点的孩子，该结点被称为双亲。树中结点的最大层次被称为树的深度。

二叉树：树的每个结点至多只有两个子树

二叉树的性质：
（1）第i层有2^(i-1)个结点
（2）深度为k的二叉树至多有2^k-1个结点
（3）终端结点数=度为2的结点数+1

遍历方式：
前序遍历：中->左->右
中序遍历：左->中->右
后序遍历：左->右->中

示例：

最优二叉树(霍夫曼树）
从n个带权结点中构造出的带权路径最短的树被称为霍夫曼树

查找

折半查找
时间复杂度：O(log2n)

动态查找表
二叉排序树：左子树的所有结点小于根结点的值，右子树的所有结点大于根结点的值，左右子树也分别为二叉排序树。
中序遍历二叉排序树可以得到一个有序的序列。

哈希表
折半查找和二叉排序树都是需要通过比较来得到结果，而哈希表将关键字与存储位置建立了一个对应关系，使得不需要经过比较，一次存取便能得到结果，这个对应关系被称为哈希函数。

冲突：计算哈希地址时可能会发现已存在相同的哈希地址，因此需要解决冲突。

解决冲突的方法有：
(1)开放定址法
(2)再哈希法
(3)链地址法