【软考向】Chapter 3 数据结构
- 线性结构
- 线性表
- 顺序存储 —— 访问易，增删难
- 链式存储 —— 访问难、增删易
- 栈 —— 后进先出 和 队列 —— 先进先出
- 字符串 —— KMP 匹配算法
- 数组、矩阵和广义表
- 数组
- 树 —— 树根为第一层，最大层数为树高/深度，度
- 线索二叉树
- 哈夫曼编码
- 树和森林 —— 树的双亲表示和孩子表示
- 图
- 存储 —— 邻接矩阵、邻接表
- 遍历 —— DFS、BFS
- 最小生成树 —— Prim 算法和 Kruskal 算法
- 拓扑排序和关键路径
- 最短路径
- 单源点最短路径 —— Dijkstra 算法
- 每对顶点间的最短路径 —— Floyd 算法
- 查找
- 静态查找 —— 顺序查找、二分查找、分块查找
- 动态查找 —— 二叉排序树、平衡二叉树、B 树
- 哈希表
- 排序
线性结构
线性表的存储结构分为顺序存储和链式存储。
线性表
顺序存储 —— 访问易，增删难
以 L O C ( a 1 ) LOC(a_1) LOC(