数据结构复习笔记

About

此文是我在期末复习(预习🤣)数据结构（严蔚敏版）期间，对各章节重难点的梳理

~~为了应付考试~~，时间紧迫，理解算法的基本思想，会做题就行。。

如果时间充足，我认为数据结构这本书上的各种算法都需要自己实现一遍(即便你理解了算法思想，但是如果不实现的话，一些编程思想就无法理解，写代码就会想半天)，才能打下坚实的代码基础，不能老是纸上谈兵

DataStructuresAndAlgorithms/C at master · OneLastChick/DataStructuresAndAlgorithms (github.com)这是我参考资料用代码实现了的一部分重要的算法

Chap2 线性表

单链表

类型

单链表的建立

生成带头结点的单链表

生成无表头结点的单链表

单链表的插入

循环链表

Chap6 树和二叉树

树的定义和基本术语

定义

一个节点的树T={A}

四个节点的树T={A,B,C,D},T1={B} T2={C} T3={D}

术语

A,B,E是K的祖先（根节点到该节点唯一路径上的任意节点)；
E是K的双亲，K是E的孩子,K,L为兄弟,K,M为堂兄弟
节点的度：节点的孩子个数
树的度:树中节点最大的度数
分支节点:度>0;叶子节点:度=0
结点的深度、高度和层次。
结点的层次从树根开始定义,根结点为第1层,它的子结点为第2层,以此类推。双亲在同一层的结点互为堂兄弟,图中结点G与E,F,H,I,J互为堂兄弟。
结点的深度是从根结点开始自顶向下逐层累加的。
结点的高度是从叶结点开始自底向上逐层累加的。
树的高度(或深度)是树中结点的最大层数。图中树的高度为4。
有序树和无序树。树中结点的各子树从左到右是有次序的,不能互换,称该树为有序树,否则称为无序树。假设图为有序树,若将子结点位置互换,则变成一棵不同的树。
路径和路径长度。树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的,而路径长度是路径上所经过的边的个数。
森林。森林是m (m≥0)棵互不相交的树的集合。森林的概念与树的概念十分相近，因为只要把树的根结点删去就成了森林。反之，只要给m棵独立的树加上一个结点，并把这m棵树作为该结点的子树，则森林就变成了树。

森林F={T1,T2,T3}

性质

树中的节点数=所有结点度数+1（根节点）
度为m的树中至多有m^i-1个节点
高度为h的m叉树至多有 $\frac{m^h-1}{m-1}$ 个节点，（等比数列求和公式)
具有n个节点的m叉树的最小高度为 $[log_m{n(m-1)+1}]$ ,(由3求解h得到)

存储结构

双亲表示法/数组表示法/顺序表示法

struct snode
{
    char data;
    int parent;
}t[maxlength+1]

例如

孩子表示法/链接表表示法

typedef struct node
{
    char data;
    node* child1;
    node* child2;
    node* child3;
}

typedef struct node
{
    char data;
    int degree;
    node* child[degree];
}

孩子兄弟表示法/二叉树表示法/二叉链表

typedef struct node
{
    char data;
    node * firstchild,*rightsib;
}

孩子链表表示法/单链表表示法
带双亲的孩子链表表示法

二叉树

定义：二叉树中不存在度大于2的节点
性质
- 二叉树的第i(i>=1)层最多有 $2^{i-1}$ 个节点
- 深度为k的二叉树最多有 $2^k-1$ 个节点
- $n0=n2+1$
- 满二叉树
  
  定义是：深度为k且有2^k-1个节点的二叉树
  - n个节点的的深度= $log_2{(n+1)}$ (n<=2^k-1)
  - 顺序编号的满二叉树，设编号分别为1,2，…n
    - 节点i的左小孩是2i
    - 节点i的右小孩是2i+1
    - 节点i的双亲是 $\lfloor i/2 \rfloor$
    - 节点i的层号= $\lfloor log_2{i} \rfloor+1=\lfloor log_2{(i+1)} \rfloor$
- 完全二叉树
  
  定义是深度为k的有n个节点的二叉树，当且仅当每一个节点都与同深度的满二叉树中编号从1到n的节点一一对应，也称顺序二叉树

存储结构

顺序存储

typedef TElemType SqBiTree[MAX_TREE_SIZE]
SqBiTree bt

链式存储结构

遍历二叉树和线索树

遍历

设D:访问根节点，输出根节点;L递归遍历左二叉树，R递归遍历右二叉树

DLR-先序遍历 DRL-逆先序遍历

LDR-中序遍历 RDL-逆中序遍历

LRD-后序遍历 RLD-逆后序遍历
先中后序遍历的非递归版本？

中序遍历非递归算法的思想：核心是回溯法，利用栈的数据结构

(1)设置一个栈S存放所经过的根结点(指针)信息;初始化S;
(2)第一次访问到根结点并不访问，而是入栈:
(3)中序遍历它的左子树，左子树遍历结束后，第二次遇到根结点，就将根结点(指针)退栈，并且访问根结点;然后(中序)遍历它的右子树。
(4)当需要退栈时，如果栈为空则结束
时间复杂度:O(n)
空间复杂度:O(logn)
层次遍历

从上到下从左到右依次遍历节点

算法

(1)设置一个队列Q存放所经过的结点的非空的左右孩子(指针)信息;初始化Q;
(2)访问根结点，将非空的左右孩子依次入队;
(3)依次出队结点指针，访问该结点，将非空的左右孩子依次入队

(4)当队列为空时，遍历结束。
由遍历序列构造二叉树
- 代码实现:
- 由二叉树的先序序列和中序序列可以唯一地确定一棵二叉树。
  在先序遍历序列中,第一个结点一定是二叉树的根结点;而在中序遍历中,根结点必然将中序序列分割成两个子序列,前一个子序列是根结点的左子树的中序序列,后一个子序列是根结点的右子树的中序序列。根据这两个子序列,在先序序列中找到对应的左子序列和右子序列。在先序序列中,左子序列的第一个结点是左子树的根结点,右子序列的第一个结点是右子树的根结点。
  如此递归地进行下去,便能唯一地确定这棵二叉树
- 同理,由二叉树的后序序列和中序序列也可以唯一地确定一棵二叉树。
  因为后序序列的最后一个结点就如同先序序列的第一个结点,可以将中序序列分割成两个子序列,然后采用类似的方法递归地进行划分,进而得到一棵二叉树。
  由二叉树的层序序列和中序序列也可以唯一地确定一棵二叉树。
- 要注意的是,若只知道二叉树的先序序列和后序序列,则无法唯一确定一棵二叉树。
  例如,求先序序列( ABCDEFGH)和中序序列( BCAEDGHFI）所确定的二叉树
  首先,由先序序列可知A为二叉树的根结点。中序序列中A之前的BC为左子树的中序序列,EDGHFI为右子树的中序序列。然后由先序序列可知B是左子树的根结点,D是右子树的根结点。以此类推,就能将剩下的结点继续分解下去,最后得到的二叉树如图©所示。
  
  给定后序序列:BGHECAJIFD 中序序列:BACGEHDIJF

线索二叉树

线索二叉树是为了方便寻找线性序列（遍历二叉树得到的）的直接前驱和直接后继

当以二叉链表作为存储结构，直接前驱和直接后续这种信息只能在遍历的动态过程中才能得到

如何存储前驱后继这种信息？

在节点增加指针域，fwd和bkwd，不过这样太浪费空间了
我们知道，有n个节点的二叉链表必有2n个链域，由树的性质m=n-1，一条边占用一个链域，那么还剩下n+1个空链域

因此利用空链域存放指针指向树中其他节点，这种指针称为线索
为了避免孩子和线索混淆，我们需要增加两个标志域

lchild | LTag | data | RTag | rchild

LTag=0，代表lchild域指向节点的左孩子，LTag=1代表指向节点的前驱

RTag=0, 代表rchild域指向节点的右孩子，RTag=1代表指向节点的后继
先中后序线索二叉树的手动构造,根据遍历序列建立线索
中序线索二叉树的构造

二叉树的线索化是将二叉链表中的空指针改为指向前驱或后继的线索。而前驱或后继的信息只有在遍历时才能得到，因此线索化的实质就是遍历一次二叉树。
以中序线索二叉树的建立为例。附设指针 pre 指向刚刚访问过的结点，指针p 指向正在访问的结点，即pre指向p 的前驱。在中序遍历的过程中，检查p的左指针是否为空，若为空就将它指向pre;检查pre的右指针是否为空，若为空就将它指向p

前序，后续，中序构造过程类似的，不过要细细考虑pre=root的位置
中序线索二叉树的遍历

在线索树中进行遍历，只要先找到序列的第一个节点，然后依次找节点后继直到其后继为空为止==若其右标志为“1”，则右链为线索，指示其后继，否则遍历右子树中第一个访问的结点（右子树中最左下的结点）为其后继。==

可以看到时间复杂度虽然是 $O(n)$ 然而常数因子更小，且无需栈的使用

应用：有中序线索二叉树，从根节点开始

1）遍历中序的第一个结点
- 中序，LDR;
- 子树L中的LDR;
- 直至子树L中没有L孩子
2)遍历中根节点的前驱节点
- 中序,LDR;
- 根节点的前驱为子树L中的最后一个节点
- 子树L中的右子树R，子树R中的右子树R
- 直至右子树R中无R孩子，L最右边的孩子即是根节点的前驱
3)遍历中根节点的后继节点
- 中序,LDR;
- 子树R中的LDR，子树L的第一个节点
- 子树R中最左边的孩子
后序线索二叉树找后继

（1）若节点x是二叉树的根，则其后继为空

（2）若节点x是其双亲的右孩子，或是其双亲的左孩子且其双亲没有右子树,则其后继即为双亲节点

（3）若节点x是其双亲的左孩子，且其双亲有右子树，则其后继为双亲的右子树上按后序遍历的第一个节点
代码实现

森林

森林与二叉树的转换

树转为二叉树
1. 在兄弟之间加连线
2. 保留根与最左孩之间的连线，删去与其他孩子之间的连线
3. 以根为轴心顺时针方向旋转45度
森林转为二叉树
1. 将每个树转为二叉树
2. 将每棵树的根节点相连成为一棵二叉树
二叉树转为树

上述的逆过程
1. 去掉右子指针：将所有右子节点都变成当前节点的兄弟节点。
2. 左子指针转子节点指针：保持左子指针，即左子指针依然指向它最主要的子节点。
二叉树转为森林

并查集

定义：
并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题（即所谓的并、查）。比如说，我们可以用并查集来判断一个森林中有几棵树、某个节点是否属于某棵树等。

实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。
操作
- 合并（union)，合并两个元素所属集合,即合并对应的树
  - 只需要把一棵树的根节点连到另一棵树的根节点
- 查询(find),查询某个元素所属集合
  - 沿着树向上移动，直至找到根节点
优化
- 路径压缩（优化find函数）
  
  简单说来就是将x到根节点路径上的所有点的pre（上级）都设为根节点
```
int find(int x)     				//查找结点 x的根结点 
{
    if(pre[x] == x) return x;		//递归出口：x的上级为 x本身，即 x为根结点        
    return pre[x] = find(pre[x]);	//此代码相当于先找到根结点 rootx，然后pre[x]=rootx 
}
```
  缺点：只有当查找了根节点后，才能对该查找路径上的各节点进行路径压缩。
- 加权标记法
  
  加权标记法需要将树中所有节点都增设一个权值，用以表示该节点所在树中的高度（比如用rank[x]=3表示 x 节点所在树的高度为3）。这样一来，在合并操作的时候就能通过这个权值的大小来决定谁当谁的上级
  
  加权标记法的核心在于对rank数组的逻辑控制，其主要的情况有：
  1、如果rank[x] < rank[y]，则令pre[x] = y；
  2、如果rank[x] == rank[y]，则可任意指定上级；
  3、如果rank[x] > rank[y]，则令pre[y] = x；
作用：
并查集的主要作用是求连通分支数（如果一个图中所有点都存在可达关系（直接或间接相连），则此图的连通分支数为1；如果此图有两大子图各自全部可达，则此图的连通分支数为2……）

树的应用

一个递归的过程，往往可以看做一个树形结构的状态树

几种问题的应用(回溯法，树形状态图，递归设计)

求含n个元素的幂集
n皇后问题
骑士游历
迷宫问题
选最优解问题

哈夫曼树

写报告的时候看吐了就不写了

树的计数

推导过程课本P152，太长了不想看

二叉树：

具有n个节点不同形态的二叉树有多少棵

$bn=\frac{1}{n+1}C_{2n}^n$
由二叉树的计数可以推得树的计数

具有n个节点不同形态的树 $t_n$ 和具有n-1个节点不同形态的二叉树一样

即 $t_n=b_{n-1}$

Chap7 图

图的定义和术语

术语

有向图，无向图

完全图:有n个节点和(n-1)*n/2条边

有向完全图，网：边上加权的图，入度，出度，度，连通图以及连通分量:极大连通子图

强连通图(每对顶点vi-vj，vj-vi都有路径)与强连通分量:极大强连通子图

生成树：极小连通子图

图的存储结构

数组表示法/邻接矩阵(顺序)

邻接表/逆邻接表（顺序+链式)

无向图的邻接表
有向图的邻接表
有向网的邻接表
有向图的逆邻接表

十字链表

有向图的十字链表

将邻接表和逆邻接表给合并起来的链表，使计算度数更加方便

十字链表的数据结构：主要由顶点表数组

顶点结构如下data | firstIn | firstOut

其中data表示顶点的具体数据信息，而firstIn则表示指向以该顶点为弧头的第一个弧节点。而firstOut则表示指向以该节点为弧尾的第一个弧节点，采用一个顶点数组存储每一个节点

在十字链表结构中，有向图中的每一条弧都有一个弧节点与之对应，具体的弧节点结构如下所示

其中的tailVex表示该弧的弧尾顶点在顶点数组xList中的位置，headVex表示该弧的弧头顶点在顶点数组中的位置。hLink则表示指向弧头相同的下一条弧，tLink则表示指向弧尾相同的下一条弧。

从十字链表的数据结构来看，每一个顶点对应两个链表：以该顶点为弧尾的弧结点所组成的链表以及以该顶点为弧头的弧结点所组成的链表。

// 边表节点
typedef struct ArcNode {
    int tailvex;                // 该边的起始顶点
    int headvex;                // 该边的终止顶点
    struct ArcNode* hlink;      // 指向下一个以该节点为终点的边（逆邻接表）
    struct ArcNode* tlink;      // 指向下一个以该节点为起点的边（邻接表）
} ArcNode;

// 顶点表节点
typedef struct VexNode {
    int data;                   // 顶点的数据
    ArcNode* firstin;           // 指向第一个以该顶点为终点的边
    ArcNode* firstout;          // 指向第一个以该顶点为起点的边
} VexNode;

// 图的定义
typedef struct {
    VexNode* vertices;          // 顶点表数组
    int numVertices;            // 顶点数
    int numEdges;               // 边数
} GraphOrthogonalList;

例如，对于如下所示的一个有向图

构造的十字链表如图

邻接多重表

无向图的另一种链式存储结构,解决了用邻接表重复存储同一条边2次的问题

同时，解决用邻接矩阵存储时，空间复杂度为 $O(V^2)$ 过大

邻接多重表由顶点表和边表构成
顶点表节点：

1、data：顶点数据域
2、firstedge:边表节点的头指针

边表节点：

1、ivex:该边的第一个端点
2、ilink:与该端点相邻的下一个边表节点的指针
3、jvex:该边的第二个端点
4、jlink:与该端点相邻的下一个边表节点的指针
5、info:权值
6、mark:标记

例如，对于该无向图

如上图所示，图中黄色标记的结点表示A-D之间的边，在邻接表中一条边需要两个结点表示。因此如果对于边的操作（标记或者删除）则需要访问两条链表。

当采用邻接多重表表示该无向图时,其邻接多重表如下图所示

如上图所示，结点A-D 之间的边，在邻接多重表中只需要一个边结点既可以表示。另外，在该结构中，每个边结点被链入了两个不同的链表。其中A-D之间的边被链入了红色和绿色标记的链表中。如果需要访问一条边，则可以从该边的两个顶点结点中的任何一个出发，遍历依附于该顶点的边构成的链表即可。如果需要删除一条边，则只需要删除一个边结点，但是需要修改这条边依附的两个顶点所对应的链表。另外，需要注意的是，在无向图中，边结点中的iVex和jVex链域与该边所依附的顶点无关，即iVex=0，jVex=3和iVex=3，jVex=0这都表示同一条边A-D，因此这给链表的指针修改带来一定的麻烦。

// 边表节点
typedef struct EdgeNode {
    int ivex;                    // 该边的一个顶点
    int jvex;                    // 该边的另一个顶点
    struct EdgeNode* ilink;      // 指向顶点 ivex 的下一条边
    struct EdgeNode* jlink;      // 指向顶点 jvex 的下一条边
    int info
    bool mark;              // 标记边是否被访问过（可选）
} EdgeNode;
// 顶点表节点
typedef struct VertexNode {
    int data;                    // 顶点数据
    EdgeNode* firstEdge;         // 指向第一条邻接边
} VertexNode;

// 图的定义
typedef struct {
    VertexNode* vertices;        // 顶点表数组
    int numVertices;             // 顶点数
    int numEdges;                // 边数
} GraphAdjMultilist;
void addEdge(GraphAdjMultilist* graph, int v1, int v2) {
    EdgeNode* newNode = (EdgeNode*)malloc(sizeof(EdgeNode));
    newNode->ivex = v1;
    newNode->jvex = v2;
    newNode->isVisited = false;
    
    // 插入到顶点 v1 的边表
    newNode->ilink = graph->vertices[v1].firstEdge;
    graph->vertices[v1].firstEdge = newNode;
    
    // 插入到顶点 v2 的边表
    newNode->jlink = graph->vertices[v2].firstEdge;
    graph->vertices[v2].firstEdge = newNode;
    
    graph->numEdges++;
}

图的遍历

深度优先搜索

广度优先搜索

图的连通性问题

无向图的连通分量和生成树

DFS生成树
BFS生成树
DFS生成树林
BFS生成树林

最小生成树

Prim算法
Kruskal算法

Kruskal算法一般不适合稠密图

关节点和重连通分量

关节点，假若在删去顶点v以及和v相关联的各边后，将图的一个连通分量分割成两个或两个以上的连通分量，则称顶点为v该图的一个关节点，即（割点）
一个没有关节点的连通图称为重连通图

即从一个双连通图中删去任何一个顶点以及相关联的边，它仍为一个连通图
visited数组

第一次对图执行深度优先搜索时，依次访问节点，同时按访问顺序对节点编号，对每一个节点v，我们称其先序序号为visited[v]
low数组

对深度优先搜索树上的每一个节点v，计算编号最低的顶点，称之为low[v]

其意义为:通过该点，经过零条或多条边以及最多一条回边，可以到达的顶点的编号的最小值

例如，上图中的C点，其先序编号为3，但可首先通过一条边达到D点，并通过D的回边到达A，所以其low数组编号，及可到达的最低节点编号为1。

顶点的数字标注为visited[v]/low[v]。

low数组的求法

$low(v)=Min\{visited[v],low[w],visited[k]\}$

其中顶点w是生成树上顶点v的孩子，顶点k是生成树上和顶点v由回边相联接的祖先，visited记录深度优先遍历时的访问次序

对于任意一个顶点V，其low数组值为自身先序编号(visited[v]),其所有孩子节点的low值的最小值，与其通过回边相连的祖先节点K的先序编号（visited[k]）这三者中的最小值。
关节点的判定
1. 若生成树中根节点顶点V，其子树大于1，则该节点一定为关节点
2. 对于非根节点v，它是割点当且仅当它有某个儿子w，使得low[w]>=visited[v]。该条件在根处总是满足，所以需要进行特别判断
  
  对于low[w]>=visited[v]的理解:Low[w]>=Visited[v]含义为，v有某个孩子w，其可到达的节点的最低先序编号大于等于其父亲的先序编号。即w一定不可能到达比v先序编号低的节点（深度优先搜索中比v先访问的节点），则删除节点v后，w一定不能与v之前的节点相连，则该图不为连通图。

Tarjan算法

void FindArticul(ALGraph G){
 //连通图G以邻接表作存储结构，查找并输出G上全部关节点。全局量count对访问计数。
 count = 1; visited[0] = 1;   //设定邻接表上0号顶点为生成树的根 
 for( i=1; i<G.vexnum; ++i)   //其余顶点清零，尚未访问。 
 visited[i]=0;
 p=G.vertices[0].firstarc;   //p为0号顶点指向的第一条依附于它的弧。 
 v=p->adjvex;                //v为该弧所指向的顶点的位置。(即树的根结点) 
 
 DFSArticul(G,v);             //从第v顶点出发深度优先查找关节点 
 if(count<G.vexnum)           //生成树的根至少有两颗子树 
 {
  printf(0,G.vertices[0].data);   //根是关节点，输出 
  while(p->nextarc)         //指向下一条弧 
  {
   p=p->nextarc;
   v=p->adjvex;         
   if(visited[v]==0)
   DFSArticul(g,v);
   } 
 }
}

void DFSArticul(ALGraph G,int v0){   //在深度遍历，标记visited[v]的同时检查关节点 
 //从第v0个顶点出发深度优先遍历图G，查找并输出G上全部关节点。全局count对访问计数。 
 visited[v0]=min=++count;
 for(p=G.vertices[0].firstarc;p;p=p->nextarc){    //对v0的每个邻接顶点检查 
  w=p->adjvex;           //w为v0邻接顶点
  if(visited[w]==0)      //w未曾访问，是v0的孩子； 注：结点v的low与其孩子有关，所以一定先递归求出节点的所有子树的low值。 
  {
   DFSArticul(G,w);    //返回前求得low[w]；
   if(low[w]<min)  min=low[w];
   if(low[w]>=visited[v0])
   printf(v0,G.vertices[v0].data);    //输出关节点;         
   } 
  else if(visited[w]<min)     //不是孩子节点，则为v0节点的祖先（回边） 
  min=visited[w];
 }
 low[v0]=min;
}

注意点：
1.搜索树的根节点需要特判
2.对于每个顶点V，其low一定要在其所有孩子的low值已知的情况下才能决定，所以在算法中要先递归调用求出所有子树的low值。
3.节点孩子的判断方式(w为v的邻接点，且w之前未被访问),
回边的判断方式（w为v的邻接点，w已被访问）。
4.DFSArticul函数同时实现visited数组的标记，low数组的更新与关节点的判定。

时间复杂度分析:
Tarjan算法的时间复杂度与图的深度优先遍历复杂度相同，都是对所有顶点与边访问一次，复杂度为O(V+E)。

有向无环图

拓扑排序

AOV网(Activity On Vertex network)是以顶点表示活动，弧表示活动之间优先关系的DAG图

例如
拓扑排序:是有向图的全部顶点的一个线性序列，该序列保持了原有向图中由各顶点间的相对次数

算法过程
1. 在有向图中选一个没有前驱的顶点输出(选择入度为0的顶点)
2. 在图中删除该顶点和所有以它为尾的弧（修改其他顶点入度)
有回路的有向图不存在拓扑排序

关键路径

AOE网(Activity On Edge)是一个带权的有向无环图，其中以顶点表示时间，弧表示活动，权表示活动持续的时间。当AOE网用来估算工程的完成时间时，只有一个开始点(入度为0，称为源点)和一个完成点（出度为0，称为汇点)
AOE可以解决的问题
- 完成整项工程至少需要多少时间
- 哪些活动是影响工程进度的关键
关键路径:在AOE网中，部分活动可以并行进行，所以完成工程的最短时间是从开始点到完成点的最长路径长度。路径长度最长的路径称为关键路径
(顶点)时间v_i的最早发生时间ve(i):

从开始点到v_i的最长路径长度。(ve(v1)=0),既表示时间v_i的最早发生时间，也表示所有以v_i为尾的弧所表示的活动a_k的最早发生时间e(k)
不推迟整个工程完成的前提下, (顶点）事件vi允许的最迟开始时间vl(i)：完成点（汇点）vn的的最早发生时间ve(n)减去vk到vn的最长路径长度。（vn的的最早发生时间ve(n)等于最迟开始时间vl(n)）。
确定了顶点vi的最迟开始时间后，确定所有以vi为弧头的活动ak的最迟开始时间l(k)：表示在不推迟整个工程完成的前提下，活动ak最迟必须开始的时间。 l(ak)=vl(ak弧头对应顶点)-活动ak的持续时间
关键路径算法步骤
1. 从开始点v1出发，令ve(1)=0，按拓扑排序序列求其他个顶点的最早发生序列
  
  即Ve(k)=max{ve{j}+dut(<j,k)}
2. 从出发点vn出发，令vl(n)=ve(n),按逆拓扑排序序列求其他各顶点的最迟发生时间
  
  即Vl(j)=min{vl(k)-dut(<j,k)}
3. 求每一项活动ai(vi，vj):
  
  e(i)=ve(j) l(i)=vl(k)-dut(ai)
关键活动:选取e(i)-l(i)的活动

最短路径

求某个源点到其余各顶点的最短路径
- 直接dfs暴力
- Dijkstra
  1. 选择起点start与终点end；
  2. 所有点除起点外加入未知集合，并将起点加入已知集合，即至标志位为真，意为已确定该点到源点的最短路径；
  3. 初始化计算，更新起点与其他各点的耗费(路径长度）dis(start,n);
  4. 在未知集合中，选择dis(start,n)中值最小的点x，将x加入已知集合。
  5. 对于剩余顶点中，计算dis(start,n)>dis(start,x)+dis(x,n)
    若真则dis(start,n)=dis(start,x)+dis(x,n)，此时start与n点路径经过x点。循环直至goal点加入已知列表，取得dis(start,goal)即为最短距离。
每一对顶点之间的最短路径
- 以每一个顶点为源点，重复执行Dijkstra算法n次，即可求出每一对顶点之间的最短路径
- Floyed
  1. 初始化距离矩阵：
    - 首先，构建一个大小为n×n的矩阵D，其中n是图中顶点的数量。D[i][j]表示顶点i到顶点j的初始距离。如果i和j之间有直接边，则D[i][j]就是这条边的权重；如果没有直接边相连，则D[i][j]设为无穷大（通常表示为一个很大的数，意味着不可达）。
  2. 选择中介顶点：
    - 然后，算法遍历图中的每一个顶点，将其作为中介顶点（记为k）。这意味着算法会考察每一对顶点（i, j），尝试通过k来寻找更短的路径。
  3. 更新最短路径：
    - 对于每一对顶点i和j，算法检查是否存在这样的情况：先从i经过k，再从k到j的路径比当前已知的i直接到j的路径更短。如果存在这样的路径，即D[i][k] + D[k][j] < D[i][j]，那么就更新D[i][j]的值为D[i][k] + D[k][j]。这一步是算法的核心，通过考虑所有的中介点k，逐步优化每对顶点间的最短路径估计。
  4. 重复步骤2-3：
    - 上述过程对所有的顶点k重复进行，直到所有可能的中介点都被考虑过了。每一轮迭代都基于前一轮的结果进行优化，最终得到的D矩阵中的每个元素D[i][j]就是顶点i到顶点j的最短路径长度。
  5. 输出结果：
    - 完成所有顶点作为中介点的遍历后，D矩阵就包含了图中任意两点间的最短路径长度。你可以进一步通过追踪最短路径来确定具体路径，但这通常需要额外的数据结构（如“前驱”矩阵）来记录路径信息。

Chap8 动态存储管理

由于不考，坑以后填

Chap9 查找

静态查找表
1. 查询某个“特定的”数据元素是否在查找表中。
2. 检索某个“特定的”数据元素和各种属性。
动态查找表-表结构本身是在查找过程中动态生成的
1. 查找时插入不存在的数据元素
2. 查找时删除已存在的数据元素
ASL(AVERAGE SEARCH LENTH)的计算
$ASL=\Sigma{P_iC_i}$
顺序查找，有序查找的算法实现
二叉排序树，二叉搜索树，平衡二叉树，*红黑树，B树的各种原理，用处以及实现
散列表的实现，哈希函数的实现，处理冲突的方法
复杂度分析

静态查找表

顺序表查找

顺序查找(Sequential Search)
- 基本思想:从线性表的一端开始，逐个检查关键字是否满足给定的条件。
- 技巧:查找方向的尽头放置“哨兵”免去了在查找过程中每一次比较后都要判断查找位置是否越界
- 时间复杂度O(n)
- $ASL_{SS}=\sum\limits_{i=1}^nP_iC_i=\frac{1}{n}\sum\limits_{i=1}^n(n-i+1)=\frac{n+1}{2}$
  
  用监视哨 $ASL_F=n+1$ 不用监视哨 $ASL_F=n$
- 假设查找不成功与成功等概率则
  
  $ASL=\frac{1}{2n}\sum\limits_{i=1}^n(n-i+1)+\frac{1}{2}(n+1)=\frac{3}{4}(n+1)$

有序表查找

折半查找(Binary Search)
- 关键:mid=(low+high)/2,high=mid-1,low=mid+1,low<=high
- 性能分析：
  
  折半查找的查找过程可以用二叉树来描述,叫做二叉判定树
  
  给定有序表 $\{1,2,3,4,5,6,7,8,9,10,11\}$ ，二叉判定树如下
  - 具有n个节点的判定树深度至多为 $\lfloor log_2n \rfloor+1$
  - 假定有序表的长度 $n=2^h-1$ ,则 $h=log_2(n+1)$ ,层次 $h$ 的结点有 $2^{h+1}$
    
    个，假定每个记录的查找概率相同,则
    $ASL=\frac{1}{n}\sum\limits_{j=1}^kj*2^{j-1}=\frac{n+1}{n}log_2(n+1)-1$
斐波那契查找
- 基本思想:在二分查找的基础上根据斐波那契数列进行分割。在斐波那契数列找一个等于略大于查找表中元素个数的数F[n]，将原查找表扩展为长度为Fn，完成后进行斐波那契分割，即F[n]个元素分割为前半部分F[n-1]个元素，后半部分F[n-2]个元素，找出要查找的元素在那一部分并递归，直到找到。
  - mid=low+F[u-1]-1
  - 查找表的长度需要是F[u-1]-1,如果长度不够,需要拓展
  - 若相等，则查找成功
  - 若key < a[Fu-1] ，则继续在 a[1] 至 a[Fu-1 - 1] 的子表中进行查找
  - 若key > a[Fu-1] ，则继续在 a[Fu-1 + 1] 至 a[Fu - 1] 的子表中进行查找。该子表的长度为 Fu-2 - 1
- 性能:平均性能比折半查找好，但最坏情况下（虽然时间复杂度仍为O(logn)）的性能却比折半查找差。它还有一个有点就是分割时只需加减运算，而二分法需要除2，除法的效率比加减法差
插值查找
- 基本思想:是二分查找的提升版,选取mid的位置是随着key而决定
- 在折半查找中 $mid=low+(high-low)*\frac{1}{2}$
  
  可以进行优化用key在整序列中的占比来代替原来固定的1/2
  
  因此在插值查找中
  $mid=low+(high-low)*\frac{key-a[low]}{a[high]-a[low]}$
  其他保持不变
- 性能: 如果表长较长，且关键字分布均匀，插值查找算法的平均性能比折半查找要好很多，如果表中关键字分布极端不均匀，就不如折半查找

静态树表查找

前面讨论的情况都是在查找表中各关键字被查找概率相同的前提下进行的

在各关键字查找概率不同的情况下，根据ASL,使用上述算法效率就不高，因此需要进一步优化

静态最优查找树（带权内路径长度之和PH值最小), $w_i$ 代表权值, $h_i$ 代表结点所在的层次数,PH最小，查找性能最优
$PH=\Sigma{w_ih_i}$
手动构造的方法就是: $w_i$ 越大，就越在上层

代码实现:代价比较高，时间复杂度为 $O(n^3)$ ，有一种构造方式创建的判定树的查找性能同最优查找树仅差 1% - 2%，称这种极度接近于最优查找树的二叉树为次优查找树。

构造次优查找树

基本思想:选出一个结点，使得它左右两侧的子数组的权值累加和之差的绝对值最小。把这个结点当做根节点，递归地用刚才的左右字数组构造它的左右子树。

已知序列{rl…rh}对应权值为{wl…wh}，定义 $\Delta{P_i}=|\sum\limits_{j=i+1}^hw_j-\sum\limits_{j=l}^{i-1}wj|$

如果对每一个元素都这样计算就有很多重复计算，效率低，我们引入累计权值和swj就可以快速求出 $\Delta{P_i}$ ,例如 $\Delta{P_j}=||sw_h-sw_j|-|sw_{j-1}-sw_l||$


关键字		A	B	C	D	E	F	G	H	I
权值	0	1	1	2	5	3	4	4	3	5
j	0	1	2	3	4	5	6	7	8	9
swj	0	`1`	`2`	`4`	`9`	`12`	`16`	`20`	`23`	`28`
△Pj		27	25	22	15	7	`0`	8	15	23
（根）							`↑i`
△Pj		11	9	6	`1`	9		8	`1`	7
（根）					`↑i`				`↑i`
△Pj		3	`1`	2		`0`		`0`		`0`
（根）			`↑i`			`↑i`		`↑i`		`↑i`
△Pj		`0`		`0`
（根）		`↑i`		`↑i`

构造好的次优二叉树如图

代码实现:DataStructuresAndAlgorithms/C/Search/secondOptimal.cpp at master · OneLastChick/DataStructuresAndAlgorithms (github.com)

索引顺序表的查找

也叫分块查找,是顺序查找的一种改进方法,实现除了需要查找表本身之外，还需要根据查找表建立一个索引表
条件:索引表按关键字有序，查找表或者有序或者分块有序，分块有序指的是第二个子表中所有记录的关键字均大于第一个子表中的最大关键字.。设n个记录分为b个块
基本思想：分两步进行
1. 确定要查找的关键字可能存在的子表
2. 在具体的子表中进行顺序查找
在第一步确定块（子表）时，由于索引表中按照关键字有序，所有可以采用折半查找算法。而在第二步中，由于各子表中关键字没有严格要求有序，所以只能采用顺序查找的方式。因此此种算法可以是介于折半和顺序的，是两种算法的简单合成
性能分析:
- $ASL_{bs}=L_b+L_w$ ,Lb为查找索引表确定，所在块的平均查找长度,Lw为所在块中查找元素的平均查找长度
- 一般情况下长度为 $n$ 的表，被均匀分为 $b$ 块，每块含有 $s$ 个记录, $b=\lceil \frac{n}{s} \rceil$
  1. 若用顺序查找确定所在块
    $ASL_{bs}=L_b+L_w=\frac{b+1}{2}+\frac{s+1}{2}=\frac{1}{2}(\frac{n}{s}+s)+1$
    最佳分块:显然是 $s=\sqrt{n}$
  2. 若用折半查找确定所在块
    $ASL_{bs}\approx{log_2(\frac{n}{s}+1)+\frac{s}{2}}$
代码实现 DataStructuresAndAlgorithms/C/Search/blockSearch.cpp at master · OneLastChick/DataStructuresAndAlgorithms (github.com)

动态查找表

二叉排序树

概念:二叉排序树又称二叉平衡树(binary sort tree)。二叉排序树或者是一棵空树，或者是具有以下性质的二叉树:
- 若它的左子树不空，则左子树上的所有结点的值均小于它的右子树节点
- 若它的右子树不空，则右子树上的所有结点的值均大于它的左子树节点
- 它的左右子树也分别为二叉排序树
查找
- 查找过程和次优二叉树类似
- 首先和根节点比较，相等则成功，大于则在右子树继续查找，小于则在左子树继续查找
插入
- 二叉排序树是一种动态树表，与次优二叉树相对。特点在与树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入
- 如果当前节点为空，则创建新节点
- 如果插入的值小于当前节点的值，递归插入到左子树
- 如果插入的值大于当前节点的值，递归插入到右子树
- 简而言之就是在查找不成功的时候，返回插入位置，在该位置插入
删除

假设在二叉排序树上被删结点为*p,其双亲节点为*f,且不失一般性，设*p是*f的左孩子

PL表示其左子树，PR表示其右子树

删除有以下三种情况
- 若*p节点为叶子节点，即PL与PR均为空树。则只需要设置双亲节点的的孩子指针为NULL
- 若*p节点只有左子树PL或者只有右子树PR。则只令PL或者PR成为双亲节点的子树即可
- 若*p节点的左子树和右子树均不空。中序遍历二叉排序树得到的有序序列 $\{...C_LC...Q_LQS_LSPP_RF...\}$ 为了保证中序遍历后，删去该元素仍然保持其他元素的相对位置不变，有两种做法
  1. 让P的直接前驱S代替P
    
    P的直接前驱S是PL中的最大值，即左子树中的最大值
    
    f->lchild=s；s->rchild=PR;
  2. 让P的直接后继S代替P
    
    p的直接后继S是PR中的最小值，即右子树中的最大值
    
    f->rchild=s; s->lchid=PL;
遍历
- 中序遍历二叉排序树可以得到一个关键字的有序序列。这个是由二叉树的定义决定的
性能分析：

查找成功的平均查找长度为： Σ(本层高度*本层结点个数) / 结点总数
查找不成功的平均查找长度为： Σ(本层高度*本层补上的叶子结点个数) / 补上的叶子总数

显然,含 $n$ 个节点的二叉排序树的平均查找长度和树的形态有关。
- 最坏的情况：当先后插入的关键字有序时，构造的二叉排序树蜕变为单支树。树的深度为n，ASL=(n+1)/2
- 最好的情况: 二叉排序树的形态和折半查找的判定树相同，其ASL与log2n成正比
- 平均性能:书上的公式推导~~鼠鼠看不懂捏~~
  
  结论就是在随机情况下，二叉排序树的ASL与logn是等数量级的
- ASL的手算
代码实现:用C++封装了一个类DataStructuresAndAlgorithms/C/Search/binarySearchTree.cpp at master · OneLastChick/DataStructuresAndAlgorithms (github.com)

平衡二叉树

平衡二叉树(AVL树)_哔哩哔哩_bilibili讲的很清晰

可以发现二叉搜索树，在有序的情况下，会退化成顺序表，大幅降低搜索效率，由此平衡二叉树优化了这个问题

概念:平衡二叉树(Balanced Binary Tree)又称AVL树。它或是一棵空树，或是具有下列性质的二叉树
- 它的左子树和右子树都是平衡二叉树
- 左子树和右子树的深度之差的绝对值不超过1，定义该节点的平衡因子BF为该节点的左子树深度减去右子树的深度，取值范围为-1,0,1

查找，插入，删除的过程和二叉搜索树是相同的，只不过失衡的时候需要调整

构造:简而言之，AVL树就是对二叉搜索树的生成过程进行调整后的树.

依次插入元素(按照二叉排序树的方式)，若出现不平衡，则要根据新插入的结点与最低不平衡结点的位置关系进行相应的调整。分为LL型、RR型、LR型和RL型4种类型

构建调整

两种操作：(原则:不改变中序遍历的序列)
- 左旋:向左旋转，冲突的左孩变右孩
- 右旋:向右旋转，冲突的右孩变左孩
4种情况对应的失衡调整策略:(书中讲的很详细，建议读一读)
1. LL型
  - 失衡结点:BL=2
  - 失衡结点左孩子:BL=1
    
    对失衡的节点进行右旋
2. RR型
  - 失衡结点:BL=-2
  - 失衡结点右孩子:BL=-1
    
    与LL型是对称的，对失衡的节点进行左旋
3. LR型
  - 失衡结点:BL=2
  - 失衡结点左孩子:BL=-1
  左旋左孩子，再右旋失衡结点
  
  左旋:
  
  右旋:
4. RL型
  - 失衡节点:BL=-2
  - 失衡结点右孩子:BL=1
  右旋右孩子，再左旋失衡节点
  
  右旋:
  
  左旋:
  
  记忆技巧：对于失衡结点:2对应L，-2对应R，对于孩子结点:1对应L,-1对应R
  
  孩子结点是针对第一个L,R，如果第一个是L，则考虑左孩子
  
  在构建过程中：如果出现了多个节点失衡，只调整离插入节点最近的失衡结点即可保持平衡
删除

删除调整如果出现了多个节点失衡，需要依次沿着祖先依次向上检查调整平衡性

调整策略如上
性能分析：时间复杂度 $O(logn)$

上述对二叉排序树和二叉平衡树的查找性能的讨论都是在等概率的前提下进行的

若查找概率不等，则类似静态树表的查找进行构造次优查找树可进一步提高效率
代码实现:用C++类进行了简单的封装DataStructuresAndAlgorithms/C/Search/AVL.cpp at master · OneLastChick/DataStructuresAndAlgorithms (github.com)

B-树

概念:B-树是一种多叉平衡查找树,在文件系统中很有用,减少了硬件访问次数，读取包含多个元素的节点的耗时和读取单个元素的节点耗时几乎相同，而硬盘访问一次很耗时,因此B树主要用作文件的索引
性质
- 平衡：所有叶节点在同一层
- 有序：节点内有序，且任意元素的左子树都小于它，右子树都大于它，
- 多路一棵m阶的B-树，或是空树，或是满足下列特性的m叉树
1. 树中的每个节点至多有m棵子树，节点内的关键字个数最多m-1
2. 若根节点不是叶子节点，则至少有两棵子树
3. 除根之外的所有非终端节点至少 $\lceil \frac{m}{2} \rceil$ 棵子树
4. 所有的非终端节点中包含下列信息数据
  
  （n,P0，K1，P1，K2，…，Kn，Pn），其中P为指向子树的指针，K为关键字,n为关键字的个数
5. 所有的叶子节点都出现在同一层次,并且不带信息(可以看作是外部结点或查找失败的节点,为空节点)
B树高度的计算

B树的最小高度：

由于每个结点的子树最多为m，第一层1个结点，第二层m个结点，第三层m^2…

n≤(m-1)(1+m+m^2+m3+…+m^(h-1))=mh-1,

因此有== $h\ge{log_m(n+1)}$ ==

B树的最大高度:

由于根结点最少1个关键字，其余非叶结点最少⌈m/2⌉-1个关键字，所以第一层1个结点，第二层2个结点，第三层2⌈m/2⌉个结点…第h+1层即叶结点层至少有2(⌈m/2⌉)^(h-1)个结点，由于叶结点有n+1个(查找失败个数)，所以n+1≥2(⌈m/2⌉)^(h-1)，

因此有== $h\le{log_{\lceil \frac{m}{2}\rceil}(\frac{n+1}{2})+1}$ ==
查找
- 访问结点是在硬盘上进行的，而节点内的查找是在内存中进行的(这里略去外存的读写)具体而言,根据指针拿一个节点，是一次硬盘IO,根据关键字在节点内寻找目标是在内存中进行
- 查找过程:
  1. 在B-树中找节点(磁盘中取节点)
  2. 在节点中找关键字(顺序查找or折半查找)
- 性能分析
  
  在磁盘中查找的次数是决定B-树查找效率的首要因素
插入

课本P242有一个详细的过程
- 先查找到插入的位置进行插入（插入位置一定在叶节点)
- 如果没有上溢出（节点内的关键字个数超过了m-1)，无需调整
- 否则中间元素 $\lceil\frac{m}{2}\rceil$ 上移，两边分裂(直到没有上溢出为止)
分裂的方法是：

插入key后从中间位置⌈m/2⌉把结点分为两部分，左部分放在这个原结点中，右部分放在新结点中，中间位置⌈m/2⌉的结点插入到原结点的父节点。

若原结点的父节点因为⌈m/2⌉位置结点的插入导致必须分裂，继续重复上述操作即可。
删除

复习一下B-树的性质
- m阶B-树的结点最少有
  1. 根节点:2个分支，1个元素
  2. 其他节点: $\lceil \frac{m}{2}\rceil$ 个分支， $\lceil\frac{m}{2}\rceil-1$ 个元素
- 删除非叶节点，为了保证有序性，需要拿直接前驱或者直接后继进行替换，即都转换成删除叶节点元素，然后把该节点替换为删除的叶节点元素
- 如果叶节点元素没有下溢出(节点内的关键字个数低于要求)就无需调整
- 如果下溢出（就是删除该节点后,节点内的关键字个数少于最低要求）
  - 兄弟够借,父亲节点下去，兄弟节点上来(保证有序性)
  - 兄弟不够借,跟兄弟节点合并，删除该节点，父亲节点下移与其兄弟节点合并
  - 直接删除关键字:删除后仍然满足B树定义
代码实现:一个简单的实现:DataStructuresAndAlgorithms/C/Search/BTree.cpp at master · OneLastChick/DataStructuresAndAlgorithms (github.com)

B+树

概念:B+树是应文件系统（数据库)所需而出的一种B-树的变型树(严格来说已经不算树了)

一颗 $m$ 阶的 $B^+$ 树的性质:
1. 有 $n$ 棵子树的节点含有 $n$ 个关键字
2. 所有的叶子节点中包含了全部关键字的信息，以及指向含这些关键字记录的指针，且叶子节点本身依关键字的大小自小到大顺序连接
3. 所有的非终端节点可以看成索引部分，节点中仅含有其子树中最大或最小的关键字
$B$ 树与 $B^+$ 树的区别
1. **在B+树中，具有n个关键字的结点只含有n棵子树，**每一个关键字为其指向的子树根结点最大关键字。**在B树中，具有n个关键字的结点含有n+1个棵子树，**因为每一个关键字分为含有比它小关键字的子树和比它大关键字的子树。
2. 在B+树中，每个非根内部结点的关键字个数n的范围是⌈m/2⌉≤n≤m，根结点2≤n≤m。在B树中，每个非根内部结点的关键字个数n的范围是⌈m/2⌉-1≤n≤m-1，根结点1≤n≤m-1。
3. **在B+树中，叶结点包含全部信息，所以非叶结点仅起索引作用，**非叶结点中每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。
4. **在B+树中，**叶结点包含了全部关键字，非叶结点中出现的关键字也会出现在叶结点中；而在B树中，内部结点的关键字都是不重复的。
B+树上进行随机查找，插入，删除的分析过程基本上与B-树类似
查找:若非叶子节点上的关键字等于key时,并不终止，而是继续向下直到叶子节点
插入:B+树的插入仅在叶子节点中进行，当节点中的关键字个数大于m时,要分裂成两个结点，关键字个数分别为 $\lceil \frac{m+1}{2}\rceil$ 和 $\lceil \frac{m+1}{2}\rceil$ ，且双亲节点同时包含这两个节点中的最大关键字
删除:B+树的删除仅在叶子节点进行，当叶子节点中的最大关键字被删除时，其在非终端节点中的值可以作为一个分界关键字存在,若因删除而使节点中的关键字的个数少于 $\lceil \frac{m}{2}\rceil$ ，与其他兄弟节点的合并过程与B-树相同
代码实现:可以看看这篇文章B+Tree原理、算法的解析和实现，超详细，图+代码，ο(=•ω＜=)ρ⌒☆ - 掘金 (juejin.cn)

键树(Digital Search Trees)

概念:它是一棵度大于等于2的树，树中的每个节点不是包含一个或几个关键字，而是只含有组成关键字的符号
- 从根到叶子结点路径中节点的字符组成的字符串表示一个关键字，叶子节点中的特殊符号$表示字符串的结束
- 在叶子节点中还含有指向该关键字记录的指针
- 为了查找和插入方便，我们约定键树是有序数，即同一层中兄弟节点之间依所含字符从左到右有序,并约定$小于任何字符
- 键树中每个节点的最大度d与关键字的基有关，若关键词是单词则d=27，若关键词是数值，则d=11
- 键树的深度则取决于关键字中字符或数位的个数
键树的用途:快速查找，自动补全，字典存储，最长前缀匹配，数据压缩，统计功能，拼写检查和纠正

通常键树有两种存储结构,分别称为双链树和Trie树
- 双链树
  - 此种数据结构通常用左孩子，右兄弟链表来表示键树，则每个分支节点包括3个域：
    - symbol域：存储关键字的一个字符；
    - first域：存储指向第一棵子树根的指针；
    - next域: 存储指向右兄弟的指针；
    同时，叶子节点的infoptr域存储指向该关键字记录的指针。此时的键树又称双链树。上图所示的双链树如下图所示
  - 查找
    
    假设给定值为K.ch(0..num-1)，其中K.ch[0]至K.ch[num-2]表示待查关键字中num-1个字符，K.ch[num-1]为结束符$，从双链树的根指针出发，顺first指针找到第一棵子树的根节点，以K.ch[0]和此节点的symbol域比较，若相等，则顺first域再比较下一字符，否则沿next域顺序查找。若直至空仍比较不等，则查找不成功。
  - 键树中每个节点的最大度d和关键字的“基”有关。若关键字是单词，则d=27; 若关键字是数值，则d=11。键树的深度取决于关键字中字符或数位的个数。假设关键字为随机的（即关键字中每一位取基内任何值的概率相同），则在双链树中查找每一位的平均查找长度为(1+d)/2。又假设关键字中字符（或数位）的个数都相等，则在双链树中进行查找的平均查找长度为h*(1+d)/2。
    
    在双链树中插入或删除一个关键字，相当于在树中某个节点上插入或删除一棵子树
- Trie树
  - 若以树的多重链表表示键树，则树的每个节点中应含有d个指针域，此时的键树又称Trie树。若从键树中某个节点到叶子节点的路径上每个节点都只有一个孩子，则可将该路径上的所有节点压缩成一个"叶子节点"，且在该叶子节点中存储关键字及指向记录的指针等信息。例如，在ds-ds-tree所示的键树中，从节点Z到节点$为单支树，则在下图所示相应的Trie树中只有一个含关键字ZHAO及相关信息的叶子节点。由此，在Trie树中有两种节点：
    - 分支节点：含有d个指针域和一个指示该节点中非空指针域的个数的整数域
    - 叶子节点: 含有关键字域和指向记录的指针域
    在分支节点中不设数据域，每个分支节点所表示的字符均由其双亲节点中（指向该节点）的指针位置所决定。
  - 查找
    
    根节点出发，沿和给定值相应的指针逐层向下，直至叶子节点，若叶子节点中的关键字和给定值相等，则查找成功；若分支节点中和给定值相应的指针为空，或叶节点中的关键字和给定值不相等，则查找不成功。

哈希表

构造哈希函数

直接定址法

关键字的线性函数如 H（key）=a*key+b
数字分析法

假设关键字集合中的每个关键字key都是由s位数字组成,分析key中的全体数据，并从中提取分布均匀的若干位或他们的组合构成全体

此种方法通常用于数字位数较长的情况，必须数字存在一定规律，其必须知道数字的分布情况，比如身份证号有规律，我们事先知道这个班级的学生出生在同一年，同一个地区。就可以用H（key）=key%100000,截取后面不同的5位来存储
平方取中法

如果关键字的每一位都有某些数字重复出现频率很高的现象，可以先求关键字的平方值，通过平方扩大差异，而后取中间数位作为最终存储地址。

比如key=1234 1234^2=1522756 取227作hash地址
比如key=4321 4321^2=18671041 取671作hash地址
这种方法适合事先不知道数据并且数据长度较小的情况
折叠法

如果数字的位数很多，可以将数字分割为几个部分，取他们的叠加和作为hash地址
使用举例
比如key=123 456 789
我们可以存储在61524，取末三位，存在524的位置
该方法适用于数字位数较多且事先不知道数据分布的情况
除留取余法

H（key）=key MOD p （p<=m m为表长）
随机数法

H（key） =Random（key）取关键字的随机函数值为它的散列地址

处理冲突

开放定址法

首先有一个H（key）的哈希函数

如果H(key1)=H(keyi)

那么keyi存储位置 $H_i=(H(key)+d_i)MODm$

$d_i$ 有三种取法
1. 线性探测再散列
  
  $d_i=1,2,3,...,m-1$
2. 平方探测再散列
  
  $d_i=1^2,-1^2,2^2,-2^2...$
3. 随机探测再散列
  
  $d_i$ 是一组伪随机数列
  
  注意
  增量di应该具有以下特点（完备性）：产生的Hi（地址）均不相同，且所产生的s（m-1）个Hi能覆盖hash表中的所有地址
  - 平方探测时表长m必须为4j+3的质数（平方探测表长有限制）
  - 随机探测时m和di没有公因子（随机探测di有限制）
链地址法

产生hash冲突后在存储数据后面加一个指针，指向后面冲突的数据
再哈希法

准备若干个hash函数，如果使用第一个hash函数发生了冲突，就使用第二个hash函数，第二个也冲突，使用第三个……
建立公共溢出区法

建立一个特殊存储空间，专门存放冲突的数据。此种方法适用于数据和冲突较少的情况。

查找

查找过程和造表过程一致，假设采用开放定址法处理冲突，则查找过程为：
对于给定的key，计算hash地址index = H（key）
如果数组arr[index]的值为空则查找不成功
如果数组arr[index]== key 则查找成功
否则使用冲突解决方法求下一个地址，直到arr[index]== key或者 arr[index]==null

性能分析

决定hash表查找的ASL因素：
1）选用的hash函数
2）选用的处理冲突的方法
3）hash表的饱和度，装载因子 α=n/m(n表示实际装载数据长度 m为表长)
一般情况，假设hash函数是均匀的，则在讨论ASL时可以不考虑它的因素
hash表的ASL是处理冲突方法和装载因子的函数

可以看到无论哪个函数，装载因子越大，平均查找长度越大，那么装载因子α越小越好？也不是，就像100的表长只存一个数据，α是小了，但是空间利用率不高啊，这里就是时间空间的取舍问题了。通常情况下，认为α=0.75是时间空间综合利用效率最高的情况。

删除

首先链地址法是可以直接删除元素的，但是开放定址法是不行的，拿前面的双探测再散列来说，假如我们删除了元素1，将其位置置空，那 23就永远找不到了。正确做法应该是删除之后置入一个原来不存在的数据，比如-1

Chap10 内部排序

以上理解记忆

排序的稳定性:如果两个元素有相等的键值，在排序后这两个元素的相对顺序应保持不变

稳定:插帽归基

插入排序

直接插入排序(Straight Insertion Sort)

假设原始数组是：3 1 4 2 6 2 1 6 7

将数组分成两个区域，一个是有序区域一个是无序区域，最开始初始化有序区域（用黄色表示）为第一个数，无需区域为剩下部分。

第一次：3 1 4 2 6 2 1 6 7

将无序区域第一个数与有序区域作比较，判断该数适合插入的位置，这里就是1 和 3做比较，发现1应该插入3的前面

第二次：1 3 4 2 6 2 1 6 7

同理将4和 1 3 作比较确定插入位置

第三次：1 3 4 2 6 2 1 6 7

下面几次同理

第四次：1 2 3 4 6 2 1 6 7
第五次：1 2 3 4 6 2 1 6 7
第六次：1 2 2 3 4 6 1 6 7
第七次：1 1 2 2 3 4 6 6 7
第八次：1 1 2 2 3 4 6 6 7
第九次：1 1 2 2 3 4 6 6 7
- 稳定性：稳定
- 时间复杂度: $O(n^2)$
折半插入排序(Binary Insertion Sort)

在直接插入排序的基础上，在确定插入位置的时候使用了折半查找
- 稳定性:稳定
- 时间复杂度:由于折半插入排序仅仅减少了关键字的比较次数，而记录的移动次数不变，所以时间复杂度仍然是: $O(n^2)$
2-路插入排序
- 2-路插入排序是在折半插入排序的基础上进行改进，目的是减少排序过程中移动记录的次数
- 代价:需要借助n个记录的辅助空间
- 过程：简而言之，就是开个n个记录的辅助空间，然后front指向最小值,final指向最大值,利用`
  1. 双端队列:
    - 维护一个双端队列，这个队列能够在两端进行插入和删除操作。
    - 初始时，队列中只有一个元素，即原数组的第一个元素。
  2. 插入过程:
    - 对于每个新元素，通过比较该元素与队列两端的元素来决定插入位置：
      - 如果新元素小于队列的最左端元素，则插入到队列的左端。
      - 如果新元素大于队列的最右端元素，则插入到队列的右端。
      - 如果新元素介于队列的最左端和最右端元素之间，则需要找到合适的位置插入，这时可以通过移动元素来腾出位置。
  3. 最终排序:
    - 在插入完成后，双端队列中的元素已经按序排列好，只需将队列中的元素依次拷贝回原数组即可。
- 性能分析
  
  对每个元素而言，找到插入位置的时间复杂度仍然是 $O(n)$ ，这里 $n$ 是已排序部分的大小。插入操作涉及将元素插入到双端队列的某一端，因此每次插入的时间复杂度为 $O(1)$ 。
  
  综合分析有n个元素的数组的时间复杂度为 $O(n^2)$
表插入排序
- 思想
  当待排数组中的元素不是简简单单的整数，而是复杂的结构体，那么移动元素所花费的时间就不能忽略不计了，这时候我们要减少元素之间移动的次数了。表排序就是这么一个排序，在表排序的过程中，实际上是不需要移动元数的，我们要移动的是指向这些元素的指针。
  
  与标准的插入排序一样，表插入排序的核心思想是在已排序部分找到新元素的适当位置并将其插入。但不同的是，这里我们使用链表来实现已排序段的维护和新元素的插入。
- 基本过程
  1. 初始化：
    - 创建一个新的链表，并将第一元素作为链表的头结点。
  2. 遍历原数组：
    - 从第二个元素开始，逐一遍历未排序的元素，对每个元素进行插入操作。
  3. 插入操作：
    - 对于每个新元素，遍历已排序的链表，找到插入位置。
    - 在链表中找到第一个大于当前元素的节点，并将新元素插入到该位置之前。
  4. 更新链表：
    - 对每个新元素，调整链表的指针以保证链表始终保持有序。
- 性能分析：
  
  与2路插入排序类似均为 $O(n^2)$
希尔排序(Shell’s Sort)
- 基本思想:将数据分组，然后将每一组进行插入排序，每一组排成有序后，整理就是有序的
- 一般的过程：
  - 首先将gap设置为n/2,用gap进行分组,如上图
  - 对每个组进行简单插入排序
  - 令gap=gap/2
  - 重复分组排序操作
  - 直到gap=1再进行插入排序,结束，此时插入排序的对象就是一个基本有序的的数组
- 性能分析：
  
  我们知道，如果一个数组是有序的，那么插入排序的时间复杂度最好，为 $O(N)$ ,而希尔排序就是利用这个特性,设置gap先粗略分割排序数组,从而使插入排序趋于最好的情况
  
  因此希尔排序的时间复杂度介于 $O(N)$ 与 $O(N^2)$ 之间，平均性能为 $O(N^{1.3})$
  - 一些常用的间隔序列（如Hibbard序列、Sedgewick序列）可以使得希尔排序的性能接近 $O(N \log^2 N)$ 。

选择排序

简单选择排序(simple Selection Sort)

时间复杂度为 $O(n^2)$

i从0开始迭代到n-1，j寻找L[i+1]~L[last]最小的元素，SWAP L[i],L[min]
树形选择排序(Tree Selection Sort)
- 基本思想：树形选择排序（Tree Selection Sort），又称锦标赛排序（Tournament Sort），是一种按照锦标赛思想进行选择排序的方法。
  
  首先对n个记录的关键字进行两两比较，然后在其中[n/2]（向上取整）个较小者之间再进行两两比较，如此重复，直至选出最小关键字的记录为止。
胜者树和败者树是完全二叉树，是树形选择排序的变形。
- 过程：
  - 首先使用一维数组(长度为n)模拟完全二叉树(开辟2n长度的数组)
    
    这里的难点是如何构建
    
    将初始的数组元素作为叶子节点放置在底层(tree[n+i]=L[i])
    
    从底至顶构建比赛树，每层进行比较，败者向上晋级
    
    设root从1开始,父节点下标为i，左子节点的下标为2i，右子节点的下标为2i+1
```
for (int i = n - 1; i > 0; i--) {
        tree[i] = (tree[2 * i] < tree[2 * i + 1]) ? tree[2 * i] : tree[2 * i + 1];
    }
```
  - 通过比赛，确定当前最小元素
    
    将当前最小元素从原数组中移除，并在比赛树种重新进行比较和调整
    
    重复此过程，直到所有元素排序完成
  - 这里的难点是如何调整
    - 首先将已选择最小值的叶子节点设为无穷大（表示已经移除）
    - 从该叶子节点开始往上调整树，更新父亲节点的值
- 性能分析
  - 时间复杂度：
    1. 构建比赛树 $O(n)$
    2. 调整树，从该叶子节点向上进行 $O(logn)$ 次比较和更新，直至根节点
    3. 由于每次选择最小，然后调整树，综合起来的时间复杂度就是 $O(logn)$
  - 空间复杂度
    
    需要额外的 $O(n)$ 空间来存储比赛树，不太好
- 代码实现
  
  DataStructuresAndAlgorithms/C/Sort/treeInsertionSort.cpp at master · OneLastChick/DataStructuresAndAlgorithms (github.com)
堆排序(Heap Sort)

堆排序是对树形选择排序的改进,避免了空间复杂度太高

【从堆的定义到优先队列、堆排序】 10分钟看懂必考的数据结构——堆_哔哩哔哩_bilibili
- 堆的定义:
  1. 堆是一个完全二叉树
  2. 堆序性
    - 大根堆:每个父节点元素都要大于它的子节点元素
    - 小根堆:每个父节点元素都要小于它的子节点元素
- 堆的存储
  
  如果用数组存储，如上图
  
  节点下标为i
  
  左子节点下标为2i+1
  
  右子节点下标为2i+2
- 堆的基本操作
  - 上滤
    
    只有树的最后一个元素破坏了堆序性，就跟父节点比较，如果大于就交换
    - 用于插入新元素到堆中
    - 复杂度为 $O(logN)$
    - 可以构建成堆
  - 下滤
    
    将破坏了堆序性的节点(父节点)与它的最大的子节点进行比较,如果小于它的最大子节点，则与之交换;持续比较，交换，直到该元素大于它的子节点位置或者下滤到底部
    - 复杂度为 $O(logN)$
    - 可以重新构建成堆
- 堆的构建
  - 自顶向下建堆法
  过程:1.插入堆 2.上滤
  
  复杂度 $O(NlogN)$
  - 自下而上建堆法
    
    过程:对每个父节点进行下滤
    
    复杂度 $O(N)$
- 堆的应用
  1. 优先队列
    
    用小根堆弹出最小元素
- 堆排序
  - 首先自下而上建立大顶堆，时间复杂度为O(N)
  - 再调整堆，把根节点(最大值)和队尾元素交换位置，再进行下滤操作，反复进行,时间复杂度为 $O(logN)$
  综合起来的时间复杂度就是 $O(NlogN)$
  
  代码实现:DataStructuresAndAlgorithms/C/Sort/heapSort.cpp at master · OneLastChick/DataStructuresAndAlgorithms (github.com)

交换排序

冒泡排序(Bubble Sort)
- 时间复杂度 $O(N^2)$
快速排序(Quick Sort)
- 基本思想
  1. 选定Privot中心轴
  2. 将大于Pivot的数字放在Pivot的右边
  3. 将小于Pivot的数字放在Pivot的左边
  4. 分别对左右子序列重复前三步操作
  Privot选什么都行
  
  关键是如何把子序列给排序(利用双指针法)
  - 首先设置l指针,r指针指向起始位置,先SWAP L[last],Pivot
  - 此时，l和r都指向最左端的元素，开始迭代比较
    
    我们可以利用双指针法，将l视作小于Pivot序列和大于Pivot序列的分界线，而r视作大于Pivot和未探索区域的分界线,区间均为左闭右开
    
    如果r指向的元素大于Pivot,r++,如果r指向的元素小于Pivot,交换L[r]与L[l],l++,r++
    
    最后r指向末尾，结束迭代
  - 最后,SWAPL[last]与L[l]
- 性能分析:根据算法的过程，显然是不稳定的,
  
  时间复杂度为 $O(NlogN)$
- 代码实现:DataStructuresAndAlgorithms/C/Sort/quickSort.cpp at master · OneLastChick/DataStructuresAndAlgorithms (github.com)

归并排序

归并排序(Merge Sort)
- 基本思想:
  
  递归
  
  归并排序算法有两个基本的操作，一个是分，也就是把原数组划分成两个子数组的过程。另一个是治，它将两个有序数组合并成一个更大的有序数组。
  
  将待排序的线性表不断地切分成若干个子表，直到每个子表只包含一个元素，这时，可以认为只包含一个元素的子表是有序表。
  将子表两两合并，每合并一次，就会产生一个新的且更长的有序表，重复这一步骤，直到最后只剩下一个子表，这个子表就是排好序的线性表。
- 关键:
  
  把原数组划分为子数组很简单，利用递归
  
  关键是分完了如何合并成一个更长的有序数组?
  - 首先，从图中可以看出，每个merge操作都是针对两个子数组(用L,R代称)而言的
    
    那么我们开辟一个数组T用于存储归并好的数组，设置三个指针，i和j分别指向两个子数组的首位,k指向T数组的首位
    - 如果L[i]<=R[j],则T[k]=L[i],i++
    - 如果L[i]>R[j]，则T[k]=R[j]，j++
    - 显然当i或j指向末尾了就不能继续比较操作了，由于我们每个子数组都是有序的（根据递归得到的),我们可以直接复制L或R剩余的元素到T中,获得有序的长数组
- 性能分析：
  
  显然，归并排序是稳定的
  
  时间复杂度为 $O(NlogN)$
- 代码实现DataStructuresAndAlgorithms/C/Sort/mergeSort.cpp at master · OneLastChick/DataStructuresAndAlgorithms (github.com)

分类排序

计数排序

例如，一个序列具有 $10^8$ 个元素，但是范围都在 $[1,1000]$ 之间
思想

计数排序是一种非比较排序算法，适用于已知范围内的整数序列。其基本思想是通过统计每个元素出现的次数，然后累积这些次数来确定每个元素在排序后数组中的位置。由于它直接对输入数据的值进行计数，所以适合数值范围有限的数据规模。计数排序具有线性时间复杂度，在特定条件下是非常高效的。
过程：
- 计算并存储每个元素的出现次数。
- 累计这些出现次数，计算元素应该放置的位置。
- 按照计算的位置将元素放置到输出数组中。
时间复杂度：
- 初始化和遍历输入数组的时间复杂度 $O(n)$
- 计数数组累加的时间复杂度为 $O(k)$ ,其中 $k$ 是计数数组的长度
- 总的时间复杂度 $O(n+k)$

桶排序

基本思想：与计数排序比较类似

流程是：
- 通过映射函数将序列分到有限数量的桶里
- 对每个桶进行单独排序
- 汇总:依次将各个桶中的值输出
例如，对于序列 $[79,29,18,27,23,89,7,56,53,21,48,33,47]$

考虑映射函数 $num[i]/10$ ,然后在每个桶的元素进行排序，然后再输出
性能分析
- 时间复杂度
  - 最坏情况： $O(n^2)$ ，所有元素都落在同一个桶
  - 平均情况: $O(n+m)$ ,其中 $n$ 是元素个数， $m$ 是桶的数量
  - 最好情况: $O(n)$ ,假设元素均匀分布且每个桶都均匀分配
- 空间复杂度
  
  额外的存储空间 $O(n+m)$ 即用于存储桶的空间

基数排序

数据结构算法———基数排序-CSDN博客

讲的很清晰,是计数排序和桶排序的拓展

基本思想：将整数按位数切割成不同的数字，然后按每个位数分别比较*由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。*

例如给定数组[126,69,593,23,6,89,54,8]

关键字是3个，需要10个桶

对个位排序[593,23,54,126,6,8,59,89]

对十位排序[06,08,23,126,54,59,89,593]

对百位排序[006,008,023,054,069,089,126,593]

这个就是LSD法
多关键字的排序
- 最高位优先（Most Sifnificant Digit first)
  
  从最高位向最低位依次按位进行排序。
- 最低位优先 (Least Significant Digit first)
  
  从最低位向最高位依次按位进行排序。
注意这个只是对关键字次序进行排序，并未规定对每个关键字进行排序使用的方法，可以根据不同情形选择合适的排序算法,如果是整数的话，一般跟计数排序结合
代码实现:OneLastChick/DataStructuresAndAlgorithms: 学习数据结构和算法的记录 (github.com)
链式基数排序(Radix Sort)
- 基本思想：链式基数排序是一种变体基数排序，利用链表处理每个桶中的元素而不是数组。它适用于输入数据分布较分散的情况，能够有效管理内存动态分配，避免了数组大小的预分配问题。
  
  将元素根据每个位上的数字分配到不同的桶中，每个桶使用链表实现，逐位处理从最低有效位到最高有效位（或相反），最后将结果合并得到有序的序列。
性能分析
- 对于 $n$ 个记录，(假设每个基数含 $d$ 个关键字，每个关键字的取值范围为 $rd$ 个值)进行链式基数排序的时间复杂度为 $O(d(n+rd))$
- 其中每一趟分配的时间复杂度为 $O(n)$ ,每一趟收集的时间复杂度为 $O(rd)$ ,整个排序需要经过 $d$ 趟收集分配

Chap11 外部排序

概念:外存中的数据读入内存->在内存中排序->数据写入外存
基本思想:采用归并排序的思想和方法
基本过程：
1. 首先，按可用内存大小，将外存上含n个记录的文件分为若干长度为l的段
2. 依次读入内存并利用内部排序算法重新写入外存，称之为归并段
3. 对这些外部归并段读入内存进行逐趟归并后写入外存，使归并段逐渐由小到大
时间开销:外部排序所需总的时间=内部排序（产生初始归并段)所需的时间( $m*t_{IS}$ )+外存信息读写的时间( $d*t_{IO}$ )+内部归并所需时间( $s*ut_{mg})$
- $m$ 是经过内部排序后得到的初始归并段的个数, $t_{IS}$ 是为得到一个归并段经过内部排序所需的时间均值
- $d$ 为总磁盘IO次数， $t_{IO}$ 是进行一次读/写时间均值
- $s$ 为归并趟数， $ut_{mg}$ 为对 $u$ 个记录进行内部归并所需时间
例如，假设有10000个记录的文件，每个物理块容纳200个记录，并且有10个初始归并段，计算时间开销?

首先，有10个初始归并段，那么经过了10次内部排序得到了10个初始归并段，磁盘IO次数为:(10000/200)*2=100

然后.10个归并段，需要 $\lceil log_210\rceil$ 趟，归并的IO=d*50*2=400,总IO为400+100=500

因此所需总时间为 $10*ts+500*t_{IO}+4*10000*ut_{mg}$
- 由于 $t_{IO}$ 很耗时，提高外排的效率主要应着眼于减少外存信息读取的次数 $d$
优化:
- 多路归并
  - 一般情况下对于 $m$ 个初始归并段，进行k-路平衡归并
    
    归并的趟数为 $s=\lceil log_k{m}\rceil$
    
    可以看到增大k可以减少s，进而减少d，从而提高效率
- 利用败者树实现k-路归并
  
  单纯增加k会导致 $ut_{mg}$ 增加，原因如下
  
  对k-路归并而言，令u个记录分布在k个归并段，每得到一个关键字最小的记录需要k-1次比较，因此为得到含u个记录的归并段需要(u-1)(k-1)次比较,由于进行了s趟归并，总的比较次数就是s(u-1)(k-1)
  
  对n个记录而言
  
  内部归并所需的时间为 $\lceil log_k{m}\rceil(k-1)(n-1)t_{mg}$ ,k增大会导致比较次数增大，进而导致内部归并排序时间增大
  
  如果我们在归并比较阶段使用败者树，那么比较次数仅需 $log_2{k}$ ，从而使内部归并所需时间消掉k的影响，进而提高效率,这里并非完全消除k的影响，k的选择并非越大越好
- 置换-选择排序
  
  这是是从减少m的角度来提高外排效率
  
  $m=\lceil \frac{n}{l} \rceil$ ,若要减少m，就要增大l，，先前的内部排序方法受到工作区内存大小的限制，即l的大小不能超出工作区内存，而如果采用置换选择排序，就可以突破工作区的限制
  
  置换-选择排序具体过程课本P300
- 利用败者树实现置换选择排序
  
  具体构建:P303
  
  败者树可以提高置换选择排序的效率
- 最佳归并树
  
  使用了置换选择排序，每个段长度不等，磁盘IO次数也不等
  
  将磁盘IO次数视作归并树的权值，
  
  那么构建归并树时，构建为哈夫曼树，就可以使磁盘IO次数最小，称之为最佳归并树
  
  由于最佳归并树是完全k叉树，当段的数量不满足条件时，我们可以添加长度为0的虚段使之进行构建哈夫曼树
  
  $n_k+n_0=n$
  
  $n-1=kn_k$
  
  联立得 $n_k=\frac{n_0-1}{k-1}$
  
  能构建则nk为整数也就是说若 $m-1\quad mod \quad k-1$ 为0就不需要添加，不为0，就添加虚段直到为0
- 模拟实现
  
  DataStructuresAndAlgorithms/C/Sort/outSort.cpp at master · OneLastChick/DataStructuresAndAlgorithms (github.com)

About

Chap2 线性表

单链表

类型

单链表的建立

生成带头结点的单链表

生成无表头结点的单链表

单链表的插入

循环链表

Chap6 树和二叉树

树的定义和基本术语

定义

术语

性质

存储结构

二叉树

遍历二叉树和线索树

遍历

线索二叉树

森林

森林与二叉树的转换

并查集

树的应用

哈夫曼树

树的计数

Chap7 图

图的定义和术语

图的存储结构

数组表示法/邻接矩阵(顺序)

邻接表/逆邻接表（顺序+链式)

十字链表

邻接多重表

图的遍历

深度优先搜索

广度优先搜索

图的连通性问题

无向图的连通分量和生成树

最小生成树

Prim算法

关节点和重连通分量

有向无环图

拓扑排序

关键路径

最短路径

Chap8 动态存储管理

Chap9 查找

静态查找表

顺序表查找

有序表查找

静态树表查找

索引顺序表的查找

动态查找表

二叉排序树

平衡二叉树

B-树

B+树

键树(Digital Search Trees)

哈希表

构造哈希函数

处理冲突

查找

删除

Chap10 内部排序

插入排序

选择排序

交换排序

归并排序

分类排序

计数排序

桶排序

基数排序

从最低位向最高位依次按位进行排序。

Chap11 外部排序