大话数据结构
绪论
if yu give someone a program, you will frustate them for a day; if you teach them how to program, you will frustate them for a lifetime.
程序设计 = 数据结构 + 算法
数据结构: 相互之间存在一种或多种特定关系的数据元素的集合
逻辑结构: 集合 / 线性 / 树形 / 图形
物理结构: 顺序 / 链式
抽象数据类型: 问题 -> 分解 / 抽象 / 信息隐藏
算法
算法是解决特定问题求解步骤的描述, 在计算机中变现为指令的有限序列
特性: 输入输出 + 有穷 + 确定 + 可行
要求: 正确性 + 可读性 + 健壮性(不确定输入的处理) + 效率高&存储低
时间复杂度: 1 < logN < N*logN < N^2 < N^3 < 2^N < N! < N^N
最好 / 最差 / 平均 / 空间复杂度
线性表
线性表List: >=0 个数据元素的有限序列
顺序存储
链式存储: 头插法 / 尾插法 / 跳跃删除 / 替代删除
静态链表: 使用数组实现链表
循环链表 / 双向链表
栈&队列
栈stack: 限定在表尾进行操作的线性表
2栈 -> 队列
栈的应用 -> 递归 / 后缀表达式
队列queue: 只允许在一端插入, 在另一端删除的线性表
循环队列 -> 队列存储不足
串
黄山叶落松落叶山黄
百度百科 - 璇玑图
串: 由 >=0 个字符组成的有限序列
串的比较: 比较字符的 ASCII 码
朴素的模式匹配算法 / KMP模式匹配算法
树Tree
森林 -> 树 -> 二叉树 -> null / 1个节点 / 斜树 -> 完全二叉树 -> 满二叉树
性质: 第i层<=2^(i-1); 深度k<=2^(k-1); 度
遍历: 前序/中序/后序(递归/栈 实现) + 层次(队列实现)
前序/后序 + 中序 构建树 -> 获取 root 节点, 就可以通过 中序遍历知道 左右子树
线索二叉树 -> 线索化(线性)
霍夫曼树(每次将权值最小的2个节点构成二叉树) -> 霍夫曼编码
图Graph
图: >0 个有穷顶点和顶点之间的边的集合组成
无向图 / 有向图
邻接矩阵 / 邻接表
dfs / bfs
最小生成树: Prim / Kruskal
最短路径: Dijkstra / Floyd
拓扑排序: 查找入度为0的顶点, 删除此顶点&边, 重复 -> 关键路径
查找
有序表查找: 二分查找 / 插值查找(数据分布均匀) / 斐波那契查找
线性索引查找: 稠密索引(按照关键码有序排列) / 分块索引 / 倒排索引(搜索技术)
二叉排序树BST: 左子树皆小于root, 右子树皆大于root / 查找 / 插入 / 删除 -> 二叉平衡数AVL: 左右子树高度差<=1 / 实现算法
多路查找树(B树): 众多文件中查找
2-3 树 -> 2-3-4 树 -> B 树 -> B+ 树(包含重复节点来标识数据范围)
散列表(hashtable) -> 散列技术(存储 / 查找) -> 散列冲突
排序
排序: 稳定性 / 内排序&外排序 / 时间 / 辅助空间 / 算法复杂性
交换排序: 冒泡 -> 快排
插入排序: 直接插入 -> 希尔
堆排序
归并排序
