ADT 【抽象数据类型】
0. 常用数据结构
- 线性表(有序表)
- 栈
- 队列(单向、双向)
- 字典(KV,无序)
- 树
- 图
* 如何设计类?
(1)封装
一般分为:客户接口、实现
(2)注释
- javadoc 生成
- 职责(方法用途)
- 前置(参数)、后置(返回值)条件
- 断言(测试用、生产环境下抛出异常)
(3)选择类
- 根据角色 【用户】
- 根据场景
- 生成 用例图 辅助
- CRC 【类责任协作卡】
- UML 【统一建模语言】
1. 栈
- void push(newEntry)
- T pop()
- T peek()
- boolean isEmpty()
- void clear
(1)相关问题
- 平衡表达式:括号对称等
- 中缀表达式 => 后缀表达式(圆括号处理:开圆括号为最低优先级运算符)
- 计算后缀表达式(不含有圆括号)
- 计算中缀表达式(两个栈)
(2)应用
- 程序栈(Java栈)
- 链式栈
- 数组栈
- 向量栈
2. 字典
【结构:KV(键值对)】
- void add(key, value)
- V remove(key)
- V getValue(key)
- boolean contains(key)
- Iterator getKeyIterator()
- Iterator getValueIterator()
- boolean isEmpty()
- int getSize()
- void clear()
3. 散列表
- 快速确定下标(快速获得 key 所在位置)
- 散列码(hashCode)
(1)散列函数
- 注意:如果类重写了 equals(),则也应该重写 hashCode()
- 结果:将 散列码 压缩为散列表的 下标
- 冲突:开放地址法(双散列)、拉链法(每个 key 对应多个 value 进行存储)
4. 树
(1)相关问题
- 前序遍历
- 中序遍历
- 后序遍历
- 广度优先遍历
- 深度优先遍历
(2)常用二叉树
- 完全二叉树(有右必有左)
- 平衡二叉树(每个节点有高度相同的两个子树)
- 表达式树(a / b + c)
- 决策树(Yes || No)
- 二叉查找树(类似二分查找)
- 堆(最大 / 最小)
- 语法树
- AVL 树(不平衡时自动重排)
- 红黑树(根黑,红父为黑,红孩都为黑,每条树枝都有相同个数的黑色节点)
- B 树(m 阶多路查找树:根无或 2~m 个孩子,内部节点有 m/2~m 个孩子,叶子节点都在同一层)
5. 图
- 有 环 否?
- 有 权 否?
- 有 方向 否?
- 连通(邻接) 否?
(1)拓扑图
有向无环图
(2)邻接矩阵
(3)相关问题
- 寻找路径
- 带权图中的最短路径(开发算法、跟踪算法)
- 广度优先遍历