【通识】数据结构

数据结构=逻辑结构+物理结构（存储结构）
其中物理结构是数据的逻辑结构在计算机中的存储形式。而存储器针对内存而言，像硬盘、软盘、光盘等外部存储器的数据组织常用文件结构描述。
数据的存储结构应正确反映数据元素间的逻辑关系
体现为线性表的顺序存储能用数据实现，而元素物理
1）
2）
3）

1. 树

1.1 二叉树（Binary Tree）

1. 特点：除了最后一层外，其他层节点必须完全填满（每层从左到右没有空缺），最后一层的节点必须连续集中在左侧（允许右侧有空缺但左侧不能有）
   

1.2 B+树

MySQL InnoDB索引（B+树）作为主要的索引结构，用于主键索引（聚簇索引）和辅助索引（二级索引）。B+树相比于AVL树、红黑树等数据结构，更适合数据库的大规模数据存储和磁盘存取优化。

1. B+:平衡树（非二叉树），具有以下特点
   1）每个B+树的结点中含有n个关键字，而B+树每个节点中关键字个数n的取值范围是$\lceil m/2\rceil \le n\le m$
   2）所有的叶子节点包含了关键字的信息，及指向关键字记录的指针，且叶子节点本身依关键字的大小自小而大顺序链接。
   3）所有非终端节点（非叶子）是索引，结点中仅含有其子树（根节点）中最大/小的关键字

2. 1

3. 1

2. 哈希表

1. 概念：哈希表指通过哈希函数将键值映射到值的数据结构
2. 哈希冲突：通过哈希查找发现该位置上已有对应的关键码值，发生冲突
3. 解决冲突的方法：
   1）开发地址法：寻找另一个空闲地址，包括线性探测法和平方探测法
   2）链地址法：将所有哈希地址相同的记录链接到同一链表中，适用于频繁插入删除
   3）再哈希法：使用其他哈希函数计算新的地址
4. 相关的代码

// 两数之和：给定一个整数数组nums和整数目标值target，请在该数组中找出和为目标值target的两个整数，并返回数组下标class Solution {public: vector<int> twoSum(vector<int>& nums, int target) {vector<int> ret;}}

2.1