顺序表的定义
Q: 顺序表可以利用一维数组表示, 因此顺序表与一维数组在逻辑结构上是相同的吗?
A: 不同
顺序表是顺序存储的线性表, 表中所有元素的类型必须相同, 且必须连续存放
一维数组中的元素可以不连续存放
Q: 一维数组可以用来表示逻辑结构-非线性的数据结构吗?
A: 可以
一维数组既可以用来表示逻辑结构线性的数据结构
例如栈, 队列等
也可以用来表示逻辑结构非线性的数据结构
例如树, 图
Q: 一维数组可以用来表示存储结构-链式存储的数据结构吗?
A: 可以
例如静态链表, 即使本身是链式存储, 也可以用数组来表示
Q: 为什么往往要在数据结构中引入头结点?
A: 1. 统一所有数据节点的查找, 删除操作
对于第一个数据结点
如果不引入头结点, 第一个数据节点没有直接前驱结点, 操作需要特殊处理
在引入头结点之后, 数据节点的查找, 删除操作相同
- 统一空表和非空表的头指针位置
没有头结点的情况下, 空表的头指针指向 Null, 非空表的头指针指向第一个数据结点
引入头结点之后, 不论是否是空表, 头指针一直指向头结点
线性表的链式表示
| 单链表 | 双链表 | |
|---|---|---|
| 前插 | 直接做:{ 后插方法优化:{ | |
| 后插 | ||
| 查找 | ||
| 删除 |
Q: 如何判断循环双链表
A: 为空表时, 其头结点的 prior 域和 next 域都等于
静态链表是用数组来描述线性表的链式存储结构
静态链表以 {
Q: 与单链表相比, 双链表是否插入, 删除操作更方便?
A: 错误
插入操作: 可以通过优化单链表的前插算法, 将前插转化为后插, 实现和双链表相同的时间复杂度
删除操作: 相同时间复杂度
| 顺序表 | 有序链表 | 无序链表 | |
|---|---|---|---|
| 插入 | |||
| 按值查找 | |||
| 删除 |
Q: 带头结点的循环单链表 L 中是否存在空指针?
A: 不存在
即使是空表的时候
头结点的指针域存放着下一个结点的地址
就是 L 的值
Q: 线性表长度计算头结点吗?
A: 线性表长度是不计算头结点的
不管带不带头结点, 对于线性表的长度没有影响