博客

由于时间的原因，这次只写完了，树，图，查找，排序这三章的一些自己容易混淆的知识，绪论和一些线性结构的部分就暂时不写了。

树：

深度：从上到下

高度：从下到上

路径：从上到下

性质：

1.节点数 = 度数 + 1

2.m度第i层至多又m^(i-1)个节点

3.h的m叉树，至多由(m^h-1)/(m-1)个节点

4.n个节点的m叉树 h（min）= logm (n*(m-1)+1) 向上取整

满二叉树：

有2^h – 1个节点 ，i的双亲为i / 2 向下取整，如果有孩子，左孩子2i，右孩子2i + 1

完全二叉树：

i < n / 2 向下取整时，为分支节点

存储结构：

完全二叉树，满二叉树，顺序存储和链式存储都可以

完全二叉树性质：

1.n0 = n2 + 1 = 2k+1

2.k层上至多有2^(k-1)个结点

3.高度为h至多有2^h – 1个结点

遍历：

先序：根左右        中序：左根右         后序：左右根

线索二叉树

tag为0时child域指向左右孩子，tag为1时child域指向线索（lchild为前驱，rchild为后继）

树—–二叉树：左孩子右兄弟

森林——-二叉树：每棵树转化为二叉树，每棵树都是兄弟关系并连线，以第一棵树为轴心旋转45°

树的遍历：先根遍历 == 线序遍历        后根遍历 == 中序遍历

二叉排序树：左 < 根 < 右 ,中序遍历可以得到一个递增的有序序列

查找：x < 根，查左子树， x > 根，查右子树

插入：同上

删：

叶子节点

直接删除，

只有左、右子树

，直接删除然后再按照左根右递增的规律用子孙结点补上。

左右孩子都有

，用直接前驱（直接后继）替代z，然后再删除直接前驱（直接后继）

查找效率：平衡二叉树O(log2 n)         单只O(n)

前缀编码：没有一个编码时另一个编码的前缀

哈夫曼编码：其权值为频度，标记0为转向左孩子，标记1为转向右孩子

哈夫曼树：不唯一，新建n – 1个结点 == 结点数为2n – 1，WPL最小，权值最小的做新节点。

查找：

静态查找：顺序查找，折半查找，散列查找

动态查找：二叉排序树查找，散列查找

平均查找长度： ASL = ΣPiCi         n为表长，Pi第i个数据的概率，Ci找到第i个元素所需比较次数

顺序查找：ASL = （n + 1） / 2 适用于顺序表，链表

折半查找：过程可用二叉树描述称为判定树，且判定树时一颗平衡二叉树，ASL = log2(n+1)  – 1,

h = log2(n+1)向上取整，时间复杂度O(log2(n+1))

分块查找：索引表中含各块的最大关键字和各块第1个元素的地址

用顺序查找：ASL = (S^2 + 2S + n)  / 2S

用折半查找：ASL = log2(b + 1)向上取整 + (S+1) / 2

长度为n，有b块，每块S个记录

B树

：1，每个结点至多有m颗子树，即m – 1个关键字

2，除根结点外所有非叶子节点，至少有m / 2 向上取整颗子树，即m / 2 向上取整 – 1个关键字

3，对于任何一个结点，其所有子树的高度都是相同的

4，关键字左 < 中 < 右

高度：logm(n + 1) <= h <= log(m/2向上取整) （n + 1）/ 2 + 1

B+树

：1.每个分支节点最多有m颗子树，2.非叶根节点至少有两颗子树，其他分支节点知道有m / 2向上取整根子树，3.结点的子树个数与关键字相等，4.叶子节点包括全部关键字，5.分支结点时子节点关键字的最大值无论查找成功或者失败都要查找到最下层。

致使B+树更矮，读磁盘次数更少

散列表：

处理冲突的方法：

开放定址法：1.线性定址法，2.平方探测法，3.再散列法，4.伪随机散列法

（不能随便物理删除，可进行逻辑删除）

拉链法

性能分析：

1.以平均查找长度作为衡量散列表的查找效率的量度

2.取决于：散列函数，处理冲突的方式和装填因子

排序：不稳定的排序算法，只需要举出一组关键字的实例说明它不稳定即可

插入排序

直接插入排序：

空间复杂度：O(1)

时间复杂度：O(n^2)         稳定        适用于顺序，链式存储

折半插入排序：

时间复杂度：O(n^2)        稳定        对于数据量不大的能表现出不错的性能

希尔排序：

时间复杂度：O(n^1.3)        不稳定        适用于顺序存储

交换排序：

冒泡排序：时间复杂度O(n^2)，        稳定

快速排序：栈的深度，最好O(log2 n)，最坏O(n)，平均O(log2 n)

时间复杂度：O(nlog2 n)        不稳定

快速排序时内部排序算法中平均性能最优的排序算法

1.将j从high往前找到第一个小于枢轴的元素，将其换到i所指的位置，i从low往后找到第一个大于数轴的元素换到j所指元素，再重复j i的上述操作，直至i==j，此时划分了两个子序列，再对子序列重复此操作。

算法：

int Partition(ElemType A[],int low,int high)

{

ElemType pivot = A[low];

while(low < high){

while(low < high && a[high] >= pivot)        –high;

A[low] = A[high];

while(low < high && a[high] <= pivot)        ++low;

A[low] = A[low];

}

A[low] = pivot;

return low;

}

选择排序

：

简单选择排序：第i趟从L[1…n]中选择关键字最小的元素与L[i]交换

空间复杂度O(1)         时间复杂度O(n^2)         不稳定

堆排序：大根堆，最大元素放在根节点，任一非根结点 < 双亲，小根堆反之。

空间复杂度O(1)         时间复杂度O(nlog2 n)         不稳定

适用于关键字较多的情况        从尾向前遍历，双亲 > 孩子

归并排序：将两个或两个以上有序表组成一个有序表

空间复杂度O(n)         时间复杂度O(nlog2 n)         稳定

K路时：m = logk N        m:趟数        N：元素个数

算法：

ElemType *B = (ElemType *)malloc((n +1) * sizeof(ElemType));

void Merge(ElemType A[], int low, int mid, int high){

for(int k = low; k <= high; k++){

B[K]=A[K];

for(i = low, j = mid + 1;i < mid && j <= high; k++){


if(B[i] <= B[j])

A[K] = B[i++];

else

A[K] = B[j++];

}

while(i <= mid)        A[k++] = B[i++];

while(j <= mid)        A[k++] = B[j++];

}

基数排序：不基于比较和移动，基于关键字各位的大小排序，通常采用链式基数排序，按照                              各位，十位，百位，依次排。

空间复杂度O(r)    r个队列        时间复杂度O（d(n+r)）  d趟分配        稳定

小结：1.n较小：直接插入排序；简单插入排序（记录本身信息量较大时）

2.初始状态基本有序：直接插入排序；，冒泡排序

3.n较大，应采用O(nlogn)：快速排序（关键字随机分布）；堆排序（所需辅助空间少，               不出现最坏情况）；归并排序（稳定且为O(nlogn)）

4.n很大：基数排序

5.信息量较大：用链式储存结构

图

：（G:Graphics图形        V:Vertex顶点        E:Edge边）

简单图：不存在重复边，不存在顶点到自身的边

完全图：无向图：有n(n – 1) / 2条边；有向图：有n(n – 1) 条弧

生成子图：V(G’) = V(G)的图，且E’是E的子集

连通分量：无向图中的极大连通子图（所有顶点都相连）

强连通分量：有向图中极大强连通子图（任意一对顶点都有w-v，v-w的路径）

连通图生成树：有全部顶点，去除一条边构成非连通图，加一条边形成回路

度：无向图：∑TD(Vi) = 2e,                         n:顶点        e:边

有向图：TD(V) = ID(V) + OD(V)        ∑ID(Vi) = ∑OD(Vi) = e

稀疏图：|E| < |V|log|V|

路径：u — v最短路径，若不存在则为（∞）

图的存储：

邻阶矩阵法：用一个一维数组存顶点信息，一个二维数组存各顶点的关系

A[i][j] = 1 是边        A[i][j] = 0 不是边

带权图：A[i][j] =权值 是边         A[i][j] = 0或∞ 不是边

注意：无向图的邻接矩阵是对称矩阵，空间复杂度O(n^2) n为|V|

特点：1.无向图有唯一的对称矩阵，只需存储上（下）三角元素即可表示

2.无向图第i行（i列）非0元素的个数正好是i的度TD(Vi)

3.有向图第i行非0元素个数 = 出度OD(Vi),第i列非0元素个数 = 入度ID(Vi)

4.适用于稠密图

5.A^n[i][j]表示由i到j长度为n的路径的数目

邻接表法：对每一个顶点Vi建立一个单链表，第i个单链表中的结点表示依附于结点Vi的边（对于有向图为弧）这是边表（出边表）表头指针和顶点数据采用顺序存储，所以只存在顶点结点和边表结点

顶点表结点

边表结点

特点：1.无向图存储空间O(|V| + 2|E|)        有向图O(|V| + |E|)

2.适用于稀疏图，不适于找两顶点间是否存在边

3.求出度：算结点个数，求入读：遍历全部

4.不唯一，顺序可变

十字链表法：有向图，链式存储        顶点之间是顺序存储

十字链表不唯一，但一个十字链表表示一个确定的图

弧结点

尾节点

邻接多重表：无向图，链式存储

图的遍历：

广度优先搜索(BFS)        不是递归的算法

visited[]初始状态为FALSE，Vi被访问则visited[i] = TRUE

a入队，取出a，然后b，c入队，b出队，d入队，c出队，d出队，与二叉树的层序遍历一                  致。

深度优先搜索(DFS)        递归形式

深度优先生成树：对连通图调用DFS才能产生，否则为森林

图的遍历算法可以判断图的连通性

图的应用：

最小生成树：权值最小的生成树

性质：1，树形不是唯一的，各边的权值不同时唯一

2，权值之和唯一且最小

3，最小生成树的边数为顶点数减一

prim算法：一个点加入T，选最近的加入T，再选对于T整体最近的加入T，直到所有点都加入         T

时间复杂度O(|V|^2)        适用于边稠密的图

kruskal算法：不断选取权值最小的边加入T，直到联通

时间复杂度O(Elog|E|)        适用于稀疏而顶点较多的图

最短路径:v0 — vi 中带权路径最短的那条

dijkstra算法：

dist[]:记录从源点V0到其它顶点的最短长度，有弧，dist[i] = 权值，否则dist[i] = ∞

path[]:patj[i]表示从源点到顶点i之间的最短路径的前驱结点，结束时可以根据其追述

V0 — Vi的最短路径

使用邻接矩阵存储：时间复杂度O(|V|^2)

边上带有负权值时，dijkstra算法并不适用，求单源最短路径，基于贪心算法

init:S初始化{Vi}，设dist[2] = 10, dist[3] = ∞, dist[4] = ∞, dist[5] = 5

round1: 选出min，dist[5], 并将V5并入S distance V1 — V5 — V2 = 8 < dist[2],update         dist[2] = 8,同理update dist[3] = 14, dist = 7.

round2:选出min，dist[4]，将V4并入S distance V1 — V5 — V4 — V3 = 13 < dist[3],

update dist[3], 不可达V2,即 dist[2]不变

round3:选出min，dist[2]，将V2并入S distance   V1 — V5 — V2 — V3 = 9 < dist[3],

update dist[3]

round3:选出min，dist[3]，将V3并入S

剩下的Floyd算法，无向图的描述的表达式，拓扑排序，关键路径由于编写周期太长，之后的文章补上。现在已经9.13号了。不能再和数据结构纠缠了。

码字及手写笔记：