数据结构

线性结构

线性表

数组

串

栈

队列

特殊矩阵

稀疏矩阵

广义表

顺序表

行主序 列主序

顺序串

顺序栈

循环队列

一维数组

三元组顺序表

🤷‍♂️

单向链表 双向链表 循环链表 静态链表

🤷‍♂️

链串

链栈

链队列

🤷‍♂️

十字链表

链表节点结构

队列

非线性结构

树

二叉树

哈夫曼树

有向图

无向图

网

双亲表示法

一维数组

一维数组

邻接矩阵

邻接矩阵

邻接矩阵

孩子表示法 孩子兄弟表示法

二叉链表 三叉链表

二叉链表 三叉链表

邻接链表

邻接链表

邻接链表

二叉树

$$\begin{matrix*}[l] \text{Node}={n} \\ \text{Level}={l} \\ \text{Depth}=d \end{matrix*}$$

---

$$\begin{matrix*}[l] |N|=2^d-1 & \text{(深度为d的满二叉树的节点数)} \\ |l_i|=2^{i-1} & \text{(二叉树第i层的节点数)}\\ d=\log_2^{|N|-1} & \text{(节点数为|N|的满二叉树的深度)} \end{matrix*}$$

静态查找表

顺序查找

折半查找

分块查找

$\frac{n+1}{2}$

$\frac{n+1}{n}\log_2(n+1)-1$

$\frac{1}{2}(\frac{n}{s}+s)+1$

动态查找表

二叉排序树

平衡二叉树

B树

哈希表

直接定址法

数字分析法

平方取中法

折叠法

随机数法

除留余数法

排序

直接插入排序

冒泡排序

简单选择排序

希尔排序

快速排序

堆排序

归并排序

基数排序

$O(n^2)$

$O(n^2)$

$O(n^2)$

$O(n^{1.3})$

$O(n\log n)$

$O(n\log n)$

$O(n\log n)$

$O(d(n+rd))$

$O(1)$

$O(1)$

$O(1)$

$O(1)$

$O(\log n)$

$O(1)$

$O(n)$

$O(rd)$