# 绪论

• 每种数据结构都具备三个基本运算：插入、删除、查找。 $\color{red}$
  • 比如二维数据就没有插入和删除
• 逻辑结构不相同的数据，可以采用多种不同的存储方法。
• 原地工作算法指的是需要的临时空间的大小不依赖问题规模 $n$，空间复杂度为 $O(1)$。
• 数据结构在计算机内存中的表示是指数据的存储结构
• 算法分析的主要任务之一是分析算法的执行时间与问题规模之间的关系。
• 算法分析的目的是：分析算法的效率以求改进。
• 算法的可行性是指指令不能有二义性。 $\color{red}$
  • 可行性是指：算法中的所有操作可以通过已经实现的基本操作之执行有限次来实现。
• 数据的运算与采用何种存储结构有关。
• 在规定的时间内完成不是算法的基本特性。
• 时间复杂度为 $O(x)$ 表示的是执行时间与 $x$ 成正比。

# 链表

• 对于一个具有 n 个元素的线性表，建立其单链表的时间复杂度是 $O(n)$
• 在长度为 n 的带表头指针的、不带表头结点的循环单链表上，删除首元素的复杂度是 $O(n)$
• 线性表的顺序存储结构和链式存储结构相比，优点是便于随机存取
• 线性表的顺序存储结构和链式存储结构相比，优点是所有的操作算法实现简单 $\color{red}$
• 线性表是一个有限序列，可以为空
• 静态链表是使用顺序表（数组）作为存储形式的链表，结构体的指针域换成了记录下表
• 要求采用静态空间分配方式，且插入和删除操作时不需要移动元素，采用的存储结构是静态链表
• 如果对含有 $n~(n>1)$ 个元素的线性表的运算只有 $4$ 种，即删除第一个元素、删除尾元素、在第一个元素前面插入新元素、在尾元素的后面插入新元素，则最好使用只有开始数据节点指针没有尾节点指针的循环双链表

# 前插法

1
2
3

void headInsert(Node *head, int n) {
    head->next = new Node{n, head->next};
}

# 尾插法

1
2
3
4
5
6

void insert(Node *head, int n) {
    Node *tmp = head;
    while (tmp->next != null)
        tmp = tmp->next;
    tmp->next = new Node{n, null};
}

# 删除元素

1
2
3
4
5
6
7
8
9
10

void remove(Node *head, int n) {
    Node *tmp = head;
    while (tmp->next != null) {
        if (tmp->next->num == n) {
            tmp->next = tmp->next->next;
            return;
        }
        tmp = tmp->next;
    }
}

# 循环链表

1
2
3
4
5
6

void insert(Node *head, Node *tail, int n) {
    Node *tmp = head;
    while (tmp->next != tail)
        tmp = tmp->next;
    tmp->next = new Node{n, tail};
}

# 双向链表

# 插入

1
2
3
4
5
6
7

void insert(Node *head, int n) {
    Node *tmp = head;
    while (tmp->next != null)
        tmp = tmp->next;
    tmp->next = new Node{n, tmp, null};
    return;
}

# 删除

1
2
3
4
5
6
7
8
9
10

void remove(Node *head, int n) {
    Node *tmp = head;
    while (tmp->next != null) {
        if (tmp->next->num == n) {
            tmp->next->last = tmp, tmp->next = tmp->next->next;
            return;
        }
        tmp = tmp->next;
    }
}

# 栈

# 模拟栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include <bits/stdc++.h>
#define null NULL

using namespace std;

struct Node{
    int num;
    Node *next;
};

void push(Node *&head, int n) {
    head = new Node{n, head};
}

void pop(Node *&head) {
    if (head->next == null)
        return;
    else
        head = head->next;
}

int top(Node *head) {
    if (head->next != null)
        return head->num;
    else
        return -1;
}

bool isEmpty(Node *&head) {
    return head->next == null;
}

int main() {
    Node *head = new Node{0, null};

    for (int i = 1; i <= 10; i++)
        push(head, i);

    while (!isEmpty(head))
        cout << top(head) << " ", pop(head);
}

# 前缀 - 中缀 - 后缀表达式

• 中缀表达式 ： 常见的运算表达式，如 a * (b + c) - d
• 前缀表达式 (波兰表达式)： 运算符位于操作数之前，如 - * a + b c d
  • 计算：从右边开始扫描字符串，遇到数字全推入栈，遇到符号取出两个来计算，再推回去，最后的结果就是栈顶的数 `
• 后缀表达式 (逆波兰表达式)： 运算符位于操作数之后，如 a b c + * d -
  • 计算：从左边开始扫描字符串，遇到数字全推入栈，遇到符号取出两个来计算，再推回去，最后的结果就是栈顶的数

# 中缀转前缀

1. 初始化两个栈，① 运算符栈、② 中间结果栈
2. 从右到左扫描字符串
   • 遇到运算符时
     • 如果 ① 栈空，或者栈顶栈顶运算符为 ) ，则直接将此运算符入栈
     • 如果 ① 栈不空
       • 如果当前符号优先级 $\ge$ 栈顶符号，则压入 ① 栈
       • 否则不断弹出 ① 栈栈顶符号，并推入 ② 栈，直到 ① 栈空或者当前符号优先级 $\ge$ 栈顶符号
   • 遇到括号时
     • 如果是 ) ，则直接推入 ① 栈
     • 如果是 ( ，则依次弹出 ① 栈顶的运算符并推入 ② 栈，直到弹完 ) 位置
   • 遇到数字时，直接推入栈 ②
3. 重复步骤 $2\to5$，直到扫完最左边的一个字符，把 ① 栈剩余的字符取出，不断推入栈 ②
4. 依次弹出 ② 栈的元素，结果就是中缀表达式

# 中缀转后缀

1. 初始化两个栈，运算符栈 ① ，存储中间结果栈 ②
2. 从左到右扫描字符串
   • 遇到运算符时
     • 如果 ① 栈空，或者栈顶运算符为 ( ，则直接将此运算符入栈
     • 如果 ① 栈不空
       • 如果当前符号优先级 $\ge$ 栈顶符号，则压入 ① 栈
       • 否则，不断弹出 ① 栈栈顶符号，并推入 ② 栈，直到 ① 栈空或者当前符号优先级 $\ge$ 栈顶符号
   • 遇到括号时
     • 如果是 ( ，则直接压入 ① 栈
     • 如果是 ) ，则依次弹出 ① 栈顶的运算符并推入 ② 栈，直到弹完 ) 位置
   • 遇到数字时，直接推入栈 ②
3. 重复步骤 $2\to5$，直到扫完最左边的一个字符，把 ① 栈剩余的字符取出，不断推入栈 ②
4. 依次弹出 ② 栈的元素，结果就是中缀表达式

# 队列

# 模拟队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

#include <bits/stdc++.h>
#define null NULL

using namespace std;

struct Node{
    int num;
    Node *next;
};

void push(Node *&head, Node *&tail, int n) {
    if (head == null) {
        tail = new Node{n, null};
        head = tail;
    }
    else {
        Node *tmp = new Node{n, null};
        tail->next = tmp, tail = tmp;
    }
}

void pop(Node *&head) {
    if (head == null)
        return;
    else
        head = head->next;
}

int front(Node *head) {
    if (head == null)
        return -1;
    else
        return head->num;
}

bool isEmpty(Node *&head) {
    return head == null;
}

int main() {
    Node *head = null, *tail = null;

    for (int i = 10; i >= 1; i--) {
        push(head, tail, i);
    }

    while (!isEmpty(head)) {
        cout << front(head) << " ", pop(head);
    }
}

# 循环队列

循环队列是以顺序表来实现的

• front 队首指针指向队首元素的前一位置， rear 队尾指针指向队尾元素
  • 队满条件： (rear + 1) % maxsize == front
  • 判空： front(头) == rear(尾)
• 入队： rear = (rear + 1) % maxsize
• 队满： front == (rear + 1) % maxsize
• 计算元素个数：
  • rear > front ： 个数 = rear - front
  • rear < front ： 个数 = rear - front + maxsize
  • 综上， 元素个数 = (rear - front + maxsize) % maxsize

# 串与数组

# 串的模式匹配：$BF$ 算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

int find(string a, string b) {
    for (int i = 0; i <= a.size() - b.size(); i++) {
        bool able = true;

        for (int j = 0; j < b.size(); j++)
            if (a[i + j] != b[j]) {
                able = false;
                break;
            }

        if (able)
            return i;
    }

    return -1;
}

# 数组

数据是由类型相同的数据元素构成的有序集合，每个元素称为数据元素，每个元素受 $n~(n\ge1)$ 个线性关系的约束。

# 树

树是 $n~(n\ge0)$ 个结点的有限集，对于非空树：

• 有且仅有一个称为根的结点
• 除根结点以外的可以分为 $m~(m>0)$ 个互不相交的有限集 $T_1,..., T_m$，其中每个集合本身又是一棵树
  树的定义用到了：递归式定义（在定义中用到定义本身）

# 树的基本术语

• 结点：树中的一个独立单元
• 结点的度：结点拥有的字数的个数
• 树的度：树内结点度的最大值
• .....

# 二叉树

二叉树是 $n~(n\ge0)$ 个结点所构成的结合，二叉树与树的区别在于：

• 二叉树每个结点至多有两颗子树
• 子树有左右之分，不能颠倒（树可以随便排列）

# 二叉树的五种基本形态

# 二叉树性质

• 在二叉树的第 $i$ 层上至多有 $2^{i-1}~(i\ge1)$ 个结点
• 深度为 $k$ 二叉树至多有 $2^k-1~(i\ge1)$ 个结点
• 对任何一棵非空二叉树 $T$，如果其叶子结点树为 $n_0$，度为 $2$ 的结点树为 $n_2$，则满足 $\color{red}$
  • 证明：度为 $0$ 的结点数：$n_0$，度为 $1$ 的结点数：$n_1$，度为 $2$ 的结点数：$n_2$
  • 总结点数 = n0 + n1 + n2 = n1 + 2 * n2 + 1 （后一个是因为，树内的结点都是由度为 $1$ 或 $2$ 的结点射出的）
  • 约去都有的项即可
• 两个特殊的二叉树：
  • 满二叉树：深度为 $k$ 且含有 $2^k-1$ 个结点的二叉树
  • 完全二叉树：深度为 $k$、有 $n$ 个结点的二叉树，当且仅当其每个结点都与深度为 $k$ 的满二叉树中编号从 $1\to n$ 的结点一一对应
    • 叶子节点只可能在层次最大的两层出现
    • 对于任一结点，若其右分支下的子孙的最大层次为 $l$，则其左分支下的子孙的最大层次必为 $l$ 或 $l+1$
    • 具有 $n$ 个结点的完全二叉树的深度为 $\lfloor{log_2n}\rfloor+1$
    • 对一颗有 $n$ 个结点的完全二叉树（深度为 $\lfloor{log_2n}\rfloor+1$）的结点按层序编号（从第 $1$ 层到第 $\lfloor{log_2n}\rfloor+1$ 层，每层从左到右），则对任一结点 $i$，有以下结论
      • 如果 i = 1 ，则结点 $i$ 是二叉树的根；如果 i > 1 ，则其父节点是 $\lfloor{i/2}\rfloor$
      • 如果 2i > n ，则结点 $i$ 无左孩子（结点 $i$ 为叶子节点）；否则左孩子是 $2i$
      • 如果 2i + 1 > n ，则结点 $i$ 无右孩子；否则右孩子是 $2i+1$

# 二叉树的遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

#include <bits/stdc++.h>
#define null NULL

using namespace std;

struct Node {
    int num;
    Node* left, * right;

    Node(int n) : num(n), left(null), right(null) {}
};

void insert(Node*& root, int n) {
    if (root == null) {
        root = new Node(n);
        return;
    }

    if (n > root->num)
        insert(root->right, n);
    else
        insert(root->left, n);
}

// 中序 LDR
void LDR(Node* root) {
    if (root == null)
        return;
    
    LDR(root->left), cout << root->num << " ", LDR(root->right);
}

// 先序 DLR
void DLR(Node* root) {
    if (root == null)
        return;

    cout << root->num << " ", DLR(root->left), DLR(root->right);
}

// 后序 LRD
void LRD(Node* root) {
    if (root == null)
        return;

    LRD(root->left), LRD(root->right), cout << root->num << " ";
}

int main() {
    Node* root = null;

    int n;
    cin >> n;

    for (int i = 1, x; i <= n; i++)
        cin >> x, insert(root, x);

    cout << "\n中序: ", LDR(root);
    cout << "\n先序: ", DLR(root);
    cout << "\n后序: ", LRD(root);
}

# 二叉树的复制

1
2
3
4
5
6
7
8
9
10
11
12

void copy(Node*& root1, Node*& root2) {
    if (root1 == null)
        return;
    
    root2 = new Node(root1->num);

    if (root1->left != null)
        copy(root1->left, root2->left);

    if (root1->right != null)
        copy(root1->right, root2->right);
}

# 计算二叉树的深度

1
2
3
4
5
6

int getH(Node *&root) {
    if (root == null)
        return 0;

    return max(getH(root->left), getH(root->right)) + 1;
}

# 统计节点个数

1
2
3
4
5
6

int count(Node *&root) {
    if (root == null)
        return 0;

    return count(root->left) + count(root->right) + 1;
}

# 线索二叉树

# 线索二叉树的类型定义

1
2
3
4
5

struct clueNode {
    // 数据域
    clueNode *left, *right;  // 左右~孩子指针
    int lTag, rTag;  // 左右标志 
};

• lTag == 0 代表有左孩子， left 指针指向左孩子
• lTag == 1 代表无左孩子， left 指针指向其前驱
• rTag == 0 代表有右孩子， right 指针指向右孩子
• rTag == 0 代表无右孩子， right 指针指向其后继

# 线索化二叉树的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

void clue(Node*& root) {
    if (root == null)
        return;

    clue(root->left);

    if (root->left == null)
        root->lTag = 1, root->left = pre;
    else
        root->lTag = 0;

    if (root->right == null)
        pre->rTag = 1, pre->right = root;
    else
        pre->rTag = 0;

    pre = root;

    clue(root->right);
}

# 树的多种表示方法

# 双亲表示法

以一组连续的存储单元存储树的结点，每个结点除数据域外，还附设一个 $parent$ 域用以指示父节点的位置

# 孩子表示法

利用多重链表来存储孩子的位置，有两种表示方法

• 不同结点指针域是同构的，都为 $x$ 个指针域
• 不同结点指针域是异构的，添加一个 $degree$ 域记录该点的度

不难推出，第一种表示方法下，在一棵有 $n$ 个度为 $k$ (树的度) 的结点的树中必有 $n(k-1)+1$ 个空链域
注意，是空链域，不是空指针域，也就是会有 $n(k-1)+1$ 个叶子结点

# 孩子兄弟表示法

以二叉链表作为树的存储结构，链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点
利用孩子兄弟表示法，可以将普通的树转换成二叉树，森林转换成二叉树

# 哈夫曼树

哈夫曼树又称最优树，是一类带权路径最短的树

• 带权路径长度：树中所有叶子结点的带权路径长度之和，通常记作 $WPL=\sum\limits_{k=1}^{n}w_kl_k$
  注意：哈夫曼树中没有度为 $1$ 的点

# 哈夫曼编码

• 哈夫曼编码是前缀编码：任一哈夫曼编码都不会与任意其他哈夫曼编码的前缀部分完全重叠
• 哈夫曼编码是最优前缀编码：对于包含 $n$ 个字符的数据文件，分别以出现次数为权值构造哈夫曼树，则利用该树对应的哈夫曼编码对文件进行编码，能使文件压缩后对应的二进制文件长度最短

# 树的计算题

• 一棵完全二叉树的第 $6$ 层上有 $23$ 个叶子节点，则此二叉树最多有多少个结点？
  • 完全二叉树的叶子结点只能在最下两层，要使结点最多，这棵二叉树深度为 $7$，前 $6$ 层结点数共为 $63$，第 $6$ 层有 $32$ 个结点，其中叶子为 $23$ 个，非叶子为 $9$ 个，它们的度都为 $2$，第 $7$ 层只有 $18$ 个结点，故整棵二叉树结点数为 $81$
  • 如果是求 最少的结点数，则让这 $23$ 个叶子结点靠左（即第六层就是最后一层，求最多时是让这 $23$ 个结点靠右，第六层是倒数第二层）
• 设深度为 $h$ 的二叉树中只有度为 $0$ 和度为 $2$ 的结点，则此类二叉树中所包含结点数至少为？
  • 除根之外，每层只有两个结点，且互为兄弟，有 2*(h - 1) + 1 = 2h - 1 个点
  • 若求的是至多，则即为满二叉树，有 $2^{h} - 1$ 个点
• 一棵深度为 $k$ 且只有 $k$ 个结点的二叉树按照完全二叉树顺序存储的方式存放于一个一维数组 $R[n]$ 中，则 $n$ 至少是？
  • 二叉树最恶劣情况是，全部右斜放，则 $R[n]$ 相当于应该有满 $k$ 层的个数，即 $2^k-1$
  • 最好情况是，二叉树全部左斜放，用的点数最少，即为 $2^{k-1}-1+1=2^{k-1}$，但题目问的是至少，为了防止不越界，应取 $2^k-1$
• 用二叉链表表示具有 $n$ 个结点的二叉树时，值为空的指针域的个数为 $n+1$
• 二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定满足的条件是：高度等于结点数
• 若二叉树采用二叉链表存储结构，要交换所有分支结点的左右子树的位置，利用基于后序遍历的递归算法最合适
• 基于中序线索化链表，其头结点指针为 $head$，对应的二叉树为空的判断条件是： head->left = head && head->right == head
• 二叉树的先序遍历的递归算法的时间复杂度为线性级

# 图

图由两个集合 $V$ 和 $E$ 组成，记为 G=(V, E) ，其中 $V$ 是顶点的有穷非空集合，$E$ 是 $V$ 中顶点偶对的有穷集合，这些顶点偶对称为边。

• $V(G)$ ：顶点集合
• $E(G)$ ：边集合
  有向图的边用 <x, y> 表示，无向图的边用 (x, y) 表示

# 图的基本术语

• 完全图
  • 无向完全图：具有 $n(n-1)/2$ 条边
  • 有向完全图：具有 $n(n-1)$ 条弧
• 度、入度、出度
  • 顶点 $v$ 的度是指和 $v$ 相关联的边的数目，记为 $TD(v)$
  • 入度是以顶点 $v$ 为头的弧的数目，记为 $ID(v)$
  • 出度是以顶点 $v$ 为尾的弧的数目，记为 $OD(v)$
• 路径和路径长度
  • 路径：从顶点 $v$ 到顶点 $v'$ 的路径是一个顶点序列 $(v = v_{i,0},...v_{i,m} = v')$
  • 路径长度：是一条路径上经过的边或弧的数目
• 连通、连通图、联通分量
  • 如果顶点 $v$ 到 $v'$ 有路径，则称 $v$ 和 $v'$ 是连通的
  • 如果对于图中任意两个顶点 $v_i, v_j∈V$，$v_i$ 和 $v_j$ 都是连通的，则称 $G$ 是连通图
  • 所谓连通分量，指的是无向图中的极大连通子图
• 强连通图、强连通分量
  • 在有向图 $G$ 中，如果每一对 $v_i,v_j∈V,v_i\ne v_j$，从 $v_i$ 到 $v_j$ 和从 $v_j$ 到 $v_i$ 都存在路径，则称 $G$ 是强联通图
  • 有向图中的极大强连通子图称作有向图的强连通分量
• 连通图的生成树
  • 一个极小连通子图，它含有图中全部顶点，但是只有足以构成一棵树的 $n-1$ 条边
• 有向树和生成森林
  • 有一个顶点的入度为 $0$，其余顶点的入度均为 $1$ 的有向图叫有向树
  • 生成森林由若干棵有向树组成

# 图的存储结构

• 邻接矩阵
• 邻接表
• 十字链表
• 邻接多重表

# 最小生成树

• $Prim$ 算法
  • 核心思想：每次选择离当前点集最近的、可以拓展新点的边加入集合（开始时选择最短的那条边）
• $Kruskal$ 算法
  • 核心思想：每次选择当前未被选择的、最短的、可拓展新点的边加入集合（开始时选择最短的那条边）

边较多的时候，用 $Prim$，边较少的时候，用 $Kruskal$

# 拓扑排序

• $AOV-$ 网：用顶点表示活动，用弧表示活动间的优先关系的有向图，图不能出现有向环

拓扑排序就是将 $AOV-$ 网中的所有顶点排成一个线性序列
该序列满足：若在 $AOV-$ 网中从顶点 $v_i$ 到 $v_j$ 有一条路径，则该线性序列中，$v_i$ 必在 $v_j$ 点之前

• 求拓扑排序的过程：
  1. 在有向图中，选择一个无前驱的点并输出
  2. 从图中删除以该顶点为尾的所有弧和该顶点
  3. 重复 $1.$ 和 $2.$
• 求拓扑排序利用的是入度 + 邻接表

// 若输出的顶点数 $<$ 有向图的顶点数，则说明有环

# 图的题目

• 一个非连通的无向图，共有 $10$ 条边，则至少有 $6$ 个顶点
  • 一个点孤立，剩下的两两之间有边
  • 假设至少有 $n$ 个点，则两两有边 $\to$ 边数 = (1 + ... + (n - 2)) ，解方程即可
• 设有 $5$ 个结点的无向图，该图至少应有 $?$ 条边才能确保是一个连通图
  • 注意确保，$n$ 个点无向完全图最少有 n(n-1)/2 条边，孤立一个点，求剩下 $n-1$ 个点的完全图边数再加上 $1$，则能确保是连通图
• 设有 $n$ 个顶点 $e$ 条弧的有向图，采用邻接表作为物理结构，则求某顶点 $v_i$ 度的算法的时间复杂度为？
  • 时间复杂度 = 求入度时间复杂度 + 求出度时间复杂度 $=O(n+e)$
  • 入度时间复杂度：需要遍历所有点 $n$、边 $e~\to O(n+e)$
  • 出度时间复杂度：求 $v_i$ 邻接表长度即可，$O(1)$
• 一个无向连通图的生成树是该连通图的极小连通子图
• 如果 $n(n>2)$ 个顶点的有向图有两个强连通分量，则至少有 $n-1$ 条弧

# 查找

为了记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度
对于含有 $n$ 个记录的表，查找成功时的平均查找长度为：$ASL=\sum\limits_{i=1}^{n}P_iC_i$

# 线性表的查找

• 顺序查找
• 折半查找（二分查找）
  • 二分查找在查找成功 / 不成功的比较次数不会超过 $\lfloor{\log_2n}\rfloor+1$
  • 查找不成功的时候，比较次数一定是 $\lfloor{\log_2 n}\rfloor$ 或者 $\lfloor{\log_2 n}\rfloor+1$，最小是 $\lfloor{\log_2n}\rfloor$
  • 查找成功的　$ASL = \frac{n+1}{n}\log_2(n+1)-1$
• 分块查找：效率介于前两者之间
  • 建立一个索引表，索引表有序而实际数列无序 $\to$ 便于插入操作
  • 平均查找长度
    • 顺序查找确定所在块 $\to~\frac{1}{2}{(\frac{n}{s}+s)}+1$
    • 二分查找确定所在块 $\to~log_2{(\frac{n}{s}+1)+\frac{s}{2}}$
  • 假设查找表长为 $n$，对于分块查找，如过采用顺序查找确定待查值可能所在的块，那么每块的关键字个数为 $\sqrt{n}$ 时，分块查找的平均查找长度可以达到最佳

# 树表的查找

# 二叉排序树

定义：左 $<$ 中 $<$ 右
中序遍历一个二叉树的时候可以得到一个递增的序列

• 二叉排序树的平均查找时间
  • 当 $n$ 个结点有序的时，树的深度为 $n$，ASL=\frac{n+1}
  • 如果二叉排序树的形态和二分查找的判定树形态相似，则 $ASL$ 与 $\log_2n$ 成正比
  • 但考虑到，若把 $n$ 个结点按各种可能随即插入二叉排序树中，有 $n!$ 棵二叉树（其中有的形态相同），在平均情况下，二叉排序树的 $ASL$ 仍然和 $\log_2n$ 成正比

# 二叉排序树的删除

假设被删结点为 $*p$，其父亲结点是 $*f$，$P_L,~P_R$ 分别代表其左子树和右子树

• 如果 $*p$ 是叶子节点，直接删除该点即可， f->lChild = NULL 或 f->rChild = NULL
• 如果 $*p$ 只左子树 $P_L$ 或右子树 $P_R$，直接删除该点即可， f->lChild = p->lChild 或 f->rChild = p->rChild
• 如果 $*p$ 左右子树均不空，则有两种处理方法
  • 中序遍历二叉树得到的序列为 \
  1. 令 $*p$ 左子树为 $*f$ 左子树，而 $*p$ 右子树为 $*s$ 的右子树， f->lChild = p->lChild, s->rChild = p->rChild ，$s$ 是，在中序遍历，$*p$ 的前一个结点（它一定是一个叶子结点）
  2. 令 $*p$ 的直接前驱（或直接后继）代替 $*p$，然后再从二叉排序树中删除它的直接前驱（或直接后继）（递归删除，可能要删多次）
  • 显然，前一种处理方法可能增加树的深度，而后一种方法是以被删结点左子树中关键字最大的结点替代被删结点，然后从左子树中删除这个结点。此结点一定没有右子树，这样就不会增加树的深度

# 平衡二叉树

二叉排序树的查找算法的性能取决于二叉树的结构，线性二叉树查找时间 $O(n)$，结构合理二叉树查找时间 $O(\log_2n)$，则提出 $AVL$ 树

• 左右子树深度之差不超过 $1$
• 左右子树也是 $AVL$ 树

含有 $n$ 个结点的 $AVL$ 树，高度

• 最小：$\lfloor{\log_2n}\rfloor+1$
• 斐波那契数列得到第一个满足大于 $n+1$ 的斐波那契数，这个数是斐波那契数列的第 $i$ 项，则最大深度为 $i-3$
  • 注：$F[0]=0,~F[1]=1,~F[2]=2.....$

# $AVL$ 树的插入删除

# 散列表的查找

• 散列函数和散列地址：在记录的存储位置 $p$ 和其关键字 $key$ 之间建立一个确定的对应关系 $H$，使得 $p=H(key)$，称 $H$ 为散列函数，$p$ 为散列地址
• 散列表：一个有限的、连续的存储空间

# 散列函数的构造方法

• 数字分析法：事先必须知道所有关键字每一位数字的分布情况，选取若干位冲突小的来确定散列地址
• 平方取中法：对数值进行平方，选取中间的若干位来确定散列地址
• 折叠法：把数字分为位数相同的若干部分，叠加起来，用和来确定散列地址
• 除留余数法：假设散列表表长 $m$，选择一个不大于 $m$ 的数 $p$，模 $p$ 所得余数为散列地址，一般取小于表长的最大质数

# 处理冲突的方法

# 开放地址法

发生冲突则寻找下一个空位，称为探测，用公式表示如下：$H_i=(H(key)+d_i)\%m,~i=1,2,···,k~(k\le m-1)$

• 线性探测法
  • $d_i=1,2,3,···,m-1$
• 二次探测法
  • $d_i=1^2,-1^2,2^2,-2^2,···,k^2,-k^2~(k\le m/2)$
• 伪随机探测法
  • $d_i=$ 伪随机数序列

# 链地址法

# 线性再散列

线性再散列的基本思想是将散列表划分为若干个子表，当一个关键字在某个子表中发生冲突时，通过线性探测 (即向后移动固定的步长) 来寻找下一个空位置
若有的个关键字互为同义词，在最坏情况下，这些同义词可能被分散到不同的子表中，并且在每个子表中都需要进行线性探测来处理冲突

假设每个子表中最多有 $k$ 个关键字，那么查找其中任意一个同义词关键字的比较次数将是这些子表中关键字的比较次数之和
对于每一个子表，最坏情况下需要进行 $k$ 次比较才能找到目标关键宇或确定其不存在。由于有多个子表，查找这些同义词其中的任意一个关键字所需的比较次数将基各子表
比较次数的总和，即 $k+k+...+k$（共 $k$ 次比较）。因此，（最多）总的比较次数为 $k^2$ 次

# 不同处理方法的 $ASL$

散列表的装填因子：$\large{a=\frac{表中填入的记录数}{散列表长度}}$

散列表的平均查找长度是 $a$ 的函数而不是记录个数 $n$ 的函数

# 排序

• 排序的稳定性
  • 若存在 $k_i=k_j~(1\le i < j \le n)$，若排序后，$i$ 仍小于 $j$，则称该排序为稳定的

# 插入排序

# 直接插入排序

• 时间复杂度 $O(n^2)$
• 总比较次数（最差） $KCN=\sum\limits_{i=2}^{n}i=(n+2)(n+1)$
• 总移动次数（最差） $RMN=\sum\limits_{i=2}^{n}(i+1)=(n+2)(n+1)$
• 是稳定的排序
  

  1 2 3 4 5 6 7 8 9

  for (int i = 2; i <= 10; i++) { if (a[i] < a[i - 1]) { a[0] = a[i]; int j = i - 1; while (a[j] > a[0]) a[j + 1] = a[j], j--; a[j + 1] = a[0]; } }

# 二分插入排序

• 时间复杂度 $O(n^2)$
• 是稳定的排序
  

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

  for (int i = 2; i <= 10; i++) { a[0] = a[i]; int l = 1, r = i - 1; while (l <= r) { int mid = l + r >> 1; if (a[0] < a[mid]) r = mid - 1; else l = mid + 1; } int j = i - 1; while (j >= r + 1) a[j + 1] = a[j], j--; a[j + 1] = a[0]; }

# 希尔排序

• 跳跃式移动导致排序方法不稳定
• 最后一个 $dk[]$ 必须是 $1$，且增量序列中没有除 $1$ 以外的公因子
  

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

  int dk[] = {1, 3, 5}; for (int k = 0; k < sizeof(dk) / sizeof(int); k++) { int gap = dk[k]; for (int i = gap + 1; i <= 10; i++) { if (a[i] < a[i - gap]) { a[0] = a[i]; int j = i - gap; while (a[j] > a[0]) a[j + gap] = a[j], j -= gap; a[j + gap] = a[0]; } } }

# 交换排序

• 稳定排序
• 可用于链式存储结构
• 平均时间性能比插入排序差
  

  1 2 3 4 5 6 7 8 9 10 11 12 13

  while (m > 0 && flag == 1) { flag = 0; int j = 1; for (j = 1; j <= m; j++) if (a[j] > a[j + 1]) { flag = 1; swap(a[j], a[j + 1]); } m--; }

# 选择排序

# 简单选择排序

• 记录移动次数
  • 最小：$0$
  • 最大：$3(n-1)$
• 比较次数：\sum\limits_{i=1}^{n-1}n-i=\frac{n(n-1)}
• 就方法本身来说，是稳定的
• 可用于链式存储结构
  

  1 2 3 4 5 6 7 8

  for (int i = 1; i < 10; i++) { int k = i; for (int j = i + 1; j <= 10; j++) if (a[j] < a[k]) k = j; if (k != i) swap(a[i], a[k]); }

# 堆排序

• 堆的定义：$n$ 个元素的序列 $\{k_1,k_2...k_n\}$ 称之为堆，当且仅当满足下列其一时
  1. $k_i\ge k_{2i}~\&\&~k_i\ge k_{2i+1}~(1\le i \le \lfloor{n/2}\rfloor$
  2. $k_i\le k_{2i}~\&\&~k_i\le k_{2i+1}$
     所有序号大于 $\lfloor{n/2}\rfloor$ 的结点都是叶子，因此以这些结点为根的子树已是堆。只需要利用筛选法，从最后一个分支节点 $\lfloor{n/2}\rfloor$ 开始，把前面的所有节点作为根的子树都调整为堆。
     

     1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

     void heapSort(int n, int a[]) { function<void(int[], int, int)> heapAdjust = [&](int a[], int n, int i) { int maxIdx = i, left = 2 * i, right = 2 * i + 1; if (left <= n && a[left] > a[maxIdx]) maxIdx = left; if (right <= n && a[right] > a[maxIdx]) maxIdx = right; if (maxIdx != i) { swap(a[maxIdx], a[i]); heapAdjust(a, n, maxIdx); } }; // 初建堆 for (int i = n / 2; i >= 1; i--) heapAdjust(a, n, i); for (int i = n; i >= 2; i--) { swap(a[1], a[i]); heapAdjust(a, i - 1, 1); } }

• 时间复杂度 $O(\log_2n)$
• 不稳定排序
• 只能用于顺序结构
• 假设待排序的表长为 $n$，那么创建堆需要时间复杂度为 $O(n)$

# 归并排序

• 时间复杂度 $O(\log_2n)$
• 空间复杂度 $O(n)$
• 稳定排序
• 可用于链式结构
  

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

  void mergeSort(int n, int a[]) { function<void(int[], int, int)> MergeSort = [&](int a[], int l, int r) -> void { if (l >= r) return; int mid = l + r >> 1; MergeSort(a, l, mid), MergeSort(a, mid + 1, r); int k = 0, i = l, j = mid + 1; while (i <= mid && j <= r) { if (a[i] <= a[j]) tmp[k++] = a[i++]; else tmp[k++] = a[j++]; } while (i <= mid) tmp[k++] = a[i++]; while (j <= r) tmp[k++] = a[j++]; for (i = l, j = 0; i <= r; i++, j++) a[i] = tmp[j]; }; MergeSort(a, 1, n); }

# 快速排序

• 不稳定
• 时间复杂度 $O(n\log_2n)$
• 空间复杂度：快速排序是递归的，最大递归调用次数和递归树的深度一直
  • 最好 $O(\log_2n)$
  • 最坏 $O(n)$
• 当待排序序列有序时，退化成简单排序水平
  

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

  void quickSort(int n, int a[]) { function<void(int[], int, int)> QuickSort = [&](int a[], int l, int r) -> void { if (l >= r) return; int mid = a[(l + r) >> 1], i = l - 1, j = r + 1; while (i < j) { do { i++; } while (a[i] < mid); do { j--; } while (a[j] > mid); if (i < j) swap(a[i], a[j]); } QuickSort(a, l, j); QuickSort(a, j + 1, r); }; QuickSort(a, 1, n); }