数据结构.md

### 学习计划
* 数据结构的定义，为什么要有数据结构？ https://blog.csdn.net/turingbooks/article/details/93998363
* 常见的数据结构 https://www.cnblogs.com/qccadmin/p/10085749.html
* 数组 常见排序算法讨论 https://www.zhihu.com/question/51337272/answer/572455307
    * 直接插入排序 https://www.jianshu.com/p/7cf0656e76dd
* [数组 八种常见的排序算法](https://github.com/zhonghuasheng/JAVA/blob/master/README.md#thinking)

### 学习笔记
* 数据结构是指数据的组织形式。高效的数据组织形式能够加快计算机阅读和处理，从而提高效率。
* 数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合，通常情况下，精心选择的数据结构可以带来更高的运行或者存储的效率。数据结构往往同高效的检索算法和索引技术有关。
* 常见的数据结构
    * 集合结构
        * 数据类型相同的一类数据。典型的有：数组。
    * 线性结构
        * 元素之间存在一对一关系。典型的有：栈、队列和线性表。
    * 树形结构
        * 元素之间存在“一对多”关系，节点间具有层次关系，每一层的一个节点能且只能和上一层的一个节点相关，但同时可以和下一层的多个节点相关。典型的有：树，堆。
    * 图形结构
        * 在图形结构中，允许多个节点之间相关，存在“多对多”关系。
### 数组
* 定义：
* 数组：存放着一组相同类型的数据，需要预先指定数组的长度，有一维数组、二维数组、多维数组等。如果数组是自己定义并且初始化的的必须在new 类型[长度]这里指明长度，数组没有默认长度。Java中数组是定长的，一旦经过初始化声明就不可能改变长度，这在实际使用中非常不方便。常见的八大排序算法：
    ![](img/八大排序算法.png)
    排序算法可以分为内部排序和外部排序。内部排序是数据记录在内存中进行排序。而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。
* 链表：链表是C语言中一种应用广泛的结构，它采用动态分配内存的形式实现，用一组任意的存储单元存放数据元素链表的，一般为每个元素增设指针域，用来指向后继元素
    * 数组和链表的区别：
        * 从逻辑结构来看：数组必须事先定义固定的长度【有默认值】，不能适应数据动态地增减的情况；链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项（数组中插入、删除数据项时，需要移动其它数据项）
        * 从内存存储来看：（静态)数组从栈中分配空间（用NEW创建的在堆中）, 对于程序员方便快速,但是自由度小；链表从堆中分配空间, 自由度大但是申请管理比较麻烦
        * 从访问方式来看：数组在内存中是连续存储的，因此，可以利用下标索引进行随机访问；链表是链式存储结构，在访问元素的时候只能通过线性的方式由前到后顺序访问，所以访问效率比数组要低
* 栈、队列和线性表：可采用顺序存储和链式存储的方法进行存储
    * 顺序存储：借助数据元素在存储空间中的相对位置来表示元素之间的逻辑关系
    * 链式存储：借助表示数据元素存储地址的指针表示元素之间的逻辑关系
    * 栈：只允许在序列末端进行操作，栈的操作只能在栈顶进行，一般栈又被称为后进先出或先进后出的线性结构
        * 顺序栈：采用顺序存储结构的栈称为顺序栈，即需要用一片地址连续的空间来存储栈的元素
        * 链栈：采用链式存储结构的栈称为链栈
* 队列：只允许在序列两端进行操作，一般队列也被称为先进先出的线性结构
    * 循环队列：采用顺序存储结构的队列，需要按队列可能的最大长度分配存储空间
　　* 链队列：采用链式存储结构的队列称为链队列，一般需要设置头尾指针只是链表的头尾结点：
* 散列表（哈希表）：散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。

线性表：允许在序列任意位置进行操作，线性表的操作位置不受限制，线性表的操作十分灵活，常用操作包括在任意位置插入和删除，以及查询和修改任意位置的元素

　 顺序表：采用顺序存储结构表示的线性表称为顺序表，用一组地址连续的存储单元一次存放线性表的数据元素，即以存储位置相邻表示位序相继的两个元素之间的前驱和后继关系，为了避免移动元素，一般在顺序表的接口定义中只考虑在表尾插入和删除元素，如此实现的顺序表也可称为栈表：
　


　线性表：一般包括单链表、双向链表、循环链表和双向循环链表
　单链表：
　　

　双向链表：

　　
　线性表两种存储结构的比较：
　顺序表：
　优点：在顺序表中，逻辑中相邻的两个元素在物理位置上也相邻，查找比较方便，存取任一元素的时间复杂度都为O(1)
　缺点：不适合在任意位置插入、删除元素，因为需要移动元素，平均时间复杂度为O(n)
　链表：
　优点：在链接的任意位置插入或删除元素只需修改相应指针，不需要移动元素；按需动态分配，不需要按最大需求预先分配一块连续空空
　缺点：查找不方便，查找某一元素需要从头指针出发沿指针域查找，因此平均时间复杂度为O(n)

2、树形结构：结点间具有层次关系，每一层的一个结点能且只能和上一层的一个结点相关，但同时可以和下一层的多个结点相关，称为“一对多”关系，常见类型有：树、堆
（1）二叉树：二叉树是一种递归数据结构，是含有n(n>=0)个结点的有限集合，二叉树具有以下特点：
二叉树可以是空树；二叉树的每个结点都恰好有两棵子树，其中一个或两个可能为空；二叉树中每个结点的左、右子树的位置不能颠倒，若改变两者的位置，就成为另一棵二叉树

（2）完全二叉树：从根起，自上而下，自左而右，给满二叉树的每个结点从1到n连续编号，如果每个结点都与深度为k的满二叉树中编号从1至n的结点一一对应，则称为完全二叉树
a、采用顺序存储结构：用一维数组存储完全二叉树，结点的编号对于与结点的下标（如根为1，则根的左孩子为2*i=2*1=2，右孩子为2*i+1=2*1+1=2）
　

b、采用链式存储结构：
二叉链表：
　

三叉链表：它的结点比二叉链表多一个指针域parent，用于执行结点的双亲，便于查找双亲结点
　

两种存储结构比较：对于完全二叉树，采用顺序存储结构既能节省空间，又可利用数组元素的下标值确定结点在二叉树中的位置及结点之间的关系，但采用顺序存储结构存储一般二叉树容易造成空间浪费，链式结构可以克服这个缺点

（3）二叉查找树：二叉查找树又称二叉排序树，或者是一课空二叉树，或者是具有如下特征的二叉树：
a、若它的左子树不空，则左子树上所有结点的值均小于根结点的值
b、若它的右子树不空，则右子树上所有结点的值均大于根结点的值
c、它的左、右子树也分别是二叉查找树

（4）平衡二叉树：平衡二叉查找树简称平衡二叉树，平衡二叉树或者是棵空树，或者是具有下列性质的二叉查找树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差的绝对值不超过1
　

平衡二叉树的失衡及调整主要可归纳为下列四种情况：LL型、RR型、LR型、RL型

（5）树：树是含有n(n>=0)个结点的有限集合，在任意一棵非空树种：
a、有且仅有一个特定的称为根的结点
b、当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,...,Tm，其中每一个集合本身又是一棵树，并且T1,T2,...,Tm称为根的子树

（6）堆：堆是具有以下特性的完全二叉树，其所有非叶子结点均不大于（或不小于）其左右孩子结点。若堆中所有非叶子结点均不大于其左右孩子结点，则称为小顶堆（小根堆），若堆中所有非叶子结点均不小于其左右孩子结点，则称为大顶堆（大根堆）
　


（7）并查集：并查集是指由一组不相交子集所构成的集合，记作：S={S1,S2,S3,...,Sn}
（8）B树

3、图形结构：在图形结构中，允许多个结点之间相关，称为“多对多”关系，可分为有向图和无向图