数据结构

线性表

$L=(a_1,a_2,\cdots,a_n) \\ \text{原子元素} \space \text{可变长度}\le$

顺序表

$LOC(a_n)=LOC(a_{n-1})+1$

单向链表

$Head \to [\text{Data}][\text{Next*},\wedge]$

双向链表

$Head \to [\text{Prev*}][\text{Data}][\text{Next*},\wedge]$

循环链表

$Head \to [\text{Data}][\text{Next*},\text{First*}]$

静态链表

$L(a_1,a_2,a_3) \iff A\begin{bmatrix} a_1 & a_2 & a_3\end{bmatrix} \\ \text{固定长度}$

数组

$A_{m*n}=\begin{bmatrix}a_{11} & \cdots & a_{1n} \\ \vdots & \ddots & \vdots \\ a_{m1} & \cdots & a_{mn}\end{bmatrix}$ $\\\text{同构元素} \space \text{固定长度}$

行主序

$\underbrace{\boxed{a_{11}}\cdots\boxed{a_{1n}}}_{\text{row}_1} \cdots \space \cdots \underbrace{\boxed{a_{m1}}\cdots\boxed{a_{mn}}}_{\text{row}_m}$

列主序

$\underbrace{\boxed{a_{11}}\cdots\boxed{a_{m1}}}_{\text{column}_1} \cdots \space \cdots \underbrace{\boxed{a_{n1}}\cdots\boxed{a_{mn}}}_{\text{column}_n}$

串

$S=(c_1,c_2,\cdots,c_n) \\ \text{字符元素} \space \text{可变长度}$

顺序结构

$LOC(c_n)=LOC(c_{n-1})+1$

链式结构

$Head \to [\text{Data}][\text{Next*},\wedge]$ $\\ \text{字符元素} \space \text{串元素}$

模式匹配

朴素

改进

广义表

$LS=(a_1,a_2,\cdots,a_n) \\ \text{原子元素} \space \text{表元素} \space \text{元素共享} \space \text{可递归(自包含)}$

链表节点存储

$\text{表节点：[1][hp][tp]} \\ \text{元素节点：[0][data]}$

栈

$\text{LIFO}$

顺序栈

$LOC(a_n)=LOC(a_{n-1})+1$

链栈

$top \to [\text{Data}][\text{Next*},\wedge]$

队列

$\text{FIFO}$

循环队列

$\text{Fixed length:}Q_{size} \\ \text{In:}Q_{\stackrel{next}{rare}}=(Q_{rare}+1)\%Q_{size} \\ \text{Out:}Q_{\stackrel{next}{front}}=(Q_{front}+1)\%Q_{size}$

链式结构

特殊矩阵

稀疏矩阵

顺序结构

三元组顺序表

链式结构

十字连表

有向图

无向图

网

树

二叉树

森林