数据结构在面试中经常遇到，以前没有系统的梳理过，最近在看《大话数据结构》，所以想整理一些笔记，供日后参考。
数据结构
是相互之间存在一种或多种特定关系的数据元素的集合，按照视点的不同，可分为:
逻辑结构：集合结构，线形结构，树形结构，图形结构
物理结构：顺序存储结构，链式存储结构
算法
算法是解决问题的方法。
五个特性：输入，输出，有穷性，确定性和可行性。
算法设计的要求：正确性，可读性，健壮性，时间效率高和存储量低
算法效率的度量方法：事后统计，事前分析
算法时间复杂度：一般采用大O记法，O(1)叫常数阶，O(n)线形阶，O（n^2）平方阶…
推导大O的方法
1、用常数1取代运行时间中的所有加法常数
2、在修改后的运行次数函数中，只保留最高阶项
3、如果最高阶项存在且不是1，则去除与这个项相乘的常数
常见的时间复杂度
| 执行次数 | 函数阶 | 非正式术语 |
|---|---|---|
| 12 | O(1) | 常数阶 |
| 2n+3 | O(n) | 线形阶 |
| 3n^2+2n+1 | O(n^2) | 平方阶 |
| 5logn+20 | O(logn) | 对数阶 |
| 2n+3nlogn+19 | O(nlogn) | nlogn阶 |
| 6n^3+2n^2+3n+4 | O(n^3) | 立方阶 |
| 2^n | O(2^n) | 指数阶 |
线形表
零个或多个数据元素的有限序列
线形表的顺序存储结构
用一段地址连续的存储单元依次存储线形表的数据元素
|a1|a2|……|a(i-1)|ai|……|an|
顺序存储结构需要三个属性
存储空间的起始位置：数组data，他的存储位置就是存储空间的存储位置。
线形表的最大存储容量：数组长度MaxSize
线形表的当前长度：length
第i个数据元素ai的存储位置可以由a1推算得出 LOC(ai) = LOC(a1)+(i-1)*c
因此存取的时间复杂度是O(1)，由于插入删除需要移动后面节点的位置，所以插入删除的时间复杂度是O(n)
线形表的链式存储结构
用一组任意的存储单元存储线形表的数据元素，这组存储单元可以是连续的，也可以是不连续的
|……|0900(头指针)|……|a1(地址0900)|0700|……|an|null|……|
单链表插入与删除的时间复杂度是O(1)，存取的时间复杂度是O(n)
静态链表
一些早期的编程高级语言，如Basic，Fortran等，由于没有指针，无法实现链表结构，于是想出用数组来代替指针，这种链表叫静态链表，也叫游标实现法
让数组的元素由两个数据域组成，data和cur，cur相当于单链表中的next指针，存放该元素的后继在数组中的位置。
循环链表
将单链表的终端节点由空指针改成指向头节点，使单链表形成一个环，这种头尾相连的单链表称为单循环链表，简称单链表
双向链表
为了解决单向链表不能找前继节点的缺点而设计，在单链表的基础上再加一个指针，指向前继节点
栈
限定在表尾进行插入和删除操作的线形表。允许插入和删除的一段叫栈顶，另一端叫栈尾。 是后进先出（Last In First Out）的线形表，简称LIFO结构。
栈的顺序存储结构及实现
让数组下标为0的一端作为栈底，入栈和出栈的时间复杂度都是O(1)
对于两个相同类型的栈可以设置两栈共享空间，最大限度利用事先开辟的空间来操作：将两个栈的栈底分别设置为一个数组的两端，然后向中间靠拢。
栈的链式存储结构及实现
把栈顶设置在链表的头部，而且在这种结构中，头节点失去了意义，不需要头节点
队列
只允许在一端进行插入操作，而在另一端进行删除操作的线形表，是一种先进先出（First In First Out）的线形表，简称FIFO结构
队列的顺序存储结构的入队操作时间复杂度是O(1)，出队操作是O(n)
队列的链式存储结构其实就是单链表，只不过它只能尾进头出
串
由零个或多个字符组成的有限序列，又名字符串
这里不做赘述，可以了解下这里的两个算法，朴素的模式匹配算法和KMP模式匹配算法
树
n(n>=0) 个结点的有限集。 n=0时称为空树。在任意一个非空树中：
1、有且只有一个特定的称为根（Root）的结点；
2、当n>1时其余结点可分为m（m>0）个互不相交的有限集T1，T2…Tm，其中每个集合本身又是一个树，并且称为根的子树（SubTree）
结点的最大层次称为树的高度或深度，子树的个数称为树的度
树的存储结构
1、双亲表示法 （data，parent）
2、孩子表示法 （data，child1，child2，child3…）
3、孩子兄弟表示法 （data，firstchild，rightsib）
二叉树的定义
二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）
二叉树的性质
1、在二叉树的第i层至多由2^(i-1)个结点
2、在深度为k的二叉树至多由2^k-1个结点（k>=1）
3、在任何一个二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1
4、具有n个结点的完全二叉树的深度为|logn+1|（|n|表示不大于n的最大整数）
二叉树的存储结构
1、二叉树的顺序存储结构：在一棵n个结点的完全二叉树中，从树根起，自上层到下层，每层从左至右，给所有结点编号，能得到一个反映整个二叉树结构的线性序列，如果不是完全二叉树
会造成空间上的浪费，所以一般只用于完全二叉树
2、二叉树的链式存储结构：二叉链表（lchild，data，rchild）
遍历二叉树：前序遍历，中序遍历，后序遍历，层序遍历
线索二叉树：二叉树添加了直接指向节点的前驱和后继的指针的二叉树称为线索二叉树
哈夫曼树：哈夫曼树是一种带权路径长度最短的二叉树，也称为最优二叉树。下面用一幅图来说明。
它们的带权路径长度分别为：
图a： WPL=52+72+22+132=54
图b： WPL=53+23+72+131=48
可见，图b的带权路径长度较小，我们可以证明图b就是哈夫曼树(也称为最优二叉树)
哈夫曼树的构造(哈夫曼算法)
1.根据给定的n个权值{w1,w2,…,wn}构成二叉树集合F={T1,T2,…,Tn},其中每棵二叉树Ti中只有一个带权为wi的根结点,其左右子树为空.
2.在F中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为左右子树根结点的权值之和.
3.在F中删除这两棵树,同时将新的二叉树加入F中.
4.重复2、3,直到F只含有一棵树为止.(得到哈夫曼树)
