数据结构

2.2 顺序表

删除顺序表中值为 x 的所有元素

void deleteElement(vector<int>& arr, int x) {
    int k = 0;
    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] == x) {
            k++;
        } else {
            arr[i - k] = arr[i];
        }
    }
    arr.resize(arr.size() - k);
}

2.3 链表

链表反转

void reverseLinkedList(Node*& head) {
    Node* prev = nullptr;
    Node* curr = head;
    Node* next = nullptr;
    while (curr != nullptr) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    head = prev;
}

循环链表的两种代码实现

front=0,rear=0,queue[rear++]=添加元素
front != rear
 
front=0,rear=n-1，queue[++rear]=添加元素
front != (rear + n) % n

4.2 KMP

vector<int> get_next(string p) {
    int n = p.size();
    vector<int> next(n + 1);
    next[1] = 0;
    for (int i = 1, j = 0; i < n;) {
        if (j == 0 || p[i] == p[j])
            next[++i] = ++j;
        else
            j = next[j];
    }
    return next;
}

vector<int> get_nextval(string p) {
    int n = p.size();
    vector<int> nextval(n + 1);
    nextval[1] = 0;
    for (int i = 1, j = 0; i < n;) {
        if (j == 0 || p[i] == p[j]) {
            i++;
            j++;
            if (p[i] != p[j])
                nextval[i] = j;
            else
                nextval[i] = nextval[j];
        } else
            j = nextval[j];
    }
    return nextval;
}

int kmp(string s, string p) {
    vector<int> next = prefix(p);
    int i = 0, j = 0;
    while (i < s.size() && j < p.size()) {
        if (j == 0 || s[i] == p[j])
            i++, j++;
        else
            j = next[j];
    }
    if (j == p.size())
        return i - j;
    else
        return -1;
}

5.1 树

5.2 二叉树

{n_{0} + n_{1} + n_{2} = n 2 n_{2} + n_{1} = n - 1 ⟹ n_{2} = n_{0} - 1 2 n_{0} - 1 + n_{1} = n ⟹ n_{0} = ⌈ \frac{n}{2} ⌉

5.4 树、森林

树存储结构：

双亲表示法
孩子表示法
孩子兄弟表示法

树、森林、二叉树转换

树转二叉树：左子右兄弟
森林转二叉树：每棵树先转二叉树，然后每棵二叉树根节点连接
二叉树转森林：根和左子树为一棵树，右子树构成其他森林转换的二叉树，递归的转换

树和森林的遍历

树	森林	二叉树
先根遍历	先序遍历	先序遍历
后根遍历	中序遍历	中序遍历

5.5 哈夫曼树

带权路径长度

W P L = i = 1 \sum n w_{i} l_{i}

6.4 图的应用

关键路径

v_{e} (src) = 0 v_{e} (j) = max {v_{e} (i) + w (i, j)} v_{l} (d s t) = v_{e} (d s t) v_{l} (i) = min {v_{l} (j) - w (i, j)} e (a_{ij}) = v_{e} (i) l (a_{ij}) = v_{l} (j) - w (i, j) d (a_{ij}) = l (a_{ij}) - e (a_{ij})

7.2 顺序查找和折半查找

平均查找长度： $A S L = \sum P_{i} C_{i}$

折半查找

折半查找判定树：平衡二叉树

查找成功：

A S L = \frac{1}{11} (1 \times 1 + 2 \times 2 + 3 \times 4 + 4 \times 4)

查找失败：

A S L = \frac{1}{12} (3 \times 4 + 4 \times 8)

分块查找

A S L = L_{I} + L_{S} = \frac{b + 1}{2} + \frac{s + 1}{2}

7.3 树形查找

二叉搜索树

判断是否为二叉搜索树

bool isVaildBST(TreeNode *root, int minVal, int maxVal) {
    if (!root) {
        return true;
    }
    if (root->val <= minVal || root->val >= maxVal) {
        return false;
    }
    return isVaildBST(root->left, minVal, root->val) 
    && isVaildBST(root->right, root->val, maxVal);
}

ASL 同折半查找判定树

平衡二叉树

右旋

左旋

BinNode<T> *maintain(BinNode<T> *cur) override {
    if (!cur)
        return nullptr;
    int Lheight = height(cur->_lc);   // 计算出cur左树的高度
    int Rheight = height(cur->_rc);   // 计算出cur右树的高度
    if (abs(Lheight - Rheight) > 1) { // 出现不平衡
        if (Lheight > Rheight) {
            // 计算cur左树的左右子树的高度
            int LLheight = cur->_lc ? height(cur->_lc->_lc) : 0;
            int LRheight = cur->_lc ? height(cur->_lc->_rc) : 0;
            if (LLheight >= LRheight) { // LL型右单旋转
                cur = cur->zig();
            } else { // LR型左右双旋
                cur->_lc = cur->_lc->zag();
                cur = cur->zig();
            }
        } else {
            // 计算cur右树的左右子树的高度
            int RLheight = cur->_rc ? height(cur->_rc->_lc) : 0;
            int RRheight = cur->_rc ? height(cur->_rc->_rc) : 0;
            if (RRheight >= RLheight) { // RR型左单旋转
                cur = cur->zag();
            } else { // RL型右左双旋
                cur->_rc = cur->_rc->zig();
                cur = cur->zag();
            }
        }
    }
    return cur; // 返回调整好的新父节点
}

指定高度最少结点的二叉树（平衡因子均为1）

F (h) = ⎩ ⎨ ⎧ 1, h = 1 3, h = 2 F (h - 1) + F (h - 2) + 1, h \geq 2

红黑树

红黑树插入：

树为空作为黑节点插入
父节点为黑结点，直接插入
父节点为红结点，叔节点y为黑色

     z.p.p(B)            z.p.p(B)               z.p(B)
    /      \             /     \              /        \
  z.p(R)    y(B)       z.p(R)    y(B)        z(R)     z.p.p(R)
   \                   / 
     z(R)             z(R)
    LR型1   -(左旋并交换z和z.p)-> LL型2    -(右旋并反转z和z.p颜色)->            
    
    z.p.p(B)             z.p.p(B)                 z.p(B)
    /      \             /      \               /       \
  y(B)    z.p(R)        y(B)     z.p(R)       z.p.p(R)    z(R)    
           /                      \  
          z(R)                   z(R)     
    RL型3  -(右旋并交换z和z.p)->  RR型4     -(左旋反转z和z.p颜色)->

父节点叔节点均为红节点

    z.p.p(R)             z.p.p(R)
    /       \           /       \
  z.p(R)   y(R)      z.p(B)    y(B)
    \                    \
     z(R)                 z(R)
     --反转z.p和y,z.p.p颜色，将z.p.p作为z递归向上调整->

红黑树删除：// todo

7.4 B树和B+树

B树：

根不为叶节点，至少2棵子树

除根以外的非叶节点，至少 $⌈ \frac{m}{2} ⌉$ 个棵子树

每个节点至多m棵子树

子树个数=关键字个数+1

插入节点

如果节点 key 数溢出，以 $⌈ \frac{m}{2} ⌉$ 处分裂为两个节点， $⌈ \frac{m}{2} ⌉$ 的 key 移至父节点，再检查父节点 key 数是否溢出。

删除节点

转化为将终端节点来替代

直接删除
兄弟够借：借兄弟当父亲，借父亲当兄弟
兄弟不够借：删除本节点，关键字合并到左或右邻节点，父节点里的关键字也要合并左或右结点

B+树：

根不为叶节点，至少2棵子树

除根以外的非叶节点，至少 $⌈ \frac{m}{2} ⌉$ 个棵子树

每个节点至多m棵子树

子树个数=关键字个数

叶节点包含所有关键字；相邻节点按大小顺序互相链接

分支节点仅包含各个子节点的最大值及指针

7.5 散列表

散列函数：H(key)=key%p

处理冲突

开放定址法
1. 线性探测 0,1,2,3,…
2. 平方探测 +-1,+-4, +-9
3. 双散列
4. 伪随机序列
拉链法查找成功

A S L = \frac{1}{n} i = 1 \sum n C_{i}, C_{i} 为第 i 个元素的冲突次数 + 1

查找失败

A S L = \frac{1}{p + 1} i = 0 \sum p C_{i}, C_{i} 为第 i 个位置到其后面第一个空位的距离 + 1

8.2 插入排序

直接插入排序

void insectSort(int A[], int n) {
    for (int i = 1; i < n; i++) {
        int x = A[i], j = i;
        for (; j >= 1 && A[j - 1] > x; j--)
            A[j] = A[j - 1];
        A[j] = x;
    }
}

折半插入排序

void binaryInsertSort(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int x = a[i];
        int idx = lower_bound(a, a + i, x) - a;
        for (int j = i; j > idx; j--)
            a[j] = a[j - 1];
        a[idx] = x;
    }
}

希尔排序

void shellSort(int a[], int n) {
    for (int gap = n / 2; gap; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int j = i, x = a[i];
            for (; j >= gap && a[j - gap] > x; j -= gap)
                a[j] = a[j - gap];
            a[j] = x;
        }
    }
}

8.3 交换排序

冒泡排序

void bubbleSort(int A[], int n) {
    for (int i = 1; i <= n - 1; i++)
        for (int j = n - 1; j >= i; j--)
            if (A[j - 1] > A[j])
                swap(A[j - 1], A[j]), cut++;
}

快速排序

int partition(int a[], int l, int r) {
    int i = l, j = r - 1, pivot = a[l];
    while (i < j) {
        while (i < j && a[j] >= pivot)
            j--;
        a[i] = a[j];
        while (i < j && a[i] <= pivot)
            i++;
        a[j] = a[i];
    }
    a[i] = pivot;
    return i;
}
void quickSort(int a[], int l, int r) {
    if (r - l <= 1)
        return;
    int k = partition(a, l, r);
    quickSort(a, l, k);
    quickSort(a, k + 1, r);
}

8.4 选择排序

简单选择排序

void selectSort(int A[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++)
            if (A[j] < A[min])
                min = j;
        if (min != i)
            swap(A[i], A[min]);
    }
}

堆排序

// 向下建堆
void heapify(int a[], int n, int i) {
    int tmp = a[i];
    for (int j = 2 * i; j <= n; j *= 2) {
        if (j < n && a[j] < a[j + 1])
            j++;
        if (tmp >= a[j])
            break;
        else {
            a[i] = a[j];
            i = j;
        }
    }
    a[i] = tmp;
}
void heapSort(int a[], int n) {
    for (int i = n / 2; i >= 1; i--)
        heapify(a, n, i);
    for (int i = n; i > 1; i--) {
        swap(a[1], a[i]);
        heapify(a, i - 1, 1);
    }
}

8.5 归并排序、基数排序、计数排序

归并排序

void inplaceMerge(int a[], int l, int m, int r) {
    int n1 = m - l, n2 = r - m;
    int L[n1], R[n2];
    for (int i = 0; i < n1; i++)
        L[i] = a[l + i];
    for (int i = 0; i < n2; i++)
        R[i] = a[m + i];
    for (int k = l, i = 0, j = 0; k < r; k++)
        if ((j >= n2) || (i < n1 && L[i] <= R[j]))
            a[k] = L[i++];
        else { // if ((i >= n1) || (j < n2 && L[i] > R[j]))
            a[k] = R[j++];
            cnt += n1 - i; // 每放入一个R[j],L[]中剩余的元素(n1-i)个都比R[j]大,即为逆序数}
        }
}
void mergeSort(int a[], int l, int r) {
    if (r - l <= 1)
        return;
    int m = (l + r) / 2;
    mergeSort(a, l, m);
    mergeSort(a, m, r);
    inplaceMerge(a, l, m, r);
}

基数排序

void radixSort(int A[], int n) {
    vector<int> bucket[10];
    for (int exp = 1; exp < 1000; exp *= 10) {
        for (int i = 0; i < n; i++)
            bucket[(A[i] / exp) % 10].push_back(A[i]);
        int idx = 0;
        for (int i = 0; i < 10; i++)
            for (int x : bucket[i])
                A[idx++] = x;
        for (int i = 0; i < 10; i++)
            bucket[i].clear();
        for (int i = 0; i < n; i++)
            cout << A[i] << " ";
        cout << endl;
    }
}

计数排序

void countingSort(int A[], int n) {
    int k = 10; // 假设元素范围是0到9
    int C[k] = {}, B[k] = {}; // C为计数数组表示小于等于i的元素个数，B为输出数组
    for (int i = 0; i < n; i++)
        C[A[i]]++;
    for (int i = 1; i < k; i++)
        C[i] += C[i - 1];
    for (int i = n - 1; i >= 0; i--)
        B[--C[A[i]]] = A[i];
    for (int i = 0; i < n; i++)
        A[i] = B[i];
}

8.6 内部排序比较

算法种类	时间复杂度（最好情况）	时间复杂度（平均情况）	时间复杂度（最坏情况）	空间复杂度	是否稳定
直接插入排序	$O (n)$	$O (n^{2})$	$O (n^{2})$	$O (1)$	是
冒泡排序	$O (n)$	$O (n^{2})$	$O (n^{2})$	$O (1)$	是
简单选择排序	$O (n^{2})$	$O (n^{2})$	$O (n^{2})$	$O (1)$	否
希尔排序	$O (n^{1.3})$	——	$O (n^{2})$	$O (1)$	否
快速排序	$O (n lo g_{2} n)$	$O (n lo g_{2} n)$	$O (n^{2})$	$O (lo g_{2} n) worst O (n)$	否
堆排序	$O (n lo g_{2} n)$	$O (n lo g_{2} n)$	$O (n lo g_{2} n)$	$O (1)$	否
二路归并排序	$O (n lo g_{2} n)$	$O (n lo g_{2} n)$	$O (n lo g_{2} n)$	$O (n)$	是
基数排序	$O (d (n + r))$	$O (d (n + r))$	$O (d (n + r))$	$O (r)$	是

8.7 外部排序

多路平衡归并与败者树

struct LoserTree {
    int k;
    vector<int> val; // 存放每一路的首元素
    vector<int> tr;  // tr[1-k]为败者的索引, tr[0]为胜者的索引
    LoserTree(int k) : k(k), val(k + 1, -1e9), tr(k, k) {}
    void update(int i, int x) {
        val[i] = x;
        // t为val[i]在败者树中的父结点；若没有到达树根，则继续；获取下一个父节点
        for (int t = (i + k) / 2; t > 0; t /= 2)
            if (val[tr[t]] < val[i]) // 与父结点t存储的败者tr[t]指示的数据进行比较
                swap(tr[t], i);      // i指示新的胜者，参加更上一层的比较
        tr[0] = i;                   // 最终的胜者记录于tr[0]
    }
    int get() { return tr[0]; }
    int getVal() { return val[tr[0]]; }
};
void multiWayBalancedMergeSort(vector<int> a[], int k) {
    LoserTree lt(k);
    int idx[k] = {};
    for (int i = 0; i < k; i++) {
        lt.update(i, a[i][idx[i]++]);
    }
    while (lt.getVal() != 1e9) {
        int s = lt.get();
        cout << lt.getVal() << " ";
        lt.update(s, (idx[s] < a[s].size()) ? a[s[]()][idx[s]++] : 1e9);
    }
    cout << endl;
}

置换-选择排序

void replacementSelectionSort() {
    vector<int> FI = {17, 21, 05, 44, 10, 12, 56, 32, 29};
    reverse(FI.begin(), FI.end());
    const int w = 3;
    set<int> WA;
    vector<vector<int>> FO;
    for (int i = 0; WA.size() < w && !FI.empty(); i++) {
        WA.insert(FI.back());
        FI.pop_back();
    }
    while (!WA.empty()) {
        FO.emplace_back();
        auto MINIMAX = WA.begin();
        while (MINIMAX != WA.end()) {
            FO.back().push_back(*MINIMAX);
            WA.erase(MINIMAX);
            if (!FI.empty()) {
                WA.insert(FI.back());
                FI.pop_back();
            }
            MINIMAX = WA.upper_bound(*MINIMAX);
        }
    }
    cout << FO << endl;
}

最佳归并树

推广哈夫曼树到 m 叉树，构建为最佳归并树

若初始段不构成正则 k 叉树，需要添加长度为 0 虚段

{n = n_{k} + n_{0} n = k n_{k} + 1 ⟹ n_{k} = \frac{n _{0} - 1}{k - 1} u = (n_{0} - 1) mod (k - 1) \neq = 0 添加 k - 1 - u 个虚段

Quartz

探索

2.2 顺序表

2.3 链表

4.2 KMP

5.1 树

5.2 二叉树

5.4 树、森林

5.5 哈夫曼树

6.4 图的应用

关键路径

7.2 顺序查找和折半查找

折半查找

分块查找

7.3 树形查找

二叉搜索树

判断是否为二叉搜索树

平衡二叉树

指定高度最少结点的二叉树（平衡因子均为1）

红黑树

红黑树插入：

7.4 B树和B+树

B树：

插入节点

删除节点

B+树：

7.5 散列表

8.2 插入排序

8.3 交换排序

8.4 选择排序

8.5 归并排序、基数排序、计数排序

8.6 内部排序比较

8.7 外部排序

多路平衡归并与败者树

置换-选择排序

最佳归并树

目录

关系图谱

Quartz

探索

数据结构

2.2 顺序表

2.3 链表

4.2 KMP

5.1 树

5.2 二叉树

5.4 树、森林

5.5 哈夫曼树

6.4 图的应用

关键路径

7.2 顺序查找和折半查找

折半查找

分块查找

7.3 树形查找

二叉搜索树

判断是否为二叉搜索树

平衡二叉树

指定高度最少结点的二叉树（平衡因子均为1）

红黑树

红黑树插入：

7.4 B树和B+树

B树：

插入节点

删除节点

B+树：

7.5 散列表

8.2 插入排序

8.3 交换排序

8.4 选择排序

8.5 归并排序 、基数排序、计数排序

8.6 内部排序比较

8.7 外部排序

多路平衡归并与败者树

置换-选择排序

最佳归并树

目录

关系图谱

8.5 归并排序、基数排序、计数排序