数据结构公式速查

数据结构公式汇总（共 35 个知识点）

线性结构：

- 线性表容量：Length(L)；元素个数：Size(L)

- 栈顶元素：Top(S)；栈的容量：MaxSize(S)

- 队列元素个数：Size(Q)；队头元素：Front(Q)

树形结构：

- 二叉树结点数：Vertex(T)；叶结点数：Leaf(T)

- 满二叉树结点数：2^Height(T)-1；满二叉树最大高度：Log2(Vertex(T)+1)

- 哈夫曼树中第 i 个结点的权值：Wi = (Leaf(T) - i + 1) * freq(i)

图论：

- 无向图边数：E = m/2；无向图点数：V = n

- 有向图边数：E = m；有向图点数：V = n

- 图的度：deg(V) = E

散列表：

- 散列表容量：M；散列表中记录数：N

- 平均查找长度：α = (N+1)/M

- 平均成功查找长度：αs = (1+α)/(1-α)

排序算法：

- 选择排序：O(n^2)

- 冒泡排序：O(n^2)

- 插入排序：O(n^2)

- 希尔排序：O(n^(1.3))

- 归并排序：O(nlogn)

- 快速排序：O(nlogn)

- 堆排序：O(n*logn)