数据结构——线性表

线性表的定义和基本操作

线性表是具有相同数据类型的(n≥0)个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，则其中一般表示为：L=(a1,a2,a3,··· ,an)。除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继。
注意： 线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构

顺序表

顺序表的定义
线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。顺序表的特点是表中元素的逻辑顺序与其物理顺序相同

• 特点：
  1. 顺序表最主要的特点是随机访问，即通过首地址和元素序号可在时间O(1)内找到指定的元素
  2. 顺序表的 存储密度高 ，每个结点只存储数据元素
  3. 顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素

---

顺序表的基本操作

• 插入操作
  1. 最好情况：在表尾插入，元素后移语句将不执行，时间复杂度为O(1)
  2. 最坏情况：在表头插入，元素后移语句将执行n次，时间复杂度为O(n)
  3. 平均情况：在长度为n的线性表中插入一个结点时，所需要移动结点的平均次数为n/2，时间复杂度为O(n)
• 删除操作：
  1. 最好情况：删除表尾元素，无须移动元素，时间复杂度为O(1)
  2. 最坏情况：删除表头元素，需移动除表头元素外的所有元素，时间复杂度为O(n)
  3. 平均情况：在长度为n的线性表中删除一个结点时，所需要移动结点的平均次数为(n-1)/2，线性表删除算法的平均时间复杂度为O(n)
• 按值查找
  1. 最好情况：查找的元素就在表头，仅需比较一次，时间复杂度为O(1)
  2. 最坏情况：查找的元素在表尾或不存在时，需要比较n次，时间复杂度为O(n)
  3. 平均情况：在长度为n的线性表中查找e元素的平均比较次数为(n+1)/2，时间复杂度为O(n)

---

线性表的链式表示

顺序表可以随时存取表中的任意一个元素，但插入和删除操作需要移动大量元素。链式存储线性表时，不需要使用地址连续的存储单元，即不要求逻辑上相邻的元素在物理位置上也相邻，他通过“链”建立起数据元素之间的逻辑关系因此插入和删除操作不需要移动元素，而只修改指针，但也会失去顺序表可随机存储取的有优点

单链表的定义
线性表的链式存储又称为单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系，对每个链表结点，除存放元素自身的信息外，还需要存放一个指向后继的指针

• 其中data为数据域，存放数据元素。为指针域，存放其后后继结点的地址
• 利用单链表可以解决顺序表需要大量连续存储单元的缺点，但单链表附加指针域，也存在浪费存储空间的缺点，由于单链表的元素离散地分布在存储空间中，所以 单链表是非随机存取的存储结构 ，不能直接找到表中某个特点的节点。查找某个特定的结点时，需要从表头开始遍历，依次查找
• 通常用头指针来标识一个单链表，单链表L，头指针为NULL时表示一个空表。为了操作上的方便，在单链表第一个结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，也可以记录表长等信息。头结点的指针域指向线性表的第一个元素结点

判断单链表是否为空的判断条件：

• 带头结点：L—>next==NULL
• 不带头结点：L==NULL