02，数据结构简介
数据结构
数据结构是为实现对计算机数据有效使用的各种数据组织形式，服务于各类计算机操作。
不同的数据结构具有各自对应的适用场景，旨在降低各种算法计算的时间与空间复杂度，达到最佳的任务执行效率。
常见数据结构
线性数据结构
数组（Array）
数组是存放在连续内存空间上的相同类型数据的集合，其长度不可变。
因为数组的在内存空间的地址是连续的，所以在删除或者增添元素的时候，就难免要移动其他元素的地址。
数组的元素是不能删的，只能覆盖。
链表（Linked List）
链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。链接的入口节点称为链表的头结点也就是head。
链表种类
单链表：上述，单链表中的节点只能指向节点的下一个节点
双链表：每个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。可向前查询和向后查询
循环链表：链表首尾相连
链表的存储方式
链表在内存中不是连续分布的，而是通过指针域的指针链接在内存中各个节点，所以是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。
栈（Stack）
栈是一种具有先入后出特点的抽象数据结构，可使用数组或链表实现。
常用操作：入栈push()，出栈pop()
队列（Queue）
队列是一种具有先入先出特点的抽象数据结构，可使用链表实现。
常用操作：入队push()，出队pop()
非线性数据结构
树（Tree）
树是一种非线性数据结构，根据子节点数量可分为 「二叉树」 和 「多叉树」，最顶层的节点称为「根节点 root」。以二叉树为例，每个节点包含三个成员变量：「值 val」、「左子节点 left」、「右子节点 right」 。
二叉树的种类
满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。深度为k，有2^k-1个节点。
完全二叉树：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。
二叉搜索树
二叉搜索树是有数值的了，二叉搜索树是一个有序树。
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉排序树
平衡二叉搜索树/AVL树
是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。二叉树的存储方式
可以链式存储，也可以顺序存储。链式存储方式就用指针， 顺序存储的方式就是用数组。
链式存储：通过指针把分布在散落在各个地址的节点串联一起。
顺序存储：如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。
二叉树的遍历方式
- 深度优先遍历：先往深走，遇到叶子节点再往回走。
- 前序遍历（递归法，迭代法）：中左右
- 中序遍历（递归法，迭代法）：左中右
- 后序遍历（递归法，迭代法）：左右中
- 广度优先遍历：一层一层的去遍历。
- 层次遍历（迭代法）
堆（Heap）
堆是一种基于「完全二叉树」的数据结构，可使用数组实现。
以堆为原理的排序算法称为「堆排序」，基于堆实现的数据结构为「优先队列」。通过使用「优先队列」的「压入push()」和「弹出pop()」操作，即可完成堆排序。
堆分为「大顶堆」和「小顶堆」，大（小）顶堆：任意节点的值不大于（小于）其父节点的值。
from heapq import heappush, heappop # 初始化小顶堆 heap = [] # 元素入堆 heappush(heap, 1) heappush(heap, 4) heappush(heap, 2) heappush(heap, 6) heappush(heap, 8) # 元素出堆（从小到大） heappop(heap) # -> 1 heappop(heap) # -> 2 heappop(heap) # -> 4 heappop(heap) # -> 6 heappop(heap) # -> 8
散列表/哈希表（Hashing）
散列表是一种非线性数据结构，通过利用 Hash 函数将指定的「键key」映射至对应的「值value」，以实现高效的元素查找。
哈希碰撞的两种解决方法
将不同的键映射到了相同索引下标位置，这种想象称为哈希碰撞（collisions）
1，拉链法？？
要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。
2，线性探测法：要保证tableSize大于dataSize，依靠哈希表中的空位来解决碰撞问题。
图（Graph）
图是一种非线性数据结构，由「节点（顶点）vertex」和「边edge」组成，每条边连接一对顶点。根据边的方向有无，图可分为「有向图」和「无向图」。
图的表示方法
1，邻接矩阵：使用数组vertices 存储顶点，邻接矩阵edges 存储边；edges[i][j] 代表节点i+1 和 节点j+1 之间是否有边。
2，邻接表：使用数组vertices 存储顶点，邻接表edges 存储边，edges 为一个二维容器，第一维i代表顶点索引，第二维 edges[i] 存储此顶点对应的边集和。
**两种方式比较
邻接矩阵的大小只与节点数量有关，即N^2 ，其中N为节点数量。因此，当边数量明显少于节点数量时，使用邻接矩阵存储图会造成较大的内存浪费。
因此，邻接表 适合存储稀疏图（顶点较多、边较少）； 邻接矩阵 适合存储稠密图（顶点较少、边较多）。
