顺序表的定义
Q: 顺序表可以利用一维数组表示, 那么顺序表与一维数组是等同的吗?
A: 不是.
- 抽象层次不同: 顺序表是逻辑结构, 属于线性表的一种. 而数组是物理存储结构或基本数据类型, 是对内存中连续空间的基本抽象.
- 操作不同: 顺序表定义了插入、删除、查找等一系列针对线性表的操作. 而数组仅提供基于下标的读写.
- 限制不同: 顺序表强调元素间的逻辑线性关系, 而数组可以用来实现各种逻辑结构 (如树、图等).
Q: 一维数组可以用来表示逻辑结构-非线性的数据结构吗?
A: 可以
一维数组既可以用来表示逻辑结构线性的数据结构
例如栈, 队列等
也可以用来表示逻辑结构非线性的数据结构
例如树, 图
Q: 一维数组可以用来表示存储结构-链式存储的数据结构吗?
A: 可以
例如静态链表, 即使本身是链式存储, 也可以用数组来表示
线性表的链式表示
Q: 在单链表中, 对指定结点进行后插操作的时间复杂度是多少?
A: O (1)
Q: 在单链表中, 如何将前插操作的时间复杂度优化到 O (1)?
A: 可以通过将新结点在指定结点之后插入, 然后交换指定结点与新结点的数据域来巧妙地实现. (这需要新结点和指定结点的数据域大小相同且可交换)
Q: 在双链表中, 对指定结点进行前插或后插操作的时间复杂度是多少?
A: O (1). 因为双链表有指向前驱的指针, 可以直接找到前驱进行操作.
Q: 在单链表或双链表中, 按值查找一个结点的时间复杂度是多少?
A: O (n). 都需要从头遍历.
Q: 在单链表或双链表中, 删除指定结点(已获取指针) 的时间复杂度是多少?
A: O (1).
Q: 与单链表相比, 双链表是否插入, 删除操作更方便?
A: 错误
插入操作: 可以通过优化单链表的前插算法, 将前插转化为后插, 实现和双链表相同的时间复杂度
删除操作: 相同时间复杂度
Q: 线性表长度计算头结点吗?
A: 线性表长度是不计算头结点的
不管带不带头结点, 对于线性表的长度没有影响