线性表的定义
在稍微复杂的线性表中, 一个数据元素可以有若干个数据项组成, 常把数据元素称为记录, 含有大量记录的线性表又称为文件
- 表中元素的个数有限
- 表中元素具有逻辑上的顺序性, 均为数据元素, 数据类型都相同, 具有抽象性
注意: 线性表是一种逻辑结构
线性表的表示
顺序表
定义
逻辑顺序与其物理存储顺序完全一致
- 主要优点
- 可进行随机访问
- 存储密度高
- 主要缺点
- 插入和删除操作效率较低, 需要移动大量元素
- 要求分配连续的存储空间
基本操作的实现
- 顺序表的初始化
- 静态分配
- 动态分配
- 插入操作
时间复杂度
- 最好情况: 在尾标插入, O(1)
- 最坏情况: 在表头插入, O(n)
- 平均情况: O(n)
- 删除操作
时间复杂度
- 最好情况: 删除表尾元素, O(1)
- 最坏情况: 删除表头元素, O(n)
- 平均情况: O(n)
- 查找操作
时间复杂度
- 按值查找, O(n)
- 按索引查找, O(1)
常见算法
双指针 王道 P20 05.
倒置 王道 P20 07. 10.
Boyer–Moore 投票算法 王道 P20 12.
空间换时间 王道 p21 13.
链表
数据元素的存储映像称为结点, 其中存储数据元素信息的域称为数据域, 存储直接后继存储位置的域称为指针域
- 单链表 各操作时间复杂度
- 求表长操作: O(n)
- 按序号查找节点: O(n)
- 按值查找表节点: O(n)
- 插入节点操作(含查找): O(n)
- 删除节点操作(含查找): O(n)
- 头插法建立单链表: O(n)
- 尾插法建立单链表: O(n)
循环链表
双向链表
静态链表
- 含备用链
- 不含备用链
常见算法
快慢指针 王道 p44 15. 16. 17. 20.
公共节点 王道 p43 05. p45 18.
空间换时间 王道 p45 19.