第 10 章 数据结构与算法
学习目标
- 理解算法、时间复杂度和空间复杂度。
- 区分线性表、栈、队列、链表、树和二叉树。
- 掌握二叉树的前序、中序和后序遍历。
- 识别顺序查找、二分查找和基本排序方法。
1. 算法和复杂度
算法是解决特定问题的有限步骤，应具有输入、输出、确定性、有限性和可行性。时间复杂度描述执行时间随数据规模增长的趋势，空间复杂度描述所需额外存储空间的增长趋势。
常见数量级从低到高大致为：
O(1) < O(log n) < O(n) < O(n log n) < O(n²)2. 线性结构
线性表中的元素存在一对一关系。顺序存储使用连续空间，按序号直接访问；插入和删除通常需要移动后续元素。
栈是后进先出结构，只在栈顶插入和删除。队列是先进先出结构，一端进入、另一端离开。
链表用结点保存数据元素和后继位置。单链表向前遍历，双向链表可以访问前驱和后继，循环链表的尾结点又指向链表头部。链表插入和删除不必移动大量元素，但不能像顺序表那样直接用序号访问。
3. 树和二叉树
树是一对多的非线性结构。二叉树的每个结点最多有两个子结点，分别称为左孩子和右孩子。
三种遍历顺序：
- 前序：根结点、左子树、右子树。
- 中序：左子树、根结点、右子树。
- 后序：左子树、右子树、根结点。
对下面的二叉树：
A
/ \
B C
/
D前序是 A、B、D、C，中序是 D、B、A、C，后序是 D、B、C、A。
4. 查找和排序
顺序查找从一端逐个比较，不要求数据事先排序。二分查找要求数据已经有序，每次比较中间元素并排除一半范围。
- 冒泡排序属于交换类排序。
- 选择排序属于选择类排序。
- 插入排序属于插入类排序。
这三种基本排序在最坏情况下的时间复杂度都是 O(n²)。
本章练习
- 说明栈和队列的进出顺序差异。
- 给出上面示例二叉树的三种遍历结果。
- 判断二分查找能否直接用于无序列表。
- 把冒泡、选择和插入排序分别归入交换、选择或插入类。
本章小结
- 复杂度关注数据规模增长时资源消耗的变化趋势。
- 栈后进先出，队列先进先出，链表通过结点链接元素。
- 二叉树遍历由根结点相对左右子树的位置决定。
- 二分查找要求有序，三种基本排序都属于平方级复杂度。