数据结构=逻辑结构+物理结构（存储结构），数据结构是计算机中存储、组织数据的方式。
其中物理结构是数据的逻辑结构在计算机中的存储形式。而存储器针对内存而言，像硬盘、软盘、光盘等外部存储器的数据组织常用文件结构描述。
在这里插入图片描述

1. 基础算法

1.1 递归Recursion

函数在定义中使用函数自身的方法，例子是求斐波那契数列。
```
long long Fib(int i) {if(i<=1) return i;return Fib(i-1)+Fib(i-2);
}
```

1.2 分治Divide and Conquer

分治，即分而治之。☞将大问题分成几个小部分计算，最后再将小部分结果合并起来

要考虑什么时候是基础情况，很多时候依靠递归实现

int RecSum(int l, int r) {int mid = l + r >> 1; // 因为这里是位运算，相当于整数除以2；该写法常见于二分查找、分治算法等腰计算中间值return RecSum(l,mid)+RecSum(mid+l, r);
}

这段代码是递归求和函数，但因为没有终止条件会导致无限递归和栈溢出（stack overflow）。即没有处理l==r的情况，修正后

int RecSum(int l, int r) {if (l==r) return l;int mid = 
}

1.3 贪心算法

基本思想
1）求解最优化问题的算法包含一系列步骤
2）每一步都有一组选择
3）做出当前最好的选择
4）通过局部最优选择达到全局最优-> 未必达到全局最优
5）是否能达到最优解需严格证明
产生最优解的条件
1）最优子结构：
2）贪心选择性：

2. 线性表

数据的存储结构应正确反映数据元素间的逻辑关系
体现为线性表的顺序存储能用数据实现，而元素物理
1）个数有限；2）元素有先后次序；3）数据类型相同；4）讨论元素间的逻辑关系
一旦数据被线性表存储，在逻辑上的相对位置就固定下来了。线性表分为顺序表和链表。其中链式存储允许存储空间不连续，但顺序表不行。

2.1 跳表

上面的对比中可以看出，链表虽然通过增加指针域提升了自由度，但是却导致数据的查询效率恶化。特别是当链表长度很长的时候，对数据的查询还得从头依次查询，这样的效率会更低。跳表的产生就是为了解决链表过长的问题，通过增加链表的多级索引来加快原始链表的查询效率。这样的方式可以让查询的时间复杂度从O(n)提升至O(logn)。
在这里插入图片描述
1）
2）
3）

3. 栈

3.1 栈

遵守LIFO原则（后进先出）

3.2 队列

遵守FIFO原则（先进先出）

4. 树

4.1 二叉树（Binary Tree）

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

二叉树代码

此处是链式存储

typedef struct BiNode {char data;struct BiTNode *lchild, *rchild; // 左右孩子指针
} BiTNode, *BiTree;
BiTree root = NULL; // 根节点
root = (BiTree)malloc(sizeof(BiTNode));
root -> data = 'A';
root -> lchild = NULL;
root -> rchild = NULL;
// 插入结点B
BiTNode *BNode = NULL;
BNode = (BiTNode*)malloc(sizeof(BiTNode));
BNode->data = 'B';
BNode->lchild = NULL;
BNode->rchild = NULL;
root->lchild = BNode; // 定义了B之后才将A对应的root的左子树连接到B中
// 插入结点C
BiTNode *CNode = NULL;
CNode = (BiTNode*)malloc(sizeof(BiTNode));
CNode -> data = 'C';
CNode -> lchild = NULL;
CNode -> rchild = NULL;
root -> rchild = CNode;

二叉树

4.2 B+树

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

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

4.3 AVL树

4.4

5. 图

5.1 图的

6. 哈希表

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

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

6.1

7. 堆

用于动态内存管理

7.1

8. 动态规划

将会定义两个关键：一是动态规划，二是状态转移。
其中状态定义是把求解过程中所有状态（子问题）表示出来是动态规划的难点

8.1 区间dp和树形dp

8.2 8.3 常见问题

朴素区间dp：在区间上进行dp，主要思路是通过合并小区间得到大区间的最优解

大区间是cost[i][j][k]，其中包含dp[i][j]和dp[j][k]，将其合并为区间dp[i][k] = dp[i][j] + dp[j][k] + cost[i][j][k]
动态规划将会定义两个关键，一是状态定义二是状态装

破坏成链
经典树形dp
树形背包
树形背包优化

9. 排序

9.1 快速排序（三路版）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 三路快速排序（递归版本）
void quickSort3Way(vector<int>& nums, int left, int right) {if (left>=right) return; // 递归终止条件// 选择基准值（选择中间元素）int pivot = nums[left+(right-left)/2];// 初始化三个指针}