| 紫梦沁香

一、卡特兰数

公式：$\frac{1}{n+1}C^n_{2n}$

适用于求出栈序列个数，不同形状的二叉树个数以及有多少种括号匹配序列

注：上述三种适用情形不能有其他额外限制

二、常用代码块

（1）快速排序

void qsort(int a[], int left, int right){
    if(left >= right) return;
    int i = left, j = right;
    int b = rand() % (right - left + 1);	
    swap(a[left], a[left+b]);	

    while(i < j){
        while(i < j && a[j] >= a[left]) j--;
        while(i < j && a[i] <= a[left]) i++;
        swap(a[i], a[j]);
    }
    swap(a[i], a[left]);
    qsort(a, left, i-1);
    qsort(a, j+1, right);
}

（2）归并排序

int temp[n];
void msort(int a[], int left, int right){
    if(left >= right) return;
    int mid = (left + right) / 2;
    msort(a, left, mid);
    msort(a, mid + 1, right);

    int i = left, j = mid + 1, p = left;
    while(i <= mid && j <= right){
        if(a[i] <= a[j]) temp[p++] = a[i++];
        else temp[p++] = a[j++];
    }

    while(i <= mid) temp[p++] = a[i++];
    while(j <= right) temp[p++] = a[j++];
    for(i = left; i <= right; i++) a[i] = temp[i];
}

（3）二分查找

// 在长度为n的有序数组a中寻找值为k的元素下标
// 返回-1则表明未找到
int(int a[], int n, int k){
    int l = 0, r = n - 1;
    while(l <= r){
        int mid = (l + r) / 2;
        if(a[mid] < k) l = mid + 1;
        else if(a[mid] > k) r = mid - 1;
        else return mid;
    }
    return -1;
}

（4）邻接表

typedef struct EdgeNode{
    struct EdgeNode *next;
    int target;	// 被指向顶点的编号
    int weight;	// 边的权重
}EdgeNode;

typedef struct VertexNode{
    EdgeNode *first;
    char name;
}VertexNode;

typedef struct Graph{
    VertexNode list[10];
    int numVertex, numEdge;
}Graph;

// i -> j = w
void addEdge(Graph *g, int i, int j, int w){
    EdgeNode edge = {g->list[i].first, j, w};
    g->list[i].first = edge;
}

（5）层序遍历

const int N = 1e7;
typedef struct TNode{
    struct TNode *left, *right;
    int val;
}*TNode;

TNode nodes[N];
void func(TNode root){
    int l = r = 0;
    nodes[r++] = root;
    while(l<r){
        TNode node = nodes[l++];
        if(!node) continue;
        nodes[r++] = node->left;
        nodes[r++] = node->right;
        cout << node->val << " ";
    }
}

（6）树的定义

双亲表示法

typedef struct{
    ElemType data;
    int parent;
}PTNode;

PTNode tree[10];

孩子表示法

//Child表示下一个孩子的信息
typedef struct Child{
    int index;             //孩子编号
    struct Child * next;   //下一个孩子
} Child;

//TreeNode用于保存结点信息
typedef struct TreeNode {
    char data;             //结点信息
    Child * firstChild;    //指向第一个孩子
} TreeNode;

TreeNode tree[10];   //定义一棵拥有10个结点的树（孩子表示法）

孩子兄弟表示法

typedef struct CSNode{
	ElemType data;							    //数据域
	struct CSNode *firstchild,*nextsibling;    //第一个孩子和右兄弟指针
}CSNode,*CSTree;

三、数据结构

逻辑结构
- 线性结构
- 非线性结构
  - 树形结构
  - 图状结构
物理(存储)结构
- 顺序存储
- 链式存储
- 索引存储
- 散列存储

四、图论算法

	邻接矩阵	邻接表	备注
Dijkstra	$O(n^2)$		不能有负权边
Floyd	$O(n^3)$		回路中不能有负权边
Prim	$O(n^2)$		适用于边稠密
Kruskal		O(eloge)	适用于边稀疏
DFS	$O(n^2)$	O(n+e)
BFS	$O(n^2)$	O(n+e)
拓扑排序	$O(n^2)$	O(n+e)
关键路径	$O(n^2)$	O(n+e)

五、红黑树

对于每个节点，从该节点到任意一个叶节点的简单路径上，所含黑节点的数量相同
n个节点的红黑树的高度 h<= $2log_2(n+1)$
任何一棵红黑树都对应一棵四阶B树

六、B树和B+树

含有n个叶节点的B+树有n个关键字
B+树无论查找成功与否，每次查找都必定查找到叶节点；而B树可能查找到中间节点就停止了。
n阶B树每个节点至多n-1个关键字，至少(n-1)/2个关键字；n阶B+树每个节点至多n个关键字，至少(n+1)/2个关键字。
n阶B树和n阶B+树除根节点外每个非叶结点至少含有(n+1)/2个子树
B树的总关键字数 + 1 = 叶节点数，

七、散列表

（1）散列函数

直接定址法

H(key) = a * key + b
除留余数法

H(key) = key % p（p取小于等于表长的最大质数）
数字分析法

选取数字中较为均匀分布的若干位作为散列地址，例如手机号后四位
平方取中法

取关键字平方的中间几位作为散列地址

（2）处理冲突

开放定址法
- 线性探测法
  - di = 0, 1, 2, 3, 4…
  - 会导致堆积
- 平方探测法
  - di = 0, 1, -1, 4, -4, …, $k^2$, $-k^2$（k <= m / 2）
  - m必须是一个能表示成4k+3的素数
  - 可以避免堆积
  - 无法探测到散列表上的所有单元，但至少能探测到一半
- 双散列法
  - di = i * h2(key)
  - Hi = (H(key) + i * h2(key)) % m
  - 初始探测位置为H0
- 伪随机序列法
  - di = 伪随机数序列
开放定址法不能随意删除元素，得先做逻辑删除。
拉链法
- 避免了非同义词的冲突
- 适用于经常插入删除的情况
- 数组部分不计入查找长度

八、排序算法

九、外部排序

（1）初始归并段

生成初始归并段相当于先做了一次归并排序

（2）败者树

败者树可以有效减少多路归并排序时的比较次数

败者树每次维护会一直维护到根节点；堆排序可能维护到一半就停止。
败者树每上一层只需要和败者节点比较一次即可；堆排序每下一层需要和左右子节点共比较两次。
相同规模下，败者树所需的空间是堆排序所需空间的两倍。
败者树首次比较仍需k-1次比较，后续每次最多需要$log_2k$次比较
败者树是一棵完全二叉树

（3）置换选择排序

获得的归并段的平均长度是内存工作区大小的两倍
获得的初始归并段大小不受内存容量的限制

（4）最佳归并树

采用哈夫曼思想构建哈夫曼树
磁盘I/O次数 = 2 * WPL

十、杂项

（1）线性表可以是空表，树可以是空树，但图不能是空图，图至少包含一个顶点。

（2）AOV无边权，AOE有边权

（3）二叉平衡树的平衡因子 = 左子树高度 - 右子树高度

（4）链表插入删除要考虑特殊情况（链表为空）

（5）矩阵转数组存储注意下标

（6）连通图特指无向图，强连通图特指有向图

一、 卡特兰数