线性表

线性表（linear list）指零个或多个数据元素的有线序列

线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储，但是把最后一个数据元素的尾指针指向了首位结点）。

特征

1. 集合中必存在唯一的一个 第一元素
2. 集合中必存在唯一的一个 最后元素
3. 除最后一个元素之外，均有 唯一的后继（后件）
4. 除第一个元素之外，均有 唯一的前驱（前件）

基本操作

1. MakeEmpty(L) 这是一个将 L 变为空表的方法
2. Length(L) 返回表 L 的长度，即表中元素个数
3. Get(L, i) 这是一个函数，函数值为 L 中位置 i 处的元素（1<=i<=n）
4. Prior(L, i) 取 i 的前驱元素
5. Next(L, i) 取 i 的后继元素
6. Locate(L, x) 这是一个函数，函数值为元素 x 在 L 中的位置
7. Insert(L, i, x) 在表 L 的位置 i 处插入元素 x，将原占据位置 i 的元素及后面的元素都向后推一个位置
8. Delete(L, p) 从表 L 中删除位置 p 处的元素
9. IsEmpty(L) 如果表 L 为空表（长度为 0）则返回 true，否则返回 false
10. Clear(L) 清除所有元素
11. Init(L) 同一个，初始化线性表为空
12. Traverse(L) 遍历输出所有元素
13. Find(L, x) 查找并返回元素
14. Update(L, x) 修改元素
15. Sort(L) 对所有元素重新按给定的条件排序
16. strstr(string1, string2) 用于字符数组的求 string1 中出现 string2 的首地址

存储结构

两种物理结构：

• 顺序存储结构
• 链式存储结构

顺序存储结构

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

顺序存储结构的三个属性：

• 存储空间的起始位置：数组 data，它的存储位置就是存储空间的存储位置
• 线性表的最大存储容量：数组长度 MaxSize
• 线性表的当前长度：length

数组的长度是存放线性表的存储空间的长度，存储分配后这个量一般是不变的。

线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的。

在任意时刻，线性表的长度应该小于等于数组的长度。

优点

• 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
• 可以快速地存取表中任一位置的元素

缺点

• 插入和删除操作需要移动大量元素
• 当线性表长度变化较大时，难以确定存储空间的容量
• 造成存储空间的 碎片

链式存储结构

为了表示每个数据元素 a(i) 与其直接后继数据元素 a(i+1) 之间的逻辑关系，对数据元素 a(i) 来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。

• 数据域：存储数据元素信息的域
• 指针域：存储直接后继位置的域

指针域中存储的信息称为 指针 或 域。这两部分信息组成数据元素 a(i) 的存储映像，称为 结点（Node）。

• 头指针：普通的指针，链表中第一个结点的存储位置。头指针用于指明链表的位置，便于后期找到链表并使用表中的数据

线性链表中的最后一个结点指针为空（通常用 NULL 或 ^ 符号表示）

• 头结点：单链表的第一个结点前附设结点。头结点的数据域不存储任何信息。也可以存储如线性表的长度等附加信息，头结点的指针域存储指向第一个结点的指针。

头指针域头结点的异同

• 头指针
  • 头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针
  • 头指针具有标识作用，所以常用头指针冠以链表的名字
  • 无论链表是否为空，头指针均不为空。头指针是链表的必要元素
• 头结点
  • 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可存放链表的长度）
  • 有了头结点，对在第一元素结点插入结点和删除第一结点，其操作与其它结点的操作就统一了
  • 头结点不一定是链表必须要素

单链表结构

单链表（Linked List），即用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素（数据元素的映象）+指针（指示后继元素存储位置），元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

单链表结构和顺序存储结构对比：

• 存储分配方式
  • 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
  • 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素
• 时间性能
  • 查找
    • 顺序存储结构
    • 单链表
  • 插入和删除
    • 顺序存储结构需要平均移动表长一半的元素，时间为
    • 单链表在线出某位置的指针后，插入和删除时间仅为
• 空间性能
  • 顺序存储结构需要预分配存储空间，分大了，浪费，分少了易发生上溢
  • 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制

静态链表

静态链表（Static Linked List），即用数组描述的链表。

使用静态链表存储数据，数据全部存储在数组中（和顺序表一样），但存储位置是随机的，数据之间「一对一」的逻辑关系通过一个整形变量（称为「游标」，和指针功能类似）维持（和链表类似）。

循环链表

循环链表（Circular Linked List），将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表。因此，从循环链表中的任何一个结点触发都能找到任何其他结点。

循环链表解决了一个很麻烦的问题。如何从当中一个结点触发，访问到链表的全部结点。

分类

• 单循环链表：在单链表中，将终端结点的指针域 NULL 改为指向表头结点或开始结点即可
• 多循环链表：将表中结点链在多个环上

双向链表

双向链表又称双链表（Double Linked List），它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。