数据结构——线性表

线性表的定义

线性表是具有相同特性数据元素的一个有限序列。序列中所含元素个数叫做线性表的长度。除了头尾元素，其余元素都只有一个直接前驱和直接后继。

线性表的存储结构

1. 顺序存储结构（顺序表）

   原理：把线性表中的所有元素按照其逻辑顺序，一次存储到从指定的存储位置开始的一块连续的存储空间中（逻辑与物理统一）。

   优点：

   1. 空间利用率高。（局部性原理，连续存放，命中率高）
   2. 存取速度高效，通过下表来直接存储。

   缺点：

   1. 插入和删除比较慢
   2. 不可以增长长度

   时间复杂度：查找\(O(1)\)，插入和删除\(O(n)\)。

2. 链式存储结构（链表）

   原理：在程序运行过程中动态的分配空间，相邻数据元素课随意存放，每个结点不仅包含所存放的信息，还包含元素之间的逻辑关系的信息。

   优点：

   1. 插入和删除速度快，保留原有的物理顺序。
   2. 没有空间限制，存储元素的个数只与内存空间大小有关。

   缺点：

   1. 占用额外的空间一存储指针
   2. 查找速度慢，

   时间复杂度：查找\(O(n)\)，插入和删除\(O(1)\)。

   链表的\(5\)中形式。

   1. 单链表：每个结点中包含数据域和一个指针域，用于只想后继结点。终端结点指向空。
   2. 循环单链表：与单链表几乎一样，只是终端结点指向链表中的第一个结点。
   3. 双链表：每个结点中包含一个数据与和两个指针域，一个指向当前结点的的前驱，一个指向当前结点的后继。开始结点（或者头结点）的前指针和终端结点的尾指针为空。
   4. 循环双链表：与双链表几乎一样，只是开始结点（或者头结点）的前指针指向终端结点，终端结点的尾指针指向开始结点（或者头结点）
   5. 静态链表（借组一维数组表示）：数组中的每个结点包含两个部分，一个是数据元素，一个是指针，指向当前结点的直接后继在数组中的位置。

顺序表和链表的比较

1. 空间的比较
   1. 存储分配的方式：顺序表的存储空间是一次性的分配，链表的存储空间是多次分配的。
   2. 存储密度（\(=\frac{结点值域所占的存储量}{结点结构所占的存储总量}\)）：顺序表\(=1\)，链表\(<1\)
2. 时间的比较
   1. 存取方式：顺序表可以随机存取，也可以顺序存取；链表只能顺序存取
   2. 插入和删除是移动元素的个数：顺序表平均移动一半元素；链表不需要移动元素，只需要修改指针。