栈和队列

栈的应用
1. 数值转换
2. 括号匹配的检验
3. 行编辑程序
4. 迷宫求解（DFS问题）
5. 表达式求值
栈与递归的实现
1. 典型题：汉诺塔问题
2. 运行被调用函数：(1) 将所有的实在参数、返回地址等信息传递给被调用函数保存；(2)为被调用函数的局部变量分配存储区；(3) 将控制转移到被调函数的入口。
3. 返回调用函数：(1) 保存被调函数的计算结果；(2) 释放被调函数的数据区；(3) 依照被调函数保存的返回地址将控制转移到调用函数。
队列的应用
1. 离散事件的模拟

串

堆分配存储表示

以一组地址连续的存储单元存放串值字符序列，但存储空间是由程序执行过程中动态分配而得的，存在堆中（由malloc()和free()来管理）。

存储密度 = 串值所占的存储位/实际分配的存储位（对于链式存储方式）

模式匹配算法——KMP算法（时间复杂度 $O(n+m)$ ）

前缀：不包含最后一个字符的所有以第一个字符开头的连续子字符串；
后缀：不包含第一个字符的所有以最后一个字符结尾的连续子字符串；
- eg. 最大相等前后缀a为0，aa为1,aab为0，aabaa为2
每次匹配到第i个字符不同时，模式串比较指针回到第0~i-1字符
的最大前后缀长度的位置。
用next数组代表匹配失败后模式串跳转的位置，next数组求法：

// 初始化
int j = -1;
next[0] = j;
    
// j指向前缀位置，i指向后缀位置
for (int i = 1; i < s.size(); i++) {
        
    // 前后缀不同情况
    while (j >= 0 && s[i] != s[j + 1]) {
        j = next[j];
    }
        
    // 前后缀相同情况
    if (s[i] == s[j + 1]) j++;
    next[i] = j;
}

模式串匹配算法

// next数组起始位置记录为-1
    int j = -1;
    for (int i = 0; i < s.size(); i++) {
        // 不匹配情况
        while (j >= 0 && s[i] != t[j + 1]) 
            // j寻找之前位置
            j = next[j];
        // 匹配，i,j同时向后移动
        if (s[i] == t[j + 1]) 
            j++;
        // 找到了模式串t
        if (j == (t.size() - 1)) return (i - t.size() + 1);
    }

用前缀表判断字符串是否可以由相同子串构成。

LeetCode.459

数组和广义表

随机存储：计算各个元素存储位置的时间相等，存储数组中任一元素的时间也相等。
稀疏矩阵
1. 基于三元组存储的稀疏矩阵转置方法：
  1. 按列序转置：多次扫描M的三元组，找到第一行、第二行、第n行的元素，由于M按行排序，故得到的顺序直接为在T中的顺序。（效率低下，时间复杂度 $O(n*m)$ )
  2. 快速转置：先扫描一遍M，记录每一行元素的个数，（需要额外的向量空间存储），在直接遍历M中的元素，直接确定转置后的位置。
2. 十字链表：每个非零元用含有五个域的结点表示（行、列、值、以及同行、同列下一个非零元），适合按行及按列操作的问题。

树和二叉树

树的同构：两棵树结构完全相同。（关系相同，字母可以不一样）
二叉树的性质
1. 二叉树的第 $i$ 层上最多有 $2^{n-1}$ 个结点
2. 深度为 $k$ 的二叉树最多有 $2^{k}-1$ 个结点
3. 对任何一个二叉树，叶子节点（度为0）的个数为 $n_0$ $n_{0}$ ，度为2的结点个数为 $n_2$ $n_{2}$ ，则 $n_0=n_2+1$ $n_{0} = n_{2} + 1$
  - 证明： $N=n_0+n_1+n_2=1+n_1+2n_2$ ，故 $n_0=n_2+1$
4. 具有n个结点的完全二叉树的深度为 $\lfloor log_2^n\rfloor+1$
5. 如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点 $i(1\le i\le n)$ $i (1 \leq i \leq n)$ ，有：
  1. 如果i=1，则结点i是二叉树的根，无双亲；如果i>1，其双亲为 $\lfloor i/2\rfloor$
  2. 如果 $2i\le n$ ，则其左孩子是2i；如果 $2i>n$ ，则结点i无左孩子；
  3. 如果 $2i+1\le n$ ，则其右孩子是2i+1；如果 $2i+1>n$ ，则结点i无右孩子；
满二叉树：一棵深度为k，有 $2^k-1$ 个结点的二叉树
完全二叉树：深度为k，有n个结点的二叉树当且仅当每一个结点都与深度为k的满二叉树中编号一一对应。
- 除最后一层外，每层都充满了结点，最下面一层结点都集中在该层的最左边。
- 小于2的结点只可能在层次最大的两层上出现，如果某个结点没有左孩子，那么它一定没有右孩子，该结点为叶子结点。
二叉树存储结构
1. 顺序存储：按完全二叉树的结点层次编号，依次存放二叉树中的数据元素
  - 浪费空间，适合存满二叉树或完全二叉树
2. 链式存储
  1
  2
  3
  4
  typedef struct BiTNode
  { TElemType data; //数据域
  struct BiTNode *lchild, *rchild;
  } BiTNode, *BiTree;
二叉树的遍历
1. 前序遍历：递归
2. 层次遍历：队列实现
3. 中序遍历：
4. 后序遍历：
二叉树的构建：已知前序+中序遍历或中序+后续或层次+中序可以推出唯一二叉树，已知前序+后序不可以。

线索二叉树

线索：指向线性序列中的前驱、后继的指针
若结点的左子树不空，线索指向左子树；若为空则指向前驱。

若结点的右子树不空，线索指向右子树；若为空则指向后继。

中序线索二叉树遍历

void InOrderTraverse_Thr(BiThrTree T, void (*Visit)(TElemType e)) {
    // T指向头节点（头节点不存储数据），头节点的左链lchild指向根节点
    // 中序遍历二叉线索树T的非递归算法，对每个数据元素调用函数visit
  	p = T->lchild;       // p指向根结点
  	while (p != T) {     // 空树或遍历结束时，p==T
    	while (p->LTag == Link)  p = p->lchild; // 链，第一个结点，即寻找当前根左子树的最左下
       	Visit (p->data);
     	while (p->RTag == Thread && p->rchild != T) { 
            // p->rchild != T 代表不为最后一个元素
            p = p->rchild;  
            Visit(p->data); 
        }  // 线索，后继结点
     	p = p->rchild; // p进至其右子树根
    }         
} // InOrderTraverse_Thr

中序遍历建立中序线索二叉树

void InThreading(BiThrTree p) {
    if (p) {
        InThreading(p->lchild); // 左子树线索化
        if (!p->lchild) {		// 前驱线索
            p->LTag = Thread;
            p->lchild = pre;
        }
        if (!pre->rchild) {		// 后继线索
            pre->LTag = Thread;
            pre->rchild = p;
        }
        pre = p;				// 保持pre指向p的前驱
        InThreading(p->rchild);·// 右子树线索化
    }
}

树和森林

双亲表示法
孩子表示法（多重链表（同构、不同构）、孩子链表）

孩子兄弟表示法（二叉树表示法）

转换
树和森林的遍历：

先根遍历：相当于转换为二叉树后前序遍历

后根遍历：先当于转换为二叉树的中序遍历

求树的深度

int CSTreeDepth(CSTree T) {
	int depth = 0;
	CSTree p;
	if (!T) return 0;	
	p = T->firstchild;
    // p不为空，则求以p为根的子树深度d（递归）
    while(p) {			
        d = CSTreeDepth(p);
        if (d > depth) depth = d;
		p = p->nextsibling;
	}
	return depth + 1;	
}

哈夫曼树
1. 构造
2. 应用：最佳判定树、哈夫曼编码

图

图的基本概念
1. 图：由两个集合V(G)和VR(G)组成,记为G=(V,VR)，V(G)是顶点的非空有限集，VR(G)是边的有限集合，边是顶点的有序对或无序对
2. 有向图：由两个集合V(G)和VR(G)组成，V(G)是顶点的非空有限集，VR(G)是有向边（即弧）的有限集合，弧是顶点的有序对，记<v,w>，v为弧尾，w为弧头
3. 无向图：由两个集合V(G)和VR(G)组成，V(G)是顶点的非空有限集，VR(G)是边的有限集合，边是顶点的无序对，记作(v,w)或(w,v)，并且(v,w)=(w,v)
4. 有向完全图：n个顶点的有向图最大边数是n(n-1)
5. 无向完全图：n个顶点的无向图最大边数是n(n-1)/2
6. 权：与图的边或弧相关的数
7. 网：带权的图
8. 子图：如果图G(V,VR)和图G‘(V’,VR‘),满足： $V'\subseteq V\enspace VR'\subseteq VR$ ，则称G‘为G的子图
9. 邻接点：顶点v和顶点w之间存在一条边，则称v和w互为邻接点；边(v,w)和顶点v和w相关联
10. 顶点的度：无向图中，顶点的度为与每个顶点相连的边数；有向图中，顶点的度分成入度与出度：
  - 入度：以该顶点为头的弧的数目
  - 出度：以该顶点为尾的弧的数目；
11. 路径：若从顶点vi经过若干条边能到达vj，称顶点vi和vj是连通的，又称顶点vi到vj有路径。
12. 路径长度：沿路径边的数目或沿路径各边权值之和
13. 回路：第一个顶点和最后一个顶点相同的路径
14. 简单路径：序列中顶点不重复出现的路径
15. 简单回路：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路
16. 连通：从顶点V到顶点W有一条路径，则说V和W是连通的
17. 连通图：图中任意两个顶点都是连通的图
18. 连通分量：非连通图的每一个连通部分
19. 强连通图：有向图中，如果对每一对 $V_i,V_j\in V,V_i\ne V_j$ ，从 $V_i$ 到 $V_j$ 和从 $V_j$ 到 $V_i$ 都存在路径，则为强连通图
20. 生成树：一个极小的连通子图，含有图中全部顶点，但只有足以构成一棵树的 $n-1$ 条边
21. 有向树：一个有向图中恰有一个顶点入度为0，其余顶点入度均为1
图的存储结构
1. 邻接矩阵
2. 邻接表
  1. 弧结点
    1
    2
    3
    4
    typedef struct Arcnode {
    int adjvex;
    struct Arcnode *nextarc;
    } ArcNode;
  2. 顶点结点
    1
    2
    3
    4
    typedef struct Vnode {
    VertexType data;
    ArcNode *firstarc;
    } VNode, AdjList[Max_Vertex_Num];
  3. 图的定义
    1
    2
    3
    4
    typedef struct {
    AdjList vertices;
    int vexnum, arcnum; //顶点及弧的数目
    } ALGraph;
  4. 无向图中，单链表中结点个数 = 边数 * 2
  5. 无向图中，顶点 $V_i$ 的度为第i个单链表中的结点数
  6. 有向图中，顶点 $V_i$ 的出度为第i个单链表中的结点数，顶点 $V_i$ 的入度为整个单链表中邻接点域为i的结点个数
    - 找邻接点容易，若找逆邻接点则需要逆邻接表
  7. 网的邻接表存储

图的遍历

DFS 深度优先

// 基于邻接表存储
int visited[MAX];
void DFSTraverse (ALGraph G) {  
    for (int i = 1; i <= G.vexnum; i++) {
        if (visited[i] == 0) DFS(G, i);
    }
}

void DFS(ALGraph G, int v)  {  
    ArcNode* w;      
    int i;
    cout<<v<<endl;  visited[v] = 1;
    w=G.vertices[v].firstarc; 
    while(w) {
        i = w->adjvex;    
        if (visited[i] == 0)  DFS(G,i);
        else  w=w->nextarc;  
    }   
}

BFS 广度优先

// 基于邻接表存储，队列实现
int visited[MAX];
void BFSTraverse (ALGraph G) {  
    for (int i = 1; i <= G.vexnum; i++) {
        if (visited[i] == 0) BFS(G, i);
    }
}

void BFS(ALGraph G, int v){  
    // 从顶点V出发遍历图
    
    // 初始化队列
    int Q[MAX], f = 0, r = 0, x;     
    ArcNode* w;
    cout<<v<<endl;  
    visited[v]=1;
    Q[r++]=v; 
    
    // 遍历（入队访问）
    while(f < r){   
        // 队头出队
        x=Q[f++];
        // 求x的邻接点w
        w=G.vertices[x].firstarc; 
        while(w)  {     
            x = w->adjvex;  
            if(visited[x] == 0){     
                visited[x] = 1;
                cout<<x<<endl;
				Q[r++]=x;    
            }
            // 遍历所有x的邻接点
            w = w->nextarc;  
        }
    }
}

应用：求两个顶点间的路径（DFS、BFS），求两个顶点间的最短路径（BFS）

生成树（所有顶点均由边连接在一起，但不存在回路的图）
1. 深度优先和广度优先生成树（利用遍历经过的分支构成的生成树）
2. 生成树的特点
  1. 一个图可以有许多棵不同的生成树
  2. 生成树顶点个数 = 图的顶点个数
  3. 生成树是图的极小连通子图
  4. 一个有n个顶点的连通图的生成树有n - 1条边
  5. 生成树中任意两顶点的路径唯一
  6. 生成树再加一条边必定形成回路，但具有n个顶点和n - 1条边的图不一定是生成树
3. 构建最小生成树
  1. Prim算法：不断加入顶点，使得加入的顶点与已有顶点构成的边中在已有顶点相邻的所有边中最小。
  2. Kruskal算法：在E中选取代价最小的边使得依附的顶点落在T中不同的连通分量上。
拓扑排序
1. AOV网：用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网
2. AOV网中不允许有回路，这意味着某项活动以自己为先决条件
3. 拓扑排序：把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程
4. 拓扑排序方法：
  1. 在有向图中选一个没有前驱的顶点且输出之
  2. 从图中删除该顶点和所有以它为尾的弧
  3. 重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止
关键路径：拓扑排序求事件最早开始时间 + 逆拓扑排序求事件最迟开始时间

最短路径

Dijkstra算法——某个源点到其余各顶点的最短路径
1. 思想：
  - 把顶点的集合V分成两组：S：{已求出最短路径的顶点}；T=V-S：{尚未确定最短路径的顶点}，保证:
    - 每一个顶点对应一个距离值，S中顶点：从V0到此顶点的最短路径长度；T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度
    - S中各顶点的距离值≤T中各顶点的距离值
  - 将T中顶点按最短路径递增的次序加入到S中，即每次从T中找出距离值最小的顶点加入到S中，直到S=V为止
2. 算法步骤
  1. 初始时，令 S={V0},T={其余顶点}，T中顶点Vi对应的距离值
    - 若存在<V0,Vi>，为<V0,Vi>弧上的权值
    - 若不存在<V0,Vi>，为∞
  2. 从T中选取一个其距离值为最小的顶点W，加入S，则S={V0, W}
  3. 对T中其余顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值
  4. 重复上述步骤，直到S中包含所有顶点，即S=V为止
3. 时间复杂度： $O(n^2)$

Floyd算法——每一对顶点之间的最短路径

void FLOYD(int cost[][M], int path[][M], int length[][M], int n) {
    int i, j, k;
    // 矩阵初始化
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++) {
            length[i][j] = cost[i][j];
            if (i == j)    path[i][j] = 0;
            else if (length[i][j] < MAX)   path[i][j] = i + 1;
            else  path[i][j] = 0;
        }
    // 加入顶点k作为中间顶点，求i->j的最短路径
    for (k = 0; k < n; k++)
        for (i = 0; i < n; i++)
            for (j = 0; j < n; j++)
                if (length[i][k] + length[k][j] < length[i][j]) {
                    length[i][j] = length[i][k] + length[k][j];
                    path[i][j] = path[k][j];
                }
}

查找

静态查找表（仅作查询和检索操作）

顺序查找
- $ASL=\dfrac{n+1}{2}$
- 时间复杂度： $O(n)$
- 改进方法：查找概率大的记录不断前移
二分查找（折半查找）
- 适用条件：采用顺序存储结构的有序静态查找表
- 查找过程：将待查记录区间缩小一半
- $ASL=log_2(n+1)-1$
- 时间复杂度： $O(log(n))$
静态树表
- 适用条件：各元素查找概率不等的有序表
- 注：构建静态最优查找树时间代价较高
- 构造近似最优查找树：已知一个按关键字有序的记录序列 $(r_l,r_{l+1},r_h)$ ，其中 $r_l.key\lt r_{l+1}.key\lt \dots\lt r_h.key$ ，每个记录权值 $w_l, \dots, w_h$
  
  构造方法：在记录序列中取第 $i(l\le i\le h)$ 个记录构造节点，使得 $\Delta P_i=|\sum_{j=i+1}^{h}w_j-\sum_{j=l}^{i-1}w_j|$ 取最小值，然后分别对子序列继续构造两棵次优查找树
分块查找
- 适用条件：分块有序表
- 查找过程：将线性表分为几块，块内无序，块间有序，先确定所在块，再在块内查找
- 算法实现：建立索引表i，含有数据域（本块最大关键字）和指针域（指向本块第一个结点）
- 注：可以使用链式存储
- 设将长为n的表平均分成b块，每块含s个记录，并设表中记录查找概率相等，则
  - 顺序查找： $ASL=\dfrac{b+1}{2}+\dfrac{s+1}{2}$
  - 二分查找+顺序查找： $ASL=log_2{(b+1)}+\dfrac{s}{2}$

静态查找方法比较

	顺序查找	折半查找	分块查找
ASL	$\dfrac{n+1}{2}$ (最大)	$log_2(n+1)-1$ (最小)	居中
表结构	有序、无序表	有序表	分块有序表
存储结构	顺序存储结构、线性链表	顺序存储结构	顺序存储结构、线性链表

动态查找表（查询的过程中可以插入和删除）
1. 二叉排序树（二叉查找树）
  1. 定义：是一棵空树，或具有如下性质：
    - 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
    - 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
    - 左、右子树本身又各是一棵二叉排序树
  2. 查找过程：空树则查找失败，相等查找成功，给定值小于根节点值在左子树上查找，反之在右子树上查找
  3. 二叉排序树的插入：若为空则作为根节点，否则从根节点查找直到某节点的左子树或右子树为空，将新节点作为叶子节点插入
  4. 二叉排序树的删除：
    1. P为叶子节点，直接删除
    2. P只有左或只有右孩子，用左或右孩子来代替P的位置
    3. P同时有左右孩子：在P的左子树上找到具有最大值的结点S（一直向右找，S没有右子树）
      1. 当S的左子树为空时，用S来替换P
      2. 当S的左子树不为空时，将S左子树成为S双亲的右子树，用S代替P
    4. 性能分析：与二叉树的构造方式有关，最好 $O(logn)$ ，最大退化为 $O(n)$
2. 平衡二叉树
  1. 平衡二叉树是一类改进的二叉排序树，它或是一棵空树，或是具有下列性质的二叉树：
    - 它的左、右子树深度之差的绝对值不大于1
    - 它的左、右子树都是平衡二叉树
  2. 平衡因子 $BF=h_L-h_R(-1,0,1)$
  3. 平衡二叉树的插入
    1. LL型和RR型——左右旋
    2. LR型
    3. RL型
  4. 性能分析
    1. 查找过程进行比较的关键字个数不超过平衡树的深度
    2. 时间复杂度 $O(logn)$
3. B-树
  1. 定义：B-树是一种平衡的多路查找树
    - 一棵m价B-树中每个结点至多有m棵子树
    - 所有非叶子结点包含信息： $n,p_0,k_1,p_1,\dots,k_n,p_n$
    在m阶B-树上，每个非终端节点可能含有：
    - n个关键字 $K_i(1\le i\le n),n<m$
    - n个指向记录的指针 $D_i(1\le i\le n)$
    - n+1个指向子树的指针 $P_i(0\le i\le n)$
  2. B-树的特性
    1. 非叶结点中的多个关键字均自小至大有序排列，即： $K_1< K_2 < … < K_n$ ；
    2. $A_{i-1}$ 所指子树上所有关键字均小于 $K_i$ ；
    3. $A_i$ 所指子树上所有关键字均大于 $K_i$ ；
    4. 树中所有叶子结点均不带信息，且在树中的同一层次上；
    5. 根结点或为叶子结点，或至少含有两棵子树；
    6. 其余所有非叶结点均至少含有 $\lceil m/2\rceil$ 棵子树，至多含有 $m$ 棵子树；
      
      其余所有非叶结点均至少含有 $\lceil m/2\rceil-1$ 个关键字，至多含有 $m-1$ 个关键字
      - 限制最少子树的原因：保证存储密度，防止树结构退化
  3. B-树的查找：是沿指针搜索结点和在结点内部顺序(或折半)查找两个过程交替进行。
    - 查找成功，返回结点指针及在结点中的位置
    - 查找失败，则返回插入位置
  4. B-树的插入：插入后若结点的关键字树n=m，需要进行节点分裂，令 $s=\lceil m/2\rceil$ ，在原结点中保留 $(A_0,K_1,\dots,K_{s-1},A{s-1})$ ，建立新结点 $(A_s,K_{s+1},\dots,K_n,A_n)$ ，将 $(K_s,p)$ 插入双亲结点，若双亲为空则建立新的根节点。
  5. B-树的删除
    
    B树和B+树的插入、删除图文详解 - nullzx - 博客园 (cnblogs.com)
  6. 查找性能分析
    
    在N个关键字的B-树上进行一次查找，需要访问的结点个数不超过 $log_{\lceil m/2\rceil}((N+1)/2)+1$
4. B+树
  
  B+树是应文件系统而出现的B-树的变型树（严格来说，已经不可以算作树了），在B+树上进行随即查找、插入、删除的过程基本上与B-树类似，只是在查找时，在非终端节点上的关键字不种植，而是继续向下找到叶子节点。
哈希表与哈希查找（散列查找）
1. 一些定义：
  1. 哈希表思想来源：希望表中位置与关键字之间存在确定关系，使得ASL=0
  2. 哈希表基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次就能得出所查元素是否存在
  3. 哈希函数：记录的关键字与记录的存储地址之间建立的一种对应关系
  4. 冲突： $key1\ne key2$ ，但 $H(key1)=H(key2)$ 的现象，又称碰撞
  5. 同义词：具有相同函数值的两个关键字
2. 哈希函数构造方法
  1. 直接定址法
    1. 构造：取关键字或关键字的某个线性函数作哈希地址
    2. 哈希函数： $H(key)=key$ 或 $H(key)=a*key+b$
    3. 特点：直接定址法所得的地址集合与关键字集合大小相等，不会发生冲突，但应用很少
  2. 数字分析法
    1. 构造：对关键字进行分析，取关键字的若干位或其组合作哈希地址
    2. 适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况
  3. 平方取中法
    1. 构造：取关键字平方后中间几位作哈希地址
    2. 目的是“扩大差别” ，平方值的中间位能受到整个关键字中各位的影响，适合于不知道全部关键字的情况
  4. 折叠法
    1. 构造：将关键字分割成位数相同的几部分(最后一部分可以不同)，取这几部分的叠加和(舍去进位)作为哈希地址
      - 移位叠加、间界叠加
    2. 适于关键字位数很多，且每一位上数字分布大致均匀的情况
  5. 除留余数法
    1. 构造：取关键字被p除后所得余数作哈希地址（p是某个不大于哈希表表长m的数）
    2. 哈希函数： $H(key)=key\enspace mod\enspace p,p\le m$
    3. 特点：简单常用，P的选取很重要，一般选取小于等于表长的最大素数
3. 冲突处理
  1. 开放定址法
    1. $H_i=(H(key)+d_i+m)\enspace MOD\enspace m$
      
      其中， $H_i$ 为新的哈希地址， $d_i$ 为增量序列， $m$ 为哈希表长
    2. 增量分类：
      1. 线性探测再散列： $d_i=1,2,3,\dots,m-1$
      2. 二次探测再散列： $d_i=1^2,-1^2,2^2,\dots,±k^2$
      3. 伪随即探测再散列： $d_i=$ 伪随机数序列
  2. 再哈希法
    1. $H_i=Rh_i(key),i=1,2,\dots,k$ ，直到不发生冲突为止，其中 $Rh_i$ 代表不同的哈希函数
    2. 特点：不易再次产生冲突，但计算时间增加
  3. 链地址法
    1. 所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放单链表的头指针
  4. 建立公共溢出区
4. 效率分析
  
  从以上结果可见：哈希表的平均查找长度是 a 的函数，而不是 n 的函数。这说明，用哈希表构造查找表时，可以选择一个适当的装填因子 a ，使得平均查找长度限定在某个范围内。

排序

排序的分类：
1. 插入排序：直接插入排序、折半插入排序、希尔排序
2. 交换排序：冒泡排序、快速排序
3. 选择排序：简单选择排序、堆排序
4. 归并排序：2-路归并排序
5. 基数排序：多关键字排序方法
稳定性：关键字相等的记录在排序前后次序始终不变

插入排序（每次将一个待排序的记录按关键字大小插入到已排好序列的适当位置）

直接插入排序

过程：先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序

算法描述

void InsertSort(SqList L) {  
   int i, j;
   for(i = 2; i <= L.length; i++)		// 将第二个到第n个记录依次插入
   {
      if(L.r[i].key < L.r[i-1].key) {
          L.r[0] = L.r[i];				// 将r[i]存储到监视哨
          for (j = i - 1; L.r[0].key < L.r[j].key; j--) {
              L.r[j + 1] = L.r[j];		// 若r[0] < r[j]，则r[j]后移
          }
          L.r[j + 1] = r[0];			// 将r[0]移至r[j + 1]
      }
   } 
 }

算法评价
1. 时间复杂度： $O(n^2)$
2. 空间复杂度： $O(1)$

折半插入排序

过程：用折半查找方法确定插入位置的排序

算法描述

void  BinSort(SqList& L) {
    int i, j, high, low, mid;
    for (i = 2; i <= L.length; i++) {
        L.r[0] = L.r[i];				// 设置监视哨
        low = 1; high = i - 1;
        while (low <= high) {			// 折半查找
            mid = (low + high) / 2;
            if (L.r[0].key < L.r[mid].key)
                high = mid - 1;
            else   low = mid + 1;
        }
        for (j = i - 1; j >= low; j--)	// 记录后移
            L.r[j + 1] = L.r[j];
        L.r[low] = L.r[0];				// 插入
    }
}

算法评价：
1. 时间复杂度： $O(n^2)$
2. 空间复杂度： $O(1)$

希尔排序
1. 过程：先将整个待排序记录分割成若干个子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
2. 示例：
3. 算法评价：
  1. 时间复杂度： $O(nlog_2n)-O(n^{1.5})$
  2. 空间复杂度： $O(1)$

交换排序（两两比较待排序记录的关键值，交换不满足顺序要求的记录）

冒泡排序

过程：类似冒泡，略

算法描述

void BubbleSort(SqList& L)
{
    int m, j, flag = 1;
    m = L.length - 1;
    while ((m > 0) && (flag = = 1))
    {
        flag = 0;
        for (j = 1; j <= m; j++)
            if (L.r[j].key > L.r[j + 1].key)	//如果逆序
            {
                flag = 1;
                // 交换
                L.r[0] = L.r[j];  
                L.r[j] = L.r[j + 1];  
                L.r[j + 1] = L.r[0];
            }
        m--;
    }
}

算法评价
1. 时间复杂度： $O(n^2)$
2. 空间复杂度： $O(1)$
3. 适用于元素较少或者初始序列基本有序

快速排序

过程：
1. 在待排序记录中任取一个记录(通常为1st记录) ，作为枢轴，将其它记录分为两个子序列：
  
  子序列1中，记录的关键值<枢轴的关键值；
  
  子序列2中，记录的关键值>=枢轴的关键值；
2. 将枢轴放置在两个子序列之间(即枢轴的最终位置)，完成一趟快速排序。
3. 分别对两个子序列重复上述过程，直到序列有序

算法描述

// 一趟快速排序
int  Partition(SqList& L, int low, int high) {
    KeyType  pivotkey;
    L.r[0] = L.r[low]; 
    pivotkey = L.r[low].key;	// 保存枢轴
    while (low < high) {		// 一趟快速排序
        while (L.r[high].key >= pivotkey && low < high)
            if (low < high) { L.r[low] = L.r[high]; low++; }
        while (L.r[low].key <= pivotkey && low < high)
            if (low < high) { L.r[high] = L.r[low]; high--; }
    }
    L.r[low] = L.r[0];	//放置枢轴
    return low;
}

// 快速排序
void  QuickSort(SqList& L, int low, int high) {
    int  pivotloc;
    if (low < high) {
        pivotloc = Partition(L, low, high);	// 记录返回枢纽位置
        QuickSort(L, low, pivotloc - 1);	// 快排两侧的序列
        QuickSort(L, pivotloc + 1, high);
    }
}

算法分析
1. 时间复杂度：
  - 最好情况：当每次选到中间值作为枢纽时， $T(n)=O(nlog_2n)$
  - 最坏情况：当初始序列升序，每次总选到最小元素做枢纽， $T(n)=O(n^2)$
2. 空间复杂度：
  - 最好情况：递归树深度为 $\lfloor log_2n\rfloor+1$ ， $S(n)=O(log_2n)$
  - 最坏情况： $S(n)=O(n)$
3. 内部排序方法中最好的以中，不适用于小规模数据

2-路归并排序

思想：
- 通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。
- 归并：将两个或两个以上的有序表组合成一个新的有序表
过程：
- 设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1
- 两两合并，得到 $\lceil n/2\rceil$ 个长度为2或1的有序子序列
- 再两两合并，……如此重复，直至得到一个长度为n的有序序列为止

算法描述：

// 将SR[i..m] 和SR[m+1..n]归并为TR[i..n]
void Merge(RcdType SR[], RcdType TR[], int i, int m, int n) {
    int  j, k;
    // 归并
    for (j = m + 1, k = i; i <= m && j <= n; ++k) {
        if (SR[i].key <= SR[j].key) TR[k] = SR[i++];
        else TR[k] = SR[j++];
    }
    // 如果有剩余则复制
    if (i <= m)for (; i <= m; i++, k++) TR[k] = SR[i];
    if (j <= n) for (; j <= n; j++, k++) TR[k] = SR[j];
}

// 2-路归并排序
void MSort(RcdType SR[], RcdType TR1[], int s, int t) {
    RcdType TR2[MAXSIZE];  int  m;
    // 当只有一个元素的时候，直接返回
    if (s == t) TR1[s] = SR[s];
    else {
        m = (s + t) / 2;			// 将SR[s..t]平分为SR[s..m]和SR[m+1..t]
        MSort(SR, TR2, s, m);		// 递归将SR[s..m]归并为有序TR2[s..m]
        MSort(SR, TR2, m + 1, t);	// 递归将SR[m+1..t]归并为有序TR2[m+1..t]
        Merge(TR2, TR1, s, m, t);	// 归并两个有序子序列到TR1[s..t]
    }
}

// 对顺序表进行归并排序
MSort(L.r, L.r, 1, L.length);

算法分析：
1. 对n个记录进行归并排序：每一趟归并的时间复杂度为 $O(n)$ ，总共进行 $\lceil log_2n\rceil$ 趟
2. 时间复杂度： $T(n)=O(nlog_2n)$
3. 空间复杂度： $S(n)=O(n)$

选择排序（每次从待排序记录中选出关键字最小的记录，顺序放在已排序的记录序列的后面）

简单选择排序

过程：首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换；再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换；重复上述操作，共进行n-1趟排序后，排序结束

算法描述

void SelectSort(SqList& L) {
    int i, j, k;
    for (i = 1; i < L.length; i++) {	// n-1趟排序，每趟找第i小的
        k = i;
        for (j = i + 1; j <= L.length; j++)	// 查找最小记录
            if (L.r[j].key < L.r[k].key)   
                k = j;
        if (i != k) {					// 若最小记录不在“适当”位置上，交换

            L.r[0].key = L.r[i];
            L.r[i] = r[k];
            L.r[k] = L.r[0].key;
        }
    }
}

算法评价
1. 时间复杂度： $T(n)=O(n^2)$
2. 空间复杂度： $S(n)=O(1)$

堆排序

堆定义：n个元素的序列 $(k1,k2,\dots,kn)$ ，当且仅当满足下列关系时，称之为堆

$(k_i\le k_{2i}\enspace\&\&\enspace k_i \le k_{2_i+1})\enspace||\enspace(k_i\ge k_{2i}\enspace\&\&\enspace k_i \ge k_{2_i+1})$

可将堆序列看成完全二叉树的顺序存储，堆顶元素（完全二叉树的根）必为序列中n个元素的最小值或最大值
堆排序过程：
1. 将无序序列建成一个堆，则堆顶是关键字最小(或最大) 的记录；
2. 输出堆顶记录后，将剩余的记录重新调整成一个新堆，则可得到次小值(或次大值) ；
3. 重复执行2 ，直到得到一个有序序列。
筛选法调整堆
1. 输出堆顶记录后，以堆中最后一个记录替代；将根节点值与左右孩子进行比较，并与其中最小者（最大者）进行交换；重复操作直至叶子节点，得到新的堆。
2. 利用小顶堆得到的是降序序列，大顶堆得到的是升序序列（小顶堆每次得到最小值，先进后出则为降序序列）
3. 例：已知小顶堆，输出堆顶后通过筛选，重新调整小顶堆
初建堆
1. 从无序序列的第 $\lfloor n/2\rfloor$ 个元素（即此无序序列对应的完全二叉树的最后一个非叶子结点）起，至第一个元素止，进行反复筛选。
2. 例：已知无序序列，通过反复筛选，建成小顶堆

算法描述

// 筛选法调整堆
// 调整H.r[s]的关键字，使H.r[s...m]成为一个小顶堆
// 不断和左右孩子最小的交换
void HeapAdjust(HeapType& H, int s, int m) {
    RcdType rc;  
    int j;
    rc = H.r[s];	// 暂存堆顶记录
    for (j = 2 * s; j <= m; j *= 2) {	// j指向其左孩子
        if (j<m && H.r[j].key > H.r[j + 1].key)	// 令j指向左右孩子中较小记录位置
            ++j;
        if (rc.key <= H.r[j].key)	// 如果比左右孩子都小，找到rc的插入位置，无需继续调整
            break;
        H.r[s] = H.r[j];			// 插入
        s = j;						// 否则记录上移，继续向下调整
    }
    H.r[s] = rc;
}

// 初建堆
void HeapSort(HeapType& H) {
    int i;
    // 初建堆
    for (i = H.length / 2; i > 0; i--)	// 从最后一个非叶子节点开始筛选
        HeapAdjust(H, i, H.length);
    // 堆排序
    for (i = H.length; i > 1; i--) {	// 将堆顶记录与当前未排序子序列的最后一个记录交换
        Swap(H.r[1], H.r[i]);
        HeapAdjust(H, 1, i - 1);		// 将H.r[1...i-1]重新调整成小顶堆
    }
}

算法评价
1. 时间复杂度：
  1. 初建堆 $\lfloor n/2\rfloor$ 次筛选，调整成新堆 $n-1$ 次筛选
  2. 时间复杂度： $O(nlog_2n)$
2. 空间复杂度： $S(n)=O(1)$

基数排序（借助“多关键字排序”的思想来实现“单逻辑关键字排序”）
1. 多关键字排序
  1. 最高位优先法：
    - 先对最高位关键字 $k^1$ 排序，将序列分成若干子序列，每个子序列有相同的 $k^1$ 值；然后分别就每个子序列对次关键字 $k^2$ 排序，又分成若干更小的子序列；依次重复，直至对关键字 $k^{d-1}$ 排序；分别就每个子序列对最低位关键字 $k^d$ 排序；最后将所有子序列依次连接在一起成为一个有序序列。
    - 必须将序列逐层分割成若干子序列，再对各子序列分别排序
  2. 最低位优先法（分配-收集）
    - 从最低位关键字 $k^d$ 起进行排序，再对高一位关键字排序；依次重复，直至对最高位关键字 $k^1$ 排序后，成为一个有序序列。
    - 不必逐层分割成子序列，并且可不通过关键字比较，而通过若干次分配与收集实现排序。
2. 链式基数排序
  1. 对于数字型或字符型的单逻辑关键字，可以看成是由多个数位或多个字符构成的多关键字，也可
    
    以采用“分配-收集”的排序方法。
    
    链式基数排序：用链表作存储结构的基数排序。
  2. 例：三位数的排序，从低位到高位三次分派、三次收集
  3. 算法评价（将n个记录，
    1. 时间复杂度：
      - 分配： $O(n)$
      - 收集： $T(n)=O(rd)$ 这里的rd是什么意思？
    2. 空间复杂度： $S(n)=O(rd+n)$
总结