常用数据结构

1. 线性表

线性表是一类最简单、最常用的数据结构。简单来说，一个线性表是n个元素的有限序列，其中n≥0，通常表示为（a1，a2，...，an）。其特点是，在非空的数据元素集合中：

（1）存在唯一的一个称作“第一个”的元素

（2）存在唯一的一个称作“最后一个”的元素

（3）除第一个元素外，集合中的每个元素均只有一个直接前驱

（4）除最后一个元素外，集合中的每个元素均只有一个直接后继

最基本的节点结构

在单向链表中插入结点时，指针的变化情况

在单向链表中删除结点时，指针的变化情况

在双向链表插入结点时的指针变化情况

在双向链表删除结点时的指针变化情况

2. 栈和队列

栈是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。即，栈的修改是按照先进后出（FILO）的原则进行的。

栈的5种基本运算

两个栈共享空间示意图

链栈示意图

队列的头、尾指针与队列中元素之间的关系

循环队列的头、尾指针示意图

链队列示意图

串值的链表存储方式

3. 广义表

广义表是线性表的推广，是由零个或多个单元素或子表所组成的有限序列。

-LS=（a1，a2，...，an）

其中ai（1≤i≤n）既可以是单个元素，又可以是广义表，分别称为原子和值表。

广义表的链表结点结构

广义表的存储结构示意图

4. 树

树的定义

注意：树的定义是递归的，即一个树由若干的子树构成，而子树又由更小的子树构成。

树的遍历操作是树中其他运算的重要基础。

几种二叉树

很容易区分：与满二叉树结点一一对应的即为完全二叉树，否则是非完全二叉树。

二叉树的顺序储存结构

显然顺序存储结构对于完全二叉树而言，既简单又节省空间；但对一般的二叉树则不适用。

二叉树的链表存储结构

二叉树转化为树和森林

5. 图

图是一种比数更复杂的数据结构

有向图和无向图