线性表

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为偶数