数据结构
数据结构
绪论
1.数据结构的研究内容
数据结构 (data structure)是带有结构特性的数据元素的集合，它研究的是 数据的逻辑结构和数据的物理结构以及它们之间的相互关系 ，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。
2.数据结构的相关概念和术语
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据结构包括三方面的内容：逻辑结构、存储结构和数据的运算。数据的逻辑结构和存储结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。
2.1数据逻辑结构
数据的逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。它与数据的具体存储形式无关，是独立于计算机的。数据逻辑结构通常分为线性结构和非线性结构。典型的数据结构与其逻辑结构的对应关系如下：
对于线性表、集合、树、图这四种典型的数据结构，他们分别有以下特点：\
集合结构：数据元素之间只存在 “同属于一个集合”的关系。
线性结构：数据元素之间只存在“一对一”的关系。
树形结构：数据元素之间存在“一对多”的关系。
图状结构或网状结构：数据元素之间存在“多对多”的关系。\
2.2数据存储结构
数据的存储结构指的是数据结构在计算机中的表示，也称为物理结构，又称映像。它包括数据元素的表示和关系的表示。数据存储结构依赖于计算机语言，它是用计算机语言实现的逻辑结构。数据的线性存储结构主要有：顺序存储、链式存储、索引存储、散列存储。
1> 顺序存储：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元里，元素之间的关系由存储单元之间的位置关系，即相邻关系来体现。如顺序表。
优点：容易实现随机存取，每个元素占用最少的存储空间。
缺点：只能使用相邻的一整块存储空间，容易产生较多的外部内存碎片。
2> 链式存储：使用表示元素存储地址的指针来表示元素之间的逻辑关系，此时不要求逻辑上相邻的数据元素在物理位置上也相邻。如单链表。
优点：不会出现碎片内存，能充分利用存储单元。
缺点：每个元素由于存储指针而占用额外的存储空间，且只能通过遍历实现顺序存取。
3> 索引存储：在存储数据元素的同时，建立一个附加的索引表。索引表中的每一项称为索引项项，其形式通常为(关键字，地址)。
优点：检索速度快。
缺点：附加的索引表会占用额外的存储空间。在添加或者删除数据元素时，需要同步修改索引表，因此会花费额外的时间。
4> 散列存储：根据元素的关键字以某种方式计算出该元素的存储地址，又称为 hash 存储。如哈希表。
优点：检索、添加、删除的操作速度都很快。
缺点：如果散列函数(或者 hash 函数)设计不好的话，可能会出现 hash 冲突，解决冲突又会增加时间和空间开销。
而数据的非线性存储结构主要有：树形存储、图形存储。
2.3数据的运算
数据的运算主要体现为运算的定义，以及运算的实现。
运算的定义是针对数据逻辑结构的，它描述了运算所能实现的功能。
运算的实现是针对数据存储结构的，它描述了运算的具体操作过程。\
3.算法的概念与特征
算法的定义是：算法是解决特定问题的求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。
算法的特征包括：有穷性、确定性、输入、输出、可行性。
有穷性：一个算法必须总在执行的有穷步之后结束，每一步都可在有穷时间内完成，不会无限循环。
确定性：算法中每条指令必须有确定的含义。
输入：一个算法有零个或多个输入，以刻画运算对象的初始情况，所谓零个输入是指算法本身给定了初始条件。
输出：一个算法有一个或多个输出。没有输出的算法毫无意义。
可行性：一个算法的任何计算步骤都是可以被分解为基本可执行的操作，每个操作都能够在有限时间内完成。\
4.算法效率的度量指标
算法效率的度量指标用算法编制的程序在计算机上运行所消耗的时间和所额外开辟的内存空间来度量，分别称作算法的时间复杂度和算法的空间复杂度。二者通常用大O符号表示，通常称为大O表示法。表示的是，随着数据规模的增加运行时间的增长情况和额外开辟内存空间的增长情况。\
5.时间复杂度与空间复杂度的计算方法
算法在最好情况下的时间复杂度为最好时间复杂度，指的是算法计算量可能达到的最小值；称算法在最坏情况下的时间复杂度为最坏时间复杂度，指的是算法计算量可能达到的最大值；算法的平均时间复杂度是指算法在所有可能情况下，按照输入实例以等概率出现时，算法计算量的加权平均值。\
6.常见时间复杂度类型与性能优劣比较
O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)\
其中，O(1)表示常数时间复杂度，O(log n)表示对数时间复杂度，O(n)表示线性时间复杂度，O(n log n)表示线性对数时间复杂度，O(n^2)表示平方时间复杂度，O(2^n)表示指数时间复杂度，O(n!)表示阶乘时间复杂度。\
线性表
栈和队列
串
数组和广义表
树和二叉树
1.树的定义和基本术语
1.1树的定义
树(Tree)是n(n≥0)个结点的有限集，它或为空树(n=0)；或为非空树，对于非空树T：(1)有且仅有一个称之为根的结点；(2)除根结点以外的其余结点可分为m(m>0)个互不相交的有限集T1, T2, …,$T_m$,其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)。\
1.2树的基本术语
(1)结点：树中的一个独立单元。包含一个数据元素及若干指向其子树的分支，如图中的A、B、C、D等。
(2)结点的度：结点拥有的子树个数称为结点的度。例如，A的度为3，C的度为1，F的度为0。
(3)树的度：树的度是树内各结点度的最大值。图所示的树的度为3。
(4)叶子：度为0的结点称为叶子或终端结点。结点K、L、F、G、M、I、J都是树的叶子。
(5)非终端结点：度不为0的结点称为非终端结点或分支结点。除根结点之外，非终端结点也称为内部结点。
(6)双亲和孩子：结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。例如，B的双亲为A，B的孩子有E和F。
(7)兄弟：同一个双亲的孩子之间互称兄弟。例如，H、I和J互为兄弟。
(8)祖先：从根到该结点所经分支上的所有结点。例如，M的祖先为A、D和H。
(9)子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。如B的子孙为E、K、L和F。
(10)层次：结点的层次从根开始定义起，根为第一层，根的孩子为第二层。树中任一结点的层次等于其双亲结点的层次加1。
(11)堂兄弟：双亲在同一层的结点互为堂兄弟。例如，结点G与E、F、H、I、J互为堂兄弟。
(12)树的深度：树中结点的最大层次称为树的深度或高度。图所示的树的深度为4。
(13)有序树和无序树：如果将树中结点的各子树看成从左至右是有次序的(即不能互换)，则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。
(14)森林：是m(m≥0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。由此，也可以用森林和树相互递归的定义来描述树。\
1.3树的性质
(1)树中的节点数等于所有结点的度数加1
(2)度为m的树中第i层上至多有$m^{i-1}$个节点
(3)高度为h的m叉树至多有$\frac{m^h-1}{m-1}$个结点
(4)具有n结点的m树的最小高度为$\vert \log_m^{n*(m-1)+1}\vert$
(5)具有n个结点的树的总边数为n-1条\
常用的三个等式：
设总边数为L，总节点数为N，$n_i$表示度为i的结点的个数。
等式一：L = N - 1
等式二：L = $0n_0+1n_1+2n_2+…+in_i$
等式三：N = $n_0+n_1+n_2+…+n_i$\
2.二叉树的定义
二叉树(Binary Tree)是n(n≥0)个结点所构成的集合，它或为空树(n=0)；或为非空树，对于非空树T：
(1)有且仅有一个称之为根的结点；
(2)除根结点以外的其余结点分为两个互不相交的子集T1和T2，分别称为T的左子树和右子树，且T1和T2本身又都是二叉树。
二叉树与树一样具有递归性质，二叉树与树的区别主要有以下两点：
(1)二叉树每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点)；
(2)二叉树的子树有左右之分，其次序不能任意颠倒。\
3.二叉树的性质
二叉树具有下列重要特性：
性质1 在二叉树的第i层上至多有2i−1个结点(i≥1)。
性质2 深度为k的二叉树至多有2k−1个结点(k≥1)。
性质3 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
性质4 具有n个结点的完全二叉树的深度为$\lfloor\log_2^{n}\rfloor+1$。($\lfloor\rfloor$表示向下取整)
性质5 如果对一棵有n个结点的完全二叉树(其深度为$\lfloor\log_2^{n}\rfloor+1$)的结点按层序编号(从第1层到第$\log_2^{n}+1$层，每层从左到右)，则对任一结点i(1≤i≤n)，有:
(1)如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲PARENT(i)是结点i/2。
(2)如果2i>n，则结点i无左孩子(结点i为叶子结点)；否则其左孩子LCHILD(i)是结点2i。
(3)如果2i+1>n，则结点i无右孩子；否则其右孩子RCHILD(i)是结点2i+1。\
常用的三个等式：
设总边数为L，总节点数为N，$n_i$表示度为i的结点的个数。
等式一：L = N - 1
等式二：L = $0n_0+1n_1+2*n_2$
等式三：N = $n_0+n_1+n_2$\
具有N个节点的二叉树有$\frac{(2N)!}{(N+1)!N!}$种形态。
4.满二叉树
深度为k且含有2k−1个结点的二叉树，且每一层上的结点数都是最大结点数，即每一层i的结点数都具有最大值$2^{i−1}$。
5.完全二叉树
深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。
完全二叉树的特点是：
(1)叶子结点只可能在层次最大的两层上出现；
(2)对任一结点，若其右分支下的子孙的最大层次为l，则其左分支下的子孙的最大层次必为l或l+1\
6.二叉树的存储结构
6.1 顺序存储结构
顺序存储结构使用一组地址连续的存储单元来存储数据元素。利用二叉树的性质5来匹配位置索引和值。例如，1号索引为根节点，则其左孩子节点索引为2，右孩子节点索引为3，以此类推。
顺序存储结构适合存储完全二叉树，因为每一个空间元素都被利用起来了。\
6.2 链式存储结构
如图所示：
7.遍历二叉树
三种遍历方式，根左右，左根右，左右根。
8.线索二叉树
如图所示：
二叉树的线索化，分为三类，先序线索二叉树，中序线索二叉树，后续线索二叉树。即为分别按照相应的遍历方式得到的线索二叉树。
9.树的存储结构
9.1双亲表示法
9.1孩子表示法
9.1孩子兄弟表示法
10.树与二叉树的转换
树转二叉树：将兄弟结点相连，保留最左侧第一个子节点与根节点相连，其他子节点与根节点断开。重复每一个子树以上行为。最后变形即可。
11.森林与二叉树的转换
森林转二叉树：将森林中的每个树转化为二叉树，再将转化的二叉树以此放在二叉树的右子树上。
二叉树转森林：过程与森林转二叉树相反。\
12.树和森林的遍历
12.1 树的遍历
由树结构的定义可引出两种次序遍历树的方法：一种是先根(次序)遍历树，即：先访问树的根结点，然后依次先根遍历根的每棵子树；
另一种是后根(次序)遍历，即先依次后根遍历每棵子树，然后访问根结点。\
12.2 森林的遍历
按照森林和树相互递归的定义，可以推出森林的两种遍历方法：先序遍历和中序遍历。\
(1)先序遍历森林若森林非空，则可按下述规则遍历：① 访问森林中第一棵树的根结点；② 先序遍历第一棵树的根结点的子树森林；③ 先序遍历除去第一棵树之后剩余的树构成的森林。
(2)中序遍历森林若森林非空，则可按下述规则遍历：① 中序遍历森林中第一棵树的根结点的子树森林；② 访问第一棵树的根结点；③ 中序遍历除去第一棵树之后剩余的树构成的森林。\
12.3 与遍历二叉树的关系
13.最优二叉树(赫夫曼树)
哈夫曼(Huffman)树又称最优树，是一类带权路径长度最短的树。
定义：假设有m个权值{w1, w2,…, wm}，可以构造一棵含n个叶子结点的二叉树，每个叶子结点的权为wi，则其中带权路径长度WPL最小的二叉树称做最优二叉树或哈夫曼树。
路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。
路径长度：路径上的分支数目称作路径长度。
树的路径长度：从树根到每一结点的路径长度之和。
权：赋予某个实体的一个量，是对实体的某个或某些属性的数值化描述。在数据结构中，实体有结点(元素)和边(关系)两大类，所以对应有结点权和边权。结点权或边权具体代表什么意义，由具体情况决定。如果在一棵树中的结点上带有权值，则对应的就有带权树等概念。
结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积。
树的带权路径长度：树中所有叶子结点的带权路径长度之和。\
性质：
(1)一棵有n个叶子结点的哈夫曼树共有2n-1个结点。
14.赫夫曼编码
图
1.定义
图(Graph)G由两个集合V和E组成，记为G=(V, E)，其中V是顶点的有穷非空集合，E是V中顶点偶对的有穷集合，这些顶点偶对称为边。V(G)和E(G)通常分别表示图G的顶点集合和边集合，E(G)可以为空集。若E(G)为空，则图G只有顶点而没有边。
对于图G，若边集E(G)为有向边的集合，则称该图为有向图；若边集E(G)为无向边的集合，则称该图为无向图。
在有向图中，顶点对<x，y>是有序的，它称为从顶点x到顶点y的一条有向边。因此，<x，y>与<y，x>是不同的两条边。顶点对用一对尖括号括起来，x是有向边的始点，y是有向边的终点。<x，y>也称作一条弧，则x为弧尾，y为弧头。
在无向图中，顶点对(x, y)是无序的，它称为与顶点x和顶点y相关联的一条边。这条边没有特定的方向，(x, y)与(y, x)是同一条边。为了有别于有向图，无向图的顶点对用一对圆括号括起来。\
图1 图的示例
2.图的基本术语
(1)子图：假设有两个图G=(V, E)和G′=(V′, E′)，如果V′′V且E′′ E，则称G′为G的子图。
图2 子图的示例
(2)无向完全图和有向完全图：对于无向图，若具有n(n−1)/2条边，则称为无向完全图。对于有向图，若具有n(n−1)条弧，则称为有向完全图。
简单理解为：每一个点都有边与其他的点相连。
(3)稀疏图和稠密图：有很少条边或弧(如e<$n{log_2^{n}}$)的图称为稀疏图，反之称为稠密图。
(4)权和网：在实际应用中，每条边可以标上具有某种含义的数值，该数值称为该边上的权。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网。
(5)邻接点：对于无向图G，如果图的边(v, v′)∈E，则称顶点v和v′互为邻接点，即v和v′相邻接。边(v, v′)依附于顶点v和v′，或者说边(v, v′)与顶点v和v′相关联。
(6)度、入度和出度：顶点v的度是指和v相关联的边的数目，记为TD(v)。例如，图1中G2的顶点v3的度是3。对于有向图，顶点v的度分为入度和出度。
入度是以顶点v为头的弧的数目，记为ID(v)；
出度是以顶点v为尾的弧的数目，记为OD(v)。顶点v的度为TD(v)=ID(v)+OD(v)。
例如，图1中G1的顶点v1的入度ID(v1)=1，出度OD(v1)=2，度TD(v1)=ID(v1)+OD(v1)=3。
一般地，如果顶点vi的度记为TD(vi)，那么一个有n个顶点，e条边的图，满足如下关系：$\frac{1}{2}\sum_{i=1}^{n}{TD(v_i)}$\
(7)路径和路径长度：在无向图G中，从顶点v到顶点v′的路径是一个顶点序列(v=vi,0, vi,1,…, vi,m=v′)，其中(vi,j−1, vi,j)∈E，1≤j≤m。如果G是有向图，则路径也是有向的，顶点序列应满足<vi,j−1,vi,j>∈E, 1≤j≤m。路径长度是一条路径上经过的边或弧的数目。
(8)回路或环：第一个顶点和最后一个顶点相同的路径称为回路或环。
(9)简单路径、简单回路或简单环：序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。
(10)连通、连通图和连通分量：在无向图G中，如果从顶点v到顶点v′有路径，则称v和v′是连通的。如果对于图中任意两个顶点$v_i$、$v_j$∈V，$v_i$和$v_j$都是连通的，则称G是连通图。图1中的G2就是一个连通图，而图3(a)中的G3则是非连通图，但G3有3个连通分量，如图3(b)所示。所谓连通分量，指的是无向图中的极大连通子图。
图3 无向图及其连通分量
(11)强连通图和强连通分量：在有向图G中，如果对于每一对$v_i$,$v_j$∈V, $v_i$≠$v_j$，从$v_i$到$v_j$和从$v_j$到$v_i$都存在路径，则称G是强连通图。有向图中的极大强连通子图称作有向图的强连通分量。例如图1(a)中的G1不是强连通图，但它有两个强连通分量，如图4所示。
图4 G1的两个强连通分量
(12)连通图的生成树：一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n−1条边，这样的连通子图称为连通图的生成树。图5所示为G3中最大连通分量的一棵生成树。如果在一棵生成树上添加一条边，必定构成一个环，因为这条边使得它依附的那两个顶点之间有了第二条路径。
图5 G3的最大连通分量的一颗生成树
(13)有向树和生成森林：有一个顶点的入度为0，其余顶点的入度均为1的有向图称为有向树。一个有向图的生成森林是由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。图6.6所示为其一例。
图6 一个有向图及其生成森林
3.图的存储结构
3.1邻接矩阵表示法
(1)优点
① 便于判断两个顶点之间是否有边，即根据A[i][j]=0或1来判断。
② 便于计算各个顶点的度。对于无向图，邻接矩阵第i行元素之和就是顶点i的度；对于有向图，第i行元素之和就是顶点i的出度，第i列元素之和就是顶点i的入度。
(2)缺点
① 不便于增加和删除顶点。
② 不便于统计边的数目，需要扫描邻接矩阵所有元素才能统计完毕，时间复杂度为O(n2)。
③ 空间复杂度高。如果是有向图，n个顶点需要n2个单元存储边。如果是无向图，因其邻接矩阵是对称的，所以对规模较大的邻接矩阵可以采用压缩存储的方法，仅存储下三角(或上三角)的元素，这样需要n(n−1)/2个单元即可。但无论以何种方式存储，邻接矩阵表示法的空间复杂度均为O(n2)，这对于稀疏图而言尤其浪费空间。\
3.2邻接表表示法
(1)优点
① 便于增加和删除顶点。
② 便于统计边的数目，按顶点表顺序扫描所有边表可得到边的数目，时间复杂度为O(n+e)。
③ 空间效率高。对于一个具有n个顶点e条边的图G，若G是无向图，则在其邻接表表示中有n个顶点表结点和2e个边表结点；若G是有向图，则在它的邻接表表示或逆邻接表表示中均有n个顶点表结点和e个边表结点。因此，邻接表或逆邻接表表示的空间复杂度为O(n+e)，适合表示稀疏图。对于稠密图，考虑到邻接表中要附加链域，因此常采取邻接矩阵表示法。
(2)缺点
① 不便于判断顶点之间是否有边，要判定vi和vj之间是否有边，就需扫描第i个边表，最坏情况下要耗费O(n)时间。
② 不便于计算有向图各个顶点的度。对于无向图，在邻接表表示中顶点vi的度是第i个边表中的结点个数。在有向图的邻接表中，第i个边表上的结点个数是顶点vi的出度，但求vi的入度较困难，需遍历各顶点的边表。若有向图采用逆邻接表表示，则与邻接表表示相反，求顶点的入度容易，而求顶点的出度较难。\
3.3十字链表表示法
3.4邻接多重表表示法
4.最小生成树
4.1普利姆算法
假设N=(V, E)是连通网，TE是N上最小生成树中边的集合。
① U={u0}(u0∈V)，TE={}。
② 在所有u∈U，v∈V−U的边(u, v)∈E中找一条权值最小的边(u0, v0)并入集合TE，同时v0并入U。
③ 重复②，直至U=V为止。此时TE中必有n−1条边，则T=(V, TE)为N的最小生成树。\
4.2克鲁斯卡尔算法
假设连通网N=(V, E)，将N中的边按权值从小到大的顺序排列。
① 初始状态为只有n个顶点而无边的非连通图T=(V, {})，图中每个顶点自成一个连通分量。
② 在E中选择权值最小的边，若该边依附的顶点落在T中不同的连通分量上(即不形成回路)，则将此边加入到T中，否则舍去此边而选择下一条权值最小的边。
③ 重复②，直至T中所有顶点都在同一连通分量上为止。\
5.最短路径
5.1迪杰斯特拉算法
对于网N=(V, E)，将N中的顶点分成两组：
第一组S：已求出的最短路径的终点集合(初始时只包含源点v0)。
第二组V−S：尚未求出的最短路径的顶点集合(初始时为V−{v0})。算法将按各顶点与v0间最短路径长度递增的次序，逐个将集合V−S中的顶点加入到集合S中去。在这个过程中，总保持从v0到集合S中各顶点的路径长度始终不大于到集合V−S中各顶点的路径长度。\
5.2弗洛伊德算法
将vi到vj的最短路径长度初始化，即D[i][j]=G.arcs[i][j]，然后进行n次比较和更新。
① 在vi和vj间加入顶点v0，比较(vi, vj)和(vi, v0, vj)的路径长度，取其中较短者作为vi到vj的中间顶点序号不大于0的最短路径。
② 在vi和vj间加入顶点v1，得到(vi,…, v1)和(v1,…, vj)，其中(vi,…, v1)是vi到v1的且中间顶点的序号不大于0的最短路径，(v1,…, vj)是v1到vj的且中间顶点的序号不大于0的最短路径，这两条路径已在上一步中求出。比较(vi,…, v1,…,vj)与上一步求出的vi到vj的中间顶点序号不大于0的最短路径，取其中较短者作为vi到vj的中间顶点序号不大于1的最短路径。
③ 依次类推，在vi和vj间加入顶点vk，若(vi,…, vk)和(vk,…, vj)分别是从vi到vk和从vk到vj的中间顶点的序号不大于k−1的最短路径，则将(vi,…, vk,…, vj)和已经得到的从vi到vj且中间顶点序号不大于k−1的最短路径相比较，其长度较短者便是从vi到vj的中间顶点的序号不大于k的最短路径。这样，经过n次比较后，最后求得的必是从vi到vj的最短路径。按此方法，可以同时求得各对顶点间的最短路径。\
6.拓扑排序
6.1AOV-网
一个无环的有向图称作有向无环图(Directed Acycline Graph)，简称DAG图。
用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网(Activity On Vertex Network)，简称AOV-网。
拓扑排序就是将AOV-网中所有顶点排成一个线性序列，该序列满足：若在AOV-网中由顶点vi到顶点vj有一条路径，则在该线性序列中的顶点vi必定在顶点vj之前。
拓扑排序过程：
(1)在有向图中选一个无前驱的顶点且输出它。
(2)从图中删除该顶点和所有以它为尾的弧。
(3)重复(1)和(2)，直至不存在无前驱的顶点。
(4)若此时输出的顶点数小于有向图中的顶点数，则说明有向图中存在环，否则输出的顶点序列即为一个拓扑序列。\
7.关键路径
与AOV-网相对应的是AOE-网(Activity On Edge)，即以边表示活动的网。AOE-网是一个带权的有向无环图，其中，顶点表示事件，弧表示活动，权表示活动持续的时间。通常，AOE-网可用来估算工程的完成时间。
8.总结
(1)根据不同的分类规则，图分为多种类型：无向图、有向图、完全图、连通图、强连通图、带权图(网)、稀疏图和稠密图等。邻接点、路径、回路、度、连通分量、生成树等是在图的算法设计中常用到的重要术语。
(2)图的存储方式有两大类：以边集合方式的表示法和以链接方式的表示法。其中，以边集合方式表示的为邻接矩阵，以链接方式表示的包括邻接表、十字链表和邻接多重表。邻接矩阵表示法借助二维数组来表示元素之间的关系，实现起来较为简单；邻接表、十字链表和邻接多重表都属于链式存储结构，实现起来较为复杂。在实际应用中具体采取哪种存储表示，可以根据图的类型和实际算法的基本思想进行选择。其中，邻接矩阵和邻接表是两种常用的存储结构，二者之间的比较如表
(3)图的遍历算法是实现图的其他运算的基础，图的遍历方法有两种：深度优先搜索遍历和广度优先搜索遍历。深度优先搜索遍历类似于树的先序遍历，借助于栈结构来实现(递归)；广度优先搜索遍历类似于树的层次遍历，借助于队列结构来实现。两种遍历方法的不同之处仅仅在于对顶点访问的顺序不同，所以时间复杂度相同。当用邻接矩阵存储时，时间复杂度为均O(n2)，用邻接表存储时，时间复杂度均为O(n+e)。
(4)图的很多算法与实际应用密切相关，比较常用的算法包括构造最小生成树算法、求解最短路径算法、拓扑排序和求解关键路径算法。
① 构造最小生成树有普里姆算法和克鲁斯卡尔算法，两者都能达到同一目的。但前者算法思想的核心是归并点，时间复杂度是O(n2)，适用于稠密网；后者是归并边，时间复杂度是O(elog2e)，适用于稀疏网。
② 最短路径算法：一种是迪杰斯特拉算法，求从某个源点到其余各顶点的最短路径，求解过程是按路径长度递增的次序产生最短路径，时间复杂度是O(n2)；另一种是弗洛伊德算法，求每一对顶点之间的最短路径，时间复杂度是O(n3)，从实现形式上来说，这种算法比以图中的每个顶点为源点n次调用迪杰斯特拉算法更为简洁。
③ 拓扑排序和关键路径都是有向无环图的应用。拓扑排序是基于用顶点表示活动的有向图，即AOV-网。对于不存在环的有向图，图中所有顶点一定能够排成一个线性序列，即拓扑序列，拓扑序列是不唯一的。用邻接表表示图，拓扑排序的时间复杂度为O(n+e)。
④ 关键路径算法是基于用弧表示活动的有向图，即AOE-网。关键路径上的活动叫做关键活动，这些活动是影响工程进度的关键，它们的提前或拖延将使整个工程提前或拖延。关键路径是不唯一的。关键路径算法的实现是在拓扑排序的基础上，用邻接表表示图，关键路径算法的时间复杂度为O(n+e)。\
查找
1.顺序查找
顺序查找(Sequential Search)的查找过程为：从表的一端开始，依次将记录的关键字和给定值进行比较，若某个记录的关键字和给定值相等，则查找成功；反之，若扫描整个表后，仍未找到关键字和给定值相等的记录，则查找失败。
顺序查找方法既适用于线性表的顺序存储结构，又适用于线性表的链式存储结构。
2.折半查找
折半查找(Binary Search)也称二分查找，它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
折半查找的查找过程为：从表的中间记录开始，如果给定值和中间记录的关键字相等，则查找成功；如果给定值大于或者小于中间记录的关键字，则在表中大于或小于中间记录的那一半中查找，这样重复操作，直到查找成功，或者在某一步中查找区间为空，则代表查找失败。
3.分块查找
分块查找(Blocking Search)又称索引顺序查找，这是一种性能介于顺序查找和折半查找之间的一种查找方法。
4.树表的查找
4.1二叉排序树
4.1.1二叉排序树的定义
二叉排序树(Binary Sort Tree)又称二叉查找树，它是一种对排序和查找都很有用的特殊二叉树。
二叉排序树的定义二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
(1)若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
(2)若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
(3)它的左、右子树也分别为二叉排序树。二叉排序树是递归定义的。由定义可以得出二叉排序树的一个重要性质：中序遍历一棵二叉树时可以得到一个结点值递增的有序序列。\
4.1.2二叉排序树的查找
因为二叉排序树可以看成是一个有序表，所以在二叉排序树上进行查找和折半查找类似，也是一个逐步缩小查找范围的过程。
二叉排序树的递归查找：
① 若二叉排序树为空，则查找失败，返回空指针。
② 若二叉排序树非空，将给定值key与根结点的关键字T->data.key进行比较：
若key等于T->data.key，则查找成功，返回根结点地址；
若key小于T->data.key，则递归查找左子树；
若key大于T->data.key，则递归查找右子树。\
4.1.3二叉排序树的插入
二叉排序树的插入操作是以查找为基础的。要将一个关键字值为key的结点S插入到二叉排序树中，则需要从根结点向下查找，当树中不存在关键字等于key的结点时才进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。
二叉排序树的插入：
① 若二叉排序树为空，则待插入结点S作为根结点插入到空树中。
② 若二叉排序树非空，则将key与根结点的关键字T->data.key进行比较：
若key小于T->data.key，则将S插入左子树；
若key大于T->data.key，则将*S插入右子树。\
4.2平衡二叉树
4.2.1平衡二叉树的定义
平衡二叉树或者是空树，或者是具有如下特征的二叉排序树：
(1)左子树和右子树的深度之差的绝对值不超过1；
(2)左子树和右子树也是平衡二叉树。
若将二叉树上结点的平衡因子(Balance Factor，BF)定义为该结点左子树和右子树的深度之差，则平衡二叉树上所有结点的平衡因子只可能是−1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。\
4.2.2平衡二叉树的平衡调整
插入结点时，首先按照二叉排序树处理，若插入结点后破坏了平衡二叉树的特性，需对平衡二叉树进行调整。调整方法是：找到离插入结点最近且平衡因子绝对值超过1的祖先结点，以该结点为根的子树称为最小不平衡子树，可将重新平衡的范围局限于这棵子树。\
一般情况下，假设最小不平衡子树的根结点为A，则失去平衡后进行调整的规律可归纳为下列4种情况。
(1)LL型：由于在A左子树根结点的左子树上插入结点，A的平衡因子由1增至2，致使以A为根的子树失去平衡，则需进行一次向右的顺时针旋转操作，如图所示。
(2)RR型：由于在A的右子树根结点的右子树上插入结点，A的平衡因子由−1变为−2，致使以A为根结点的子树失去平衡，则需进行一次向左的逆时针旋转操作，如图所示。
(3)LR型：由于在A的左子树根结点的右子树上插入结点，A的平衡因子由1增至2，致使以A为根结点的子树失去平衡，则需进行两次旋转操作。第一次对B及其右子树进行逆时针旋转，C转上去成为B的根，这时变成了LL型，所以第二次进行LL型的顺时针旋转即可恢复平衡。如果C原来有左子树，则调整C的左子树为B的右子树，如图所示。
(4)RL型：由于在A的右子树根结点的左子树上插入结点，A的平衡因子由−1变为−2，致使以A为根结点的子树失去平衡，则旋转方法和LR型相对称，也需进行两次旋转，先顺时针右旋，再逆时针左旋，如图所示。
4.3B-树
4.3.1B-树的定义
一棵m阶的B-树，或为空树，或为满足下列特性的m叉树：
（1）树中每个结点至多有m棵子树；
（2）若根结点不是叶子结点，则至少有两棵子树；
（3）除根之外的所有非终端结点至少有$\lceil{m/2}\rceil$棵子树；则至少含有$\lceil{m/2}\rceil-1$个关键字
（4）所有的叶子结点都出现在同一层次上，并且不带信息，通常称为失败结点（失败结点并不存在，指向这些结点的指针为空。引入失败结点是为了便于分析B-树的查找性能）；
（5）所有的非终端结点最多有m−1个关键字，结点的结构如图所示。\
其中，Ki（i=1, …, n）为关键字，且$K_i<K_i+1$（i=1, …, n−1）;
$P_i$（i=0, …, n）为指向子树根结点的指针，且指针$P_i$−1所指子树中所有结点的关键字均小于$K_i$（i=1, …, n）;
$P_n$所指子树中所有结点的关键字均大于Kn，[插图]为关键字的个数（或n+1为子树个数）。
从上述定义可以看出，对任一关键字Ki而言，Pi−1相当于指向其“左子树”，Pi相当于指向其“右子树”。
B-树具有平衡、有序、多路的特点，图所示为一棵4阶的B-树，能很好地说明其特点。\
（1）所有叶子结点均在同一层次，这体现出其平衡的特点。
（2）树中每个结点中的关键字都是有序的，且关键字Ki“左子树”中的关键字均小于Ki，而其“右子树”中的关键字均大于Ki，这体现出其有序的特点。
（3）除叶子结点外，有的结点中有一个关键字，两棵子树，有的结点中有两个关键字，三棵子树，这种4阶的B-树最多有三个关键字，四棵子树，这体现出其多路的特点。
在具体实现时，为记录其双亲结点，B-树结点的存储结构通常增加一个parent指针，指向其双亲结点，存储结构示意图如图所示。
重要结论：
n个关键字的m阶B-树高度h的范围为：$\log_m^{n+1} ≤ h ≤ \log_{\lceil{m/2}\rceil}^{\frac{n+1}{2}}+1$\
4.3.2B-树的查找
将给定值key与根结点的各个关键字K1, K2, …, Kj（1≤j≤m−1）进行比较，由于该关键字序列是有序的，所以查找时可采用顺序查找，也可采用折半查找。查找时：
① 若key=Ki（1≤i≤j），则查找成功；
② 若key<K1，则顺着指针P0所指向的子树继续向下查找；
③ 若Ki<key<Ki+1（1≤i≤j−1），则顺着指针Pi所指向的子树继续向下查找；
④ 若key>Kj，则顺着指针Pj所指向的子树继续向下查找。如果在自上而下的查找过程中，找到了值为key的关键字，则查找成功；如果直到叶子结点也未找到，则查找失败。
如果在自上而下的查找过程中，找到了值为key的关键字，则查找成功；如果直到叶子结点也未找到，则查找失败。\
4.3.3B-树的插入
① 在B-树中查找给定关键字的记录，若查找成功，则插入操作失败；否则将新记录作为空指针ap插入到查找失败的叶子结点的上一层结点（由q指向）中。
② 若插入新记录和空指针后，q指向的结点的关键字个数未超过m−1，则插入操作成功，否则转入步骤③。
③ 以该结点的第$\lceil{m/2}\rceil$个关键字$K_{\lceil{m/2}\rceil}$为拆分点，将该结点分成3个部分：$K_{\lceil{m/2}\rceil}$左边部分、$K_{\lceil{m/2}\rceil}$右边部分。$K_{\lceil{m/2}\rceil}$左边部分仍然保留在原结点中；$K_{\lceil{m/2}\rceil}$右边部分存放在一个新创建的结点（由ap指向）中；关键字值为$K_{\lceil{m/2}\rceil}$的记录和指针ap插入到q的双亲结点中。因q的双亲结点增加一个新的记录，所以必须对q的双亲结点重复②和③的操作，依次类推，直至由q指向的结点是根结点，转入步骤④。
④ 由于根结点无双亲，则由其分裂产生的两个结点的指针ap和q，以及关键字为$K_{\lceil{m/2}\rceil}$的记录构成一个新的根结点。此时，B-的高度增加1。\
4.4B+树
B+树是一种B-树的变形树，更适合用于文件索引系统。
一棵m阶的B+树和m阶的B-树的差异在于：
（1）有n棵子树的结点中含有n个关键字；
（2）所有的叶子结点中包含了全部关键字的信息，以及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接；
（3）所有的非终端结点可以看成是索引部分，结点中仅含有其子树（根结点）中的最大（或最小）关键字。\
5.散列表的查找
散列查找法（Hash Search）的思想，它通过对元素的关键字值进行某种运算，直接求出元素的地址，即使用关键字到地址的直接转换方法，而不需要反复比较。因此，散列查找法又叫杂凑法或散列法。
（1）散列函数和散列地址：在记录的存储位置p和其关键字key之间建立一个确定的对应关系H，使p=H(key)，称这个对应关系H为散列函数，p为散列地址。
（2）散列表：一个有限连续的地址空间，用以存储按散列函数计算得到相应散列地址的数据记录。通常散列表的存储空间是一个一维数组，散列地址是数组的下标。
（3）冲突和同义词：对不同的关键字可能得到同一散列地址，即key1≠key2，而H(key1)=H(key2)，这种现象称为冲突。具有相同函数值的关键字对该散列函数来说称作同义词，key1与key2互称为同义词。\
散列查找法主要研究以下两方面的问题：（1）如何构造散列函数；（2）如何处理冲突。
构造散列函数的几种常用方法:
1．数字分析法
如果事先知道关键字集合，且每个关键字的位数比散列表的地址码位数多，每个关键字由n位数组成，如$k_1 k_2 … k_n$，则可以从关键字中提取数字分布比较均匀的若干位作为散列地址。
2．平方取中法
通常在选定散列函数时不一定能知道关键字的全部情况，取其中哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，如果取关键字平方后的中间几位或其组合作为散列地址，则使随机分布的关键字得到的散列地址也是随机的，具体所取的位数由表长决定。平方取中法是一种较常用的构造散列函数的方法。
3．折叠法
将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为散列地址，这种方法称为折叠法。根据数位叠加的方式，可以把折叠法分为移位叠加和边界叠加两种。移位叠加是将分割后每一部分的最低位对齐，然后相加；边界叠加是将两个相邻的部分沿边界来回折叠，然后对齐相加。
4．除留余数法
假设散列表表长为m，选择一个不大于m的数p，用p去除关键字，除后所得余数为散列地址，即H(key)=key%p这个方法的关键是选取适当的p，一般情况下，可以选p为小于表长的最大质数。例如，表长m=100，可取p=97。除留余数法计算简单，适用范围非常广，是最常用的构造散列函数的方法。它不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模，这样能够保证散列地址一定落在散列表的地址空间中。\
处理冲突的方法:
1．开放地址法
把记录都存储在散列表数组中，当某一记录关键字key的初始散列地址H0=H(key)发生冲突时，以H0为基础，采取合适方法计算得到另一个地址H1，如果H1仍然发生冲突，以H1为基础再求下一个地址H2，若H2仍然冲突，再求得H3。依次类推，直至Hk不发生冲突为止，则Hk为该记录在表中的散列地址。
这种方法在寻找“下一个”空的散列地址时，原来的数组空间对所有的元素都是开放的，所以称为开放地址法。
通常把寻找“下一个”空位的过程称为探测，上述方法可用如下公式表示：Hi=(H(key)+di)%mi=1, 2, …, k (k≤m−1)其中，H(key)为散列函数，m为散列表表长，di为增量序列。
根据di取值的不同，可以分为以下3种探测方法。
（1）线性探测法
di=1, 2, 3, …, m−1
这种探测方法可以将散列表假想成一个循环表，发生冲突时，从冲突地址的下一单元顺序寻找空单元，如果到最后一个位置也没找到空单元，则回到表头开始继续查找，直到找到一个空位，就把此元素放入此空位中。如果找不到空位，则说明散列表已满，需要进行溢出处理。
（2）二次探测法
di=12, −12, 22,−22, 32,…,+k2, −k2 (k≤m/2)
（3）伪随机探测法
di=伪随机数序列
当表中i，i+1，i+2位置上已填有记录时，下一个散列地址为i、i+1、i+2和i+3的记录都将填入i+3的位置，这种在处理冲突过程中发生的两个第一个散列地址不同的记录争夺同一个后继散列地址的现象称作“二次聚集”（或称作“堆积”），即在处理同义词的冲突过程中又添加了非同义词的冲突。\
线性探测法的优点是：只要散列表未填满，总能找到一个不发生冲突的地址。缺点是：会产生“二次聚集”现象。
而二次探测法和伪随机探测法的优点是：可以避免“二次聚集”现象。缺点也很显然：不能保证一定找到不发生冲突的地址。\
2．链地址法
排序
1.插入排序
1.1直接插入排序
1.2折半插入排序
1.3希尔排序
2.交换排序
2.1冒泡排序
2.2快速排序
3.选择排序
3.1简单选择排序
3.2树形选择排序
3.3堆排序
4.归并排序
5.基数排序
5.1多关键字的排序
5.2链式基数排序
6.外部排序
外部排序基本上由两个相对独立的阶段组成。首先，按可用内存大小，将外存上含n个记录的文件分成若干长度为l的子文件或段（segment），依次读入内存并利用有效的内部排序方法对它们进行排序，并将排序后得到的有序子文件重新写入外存，通常称这些有序子文件为归并段或顺串（run）；然后，对这些归并段进行逐趟归并，使归并段（有序的子文件）逐渐由小至大，直至得到整个有序文件为止。