数据结构 | 缘来我们在这里

引子

诚者自成也，而道自道也。

诚者，物之终始。不诚无物。是故君子诚之为贵。

诚者，非自成己而己也。所以成物也。成己仁也，成物知也。性之德也，合外内之道也。故时措之宜也。

–《中庸》

绪论

数据结构

数据(data): 是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素(data element)：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理
数据对象(data object)：是性质相同的数据元素的集合，是数据的一个子集。
数据结构(data structure)：又称逻辑结构，是相互之间存在一种或多种特定关系的数据的集合，通常包括四种：集合、线性结构、树形结构、网状结构。
存储结构：是数据结构在计算机中的表示。
数据类型(data type)：是一个值的集合和定义在这个值集上的一系列操作的总称。
抽象数据类型(AbstractData Type)：是指一个数据模型以及定义在该模型上的一组操作，可细分为：原子类型、固定聚合类型、可变聚合类型。

算法

算法的5个重要特性：有穷性，确定性，可行性，输入，输出

衡量一个算法是否优秀，一般从以下几个点考虑：正确性，可读性，健壮性，时间复杂度，空间复杂度

一般情况下，算法中基本操作重复执行的次数时问题规模n的某个函数f(n)，算法的时间量度记作：T(n) = O(f(n))。他表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。

类似时间复杂度，基本操作带来的空间消耗和问题规模n通常也有关系，这个关系叫空间复杂度：S(n) = O(f(n))。若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的额外空间，否则应该同时考虑输入本身所需空间。若额外空间相对于输入数据量来说是常数，则称此算法为原地工作。

算法书写规范

算法说明：指明算法功能；参数表中各参量的含义和输入输出属性；算法中引入了哪些全局变量或外部定义的变量，作用入口初值以及应满足哪些限制条件
注释和断言：注释抽象度应高于语句，断言用来陈述算法执行到此处应该满足的条件
输入和输出：scanf和printf语句；参数显示；全局变量或外部变量隐式的传递信息
错误处理：尽可能使用函数返回算法的执行状态，便于调用者处理异常情况，有益于培养良好的程序设计习惯
语句选用和算法结构：尽量不使用goto
基本运算：自己实现
建议：使用图说明算法；用边界条件检测算法

第二章

线性表和单链表

第三章

栈和队列

表达式求值：算符优先法

为了实现算符优先法，可以使用两个工作栈，一个称作OPTR，用来寄存运算符，另一个称为OPND用来寄存操作数或运算结果。

首先置操作数栈为空栈，表达式起止符‘#’为栈底元素
依次读入表达式中的每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕（即OPTR的栈顶元素和当前读入字符均为‘#’）

栈与递归的实现

递归：一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称作递归函数。

hanoi问题：

#include <stdio.h>
int c = 0;
void moveH(char *x, int n, char *z){
    printf("%i. Move disk %i from %s to %s\n", ++c, n, x, z);
}
void hanoi(int n, char *x, char *y, char *z){
    // 将塔座x上按直径由小到大且自上而下编号为1到n的n个圆盘按规则搬到塔座z上，y可以作为辅助塔座。(c是初值为0的全局变量，对搬动记数)
    // 搬动操作move(x,n,z)可定义为: printf("%i. Move disk %i from %c to %c\n", ++c, n, x, z);
    if(n == 1){
        moveH(x, 1, z);
    } else {
        hanoi(n-1, x, z, y);
        moveH(x, n, z);
        hanoi(n-1, y, x, z);
    }
}
int main()
{
    char first[20] = "第一个柱子";
    char second[20] = "第二个柱子";
    char third[20] = "第三个柱子";
    
    hanoi(10, first, second, third);
    return 0;
}

递归的实现：调用函数和被调用函之间的链接及信息交换需要通过栈来执行

在运行被调用函数之前，系统需要先完成3件事

将所有的实参、返回地址等信息传递给被调用函数保存
为被调用函数的局部变量分配存储区
将控制转移到被调用函数的入口

从被调用函数返回调用函数之前，系统也要完成三件工作

保存被调用函数的计算结果
释放被调用函数的数据区
依照被调用函数保存的返回地址将控制转移到调用函数

队列

循环队列

离散事件模拟

略

第四章串

kmp算法（克努特-莫里斯-普拉特算法）

思路：模式串本身是已知量，已知量，若和待匹配字符串已经出现部分匹配，则根据这部分匹配我们可以得知，再进行匹配需要滑动的距离。根本目的在于减少重复计算量

关键：next函数

1 2	// j是模式串的下标，k是滑动距离 next[j] = k

tips: 求next函数的过程其实也是一个递归的过程，哈哈哈哈，考虑相同字符问题可以对算法进行修正，得到更好的答案。此算法启示为对细节孜孜不倦的苛求，可以有颠覆的结论。

第五章数组和广义表

矩阵的压缩存储

压缩存储是指：为多个值相同的元只分配一个存储空间，对零元不分配空间

矩阵运算: 加法，减法，数乘，转置，共轭，共轭转置，乘法，行列式

对称矩阵，三角矩阵，对角矩阵

稀疏矩阵：三元组存储法(位置，值)

广义表

广义表一般记作：LS = $(a_1,a_2,…,a_n)$

$a_i$可以是单个元素，也可以是子表，分别称为原子和子表。习惯上用大写字母表示广义表的名称，用小写字母表示广义表的原子，表非空时，习惯称第一个元素为表头，其余元素组成的表为表尾

广义表的存储结构

通常采用链式存储。

m元多项式的表示

$P(x,y,x) = x^{10}y^3z^2 + 2x^6y^3z^2 + 3x^5y^2z^2 + x^4y^4z + 6x^3y^4z + 2yz + 15$
$P(x,y,x) = ((x^10+2x^6)y^3 + 3x^5y^2)z^2 + ((x^4+6x^3)y^4 + 2y)z + 15$
广义表表示：$P = z((A,2),(B,1),(15,0))$ (数字代表变元的幂次)
其中$A = y((C, 3), (D, 2)) C = x((1, 10), (2, 6)) D = x((3, 5)) B = y((E, 4), (F, 1)) E = x((1, 4), (6, 3)) F = x(2, 0)$

广义表的递归算法

分治法设计递归算法

首先应书写函数的首部和规格说明，严格定义函数的功能和接口（递归调用的界面），对求精函数中所得的和原问题性质相同的子问题，只要接口一致，便可进行递归调用
对函数中的每一个递归调用都看成只是一个简单的操作，只要接口一致，必能实现规格说明中定义的功能，切忌想的太深太远。

重要的是递归思想的理解和运用

树和二叉树

树的定义：树(Tree)是n(n>=0)个结点的有限集，在任何一个非空树中，树特征：

有且只有一个特定的称为根(Root)的结点
当n>1时，其余结点可分为m(m>0)个互不相交的有限集$T_1,T_2…,T_m$，其中每一个集合本身又是一棵树，并且称为根的子树(subtree)

树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度(Degree)。度为0的结点称为非终端结点或分支结点。除根节点之外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。结点的子树的根的根称为该结点的孩子(Child)，相应地，该结点称为孩子的双亲(Parent)。同一个双亲的孩子之间互称为兄弟。结点的祖先是从根到该节点所经分支上的所有结点。以某结点为根的子树中的任一节点都称为该节点的子孙。

结点的层次从根开始定义，根为第一层，根的孩子为第二层。其双亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度(Depth)或高度。

如果树的结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。在有序树中，最左边子树的根称为第一个孩子，最右边的称为最后一个孩子。

森林(Forest)是m(m>0)棵互不相交的树的集合。对树中的每个结点而言，其子树的集合即为森林。由此，也可以森林和树相互递归的定义来描述树。

Tree = (root, F);$F=(T_1,T_2,…,T_m);T_i=(r_i, F_i)$

二叉树

二叉树是另一种树形结构，它的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。

二叉树有五种形态：空二叉树，仅有根节点的二叉树，右子树为空的二叉树，左右子树均非空的二叉树，左子树为空的二叉树

二叉树的性质：

在二叉树第i层上至多有$2^{i-1}$个结点
深度为k的二叉树至多有$2^k-1$个结点
对任何一个二叉树，如果其终端结点数为$n_0$，度为2的结点数为$n_2$。则$n_0 = n_2+1$。思路：节点总数为$n = n_0 + n_1 + n_2$；根据分支推出等式：$ n - 1 = B = n_1 + 2n_2$；结合两个等式即可推出。一颗深度为k且有$2^k-1$个结点得二叉树称为满二叉树。深度为k的，有n个结点的二叉树，当且仅当其每一点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。
具有n个结点的完全二叉树的深度为$\lfloor log_2n\rfloor + 1$
对于一颗有n个结点的完全二叉树的结点按层序编号，则对任一结点i，有：
- i=1，此结点为根节点；i>1，则其双亲PARENT(i)是结点$\lfloor i/2 \rfloor$
- 如果2i>n,则结点i无左孩子；否则其左孩子LCHIL(i)是结点2i
- 如果2i+1>n，则结点i无右孩子；否则其右孩子RCHILD(i)是结点2i+1
  二叉树的存储结构

顺序存储：最坏的情况，一个深度为k且有k个结点的二叉树却需要长度为$2^k-1$的一维数组

链式存储：二叉链表和三叉链表

遍历二叉树和线索二叉树

特点：先序中序后序是根据根结点的位置定的，顺序是先左后右

先序遍历二叉树操作定义(DLR):
1. 访问根结点
2. 先序遍历左子树
3. 先序遍历右子树
中序遍历二叉树的操作定义(LDR):
1. 中序遍历左子树
2. 访问根结点
3. 中序遍历右子树
后序遍历二叉树的操作定义(LRD):
1. 后序遍历左子树
2. 后序遍历右子树
3. 访问根结点

从中序遍历递归算法执行过程中递归工作栈的状态可见：

工作记录中包含两项，其一是递归调用的语句编号，其二是指向根结点的指针，则当栈顶记录中的指针非空时，应遍历左子树，即指向左子树根的结点入栈。
若栈顶记录种的指针值为空，则应退至上一层，若是从左子树返回，则应访问当前层即栈顶记录中指针所指的根结点。
若是从右子树返回则表明当前层的遍历技术，应继续退栈。从另一角度看，这意味着，遍历右子树时不再需要保存当前层的根指针，可直接修改栈顶记录中的指针即可。

“遍历”是二叉树各种操作的基础，可以在遍历过程中对结点进行各种操作，如：对于一棵已知树可求结点的双亲，求结点的孩子结点，判定结点所在层次，反之，也可在遍历的过程中生成结点，建立二叉树的存储结构。

对二叉树进行遍历的搜索路径除了上述先序、中序、后序外，还可以从上到下、从左到右按层次进行。

显然，遍历二叉树的算法中的基本操作是访问结点，则不论按哪一种次序进行遍历，对含n个结点的二叉树，其时间复杂度均为O(n)。所需辅助空间为遍历过程中栈的最大容量，即树的深度，最坏情况下为n，则空间复杂度也为O(n)。遍历的时候也可以采用二叉树的其他存储结构，如带标志域的三叉链表，此时因存储结构中已存有遍历所需足够信息，则遍历过程中不需另设栈。

线索二叉树

如下规定：若结点有左子树，则其lchild域指示其左孩子，否则令lchild域指示其前驱；若结点有右子树，则其rchild域指示其右孩子，否则令rchild域指示其后继。为了避免混淆，还需要改变结点结构，增加两个标志域：lchild,LTag,data,RTag,rchild。其中LTag取值0，1，分别代表lchild域指示左孩子，前驱。RTag同理。

以这种节点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱和后继的指针，叫做线索。加上线索的二叉树称之为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。

树和森林

树得存储结构

双亲表示法：一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置。

孩子表示法：把每个结点的孩子结点排列起来，看成一个线性表，且以单链表作为存储结构，则n个结点有n个孩子链表。而n个头指针又组成一个线性表

孩子兄弟表示法：又称二叉树表示法，或二叉链表示法。即以二叉链表作树的存储结构。链表中结点的两个链域分别指向该节点的第一个孩子结点和下一个兄弟结点。（按照这个思想，所有的树都可以转换为二叉树！！）

森林与二叉树的转换

从树的二叉链表示法可知，任何一课和树对应的二叉树，其右子树必然为空，若把森林中下一棵树看成前一棵树的根结点二叉树表示的右儿子，则同样可以导出二叉树和森林的对应关系

树和森林的遍历

同样分为：先序遍历，中序遍历，后序遍历

树与等价关系

概念：等价关系，等价类，利用树可以划分等价类

赫夫曼树及其应用

从树中一个结点到另一个结点的分支构成这两者之间的路径，路径上的分支数目称为路径长度。树的路径长度是从树根到每一个结点的路径长度之和。树的带权路径长度为树中所有叶子结点的带权路径长度之和，通常记作: $WPL = \sum_{k=1}^{n}w_kl_k$

假设有n个权值${w_1,w_2,…,w_n}$，试构造有n个叶子结点的二叉树，每个叶子结点带权值为$w_i$，其中带权路径长度WPL最小的二叉树称作最优二叉树或赫夫曼树

赫夫曼算法

根据给定的n个权值${w_1,w_2,…,w_n}$构成n棵二叉树的集合$F={T_1,T_2,…,T_n}$，其中每一棵二叉树$T_i$中只有一个带权为$W_i$的根结点，其左右子树均空
在F中选取两棵根结点的权值最小的树作为左右子树构造一颗新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
在F中删除这两棵树，同时将新得到的二叉树加入到F中
重复2，3步骤，直到F中只含有一颗树为止。这棵树便是赫夫曼树

赫夫曼编码

若要设计长短不等的编码，则必须是任一个字符的编码都不是另一个字符的编码的前缀，这种编码称做前缀编码

赫夫曼编码

假设每种字符在电文中出现的次数为$w_i$，其编码长度为$l_i$，电文中只有n种字符，则电文总长为$\sum_{i=1}^{n}w_il_i$。对应到二叉树上，若置$w_i$为叶子结点的权，$l_i$恰为从根到叶子的路径长度。则$\sum_{i=1}^{n}w_il_i$恰为二叉树上的带全路径长度。由此可见，设计电文最短的二进制前缀编码即以n种字符出现的频率作权，设计一棵赫夫曼树的问题，由此得到的二进制前缀编码称为赫夫曼编码。

回溯法与树的遍历

在程序设计中，有相当一类求一组解、或求全部解或求最优解的问题，例如：八皇后问题。不是根据某种确定的计算法则，而是利用试探和回溯得搜索技术求解。回溯法也是递归设计的一种重要的方法，它的求解实质上是一个先序遍历一棵‘状态树’的过程，只是这棵树不是遍历前预先建立的，而是隐含在遍历过程中，但如果认识到这点，很多问题的递归过程也就迎刃而解了。

题目：求含n个元素的集合的幂集。
集合A的幂集是由集合A的所有的子集所组成的集合。则A得幂集为$\rho(A)$。

可以利用分治法来设计解法，在此，从另一角度分析问题。幂集的每个元素是一个集合，它或是空集，或含集合A中的一个元素，或集合A中的两个元素，或等于集合A。反之，从集合A的每个元素看，它只有两种状态：它或属于幂集的元素集，或不属于A的幂集元素集。则求$\rho(A)$的元素的过程可看成是依次对集合A中元素进行取或舍的过程，并且可以用一棵树来表示。

回溯法

算法：

void PowerSet(int i, int n){
    //求含n个元素的集合A的幂集$\rho(A)$。进入函数时已对A中前i-1个元素做了取舍处理，现从第i个元素起进行取舍处理。若i>n则求得幂集的一个元素并输出之，初始调用：PowerSet(1, n)
    if(i > n) 输出幂集的一个元素；
    else {
        取第i个元素: PowerSet(i+1, n);
        舍第i个元素: PowerSet(i+1, n);
    }
} // PowerSet

上述问题的解决是一个满二叉树，树中每个叶子结点的状态都是求解过程中可能出现的状态(即问题的解)。然而很多问题用回溯法和试探求解的时候，描述求解过程的状态树不是一棵满的多叉树。当时谈过程中出现的状态和问题求解产生矛盾时，不再继续试探下去。这时出现得叶子结点不是问题的解的终结状态。这类问题的求解过程可看成是在约束条件下进行先序遍历，并在遍历过程中剪去那些不满足条件的分支。

树的技术

推导过程较麻烦，略，有用到再说

揭露：n个结点的不想似的二叉树有$\frac{1}{n+1}C^n_{2n}$

图

图是一种数据结构，加上一组基本操作，就构成了抽象数据类型。在图形结构中，结点之间的关系可以是任意的，图中任意两个元素之间都有可能相关。

在图中的数据元素通常称为顶点(Vertex)，V是顶点的有穷非空集合；VR是两个顶点之间的关系的集合。若$<\nu,\omega>\in VR$，则$<\nu,\omega>$表示从$\nu$到$\omega$的一条弧(Arc)。且称$\nu$为弧尾或初始点(Initial node)，称$\omega$为弧头(HEAD)或终端点(Terminal node)，此时的图称为有向图(Digraph)。若$<\nu,\omega>\in VR$，则必有$<\omega,\nu>\in VR$。即VR是对称的，则以无序对$(\nu,\omega)$代替这两个有序对，表示$\nu$和$\omega$的一条边(Edge)，此时的图称为无向图(Undigraph)。

我们用n表示图中顶点的数目，用e表示边或弧的数目。在下面的讨论中，我们不考虑顶点到其自身的弧或边，即若$<\nu_i, \nu_j> \in VR$则$i \not= j$，那么，对于无向图，e的取值范围是0到$\frac{1}{2}n(n-1)$。有$\frac{1}{2}n(n-1)$条边的无向图称为完全图(Completed graph)。对于有向图e的取值范围是0到$n(n-1)$。具有$n(n-1)$条弧的有向图称为有向完全图。又很少条边或弧(如$e < nlogn$)的图称为稀疏图(Sparse grapth)。反之称为稠密图(Dense grapth)。

有时图的边或弧具有与它相关的数，这种与图的边或弧相关的数叫做权(Weight)。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网(Network)。

假设有两个图G = (V, {E})和G’ = (V’, {E’})，如果$V’\subseteq V$且$E’\subseteq E$，则称G’为G的子图(Subgraph)。

对于无向图G = (V, {E})，如果边$(v, v’) \in E$，则称v,v’互为邻接点(Ajacent)。即v和v’相邻接。边(v,v’)依附(Incident)于定点v和v’，或者说(v,v’)和定点v和v’相关联。顶点v的度(Degree)是和v相关联的边的数目。记为TD(V)。以顶点v为头的弧的数目称为入度(InDegree)，记为ID(V)。以v为尾的弧的数目称为v的出度(Outdegree)，记为OD(v);顶点v的度为TD(v) = ID(v) + OD(v);

无向图G = (V, {E})中从顶点$\nu$到$\nu’$的路径(Path)。如果G是有向图，则路径也是有向的，顶点序列应该满足$< \nu_{i-1}, \nu_i > \in E$。路径的长度是路径上的边或弧的数目。第一个顶点和最后一个顶点相同的路径称为回路或环。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点，其余顶点不重复出现的回路，称为简单回路或简单环。

在无向图G中，如果从定点v到v’有路径，则称v和v’是连通的。如果对于图中任意两个顶点都是连通的，则称G为连通图(Connected Graph)。连通分量(Connected component)，指的是无向图中的极大连通子图。

在有向图中，如果对于每一对顶点，相互之间都存在路径，则称G是强连通图。有向图的极大连通子图称为有向图的强连通分量。

一个连通图的生成树是一个极小连通子图。

如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一棵有向树。一个有向图的生成森林由若干棵有向树组成，含有图中全部定点，但只有足以构成若干棵不相交的有向树的弧。

可对某个顶点的所有邻接点进行排队，在这个排队中自然形成了第一个或第k哥邻接点。若某个顶点的邻接点的排序大于k，则称第k+1个邻接点为第k个邻接点的下一个邻接点，而最后一个邻接点的下一个邻接点为’空’。

图的存储结构

自然采取多重链表的存储结构。由于途中各顶点度不同，最大度数和最小度数可能相差很多，因此，若按度数最大的定点设计结点结构，则会浪费很多单元；反之，按每个顶点自己的度数设计不通的结点结构，又会给操作带来不便。因此，和树类似，在实际应用中不宜采用这种结构，而应根据具体的图和需要进行的操作，设计恰当的结点结构和表结构。常用的有邻接表，邻接多重表和十字链表。

邻接矩阵表示法：使用矩阵存储顶点间相互关系，n个结点构成n*n矩阵。优点：直观，清晰。缺点：占用存储空间大

邻接表: 思路是每个顶点建立一个单链表，存储其邻接边信息。这样若无向图中有n个结点、e条边，则它的邻接表需n个头结点和2e个表结点。显然在边稀疏的情况下，用邻接表表示图比邻接矩阵节省存储空间。当和边相关的信息多时更是如此。邻接表判定两个顶点是否有边或弧链接，没有邻接矩阵方便

图的遍历

和树的遍历类似，在此，我们希望从图中的某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次。这一过程叫做图的遍历。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。

通常有两种遍历图的路径：深度优先搜索和广度优先搜索。

深度优先搜索: 此遍历类似于树的先根遍历，是树的先根遍历的推广。深度优先搜索可从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图。

深度优先搜索，邻接矩阵的时间复杂度为$O(n^2)$，邻接表的时间复杂度为O(n+e)。

广度优先搜索: 类似于树的按层遍历的过程。假设从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直到所有顶点被访问到为止。

图的连通性

连通图：从图中任意顶点进行深度优先或广度有限访问，都能访问到所有的顶点

深度优先搜索过程生成的树为深度优先生成树；广度优先搜索过程生成的数为广度优先生成树

非连通图，对应深度优先生成森林，广度优先生成森林

强连通分量: 有向图强连通分量：在有向图G中，如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量(strongly connected components)。

最小生成树: 假设要在n个城市之间建立通信联络网，则n个城市只需要n-1条线路。如何在最节省经费的前提下建立这个通信网。可以用连通网来表示这个问题，我们需要寻找到一棵耗费最小的生成树，这个问题就是最小生成树问题

MST性质：假设 N = (V, {E})是一个连通网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值（代价）的边，其中$u \in U,v \in V - U$则必存在一棵包含边$(u, v)$的最小生成树

普里姆算法：假设 N = (V, {E})是一个连通网，TE是N上最小生成树中边的集合。算法从U = { $\mu_0$ }$(\mu_0 \in V)$，TE = {} 开始，重复执行下述操作：在所有$u \in U, v \in V - U$的边$(u,v) \in E$中找一条代价最小的边$(u_0, v_0)$并入集合TE，同时$v_0$并入U，直至U = V为止。此时TE中必有n-1条边，则T = (V, {TE})为N的最小生成树。

普里姆算法时间复杂度为$O(n^2)$(其中n为顶点数)。所以普里姆算法适合求边稠密的网的最小生成树

克鲁斯卡尔算法：假设连通网N = (V, {E})，则令最小生成树的初始状态为只有n个顶点而无边的非联通图T = (V, {})，图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T当中，否则舍去此边而选择下一条代价最小的边。依次类推，直至T中所有顶点都在同一连通分量上为止。时间复杂度为$O(eloge)$(e为边数)，因此适合求边稀疏的网的最小生成树

关节点：假若在删去顶点v以及和v相关联的各边之后，将图的一个连通分量分割成两个或两个以上的连通分量，则称顶点v为该图的一个关节点(articulation point)。

一个没有关节点的连通图称为重连通图(biconnected graph)。若连通图中至少删去k个顶点才能破坏图的连通性，则称此图的连通度为k。

一个无环的有向图称为有向无环图(directed acycline graph)，简称DAG图。

有向无环图是描述含有公共子式的表达式的有效工具。例如下述表达式：((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)

有向无环图应用示例

有向无环图也是描述一项工程或系统的进行过程的有效工具。除最简单的情况之外，几乎所有的工程都可分为若干个称作活动的子工程，而这些子工程之间，通常受着一定条件的约束，如其中某些子工程的开始必须在另一些子工程完成之后。对于整个工程和系统，人们关心的是两个方面的问题：一是工程能否顺利进行；二是估算整个工程完成所必需的最短时间。

自反关系：设 R是 A上的一个二元关系，若对于 A中的每一个元素 a， (a,a)都属于 R，则称 R为自反关系。换言之，在自反关系中， A中每一个元素与其自身相关

反对称关系：反对称性是一个关于数学上二元关系的性质。大概地说，集合 X 上的二元关系 R 是反对称的，当且仅当不存在X里的一对相异元素a, b，它们 R-关系于彼此。

传递关系：在逻辑学和数学中，若对所有的 a，b，c 属于 X，下述语句保持有效，则集合 X 上的二元关系 R 是传递的：「若a 关系到 b 且 b 关系到 c，则 a 关系到 c。」

偏序和全序

偏序和全序是公里集合论中的概念。

首先你要知道什么是二元关系。
比如实数中的“大小”关系，集合的集合中的“包含”关系就是两种二元关系。

所谓偏序，即偏序关系，是一种二元关系。
所谓全序，即全序关系，自然也是一种二元关系。

全序是指，集合中的任两个元素之间都可以比较的关系。比如实数中的任两个数都可以比较大小，那么“大小”就是实数集的一个全序关系。

偏序是指，集合中只有部分元素之间可以比较的关系。比如复数集中并不是所有的数都可以比较大小，那么“大小”就是复数集的一个偏序关系。

显然，全序关系必是偏序关系。反之不成立。

拓扑排序：由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

这种用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网(Activity On Vertex Network)。简称AOV-网

拓扑排序

在有向图中选一个没有前驱的顶点且输出之
从图中删除该顶点和所有以它为尾的弧

重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止，后一种情况说明有向图中存在环

关键路径

与AOV-网相对应的是AOE-网(Activity On Edge)即表示活动的网。AOE-网是一个带权的有向无环图，其中顶点表示事件(Event)，弧表示活动，权表示活动持续时间。

AOE-网有待研究的问题是：1，完成整项工程至少需要多少时间。2，哪些活动是影响工程进度的关键

由于在AOE-网中有些活动可以并行的进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度。路径长度最长的路径叫做关键路径(Critical Path)。

关键路径的算法：

输入e条弧<j,k>。建立AOE-网的存储结构
从源点$v_0$出发，令ve[0] = 0，按拓扑有序求其余各顶点的最早发生时间$ ve[i] (1 \le i \le (n-1)) $。如果得到的拓扑有序中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止；否则执行步骤3
从汇点$v_n$出发，令vl[n-1] = ve[n-1]，按逆拓扑有序求其余各顶点的最迟发生时间$vli$。
根据各点的ve和vl值，求每条弧s的最早开始时间e(s)和最迟开始时间ls(s)。若某条弧满足条件e(s)=l(s)，则为关键活动。

理解要点，求关键活动 –> 各事件最早发生时间和最迟发生时间 –> 求弧的最早发生时间和最迟发生时间 –> 关键弧。2，3步骤一个给出初始值，一个给出终值。但思路都是由后往前推，递归思想。

应用：1956年，美国杜邦公司提出关键路径法，并于1957年首先用于1000万美元化工厂建设，工期比原计划缩短了4个月。杜邦公司在采用关键路径法的一年中，节省了100万美元。

最短路径

假如，一个旅客从A城到B城，他希望选择一条途中中转次数最少的路线。假设图中每一站都要换车，则这个问题反映到图上就是要找一条从顶点A到B所含边的数目最少的路径。我们只需从A出发对图作广度优先搜索，一旦遇到顶点B就终止。由此所得广度优先生成树上，从根顶点A到顶点B的路径就是中转次数最少的路径，路径A与B之间的顶点就是途径的中转站数。

本节将讨论带权有向图，并称路径上的第一个顶点为源点(Sourse)，最后一个顶点为终点(Destination)。

从某个源点到其余各顶点的最短路径

迪杰斯特拉算法

首先，引进一个辅助向量D，它的每个分量D[i]表示当前所找到的从始点v到每个终点$v_i$的最短路径的长度。他的初态为：若从v到$v_i$有弧，则D[i]为弧上的权值；否则置D[i]为$\infty$。显然，长度为$D[j] = Min{D[i] | v_i \in V}$的路径就是从v出发的长度最短的一条，此路径为$(v, v_j)$

一般情况下，假设S为已求得最短路径的终点的集合，则可证明：下一条最短路径(设其终点为x)或者是弧(v,x)，或者是中间只经过S中的顶点而最后到达顶点x的路径。

因此在一般情况下，下一条长度次短的最短路径的长度必是：$D[j] = Min{D[i] | v_i /in V - S}$。其中，D[i]或者是弧$(v,v_i)$上的权值或者是$Dk$和弧$(v_k, v_i)$上的权值之和。

根据以上分析，可得到如下描述的算法：

假设用带权的邻接矩阵arcs来表示带权有向图，arcs[i][j]表示弧$(v_i,v_j)$上的权值。若$(v_i,v_j)$不存在，则置arcs[i][j]为$\infty$。S为已找到从v出发的最短路径的终点的集合，它的初始状态为空集。那么，从v出发到图上其余各顶点$v_i$可能达到的最短路径长度的初值为：$D[i] = arcs[Locate Vex(G, v)][i] v_i \in V$。
选择$v_j$，使得：$D[j] = Min{D[i] | v_i \in V-S }$。$v_j$就是当前求得的一条从v出发的最短路径的终点，令：$S = S \cup {j}$
修改从v出发到集合V-S上任一顶点$v_k$可达的最短路径长度。如果：D[j] + arcs[j][k] < D[k]。则修改D[k]为D[k] = D[j] + arcs[j][k]
重复2，3共n-1次。由此求得从v到图上其余各顶点的最短路径是依路径长度递增的序列。

迪杰斯特拉算法时间复杂度$O(n^2)$

每一对顶点之间的最短路径

很简单的方法是每次以一个顶点为源点，重复执行迪杰斯特拉算法n次，这样便可求的每一对顶点之间的最短路径。时间复杂度为$O(n^3)$。

弗洛伊德算法：时间复杂度也是$O(n^3)$，形式上要简单一点。

弗洛伊德算法仍然从带权的邻接矩阵cost出发，其基本思想为：

现在定义一个n阶方阵序列
$D^{-1},D^{0},D^{1},…,D^{k},…,D^{(n-1)}$

其中
$D^{-1}[i][j] = G.arcs[i][j]$
$D^{(k)}[i][j] = Min\{D^{(k-1)}[i][j],D^{(k-1)}[i][k] + D^{(k-1)}[k][i]\} 0 \le k \le n-1$

理解要点：递归思想，根据公式理解

动态存储管理

动态存储管理的基本问题是系统如何应用户提出的‘请求’分配内存？又如何回收那些用户不再使用而‘释放’的内存，以备新的‘请求’产生时重新进行分配？

系统每次分配给用户都是一个地址连续的内存区。为了叙述方便起见，将统称已分配给用户使用的地址连续的内存区为‘占用快’，称未分配的地址连续的内存区为‘可利用空间块’或‘空闲块’。

当系统运行了一段时间后，内存区形成犬牙交错的形态，当有新的用户进入系统请求分配内存，那么系统应该如何做呢？

通常有两种做法：一种策略是系统继续从高地址的空闲块中进行分配，而不理会已分配给用户的内存区是否空闲，直到分配无法进行（即剩余的空间块不能满足分配的请求）时，系统才去回收所有用户不再使用的空闲块，并且重新组织内存，将所有空闲区连接在一起称为一个大的空闲块。另一种策略是用户一旦运行结束，便将它所占用的内存区释放为空闲块，同时，每当新的用户请求分配内存时，系统需要巡视整个内存区中所有空闲块，并从中找出一个‘合适’的空闲块分配之。由此，系统需建立一张记录所有空闲块的‘可利用空间表’，此表的结构可以是‘目录表’，也可以是‘链表’

可利用空间表及分配方法

下面仅讨论链表的情况

可以用空间表又称‘存储池’

根据系统的不同情况，可利用空间表可以有以下3种不同的结构形式：

系统运行期间所有用户请求分配的存储量大小相同。对此类系统，通常的做法是，在系统开始运行时将归它使用的内存区按所需大小分割成大小相同的块，然后用指针链接成一个可利用空间表。由于表中结点大小相同，则分配时无需查找，只要将第一个结点分配给用户即可；同样，当用户释放内存时，系统只要将用户释放的空间块插入在表头即可。可见，这种情况下的可利用空间表实质上是一个链栈。这是一种最简单的动态存储管理方式。
系统运行期间，用户请求分配的存储量有若干种大小的规格。对此类系统，一般情况下是建立若干个可利用空间表，同一链表中的结点大小相同。每个结点中第一个字设有链域(link)、标志域(tag)和结点类型域(type)
系统运行期间分配给用户的内存块的大小不固定，可以随请求而变。因此，可利用空间表中结点即空闲块的大小也是随意的。通常，操作系统中的可利用空间表属这种类型。由于链表中结点大小不同，则结点的结构与前两种情况也有所不同，结点中除标志域和链域之外，尚需有一个结点大小域(size)，以指示空闲块的存储量。假设某用户需大小为n的内存，而可利用空间表中仅有一块大小为$m ge n$的空间快，则只需将其中大小为n的一部分分配给申请分配的用户，同时将剩余大小为m-n的部分作为一个结点留在链表中即可。然而，若可利用空间表中有若干个不小于n的空闲块时，该分配哪一块呢？通常，可有3种不同的分配策略：
- 首次拟合法：从表头指针开始查找可利用空间表，将找到的第一个大小不小于n的空闲块的一部分分配给用户
- 最佳拟合法：将可利用空间表中一个不小于n且最接近n的空闲块的一部分分配给用户，为了节省时间，预先需要排序
- 最差拟合法：讲可利用空间表中不小于n且是链表中最大的空闲块的一部分分配给用户，为了节省时间，预先需要排序
  上述三种分配策略个有所长。一般来说，最佳拟合法适用于请求分配的内存大小范围较广的系统。最差拟合法适用于请求分配大小范围较窄的系统。首次拟合介于二者之间，通常适用于系统事先不掌握运行期间可能出现的请求分配和释放的信息的情况。

从时间上来说，首次拟合 < 最差拟合法 < 最佳拟合法

为了更有效的利用内存，就要求系统在回收时应考虑将地址相邻的空闲块合并成尽可能大的结点。

边界标识法

边界标识法(boundary tag method)是操作系统中用以进行动态分区分配的一种存储管理方法。

分配算法（首次拟合法）

假设找到的此块待分配的空闲块的容量为m个字，若每次分配只是从中分配n个字给用户，剩余m-n哥字大小的结点仍留在链表中，则在若干次分配后，链表中会出现一些容量极小总也分配不出去的空闲块，这就大大减慢了分配（查找）的速度。弥补的办法是：选定一个适当的常量e，当$m - n le e$时，就将容量为m的空闲块整块分配给用户；反之，只分配其中n个字的内存块。同时为了避免修改指针，约定将该结点中的高地址部分分配给用户。
如果每次分配都从同一个结点开始查找的话，势必造成存储量小的结点密集在头指针pav所指结点附近，这同样会增加查询较大空闲块的时间。反之，如果每次分配从不同的结点开始查找，使分配后剩余的小块均匀的分布在链表中
回收算法

一旦用户释放占用块，系统需要立即回收以备新的请求产生时进行再分配。为了使物理地址毗邻的空闲结合成一个尽可能大的结点，则首先需要检查刚释放的占用块的左，右紧邻是否为空闲块。由于本系统在每个内存区的边界上都设有标志值，则很容易辨明这一点。

若释放块的左右邻块均为占用块，则处理最为简单，只要将此新的空闲块作为一个结点插入到可利用空闲表即可；若只有左邻区是空闲块，则应与左邻区合并成一个结点；若是只有右邻区是空闲块，则应与右邻区合并成一个结点；左右邻区都是空闲块，则应将3块合起来称为一个结点留在可利用空间表中。

伙伴系统

伙伴系统(buddy system)是操作系统中用到的另一种动态存储管理方法。它和边界标识法类似，在用户提出申请时，分配一块‘恰当’的内存区给用户；反之，在用户释放内存区时即回收。所不同的是：在伙伴系统中，无论是占用块或空闲块，其大小均为2的k次幂。

可利用空间表的结构

假设系统的可利用内存空间容量为$2^m$个字（地址从0到$2^m - 1$）。则在开始运行时，整个内存区是一个大小为$2^m$的空闲块，在运行一段时间后，被分割成若干占用块和空闲快。为了再分配时查找方便起见，我们将所有大小相同的空闲块建于一张子表中。每个子表是一个双重链表，这样链表可能有m+1个，将这m+1个表头指针用向量结构组织成一个表，这就是伙伴系统中的可利用空间表。

分配算法

当用户提出大小为n的内存请求时，首先在可利用标上寻找结点大小与n相匹配的子表，若此子表非空，则将子表中任意一个结点分配之即可；若此子表为空，则需从结点更大的非空子表中去查找，直至找到一个空闲块，则将其中一部分分配给用户，而将剩余部分插入相应的子表中。

回收算法

在分配的时候经常需要将一个大的空闲块分裂成两个大小相等的存储区，这两个由同一个大块分裂出来的小块就称之‘互为伙伴’。

思路是，内存按照2的倍数划分，如果两个空闲内存分别处于两个不同的2的同倍区间，则不能合并

无用单元回收

有时，系统在不恰当的时候没有进行回收，会产生‘无用单元’和‘悬挂访问’

1 2	p = malloc(size); p = null;

上述为无用单元

1
2
3

p = malloc(size);
q = p;
free(p);

上述为悬挂访问

结构性问题也会产生‘无用单元’，解决方案：

使用访问计数器：在所有的广义表或字表中增加一个表头结点，并设立一个‘计数域’，它的值为指向该子表或广义表的指针数目。只有当该计数域的值为零时，此子表或广义表中结点才被释放。
收集无用单元：在程序运行过程中，对所有的链表结点，不管它是否还有用，都不回收，直到整个可利用空间表为空。此时才暂时中断执行程序，将所有当前不被使用的结点链接在一起，称为一个新的可利用空间表，而后程序再继续执行。显然在一般情况下，是无法辨别哪些结点是当前未被使用的。然而，对于一个正在运行的程序，哪些结点正在使用是容易查明的，这只要从所有当前正在运行的程序，哪些结点正在使用是容易查明的，这只要从所有当前正在工作的指针变量出发，顺链遍历，那么，所有链结在这些链上的结点都是占用的。反之，可利用存储空间中的其余结点就都是无用的了。由此，收集无用单元应分两步进行：第一步是对所有占用结点加上标志。回顾第五章的广义表存储结构可在每个结点上再加设一个标志（mark）域，假设在无用单元收集之前所有结点的标志域均置为‘0’，则加上标志就是将结点的标志域置为‘1’；第二步是对整个可利用存储空间顺序扫描一遍，将所有标志域为’0‘的结点链接成一个新的可利用空间表。值得注意的是：上述第二步是容易进行的，而第一步是在极其困难的条件下进行的，因此，人们的精力主要集中在研究标志算法上。下面我们介绍3中标志算法。

标志算法

递归算法：从上面所述可知，加标志的操作实质上是遍历广义表，将广义表中所有结点的标志域赋值‘1’。我们可以写出遍历（加标志）算法的递归定义。这个算法很简单，易于用允许递归的高级语言描述之。但是，它需要一个较大的实现递归用的栈的辅助内存，这部分内存不能用于动态分配。并且，由于列表的层次不定，使得栈的容量不容易确定，除非是在内存区开辟一个相当大的区域留作栈，否则就有可能由于在标志过程中因栈的溢出而使系统瘫痪。
非递归算法：前序遍历二叉树思想（深度优先搜索），广度有优先搜索。这两种非递归算法中，虽然附设的栈或队列的容量比递归算法中的栈容量小，但和递归算法有同样的问题，仍需要一个不确定量的附加存储，因此也不是理想的方法。
利用表结点本身的指针域标记遍历路径的算法：利用指针变换可以解决内存占用问题

三种方法个有利弊。第三种方法进行标志的时候不需要附加存储，使得动态分配的可利用空间得到充分利用，但是时间上开销很大。第二种方法操作简单，时间上要节省很多，然而需要占有一定空间，使动态分配所有的存储量减少。总之，无用单元的收集是很费时间的，不能在实时处理的情况下应用。

可利用内存区只有少量结点为无用结点时，收集无用单元的工作效率很低，当系统回复运行的时候，这些结点又很快被消耗掉，导致另一次无用单元的收集。如此下去有可能导致恶性循环，以致最后整个系统瘫痪。解决的办法可以由系统事先确定一个常数k，当收集到的无用单元数为k或更少时，系统就不再运行下去。

存储紧缩

另一种结构的动态存储管理方法

在整个动态存储管理的过程中，不管在哪个时刻，可利用空间都是一个地址连续的存储区，在编译程序中称之为‘堆’，每次分配都是从这个可利用空间中划出一块。但是回收用户释放的空闲块就比较麻烦。由于系统的可利用空间始终是一个地址连续的存储块，因此回收时必须将所释放的空闲块合并到整个堆上去才能重新使用，这就是‘存储紧缩’的任务。需要四步操作：

计算占用块的新地址
修改用户的初始变量表
检查每个占用块中存储的数据
将所有占用块迁移到新地址去

可见，存储紧缩法比无用单元收集法更为复杂，前者不仅要传送数据，而且还要修改所有占用块中的指针值，因此，存储紧缩也是一个系统操作，且非迫不得已就不用。

查找

查找表(Search Table)：是由同一类型的数据元素（或记录）构成的集合。由于‘集合’中的数据元素之间存在着完全松散的关系，因此查找表是一种非常灵便的数据结构。

对查找表经常进行的操作有：

查询某个‘特定的’数据元素是否在查找表中
检索某个‘特定的’数据元素的各种属性
在查找表中插入一个数据元素
查找表中删去某个数据元素

若对查找表只作前两种统称为‘查找’的操作，则称此类查找表为静态查找表(Static Search Table)。若存在后两种操作，称为动态查找表(Dynamic Search Table)。

关键字(Key)：数据元素（或记录）中某个数据项的的值，用它可以标识（识别）一个数据元素（或记录）。若此关键字可以唯一地标识一个记录，则称此关键字为主关键字(Primary Key)(对不同的记录，其主关键字均不同)。反之，称用以识别若干记录的关键字为次关键字(Secondary Key)

查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值记录或数据元素。若表中存在这样一条记录，则称查找是成功的，此时查找的结果为给出整个记录的信息，或指示该记录在查找表中的位置；若表中不存在关键字等于给定值的记录，则称查找不成功，此时查找的结果可给出一个‘空’记录或‘空’指针

静态查找表

顺序表的查找

顺序查找(Sequential Search)的查找过程为：从表中最后一个记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录，反之，若直至第一个记录，其关键字和给定值比较都不等，则表明表中没有所查记录，查找不成功。

查找操作的性能分析

定义：为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度(Average Search Length)。

公式：$ASL = \sum_{i=1}^n P_iC_i$ 其中：$P_i$为查找表中第i个记录的概率，且$\sum_{i=1}^n P_i = 1$。

$ASL_{ss} = \frac{n+1}{2}$

有序表的查找

折半查找(Binary Search)：先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到记录为止。

$ASL_{bs} = log_2(n+1) - 1$

可见，折半查找的效率比顺序查找高，但折半查找只适用于有序表，且限于顺序存储结构

以有序表表示静态查找表时，进行查找的方法除折半查找之外，还有斐波那契查找和插值查找。

斐波那契查找的平均性能比折半查找好，但最坏情况下的性能却比折半查找差。它还有一个优点就是分割的时候只需进行加，减运算

插值查找只适用于关键字分布均匀的表，在这种情况下，对表长较大的顺序表，其平均性能比折半查找好。

静态树表的查找

当有序表中各记录的查找概率不等时，如果只考虑查找成功的情况，则使查找性能最佳的判定树是其带权内路径长度之和PH值(PH值和平均查找长度成正比)：

$PH = \sum_{i=1}^n w_i h_i$

取最小值的二叉树。其中：n为二叉树上结点的个数（即有序表的长度）；$h_i$为第i个结点在二叉树上的层次数；结点的权$w_i = cp_i(i = 1,2…,n)$。其中$p_i$为结点的查找概率，c为某个常量。称PH值取最小的二叉树为静态最优查找树(Static Optimal Search)。静态最优查找树花费的时间代价较高，因此不做详细讨论。在此介绍一种构造近似最优查找数的有效算法。

已知一个按关键字有序的记录序列

$(r_l, r_{l+1}, … , r_h$ （9-8）

其中：$r_{l}.key < r_{l+1}.key < … < r_{h}.key$

与每个记录相应的权值为：${w_{l},w_{l+1}, … , w_{h}}$

现构造一棵二叉树，使这棵二叉树的带权内路径长度PH值在所有具有同样权值的二叉树中近似为最小，称这类二叉树为次优查找树(Nearly Optimal Search Tree)。

构造次优查找树的方法是：首先在式(9-8)所示的记录序列中取第i($l \le i \le h$)个记录构造根结点$r_i$，使得：

$\Delta P_{i} = | \sum_{j=i+1}^h w_j - \sum_{j=l}^{i-1} w_j|$

取最小值($\Delta P_{i} = min{\Delta P_{j}}, l \le j \le h$)，然后分别对子序列$(r_l, r_{l+1}, … , r_{i-1}$ 和$(r_{i+1}, … , r_{h}$ 构造两棵次优查找树。分别设为根结点$r_i$的左子树和右子树。

为了便于计算$\Delta P$，引入累计权值和：$sw_i = \sum_{j=l}^i w_j$，并设$w_{l-1} = 0$，则：

$\Delta P_{i} = |(sw_h + sw_{l-1}) - sw_i - sw_{i-1}|$

由此可得构造次优查找树的递归算法。

大量的实验研究表明，次优查找树和最优查找树的查找性能之差仅为1%-2%，很少超过3%，而且构造次优查找树的算法时间复杂度为O(nlogn)。

可见，在记录的查找概率不等时，可用次优查找树表示静态查找树，故又称静态树表。

索引顺序表的查找

索引项组成的索引表按关键字有序，则确定块的查找可以用顺序查找，亦可用折半查找，而块中记录是任意排列的，则在块中只能是顺序查找。由此，分块查找的算法即为两种算法的简单合成

$ASL_{bs} = L_b + L_w$

其中$L_b$为查找索引表确定所在块的平均查找长度。$L_w$为在块中查找元素的平均长度。

一般情况下，为进行分块查找，可以将长度为n的表均匀的分成b块，每块含有s个记录，即$b = \lceil n/s \rceil$；又假定表中每个记录的查找概率相等，则每块查找的概率为1/b，块中的每个记录的查找概率为1/s。

若用顺序查找确定所在块，则平均查找长度为：$ASL_{bs} = \frac{1}{2}(\frac{n}{s} + s) + 1$

若用折半查找确定所在块，则分块查找的平均查找长度为：$ASL_{bs} = log_{2}(\frac{n}{s} + 1) + \frac{s}{2}$

动态查找表

动态查找表的特点就是，表结构本身是在查找过程中动态生成的，即对于给定值key，若表中存在其关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录。

二叉排序树和平衡二叉树

假设i个关键字小于第一个关键字：
平均查找长度：$P(n,i) = 1 \frac n [1 + i*(P(i) + 1) + (n - i -1)(P(n-i-1)+1)]$
其中P(i)为含有i个结点的二叉排序树的平均查找长度，则P(i)+1为查找左子树中每个关键字所用比较次数的平均值

对上式取平均值：当$n ge 2$时，$ P(n) le 2(1 + 1 /frac n)lnn $

由此可见，在随机的情况下，二叉排序树的平均查找长度和logn是等数量级的，然而在某些情况下（概率约为46.5%），尚需在构成二叉排序树的过程中进行‘平衡化’处理，称为二叉平衡树。

平衡二叉树

平衡二叉树(Balanced Binary Tree)又称AVL树。它或者是一颗空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差绝对值不超过1。若将二叉树上结点的平衡因子BF(Blance Factor)定义为该节点的左子树的深度减去该节点的右子树的深度，则平衡二叉树上所有的平衡因子只可能是-1，0和1。

二叉排序树构成平衡二叉树方法

单向右旋平衡处理
单向左旋平衡处理
双向旋转(先左后右)平衡处理
双向旋转(先右后左)平衡处理

平衡树查找分析：时间复杂度为O(logn)

B-树和B+树

B-树是一种平衡的多路查找树，它在文件系统中很有用。在此介绍这种树的结构及其查找算法

一棵m阶的B-树，或为空树，或为满足下列特性的m叉树：

树中每个结点至多有m棵子树
若根结点不是叶子结点，则至少有两棵子树
除根之外的所有非终端结点至少有$\lceil m/2 \rceil$棵子树
所有的非终端结点中包含下列信息数据：$(n, A_0, K_1, A_1, K_2, A_2, … , K_n, A_n)$
其中：$K_i(i=1, … ,n)$为关键字，且$K_i<K_{i+1}$;$A_i(i=1, … ,n)$为指向子树根结点的指针，且指针$A_{i-1}$所指子树中所有结点的关键字均小于$K_i$，$A_n$所指子树中所有结点的关键字均大于$K_n$。
所有叶子结点都出现在同一层次上，并且不带信息

由此可见，在B-树上进行查找的过程是一个顺时针查找结点和在结点关键字中进行查找的交叉进行过程

B-树查找分析
B-树上查找包含两种基本操作：1）在B-树中找结点。2）在结点中找关键字。
其中第一步是在磁盘上进行的，因此，在磁盘上进行查找的次数，即待查关键字所在结点再B-树上的层次数，是B-树查找效率的首要因素。

B+树

和B-树的差异

有n棵子树的结点中含有n个关键字
所有的叶子结点中包含了全部关键字信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接
所有的非终端结点可以看成是索引部分，结点中仅含有其子树中的最大(或最小)的关键字。

键树

键树又称数字查找树(Digital Search Trees)。它是一颗度>=2的树。

哈希表

哈希函数是一个映像，因此哈希函数的设定很灵活，只要使得任何关键字由此所得的哈希函数值都落在表长允许范围之内即可。
对不同的关键字可能得到同一哈希地址

内部排序

排序：将一个数据元素(或记录)的任意序列，重新排列成一个按关键字有序的序列。

假设$K_i = K_j$，且在排序前的序列中$R_i$领先于$R_j$。若在排序后的序列中$R_i$仍领先于$R_j$，则称所用的排序方法是稳定的。否则称排序方法是不稳定的。

内部排序：指的是待排序记录存放在计算机随机存储器中进行的排序过程

外部排序：指的是带排序记录数量很大，以致内存一次不能容纳全部记录。在排序过程中需要对外存进行访问的排序过程。

插入排序

直接插入排序

function insertSort(sqList){
  if(sqList.length === 0){
    return sqList
  }
  let newList = [sqList[0]]
  for (let i = 1; i < sqList.length; i++) {
    innerloop:
    for (let j = newList.length-1; j >=0 ; j--) {
      let newEle = sqList[i]
      let ele = newList[j]
      let leftArr = newList.slice(0,j+1)
      let rightArr = newList.slice(j+1, newList.length)
      if(newEle >= ele){
        newList = [].concat(leftArr, newEle, rightArr)
        break innerloop
      }
      if(j === 0 && newEle < ele){
        newList = [].concat(newEle, rightArr)
        break innerloop
      }
    }
  }
  return newList
}

#include <stdio.h>
int main()
{
    int a[]={98,76,109,34,67,190,80,12,14,89,1};
    int k=sizeof(a)/sizeof(a[0]);
    int j;
    for(int i=1;i<k;i++)//循环从第2个元素开始
    {
        if(a[i]<a[i-1])
        {
            int temp=a[i];
            for(j=i-1;j>=0 && a[j]>temp;j--)
            {
                a[j+1]=a[j];
            }
            a[j+1]=temp;//此处就是a[j+1]=temp;
        }
    }
    for(int f=0;f<k;f++)
    {
        printf("%d\n", a[f]);
    }
    return 0;
}

关键是第二个循环由后往前走，找到正确的位置必须跳出循环，时间复杂度是$O(n^2)$，注意c语言版本充分利用了原有空间！

折半插入排序
2-路插入排序

希尔排序
希尔排序(Shell’s Sort)又称‘缩小增量排序’(Diminishing Increment Sort)，它也是一种属插入排序类的方法，但在时间效率上较前几种排序方法有较大的改进

#include<stdio.h>
#include<math.h>
#define MAXNUM 10
void main()
{
    void shellSort(int array[],int n,int t);//t为排序趟数
    int array[MAXNUM],i;
    for(i=0;i<MAXNUM;i++)
        scanf("%d",&array[i]);
    shellSort(array,MAXNUM,(int)(log(MAXNUM+1)/log(2))); //排序趟数应为log2(n+1)的整数部分
    for(i=0;i<MAXNUM;i++)
        printf("%d ",array[i]);
    printf("\n");
}
 
//根据当前增量进行插入排序
void shellInsert(int array[],int n,int dk)
{
    int i,j,temp;
    for(i=dk;i<n;i++)//分别向每组的有序区域插入
    {
        temp=array[i];
        for(j=i-dk;(j>=i%dk)&&array[j]>temp;j-=dk)//比较与记录后移同时进行
            array[j+dk]=array[j];
        if(j!=i-dk)
            array[j+dk]=temp;//插入
    }
}
 
//计算Hibbard增量
int dkHibbard(int t,int k)
{
    return (int)(pow(2,t-k+1)-1);
}
 
//希尔排序
void shellSort(int array[],int n,int t)
{
    void shellInsert(int array[],int n,int dk);
    int i;
    for(i=1;i<=t;i++)
        shellInsert(array,n,dkHibbard(t,i));
}
 
//此写法便于理解，实际应用时应将上述三个函数写成一个函数。

var arr=[49,38,65,97,76,13,27,49,55,04];
var len = arr.length;
//分段缩小循环
for(var fraction = Math.floor(len/2); fraction>0; fraction = Math.floor(fraction/2)){
  //基础循环
  for(var i = fraction; i<len; i++){
    //分段排序循环
    for(var j = i - fraction; j >= 0 && arr[j] > arr[fraction+j]; j -= fraction){
      var temp = arr[j];
      arr[j] = arr[fraction+j];
      arr[fraction+j] = temp;
    }
  }
}
console.log(arr);

快速排序

藉由交换进行排序的方法

起泡排序

var arr=[49,38,65,97,76,13,27,49,55,04];

function BubbleSort(arr){
  for (let i = arr.length-1; i > 0; i--) {
    for (let j = 0; j < i; j++) {
      let cur = arr[j];
      let next = arr[j+1];
      if(cur > next){
        arr[j+1] = cur
        arr[j] = next
      }
    }
  }
  console.log(arr)
}

BubbleSort(arr)

快速排序

let arr = [1, 2, 9, 8, 78, 131, 38, 12]
function quickSort(arr, left, right){
  let i = left;
  let j = right;
  let k = left;
  while (i < j) {
    while (arr[k] <= arr[j] && j > k) {
      j --
    }
    let temp = arr[k]
    arr[k] = arr[j]
    arr[j] = temp
    k = j
    while (arr[k] >= arr[i] && i < k) {
      i ++
    }
    temp = arr[k]
    arr[k] = arr[i]
    arr[i] = temp
    k = i
  }
  if((k - left) > 1){
    quickSort(arr, left, k-1)
  }
  if((right - k) > 1){
    quickSort(arr, k+1, right)
  }
}
quickSort(arr, 0, arr.length - 1)
console.log(arr)

快速排序平均性能最好，时间复杂度为O(nlogn)。缺点是占用栈空间，经过优化后空间复杂度可以为O(logn)

选择排序

简单选择排序
树形选择排序

堆排序

/**
*AuthorJenaszhang
*/
Array.prototype.buildMaxHeap = function(){
  for(var i = Math.floor(this.length/2)-1 ; i>=0 ; i--){
    this.heapAdjust(i, this.length);
  }
};
   
Array.prototype.swap = function(i,j){
  var tmp = this[i];
  this[i] = this[j];
  this[j] = tmp; 
};
   
Array.prototype.heapSort=function(){
  this.buildMaxHeap();
  for(var i = this.length-1;i>0;i--){
    this.swap(0,i);
    this.heapAdjust(0,i);
  }
   
  return this;
};
   
Array.prototype.heapAdjust=function(i,j){
  var largest=i;
  var left=2*i+1;
  var right=2*i+2;
   
  if(left<j && this[largest] < this[left]){
    largest = left;
  }
   
  if(right<j && this[largest] < this[right]){
    largest = right; 
  }
   
  if(largest!=i){
    this.swap(i,largest);
    this.heapAdjust(largest,j);
  }
};
   
var a=new Array();
[].push.apply(a,[2,3,89,57,23,72,43,105]);
console.log(a.heapSort());

归并排序

基本思路是，假设要排序的序列本来就是一个个有序数列，然后逐渐合并

归并排序是稳定的排序算法，实现归并排序需要等数量的辅助空间，时间复杂度为O(nlogn)

基数排序

基本思路是，按照关键码分组，由高到低是MSD，由低到高是LSD

基数排序(Radix Sorting)是完全不同的一种排序方法。

各种内部排序方法的比较讨论

排序方法平均时间最坏情况辅助存储

简单排序 $O(n^2)$ $O(n^2)$ O(1)
快速排序 O(nlogn) $O(n^2)$ O(logn)
堆排序 O(nlogn) O(nlogn) O(1)
归并排序 O(nlogn) O(nlogn) O(n)
基数排序 O(d(n + rd)) O(d(n + rd)) O(rd)

外部排序

外存信息的存取

计算机一般有两种存储器：内存储器(主存)和外存储器(辅存)。内存的信息可随机存储，且存取速度快，但价格贵，容量小。外存储器包括磁带和磁盘，前者为顺序存储设备，后者为随机存储设备。

归并排序
置换-选择排序

重要概念是，外存是必须要读到内存中进行排序的，外存读取速度慢，容量大

文件

有关文件的基本概念

文件及其类别：操作系统中的文件仅是一维的连续的字符序列，无结构，无解释。它也是记录的集合，这个记录仅仅是一个字符组，用户为了存取、加工方便，把文件中的信息划分称若干组，每一组信息称为一个逻辑记录，且可按顺序编号。数据库中的文件是带有结构的记录的集合；这类记录是由一个或多个数据项组成的集合；这类记录是由一个或多个数据项组成的集合，它也是文件中可存取的数据的基本单位。数据项是最基本的不可分的数据单位，也是文件中可使用的数据的最小单位。若文件中每个记录含有的信息长度相同，则称这类记录为定长记录，由这类记录组成的文件称做定长记录文件。若文件中含有信息长度不等的不定长记录，则称不定长记录文件。数据库文件还分为单关键字文件和多关键字文件。
记录的逻辑结构和物理结构：逻辑结构着眼于用户使用方便；物理结构应该考虑提高存储空间的利用率和减少存取记录的时间。一个物理记录是指计算机用一条I/O命令进行读写的基本数据单位。物理记录和逻辑记录的关系：一个物理记录存放一个逻辑记录；一个物理记录包含多个逻辑记录；多个物理记录表示一个逻辑记录。
文件的操作(运算)：文件的操作有两种，检索和修改。
文件检索的三种方式
1. 顺序存取
2. 直接存取
3. 按关键字存取
文件的物理结构：顺序组织，随机组织和链组织。一个特定的文件应才用何种物理结构应综合考虑各种因素：存储介质的类型、记录的类型、大小和关键字的数目以及对文件作何种操作等。

顺序文件

顺序文件：顺序文件是记录按其在文件中的逻辑顺序依次进入存储介质而建立的，即顺序文件中物理记录的顺序和逻辑记录的顺序是一致的

索引文件

索引文件：除了文件本身（称作数据区）之外，另建立一张指示逻辑记录和物理记录之间一一对应关系的表——索引表。这类包含文件数据区和索引表两大部分的文件称做索引文件。

ISAM文件和VSAM文件

索引顺序存取方法ISAM为 Indexed Sequential Access Methed 的缩写，它是一种专为磁盘存储设计的文件组织方式。由于磁盘是以盘组，柱面和磁道三级地址存取的设备，则可对磁盘上的数据文件建立盘组、煮面和磁道三级索引。

虚拟存储存取方法VSAM是Virtual Storage Access Method 的缩写。这种存取方法利用了操作系统的虚拟存储器的功能，给用户提供方便。

直接存取文件（散列文件）

直接存取文件指的是利用杂凑（Hash）法进行组织的文件。它类似于哈希表，即根据文件中关键字的特点设计一种哈希函数和处理冲突的方法将记录散列到存储设备上，故又称散列文件。

多关键字文件

多重表文件(Multilist File): 构造和修改都很容易，插入一个新纪录也很容易，但是删除一个记录很麻烦
倒排文件：次关键字中存放有序的物理记录，优点是查询方便，缺点是维护困难。

引子

绪论

第二章

第三章

第四章 串

第五章 数组和广义表

树和二叉树

赫夫曼树及其应用

图

动态存储管理

查找

内部排序

插入排序

快速排序

选择排序

归并排序

基数排序

各种内部排序方法的比较讨论

外部排序

外存信息的存取

文件

有关文件的基本概念

顺序文件

索引文件

ISAM文件和VSAM文件

直接存取文件（散列文件）

多关键字文件

第四章串

第五章数组和广义表