前言
什么是数据结构？
数据结构(data structure)是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系。
线性表
拿处理学生信息举一个例子，我们希望能够将这些数据按顺序存放，支持在某个位置插入一条数据、删除一条数据、修改一条数据等，这时候，数组就显得有些乏力了。
数组无法做到这么高级的功能，那么我们就需要定义一种更加高级的数据结构来做到，我们可以使用线性表（Linear List）
线性表是由同一类型的数据元素构成的有序序列的线性结构。线性表中元素的个数就是线性表的长度，表的起始位置称为表头，表的结束位置称为表尾，当一个线性表中没有元素时，称为空表。
线性表一般需要包含以下功能：
- 初始化线性表：将一个线性表进行初始化，得到一个全新的线性表。
- 获取指定位置上的元素：直接获取线性表指定位置
i上的元素。 - 获取元素的位置：获取某个元素在线性表上的位置
i。 - 插入元素：在指定位置
i上插入一个元素。 - 删除元素：删除指定位置
i上的一个元素。 - 获取长度：返回线性表的长度。
也就是说，现在我们需要设计的是一种功能完善的表结构，它不像是数组那么低级，而是真正意义上的表：
实现线性表的结构一般有两种，一种是顺序存储实现，还有一种是链式存储实现。他们分别是顺序表和链表。
链表
链表不同于顺序表，顺序表底层采用数组作为存储容器，需要分配一块连续且完整的内存空间进行使用，而链表则不需要，它通过一个指针来连接各个分散的结点，形成了一个链状的结构，每个结点存放一个元素，以及一个指向下一个结点的指针，通过这样一个一个相连，最后形成了链表。它不需要申请连续的空间，只需要按照顺序连接即可，虽然物理上可能不相邻，但是在逻辑上依然是每个元素相邻存放的，这样的结构叫做链表（单链表）。
链表分为带头结点的链表和不带头结点的链表，戴头结点的链表就是会有一个头结点指向后续的整个链表，但是头结点不存放数据
而不带头结点的链表就像上面那样，第一个节点就是存放数据的结点，一般设计链表都会采用带头结点的结构，因为操作更加方便。
单链表的插入
我们可以先修改新插入的结点的后继结点（也就是下一个结点）指向，指向原本在这个位置的结点：
接着我们可以将前驱结点（也就是上一个结点）的后继结点指向修改为我们新插入的结点：
这样，我们就成功插入了一个新的结点，现在新插入的结点到达了原本的第二个位置上：
双链表
通过链式存储，我们不用再像顺序表那样一次性申请一段连续的空间，而是只需要单独为结点申请内存空间，同时在插入和删除的速度上也比顺序表轻松。不过有一个问题就是，如果我们想要操作某一个结点，比如删除或是插入，那么由于单链表的性质，我们只能先去找到它的前驱结点，才能进行。
为了解决这种查找前驱结点非常麻烦的问题，我们可以让结点不仅保存指向后续结点的指针，同时也保存指向前驱结点的指针。这样我们无论在哪个结点，都能够快速找到对应的前驱结点，就很方便了，这样的链表我们成为双向链表（双链表）
循环链表
接着我们再来简单认识一下另一种类型的链表，循环链表，这种链表实际上和前面我们讲的链表是一样的，但是它的最后一个结点，是与头结点相连的，双向链表和单向链表都可以做成这样的环形结构，我们这里以单链表为例：
这种类型的链表实际上与普通链表的唯一区别就在于最后是否连接到头结点，因此循环链表支持从任意一个结点出发都可以到达任何的结点，而普通的链表则只能从头结点出发才能到达任意结点，同样也是为了更灵活而设计的。
双链表插入操作
接着是双向链表的插入操作，这就比单链表要麻烦一些了，我们先来分析一下：
首先我们需要考虑后继结点，当新的结点插入之后，新的结点的后继结点就是原本在此位置上的结点，所以我们可以先将待插入结点的后继指针指向此位置上的结点。
由于是双向链表，所以我们需要将原本在此位置上的结点的前驱指针指向新的结点：
接着我们来处理一下前驱结点，首先将前驱结点的后继指针修改为新的结点：
最后我们将新的结点的前驱指针指向前驱结点即可：
双链表删除操作
无论是正向遍历还是反向遍历，都可以正常完成，相比单链表的灵活度肯定是更大的，我们接着来看删除操作，其实删除操作也是差不多的方式：
我们只需将前驱结点和后继结点的指向修改即可：
接着直接删除对应的结点即可：
栈
栈的定义
栈是一种特殊的线性表，插入和删除操作在表的某一端进行，允许插入和删除操作的一端称为栈顶，另一端称为栈底。
可以把栈看作一个竖直的桶，每次只能放入一个元素，先放入的元素在下，后放入的元素在上，后放入的元素先出。
栈的特征
- 后进先出（LIFO）
栈的基本运算
- 初始化栈
- 进栈
- 出栈，即返回栈顶元素，并删除当前的栈顶元素
- 取栈顶元素
- 判断栈空
栈的存储结构
栈的结构定义主要包含以下属性
- data: 一维数组，用于保存栈中的元素
- StackSize：栈的大小，即数组的大小
- ElemType：元素的类型
- top: 栈顶的指针
队列
队列的定义
队列也是一种特殊的线性表，插入操作在一端进行，称为队头，删除操作在另一端进行，称为队尾。
队列就跟生活中的排队类似，不允许插队，先排的人可以先得到服务。
队列的特征
- 先进先出（FIFO）
队列的基本运算
- 初始化队列
- 入队
- 出队
- 取队头的元素
- 判断队列是否为空
队列的存储结构
顺序存储结构
1 |
|
链式存储结构
1 | typedef char ElemType; |
二叉树
二叉树的定义
树形结构是一种非线性结构，二叉树是度为2，即子结点的个数最多为2的有序树（左右子树是有次序的）。最重要，应用最广泛的一种树。
完全二叉树
在一个二叉树中，除了最后一层外，其余的其他层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干个结点，则该树称为完全二叉树。
满二叉树是一种特殊的完全二叉树，即所有的层的结点都是满的。
树的基本术语
- 结点的度：该节点的后继节点的个数
- 树的度：所有节点的度的最大值
- 分支结点
- 叶子结点
- 孩子结点
- 双亲结点
- 子孙结点
- 祖先结点
- 兄弟结点
- 结点层数
- 树的深度（高度）：树中结点的最大的层数
- 有序树：左右子树是有次序的
- 无序树：左右子树是无次序的
- 森林：不同树的集合
二叉树的性质
- 二叉树上叶子节点的个数等于度为2的结点的个数加1
- 二叉树上第i层上至多有2^(i-1)个结点（i>1）
- 深度为h的二叉树至多有2^h-1个结点
二叉树的基本运算
- 创建二叉树
- 求二叉树的高度
- 求二叉树结点的个数
- 求二叉树叶子结点的个数
- 用括号表示法输出二叉树
- 用凹入表示法输出二叉树
二叉树的存储结构
顺序存储结构
1 | typedef ElemType SqBinTree[MaxSize] |
链式存储结构
1 |
|
