线性表
线性表介绍
线性表：数据元素的有序集合，除第一个和最后一个外，所有元素都有唯一前驱和唯一后继，即一对一
线性表是逻辑结构
线性表的实现通常有两种，顺序存储和链式存储，顺序存储就是我们常用的数组、向量等，把数据存放在一片连续的地址空间，物理相邻等价于逻辑相邻，下面主要介绍链式存储
线性表的链式存储及其实现
在链式存储种，我们使用指针的方式来指向当前元素的前驱和后继元素，将数据和指针存储在节点之中
单向链表
头节点：指向链表第一个元素的节点
结构定义：
typedef struct node
{
elemtype data;
node* next;
}node,*list;
这里我们以 int 作为数据种类，给出带头节点的单向链表代码参考 代码文件
双向链表：在单向链表的基础上加入前驱指针
循环链表：尾节点的指针指向头节点
链表的应用
- 环的判定：判定一个链表上是否存在环（某个节点指向之前的节点）
解法：快慢指针法，采用两个指针以不同的速度遍历链表，若没在空指针前没相遇就没有环，相遇了就有环
- 链表合并：将两个升序的链表合并成一个
解法：采用一个新的链表，三个指针分别指向三个链表，每次取两个链表中较小的元素插入新联表后指针后移，直到一个链表结束，把另一个链表剩下的直接接到新联表后面