线性表

线性表的定义和基本操作

这里没什么好说的, 主要注意几点. 线性表是逻辑结构, 表示元素之间 是一对一关系, 而顺序表, 链表都是线性表的存储结构. 这里也呼应了上一章的逻辑结构可以独立存在, 而存储结构需要依托于逻辑结构. 有了线性表这个逻辑结构, 才可以谈及顺序表, 链表这样的存储结构.

线性表的操作主要包括: 初始化, 求表长, 按值查找, 按位查找, 插入, 删除, 输出, 判空, 销毁. 涉及这些操作, 在考试伪码可以不去实现.

以及, 线性表一定要有顺序关系, 也就是除了表头, 其他都要有一个直接前继. 由n个数字组成的集合不是线性表, 因为他们不带有顺序.

线性表的实现

顺序存储结构

线性表的顺序存储结构又称为顺序表. 其特点是表中元素逻辑顺序和物理顺序一致. 顺序表支持随机访问, 存储密度高, 每个节点只存储数据元素.

需要注意的是, 线性表位序从1开始, 数组元素下标从0开始(C)

顺序表的各种操作算法复杂度如下:

1. 插入: 时间复杂度O(n) (平均下来是 $\frac{n}{2}$ )
2. 删除: 时间复杂度O(n)(平均下来是$\frac{n-1}{2}$)
3. 按值查找: 时间复杂度:O(n))(平均下来是$\frac{n+1}{2}$)

链式存储结构

线性表的链式存储又称单链表, 单链表元素离散分布在存储空间中, 因此单链表是非随机存储结构. 单链表设置头节点是为了统一插入删除, 方便操作 单链表的各种操作算法复杂度如下:

1. 建立链表: 头插法尾插法时间复杂度都是O(n)
2. 按序号查找:O(n)
3. 插入节点: 最低O(1)最高O(n)
4. 删除节点: 同上
5. 求表长:O(n)

双链表

没啥好说的, 双链表的插入删除操作时间复杂度O(1),

循环链表

略

静态链表

静态链表是链式存储结构, 在实现上可以用结构体数组来实现.

静态链表的插入删除和动态链表相同, 只需要修改指针, 不需要移动元素.

静态链表的指针指的是节点的相对地址(数组下标), 也称游标(cur)

易错点

1. 线性表的顺序存储结构是一种随机读取 的的存储结构. 不要看到顺序就选顺序.
2. 线性表位序从1开始
3. 交换两个节点的值, 顺序表比链表快