线性表
n个相同类型元素组成的有限序列
- 数组
- 链表
数组
数组的特点：
- 系统根据用户需求，开辟
连续的一定大小的内存空间 - 内容为连续存储
数组的优点：
- 数组可按索引查找
- 随机读取元素，数组效率很高
数组的缺点：
- 数组开辟的空间是固定的，未使用的内存会造成空间浪费
- 由于分配的空间必须连续，数据插入和删除操作更加耗时
链表
链表的特点：
- 链表的基本组成是节点，每一个节点中，存储着数据和下一个数据的内存地址
- 内容为链式存储
链表的优点：
- 可以快速进行数据的增删改
- 链表使用的空间是动态分配，使用时才分配新空间，不会造成内存浪费
链表的缺点：
- 读取数据需要按节点依次向下查找
数组和链表的耗时统计
| 操作 | 数组 | 链表 |
|---|---|---|
| 读取 | O(1) | O(n) |
| 插入 | O(n) | O(1) |
注：在代码实现过程中，链表仅插入这一步操作时间复杂度为O(1)
树
- 二叉树
二叉树
二叉树分类：
- 满（真）二叉树
- 完全二叉树
满（真）二叉树
- 特点：所有节点的度要么为0，要么为2
完全二叉树
- 特点：叶子节点只会出现最后2层，且 最后1层 的叶子节点都 靠左 对齐
- 计算总节点数：
- 假设叶子节点个数为n0，度为1的节点个数为n1，度为2的节点个数为n2；
总节点个数 n = n0 + n1 + n2，且 n0 = n2 + 1；
得 n = 2n0 + n1 -1 - 完全二叉树的n1要么为0，要么为1
- n1为1时，n = 2n0，n为偶数
- 假设叶子节点个数为n0，度为1的节点个数为n1，度为2的节点个数为n2；
网友评论