目录
数据结构
数据结构定义
数据结构类型
链表
数组
栈
队列
哈希表
堆
二叉查找树
排序
排序定义
排序种类
冒泡排序
选择排序
插入排序
堆排序
归并排序
快速排序
数组的查找
线性查找
二分查找
数据结构
数据结构定义
数据结构指所有数据元素以及数据元素之间的关系，可以看作是相互之间存在着某种特定关系的数据元素的集合。简单来说，决定着数据存储在内存中时数据顺序和位置关系的便是“数据结构”。
例如：内存中存放数据1、数据2、数据3，顺序排列有3!=6种排序方式，决定着哪种排序方式的就是“数据结构”
数据结构类型
链表
链表的大类属于线性表，线性表是具有相同特性的数据元素的一个有限序列。线性表的顺序存储结构成为顺序表，链式存储结构称为链表。由于顺序表概念简单且利用率低，此处仅讨论链表。
链表中逻辑上相邻的元素对应的存储位置通过指针来链接
链表种类：单链表、双链表、循环链表
链表特点：可以实现空间动态管理，数据呈线性排列，分散存储与内存中。
优点：数据添加、删除较快
缺点：访问较慢
数组
数组是具有相同类型数据元素的有限序列
特点：数据呈线性排列存储在内存的连续空间内
优点：访问较快
缺点：添加、删除数据较慢
栈
栈是一种只能在一端进行插入或删除操作的线性表
特点：“后进先出”
队列
队列简称队，是一种只能在表的一端进行插入、在表的另一端进行删除的线性表
特点：“先进先出”
哈希表
哈希表利用哈希函数快速访问到数组中的目标数据
(此处省略哈希函数的计算方法和哈希冲突解决方法，详后对哈希函数单独解)
特点：线性存储
堆
堆是一种图的树形结构，被用于实现“优先队列”（优先队列可以自由添加数据，但要求取出数据时从最小值按序取出）分为最大堆和最小堆，区别是节点排序方式不同
最小堆规则：每个结点最多两个子结点，存储数据时子结点必定大于父结点（故最小值被存储在顶端的根节点中），结点排列顺序为从上到下，同一行从左到右。添加新数据时，新数据被放在最下面一行靠左的位置，最下面一行没有多余空间时再往下另起一行，数据加在该行的最左端，再一边比较它与父结点数据大小，一边往上移动。取出数据时将最后的数据移动到最顶端，一边比较它与子结点数据的大小，一边往下移动。
最大堆同理
二叉查找树
二叉查找树采用了图的树形结构，数据存储于二叉查找树的各个结点中
规则：每个结点最多有两个子结点，每个结点的值均大于其左子树上任意一个结点的值、小于其右子树上任意一个结点的值
查找结点：查找最小结点从顶端开始，往左下末端查找；查找最大节点从顶端开始，往右下末端寻找
添加结点：从顶端开始比较，小于则左移，大于则右移
删除结点：若所需删除结点无子结点，则直接删除该结点；若有所需删除结点只有一个子结点，先删除目标结点，再移位子结点；若所需删除结点有两个子结点，先删除目标结点，在被删除结点左子树中寻找最大结点移到被删除结点位置上，若需要移动的点还有子结点，递归执行前面操作。
排序
排序定义
排序：按照递增或递减关系有序整理表中的元素
排序种类
冒泡排序
冒泡排序：通俗来讲就是重复从序列右边开始比较相邻两数字大小，根据结果交换两数字位置这个操作
特点：交换数字的次数和输入数据的排列数序有关
选择排序
选择排序：通俗来讲就是重复从数据中寻找最小值与序列最左边数字进行交换这个操作
特点：使用线性查找寻找最小值
插入排序
插入排序：从序列左端开始依次对数据进行排序
堆排序
堆排序：在堆中存储所有的数据，按降序来构建堆
特点：从降序排列的堆中取出数据会从最大的数据开始取，故将取出得数据反序输出则排序完成
归并排序
归并序列：将序列分成长度相同的两个子序列，无法继续下分时，对子序列进行归并，合并时顺序排列
快速排序
快速排序：在序列中随机选择一个基准值，将除了基准值以外的数分为“比基准值小的数”和“比基准值大的数”两个类别，即[比基准值小的数]基准值[比基准值大的数]，再使用快速排序对“[]”中的数据进行排序
数组的查找
线性查找
线性查找：从头开始不断按照顺序查找数据
二分查找
与线性查找不同，二分查找只能查找已经排好序的数据，每一次查找都可以将查找范围减半
