数据结构 存储、组织数据的方式,是抽象数据类型(ADT)的实现。
线性结构(顺序结构) 非线形结构
- 一般语言不能存放不同类型的数据
- 数组容量不会自动改变
- 数组的插入和删除操作性能较低
遵循后进先出
的原则的有序集合
遵循先进先出
的原则的有序集合
优先队列 入队和出队基于优先级的队列
循环队列
- 插入或移除元素无需移动大量元素,效率较高;
- 访问元素需要从起点开始遍历查找元素,效率较低。
集合中的元素无序且唯一。 集合运算:并集、交集、差集
一种分层的非线性数据结构,由一系列存在父子关系的节点组成。 子树 由节点及其后代构成的树。 节点的深度是指其祖先节点的数量。 树的高度是树所有节点深度的最大值。
二叉树是指每个节点最多只能有两个节点的树。 二叉搜索树是指节点、左节点和右节点存在大小关系的二叉树。
自平衡二叉树 任何节点左右两侧子树高度之差最多为1。 解决添加、删除或搜索节点的性能问题。
红黑树
由顶点和边组成 G = (V, E) 相邻顶点 一条边连接的两个顶点。 顶点的度 一个顶点与其相邻顶点的数量,也即是这个顶点上的边数。 路径 一个顶点到另外一个顶点之间相邻顶点的连续序列。 简单路径 不包含重复顶点的路径(不包含起止顶点)。 有向图 无向图
- 邻接矩阵 用索引与顶点关联构建二维矩阵,若索引为i的节点与索引为j的节点相邻则将array[i][j]置为1,否则置0。 非强连通图,浪费存储空间,无向图则是以主对角线对称的。
- 邻接表 每个顶点及其相邻顶点的列表
- 关联矩阵 行表示顶点,列表示边 元素array[i][j] 表示以索引为i的顶点为入射点的边j。
- 线性查找 无序数据
- 二分查找 有序数据 当使用二分查找时数据集中还有其他相同值,则这些相同值在已查找到的值左边或右边。
- 冒泡排序
- 选择排序
- 插入排序
- 希尔排序
- 快速排序
- 归并排序
- 堆排序
- 桶排序
- 计算排序
- 基数排序