README.md

数据结构与算法

数据结构 存储、组织数据的方式，是抽象数据类型(ADT)的实现。

线性结构(顺序结构) 非线形结构

数组

1. 一般语言不能存放不同类型的数据
2. 数组容量不会自动改变
3. 数组的插入和删除操作性能较低

栈

遵循后进先出的原则的有序集合

队列

遵循先进先出的原则的有序集合

优先队列 入队和出队基于优先级的队列

循环队列

链表

• 插入或移除元素无需移动大量元素，效率较高；
• 访问元素需要从起点开始遍历查找元素，效率较低。

单链表

双向链表

循环列表

集合

集合中的元素无序且唯一。 集合运算：并集、交集、差集

字典与散列表

树

一种分层的非线性数据结构，由一系列存在父子关系的节点组成。 子树 由节点及其后代构成的树。 节点的深度是指其祖先节点的数量。 树的高度是树所有节点深度的最大值。

二叉树

二叉树是指每个节点最多只能有两个节点的树。 二叉搜索树是指节点、左节点和右节点存在大小关系的二叉树。

自平衡二叉树 任何节点左右两侧子树高度之差最多为1。 解决添加、删除或搜索节点的性能问题。

红黑树

图

基本概念

由顶点和边组成 G = (V, E) 相邻顶点 一条边连接的两个顶点。 顶点的度 一个顶点与其相邻顶点的数量，也即是这个顶点上的边数。 路径 一个顶点到另外一个顶点之间相邻顶点的连续序列。 简单路径 不包含重复顶点的路径(不包含起止顶点)。 有向图 无向图

图的表示

• 邻接矩阵 用索引与顶点关联构建二维矩阵，若索引为i的节点与索引为j的节点相邻则将array[i][j]置为1,否则置0。 非强连通图，浪费存储空间，无向图则是以主对角线对称的。
• 邻接表 每个顶点及其相邻顶点的列表
• 关联矩阵 行表示顶点，列表示边 元素array[i][j] 表示以索引为i的顶点为入射点的边j。

查找算法

1. 线性查找 无序数据
2. 二分查找 有序数据 当使用二分查找时数据集中还有其他相同值，则这些相同值在已查找到的值左边或右边。

排序算法

• 冒泡排序
• 选择排序
• 插入排序
• 希尔排序
• 快速排序
• 归并排序
• 堆排序
• 桶排序
• 计算排序
• 基数排序