3. 线性表
3.1 线性表(List): 零个或多个数据元素的有限序列
3.2 线性表的定义
若将线性表记为(a1, ... ,ai-1, ai, ai+1, ... , an), 则表中 ai-1 领先于 ai, ai, 领先于 ai+1, 称ai-1是ai的直接前驱元素, ai+1 是 ai 的直接后继元素. 当 i=1, 2, ... , n-1 时, ai 有且仅有一个直接后继, 当 i=2, 3 , ... , n 时, ai 有且仅有一个直接前缀.
线性元素的个数 n (n>=0) 定义为线性表的长度, 当 n = 0 时, 称为空表
3.5 顺序存储结构的插入与删除
- 线性表的顺序存储结构, 在存, 读 数据时, 时间复杂度是 O[1]
- 插入, 删除时, 时间复杂度为 O[n]
线性表顺序存储结构的优缺点
- 优点:
- 无需为表示表中元素之间的逻辑关系而增加二外的存储空间
- 可以快速的存取表中任一位置的元素
- 缺点:
- 插入和删除操作需要移动大量的元素
- 当线性表长度变化较大时, 难以确定存储空间的容量
- 造成存储空间的 "碎片"
链表
3.6 线性表的链式存储结构
链式结构中, 除了要存储数据元素信息外, 还要存储它的后继元素地址
为了表示每个元素ai与其直接后继数据元素ai+1之间的逻辑关系, 对数据元素ai来说, 除了存储本身的信息之外, 还需存储一个指示其直接后继的信息(即直接后继的存储位置). 我们把存储元素信息的域称为数据域, 把存储直接后继位置的域称为指针域. 指针域中存储的信息称为指针或者链. 这两部分信息组成数据元素ai的存储映像, 称为节点(Node)
n 个节点(ai的存储映像)链接成一个链表, 即 为线性表(a1,a2,...an)的链式结构, 因为此链表的每个节点中只包含有一个指针域, 所以叫做单链表.
链表中第一个节点的存储位置叫做头指针, 最后一个节点为空(NULL 或者 ^)
单链表的第一个节点前附加一个节点,称为头节点(不是必须的). 不存储任何信息, 指向第一个节点.
3.7 单链表的读取
工作指针后移, 一个一个顺序读取.
3.8 单链表的插入与删除
插入与删除的时间复杂度都是O[1], 对于插入和删除数据越频繁的操作, 单列表的效率优势就越是明显
3.9 单链表的整表创建
- 头插法:
- 尾插法:
3.10 单链表的整表删除
将链表中的所有元素依次删除
3.11 单链表结构与顺便存储结构优缺点
存储分配方式
- 顺便存储结构用一段连续的存储单元依次存储线性表的数据元素
- 单链表采用链式存储结构,用一组任意的存储单元存放线性表的元素
时间性能
- 查找:
- 顺序存储o(1)
- 单链表o(n)
- 插入和删除
- 顺序存储结构需要平均移动表上一般的元素 时间为o(n)
- 单链表在得到某位置的指针后, 插入和删除时间仅为o(1)
空间性能
- 顺序存储结构需要预分配存储空间, 分大了 浪费, 分小了, 容易发生上溢
- 单链表不需要分配存储空间, 只要有就可以分配, 元素个数也不受限制
结论:
- 若线性表需要频繁查找, 很少进行插入和删除操作时, 宜采用顺序存储结构. 若需要频繁插入和删除时, 宜采用单链表结构
- 当线性表中的元素个数变化较大或者根本不知道有多大时, 最好用单链表结构. 这样可以不需要考虑存储空间的大小问题. 而如果实现知道线性表的大致长度,如一年12个月, 一周就是星期一至星期天共七天, 用顺序存储结构效率会高很多
3.12 静态链表
优点: 在插入和删除操作时, 只需要修改游标, 不需要移动元素, 从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点
缺点: 没有解决连续存储分配带来的表长难以确定的问题
失去了顺序存储结构随机存取的特性
3.13 循环链表
将单链表中终端节点的指针端由空指针改为指向头节点, 就使整个单链表形成一个环, 这种头尾相接的单链表称为单循环链表, 简称循环链表(circular linked list)
3.14 双向链表
双向列表插入, 要先完善插入元素的 next 和 prior 指向, 再完善其他的
3.15 总结
- 线性表
- 顺序存储结构
- 链式存储结构
- 单链表
- 静态链表
- 循环链表
- 双向链表
