一、数据结构说明

复制数据结构：
分为数据和结构
- 数据：就是所有的信息
- 结构：把数据以一定的规律，进行保存
- 最常见的数据结构：
	线性结构：数组、链表
	树型结构：永远都是有一个根
	网状结构：节点之间相互连接，组成一个网

二、数组

复制数组：连续的存储空间，每个元素的长度是一样的
   保存一个起始地址，加一个 size， 这个size，保存了数组的长度
   我们需要去取数组中的某一个 元素 的时候
   譬如： 
   '\x01\x02\x03\x04\x05\x06' ，假设这个字符串就是存储的数组内容，size是一个字节，
   下面的(2-1) 就是第几个元素  -1 ，得到的其实就是数组的下标， 从 0开始
   取第二个元素： 起始地址+size*(2 - 1) ，取到 \x02
   取第五个元素： 起始地址+size*(5 -1 )， 取到 \x05
   取第N个元素：  起始地址+size*(N -1 ) 
   
   特性：
   读取：直接通过 起始地址+size*(N -1 ) 得到地址，检索非常快
   写入：慢，
       1、插入新 元素 到最后的时候，是比较快的，直接把元素添加到最后一个位置
       2、插入新 元素 到最开始的时候，最慢，会把数组的所有 元素 都往后 移动 一位，然后把元素插入到第一个位置
       3、插入新 元素 到中间位置时，会把插入位置即之后的所有元素都往后移动一位，然后把元素插入到目标位置
   删除： 把 元素 删除后，需要把后面的所有元素，全部往前移动

三、链表

复制链表
    内容: 除了有 本身的数据外，还有 一个指针
    首先记忆一个 head， 第一个元素的位置
    譬如找第3个元素：
    先通过head，找到一个元素，通过元素中的指针，定位下一个元素
    找到第二个元素，继续通过第二个元素的指针，定位到下一个元素
    
    譬如：
    元素1 ，地址：地址1，内容：('内容1', '地址2')
    元素2  地址：地址2 ，内容：('内容2', '地址3')
    元素3  地址：地址3 ，内容：('内容2', 'None')
    
    新增一个元素4，地址是:地址4：插入到上限的元素1和元素2之间:
    元素1 ，地址：地址1，内容：('内容1', '地址4')
    元素4 ，地址：地址4，内容：('内容4', '地址2')
    元素2  地址：地址2 ，内容：('内容2', '地址3')
    元素3  地址：地址3 ，内容：('内容2', 'None')
    
    读取：慢，因为需要通过链接的方式，一个个查询
    写入：较快，只需要改写上一个元素的 指针，并且新增元素本身，并且将元素本身的指针指向 下一个元素
    删除：把自身删除后，需要把上一个元素的 指针，指向被删除元素指向的元素
    
    双向链表：
    在上述的单向链表中，多一个指针，指向上一个 元素
    
    循环链表：
    最后一个元素指向第一个元素，形成循环，
    循环链表是没有head的，所以必须人为指定一个 元素 为head

四、堆栈

复制堆栈
    这里的堆栈是指数据结构栈，不是内存中的堆和栈
    栈的最大特征就是： 后进先出 
    压栈： 往栈里压入 元素
    出栈： 从栈中 弹出 一个元素
    栈底，栈顶

五、队列

复制队列
    特征:先进先出
    
    双端队列：打破了 先进先出
    两端都可以压入元素，同时两端也可以弹出 元素
    
    只能取两端的，不能取中间的
    
    双端队列可以实现 队列 和 堆栈 的特征

六、树

复制树
    树形结构由 节点 和 边 组成
    边是连接 2个节点 的
    上下2个连接的节点，上层节点叫做父节点，下层节点叫做子节点
    同一个父亲的节点之间，叫做兄弟节点
    没有父节点的最上层节点叫做 根节点
    没有子节点的节点 叫做  叶子 
    
    二叉树：
    任意节点最多有2个子节点，可以没有，也可以只有一个
    
    树有几层，叫做深度为 几
    
    满二叉树： 层数为 m ， 节点数为 2^m - 1 的二叉树，叫做 满二叉树
    完全二叉树： 从满二叉树的基础上，最右边最下层的节点开始减少，减少后的树形都叫 完全二叉树
    
    数的遍历：
    遍历都是从根节点开始查找，仅仅是起始点而已，并不是一定从根节点开始获取数据或者操作 
    1、广度遍历：一层一层的检索
    2、深度遍历：
        节点遍历的时候，有3个节点相关，分别是 根、左、右
        以 二叉树.jpg 为例
        2.1 先序： 根、左、右
            1、2、4、8、9、5、10、11、3、6、12、7
        2.2 中序： 左，根，右
            8、4、9、2、10、5、11、1、12、6、3、7
        2.3 后序： 左、右、根
            8、9、4、10、11、5、2、12、6、7、3、1
            你去搜索一个节点的时候，先判断它是否有 左子节点
            有的话，先搜索左子节点，然后同样递归查找 左子节点

七、哈希表

复制哈希
    将一组关键字，通过 哈希函数 运算后，得到一个哈希地址
        映射到一个有限的地址集上 这个地址集叫做哈希表
    哈希函数要注意平均分布
    哈希函数对同一个内容，无论进行多少次运算，都得到同一个 哈希地址

八、复杂度

复制时间复杂度：
        最好执行次数、平均执行次数、最坏执行次数
        一般只考虑最坏执行次数
        
        时间复杂度由 简单 >>>> 复杂
        O(1) < O(logn) < O(n) < O(nlogn) < O(n ^ 2) < O(n ^ 2 logn) < O(n^3)......
        
        1、O(1)：时间的复杂度，不随着元素的数量的增多而增加，就叫做时间复杂度为 0(1)
        2、O(n):时间的复杂度，随着元素的数量的增多而增加，叫做 O（n）