# 线性表
# 一、概念
TIP
线性表是由
- 当
为0时，称为空表 - 线性表是一种逻辑结构，表示元素之间一对一的相邻关系
- 顺序表和链表是存储结构
# 二、特点
- 线性表中一定存在唯一的第一个元素
- 线性表中一定存在唯一的最后一个元素
- 除第一个元素外，其他元素均有唯一的直接前驱
- 除最后一个元素外，其他元素均有唯一的直接后继
- 表中元素个数有限
- 表中元素具有逻辑上的顺序性，在序列中各元素有其先后次序
- 线性表中的节点可以是记录型元素，每个元素含有多个数据项，每个项称为结点的一个域，每个元素有一个可以唯一标识每个结点的数据项组，称为关键字
- 表中每个元素的数据类型都相同，意味着每一个元素占有相同大小的存储空间
# 三、存储结构
# （一）顺序存储结构
顺序存储结构是指用一组地址连续的存储单元依次存储线性表中的各个元素。用顺序存储方式实现的线性表称为顺序表，逻辑结构上相邻的元素在物理存储单元中也相邻。
# 顺序表
- 顺序表最主要的特点是随机访问，即通过首地址和元素序号可以在
时间内找到指定元素 - 顺序表的存储密度高，每个结点只存储数据元素
- 顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需移动大量元素
# 时间复杂度
- 最好情况：查找的元素就在表头，仅需比较一次，时间复杂度为
- 最差情况：查找的元素在表尾或不存在时，需要比较
次时间复杂度为 - 平均情况：假设
是查找的元素在第 个位置上的概率，则在长度为 的线性表中查找值为 的元素所需比较的平均次数为：
因此，线性表按值查找算法的平均时间复杂度为
# （二）链式存储结构
顺序表在插入和删除时，需要移动大量的元素，影响效率，链表能克服这些不足。
- 存储链表中结点的一组任意的存储单元可以是连续的，也可以是不连续的
- 链表中结点的逻辑顺序和物理顺序不一定相同
# 单链表
为了操作方便，总是在链表的第一个结点之前附设一个头结点指向第一个结点。头结点的数据域可以不存储任何信息（也可以存储长度等信息）。
引入头结点的优点？
- 链表第一个位置上的操作和在表其他位置的操作一致，无需进行特殊处理
- 无论链表是否为空，其头指针是指向头结点的非空指针，因此空表和非空表的处理也被统一了
TIP
单链表是由表头唯一确定的，因此单链表可以用头指针的名字来命名
带头结点的单链表
头指针为
不带头结点的单链表
头指针为
# 基本操作：插入
- 头插法
每次插入的结点都作为链表的第一个结点
//假设在p结点之后插入结点s
//先右后左
s->next = p->next;
p->next = s
1
2
3
4
2
3
4
- 尾插法
头插法虽然简单，但是生成的链表与插入次序相反，若希望链表次序与插入次序一致则使用尾插法。
//假设删除结点p之后的结点s
//先右后左
s->next = p->next;
p->next = s;
p = s;//新结点变为尾结点
1
2
3
4
5
2
3
4
5
# 基本操作：删除
假设删除结点p的后继结点q
q = p->next;
p->next = q->next;
free(q);
1
2
3
2
3
# 循环链表
循环链表，又称循环单链表，是一个首尾相接的链表，将单链表的最后一个结点的后继指针指向头结点，就得到了循环链表。
- 循环链表的判空：
- 判断是否是表尾结点：
- 循环链表的插入、删除算法与单链表几乎一样，不同的是如果操作在表尾进行，要让单链表保持继续循环的性质
- 有时对单链表常做的操作是在表头和表尾进行的，此时可对循环单链表不设头指针而仅设尾指针，从而使得操作效率更高，原因：若设的是头指针，对表尾进行操作需要
的时间复杂度，而如果设的是尾指针，可通过 得到头指针，这样对于表头表尾的操作都只需要 的时间复杂度
# 双向链表
单链表和循环链表每个结点都只有一个用于指向直接后继的指针域，所以遍历时只能沿一个方向寻找其他结点。为了克服查找不便的缺点，出现了双向链表。
双向链表每个结点都有两个指针域，一个用于指向该结点的直接后继，另一个用于指向该结点的直接前驱。空双向链表与非空双向链表结构如下图所示。
- 判断是否是尾结点：
- 当双向链表为空时，头结点的
域和 域都等于
# 基本操作：插入
//假设在结点p之后加入结点s
//加入结点时先把新加入的结点两端接上
s->next = p->next;
s->prior = p;
p->next = s;
s->next->prior = s;
1
2
3
4
5
6
2
3
4
5
6
# 基本操作：删除
//假设删除结点p的后继结点q
q = p->next;
p->next = q->next;
q->next->prior = p;
free(q);
1
2
3
4
5
2
3
4
5
# 静态链表
静态链表是借助数组来描述线性表的链式存储结构，结点分为数据域和指针域，与前面链表指针不同的是，这里的指针是指数组下标。
- 静态链表以
作为其结束标志 - 与顺序表一样，静态链表需要预先分配一块连续内存空间
- 静态链表指针与单链表类似，只需修改指针，不需要移动元素
# 四、比较
存取方式：
- 顺序表可以顺序存取，也可以随机存取，但是链表只能从表头顺序存取
存储结构：
- 顺序存储时，逻辑上相邻的元素，其对应的物理位置也相邻；而链式存储时，逻辑上相邻的元素，物理存储位置不一定相邻
操作：
- 按值查找：当数据无序时，时间复杂度均为
；当数据有序时，顺序表可使用折半查找，此时时间复杂度为 - 按序号查找：顺序表时间复杂度为
;链表的平均时间复杂度为
空间分配：
- 顺序表在存储空间装满的情况下不能扩充，需要预先分配足够大的存储空间
- 链表的空间可以在需要的时候再申请分配
栈 →