数据结构 1.哈夫曼数

构造哈夫曼树，左小右大，左0右1。下图反了。

哈夫曼树是个没有度为1的二叉树，即n=n0+n2。对于任意树，有n0=n2+1。所以，对于哈夫曼树，n=2n2+1=2n0-1。

下列为某文件中字符的出现频率，采用哈夫曼编码对下列字符编码，则字符序列“bee”的编码为101 1101 1101。字符有6个，占3位二进制，则码长为3。

2.堆排序，选择排序，时间复杂度为O(nlog2n)

设有n个元素的序列{K1,K2,...,Kn}，当且仅当满足下述关系之一时，称之为堆。

Ki<=k2i且ki<=k2i+1 小顶堆

Ki>=k2i且ki>=k2i+1 大顶堆

3.贪心算法

在对问题求解时，总是做出在当前看来是最好的选择。非整体最优，为局部最优。

4.分治算法

将数据分成若干份，每份单独处理后再合并。

5.二叉排序树（二叉查找树）

二叉排序树中没有值相同的节点。或者是一棵空树；或者是具有下列性质的二叉树：

1)若它的左子树不为空，则左子树上所有节点的值均小于它的根节点的值；

2)若它的右子树不为空，则右子树上所有节点的值均大于它的根节点的值；

3)它的左、右子树也分别为二叉排序树。

二叉树的顺序存储采用数组存储：对于下标为i的结点，左子树下标为2i，右子树下标为2i+1。

树结点的度是结点所拥有的分支的数目。

二叉排序树的根结点肯定是关键码序列的第一位。

对一颗二叉排序树进行中序遍历，可得到该二叉树中结点关键字的有序序列。

平衡二叉树：任意结点的左右子树深度相差不超过1；

平衡度=左子树深度-右子树深度。每结点的平衡度只能为-1、0、1。

完全二叉树：除了最底层，上面层为满二叉树。最底层，结点从左到右排序，不行成空缺。

单枝数效率最差。

删除结点操作： 

 

二叉树的重要特性

6.等比求和和等差求和

7.n个元素，等概率删除元素操作。若顺序存储结构，则平均需要移动（n-1）/2个元素。若链式存储结构，则平均需要移动0个元素。 8.若在单向链表上，除访问链表中所有结点外，还需在表尾频繁插入结点或删除最后一个结点，采用仅有尾指针的单循环链表最节省时间和存储空间。 9.图 

权：图边上的数字。

网：带权的图。

连通图：任意两顶点都是连通的图。

连通分量：无向图的极大连通子图。

图没有顺序存储的方式。图的存储结构：邻接矩阵和邻接表。

   

10.无向图 

无向图中若有n个顶点、e条边，则它的邻接表需要n个表头指针和2e个边结点。

有向图中若有n个顶点、e条边，则它的邻接表需要n个表头指针和e个边结点。

无向图的邻接矩阵是对称的，而有向图的邻接矩阵不一定对称。

对于无向图，顶点Vi的度是邻接矩阵中第i行(或第i列)的非零元素的个数。

对于有向图，顶点Vi的度是邻接矩阵中第i行和第i列的非零元素的个数之和。

11.深度优先搜索和广度优先搜索

深度用栈实现，使用递归方式。

广度用队列实现。

连通图，从图的任意一顶点开始深度或广度优先遍历一定可以访问图中的所有顶点。

非连通图，从图的任意一个顶点开始深度或广度优先遍历并不能访问图中的所有顶点。

12.用哈希表存储元素时，需要进行冲突处理，冲突是指关键字不同的元素被映射到相同的存储位置。 13.时间复杂度递归式T(n)=T(n-1)+n，n为问题的规模，则时间复杂度为O(n^2)。若问题的规模增加了16倍，则运行时间增加256倍。

假设T(1)=1， T(n)=T(n-1)+n=T(n-2)+n-1+n=T(n-3)+n-2+n-1+n=...=T(n-(n-1))+n(n-1)-(1+2+...+(n-2))=1+n(n-1)-(n-2)(n-1)/2=1+(n-1)(n+2)/2。

14.散列存储结构的特点是数据结构中元素的存储地址与其关键字之间存在某种映射关系。 15.树的遍历

先序遍历：根左右

中序遍历：左根右

后序（后缀）遍历：左右根

16.二叉树采用二叉链表时，空指针个数为结点数+1；二叉树采用三叉链表时，空指针个数为结点数+2； 17.深度优先搜索

类似于树的先序遍历，是树的先序遍历的推广。

(1)首先从图中某个顶点v出发， 首先访问此顶点，将其标记为已访问过;

(2)然后任选一个v的未被访问的邻接点w出发，继续进行深度优先搜索;

(3)直到图中所有和v路径相通的顶点都被访问到;

(4)若此时图中还有顶点未被访问到，则另选一个未被访问的顶点作为起始点，重复上面的步骤，直至图中所有的顶点都被访问。

18.广度优先搜索

类似于树的按层次遍历。

假设从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。

若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

19.若该队列的容量为M，则长度为(Q.rear-Q.front+M)%M。

队列长度为Q.rear-Q.front。队列中存储位置编号为：0~M-1。

20.栈的应用：表达式求值、括号匹配、递归调用。队列的应用：打印序列。 21.Prim算法和 Kruscal算法

都基于贪心算法。

Prim算法的时间复杂度为O(n2)，与图中边数无关，该算法适合于稠密图。

Kruskal 算法的时间复杂度只和边有关系，为O(elog2e)，由于 Kruskal 算法只与边有关，因此适合求稀疏图的最小生成树。

普利姆算法：

任选一个结点变成红点，其余为蓝点。

在它能一步到位的蓝点中选择权值最小的路径，路径末的结点变成红点。

在红点群中选择它能一步到位的蓝点权值最小的路径，路径末的结点变成红点。以此循环。注意，不能形成环路。边数=结点数-1。

克鲁斯卡尔算法：先选最短的边，循环选最短的边。注意，不能形成环路。边数=结点数-1。

22.优先队列一般采用二叉堆数据结构实现，由于是二叉堆，所以插入和删除一个元素的时间复杂度均为O(lgn)。

23.