数组
定义：数组是具有一定顺序关系的若干对象组成的集合，组成数组的对象称为数组元素。
一维数组（线）
二维数组的引用格式为：数组名[行下标][列下标];
int a[3][4] = {
{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};（面）
三维数组：x,y,z （体）
下标由n个数组组成的数组称为n维数组
数组存储的特点：1.数组元素在内存中按顺序连续存储 2.数组的存储分配按照行或列进行 3.数组名表示该数组的首地址，是常量
一维数组：a[n] 存储：（c为每个元素占用的存储空间字节数） Loc(a[i])=Loc(a[0])+i*c
二维数组a[m,n] 存储：（c为每个元素占用的存储空间字节数）Loc（a[i,j]）=Loc(a[0,0])+(i*n+j)*c
三维数组a[m,n,l] 存储：第一维下标变化最慢，第三维（最后一维）下标变化最快 Loc(a[i,j,k])=Loc(a[0,0,0])+(i*n*l+j*l+k)*c
链表
1. 单链表的逻辑结构与存储结构
?逻辑结构：数据元素之间的逻辑关系
集合、线性结构（一对一）、树形结构（一对多）、图结构（多对多）
?存储结构：
顺序存储、链式存储、索引存储、散列存储
顺序存储（顺序表）：逻辑上相邻的元素物理位置也相邻
链式存储（单链表）：逻辑上相邻的元素物理位置不一定相邻
??????(47条消息) 数据结构——单链表的定义_晓风岚月-CSDN博客_单链表的定义
C语言的单链表的操作——插入和删除 - 知乎 (zhihu.com)
尾插法创建单链表：
该方法是从一个空表开始，读取数组的元素，生成新节点，将读取的数据放到存放在新节点的数据域中，然后将该节点插入到链表的表头上，直到结束为止。
思路：（尾插法）
1.先建立一个头结点，r始终指向尾结点，开始时指向头结点
2.通过循环读取数组的元素，生成新节点
其中，第一，数据域赋值 第二，指针域更换
意思为：将新生成的结点插入头结点后
需要定义： 一个指针s指向新生成的结点，一个指针r指向尾结点。定义循环变量i
3，最后将尾结点置为空 r->next = null;
(47条消息) 创建单链表的头插法与尾插法详解_Frank的博客-CSDN博客_头插法和尾插法
双链表 - 数据结构教程? (yiibai.com)
双链表：解决单链表无法逆向索引的问题
循坏单链表：从一个结点出发可以找到其他任何结点
循坏双链表：从头找到尾和从尾找到头时间复杂度都是O(1)
王道考研数据结构
栈
（stack）也称为堆栈。一种线性表数据结构，是一种只允许在表的一端进行插入和删除操作的线
性表。
我们把栈中允许插入和删除的一端称为「栈顶（top）」；另一端则称为「栈底（bottom）」。当表中没有任何数据元素时，称之为「空栈」。
堆栈有两种基本操作：「插入操作」和「删除操作」。
栈的插入操作又称为「入栈」或者「进栈」。栈的删除操作又称为「出栈」或者「退栈」。
简单来说，栈是一种 「后进先出（Last In First Out）」的线性表，简称为 「LIFO 结构」。
栈的定义：
1.线性表：栈中元素具有前驱后继的线性关系。栈中元素按照 a1, a2, ... , an 的次序依次进
栈。栈顶元素为 an。
2.后进先出：每次删除的总是堆栈中当前的栈顶元素，即最后进入堆栈的元素。而在进栈时，最先
进入堆栈的元素一定在栈底，最后进入堆栈的元素一定在栈顶。也就是说，元素进入堆栈或者退出退栈是按照「后进先出（Last In First Out）」的原则进行的。
栈的顺序存储与链式存储：栈有两种存储表示方法：「顺序栈」和 「链式栈」。
?「顺序栈」：即堆栈的顺序存储结构。利用一组地址连续的存储单元依次存放自栈底到栈顶的元素，同时使用指针 top 指示栈顶元素在顺序栈中的位置。
?「链式栈」：即堆栈的链式存储结构。利用单链表的方式来实现堆栈。栈中元素按照插入顺序依次插入到链表的第一个节点之前，并使用栈顶指针 top 指示栈顶元素，top 永远指向链表的头节点位置。
基本操作：
?初始化空栈：创建一个空栈，定义栈的大小 size，以及栈顶元素指针 top。
?判断栈是否为空：当堆栈为空时，返回 True。当堆栈不为空时，返回 False。一般只用于栈中删除操作和获取当前栈顶元素操作中。
?判断栈是否已满：当堆栈已满时，返回 True，当堆栈未满时，返回 False。一般只用于顺序栈中插入元素和获取当前栈顶元素操作中。
?插入元素（进栈、入栈）：相当于在线性表最后元素后面插入一个新的数据元素。并改变栈顶指针 top 的指向位置。
?删除元素（出栈、退栈）：相当于在线性表最后元素后面删除最后一个数据元素。并改变栈顶指针 top 的指向位置。
?获取栈顶元素：相当于获取线性表中最后一个数据元素。与插入元素、删除元素不同的是，该操作并不改变栈顶指针 top 的指向位置。
栈的顺序存储：借助于一个数组来描述堆栈的顺序存储结构
栈的链式存储：堆栈的顺序存储结构保留着顺序存储分配空间的固有缺陷，即在栈满或者其他需要重新调整存储空间时需要移动大量元素。为此，堆栈可以采用链式存储方式来实现。
栈的应用：
?使用栈可以很方便的保存和取用信息，因此长被用作算法和程序中的辅助存储结构，临时保存信息，供后面操作中使用。例如：操作系统中的函数调用栈，浏览器中的前进、后退功能。
?堆栈的后进先出规则，可以保证特定的存取顺序。例如：翻转一组元素的顺序、铁路列车车辆调度。
字符串
简称为串，由零个或多个字符组成的有限序列。s="a1a22a3.....an" 一般用双引号括起来
空串、子串、主串
字符串的比较操作：
字符串之间的大小取决于它们按顺序排列字符的前后顺序。比如字符串 str1 = "abc" 和 str2 = "acc"，它们的第一个字母都是 a，而第二个字母，由于字母 b 比字母 c 要靠前，所以 b < c，于是我们可以说 "abc" < "acd" ，也可以说 str1 < str2。字符串之间的比较是通过组成字符串的字符之间的「字符编码」来决定的。而字符编码指的是字符在对应字符集中的序号。
"abcde" > "abc"。
可以定义一个 strcmp 方法，并且规定：
?当 str1 < str2 时，strcmp 方法返回 -1。
?当 str1 == str2 时，strcmp 方法返回 0。
?当 str1 > str2 时，strcmp 方法返回 1。
字符串的字符编码：ASCII 编码，GB2312、GBK、GB18030 等中文编码标准
Unicode 编码最常用的就是 UTF-8 编码，UTF-8 编码把一个 Unicode 字符根据不同的数字大小编码成 1 ~ 6 个字节，常用的英文字母被编码成 1 个字节，汉字通常是 3 个字节。
字符串的存储结构：
跟线性表相同，分为「顺序存储结构」和「链式存储结构」。
字符串匹配：模式匹配，可以简单理解为，给定字符串 T 和 p，在主串 T 中寻找子串 p。主
串 T 又被称为「文本串」，子串 p 又被称为「模式串」。
「单模式串匹配问题」：给定一个文本串，再给个特定模式串，要求从文本串T找出特定模式串p的所有出现位置
三种算法：
1.基于前缀搜索方法：在搜索窗口内从前向后（沿着文本的正向）逐个读入文本字符，搜索窗口中文本和模式串的最长公共前缀
KMP算法
(47条消息) KMP算法—终于全部弄懂了_dark_cy的博客-CSDN博客_kmp算法
Shift-Or算法
shift-and,shift-or算法 - 多喝水还是好的 - 博客园 (cnblogs.com)
2.基于后缀搜索方法：在搜索窗口内从后向前（沿着文本的反向）逐个读入文本字符，搜索窗口中文本和模式串的最长公共后缀。使用这种搜索算法可以跳过一些文本字符，从而具有亚线性的平均时间复杂度。
BM算法(50条消息) 不用找了，学习BM算法，这篇就够了（思路+详注代码）_BoCong-Deng的博客-CSDN博客_bm算法
Horspool算法
串的模式匹配算法---Horspool - CobbLiu - 博客园 (cnblogs.com)
Sunday算法
(50条消息) 字符串匹配——Sunday算法_Switch的博客-CSDN博客_sunday算法
3.基于子串搜索方法：在搜索窗口内从后向前（沿着文本的反向）逐个读入文本字符，搜索满足「既是窗口中文本的后缀，也是模式串的子串」的最长字符串。与后缀搜索方法一样，使用这种搜索方法也具有亚线性的平均时间复杂度。这种方法的主要缺点在于需要识别模式串的所有子串，这是一个非常复杂的问题。
Rabin-Karp 算法（基于散列的子串搜索算法）
(50条消息) Rabin-Karp算法_胖哥的博客-CSDN博客_rabin-karp算法
BDM 算法：使用后缀自动机来搜索子串
BNDM 算法(50条消息) BNDM字符串匹配算法_Aiphis的博客-CSDN博客
BOM 算法 ：递归遍历、非递归遍历和层次遍历等
「多模式串匹配问题」
给定一个文本串，再给定一组模式串，找出文本串中模式串集合所有模式串出现的位置
Aho-Corasick算法纵览（AC自动机） - 知乎 (zhihu.com)
1.基于前缀搜索方法：AC自动机算法（在 KMP 算法 的基础上，与「字典树」结构相结合而诞生的）、Multiple Shift-And算法
2.基于后缀搜索方法：Set Horspool算法、Wu-Manber算法
3.基于子串搜索方法：Multiple BNDM算法、SBDM算法、SBOM算法
多模式串匹配算法大多使用一种基本的数据结构：字典树
单模式串朴素匹配算法：
Brute Force算法：暴力匹配算法/朴素匹配算法，效率低 最坏时间复杂度O（m*n），平均复杂度O（m+n） 每轮m次字符对比，n长度
KMP匹配算法：利用匹配失败后的信息：主串的某一个子串等于模式串的某一个前缀KMP算法（快速模式匹配算法）C语言详解 (biancheng.net)
树
单链表：一个数据域+一个指针域
树：一个数据域+多个指针域
树是N（N>=0）个节点的有限集合。N=0时为空树，N>0时应满足：
1. 有且仅有一个特定的称为根的节点
2. N>1时，其余节点可分为m（m>0）个互不相交的有限集合。其中，每一个有限集合自身又
是一棵树
3. 树的相关概念
1. 根节点：非空树处于最上层的唯一节点，其余节点都是它的子孙后代
2. 节点的度：节点具有的孩子节点个数
3. 叶子节点：度为0的节点
4. 父子节点：直接相连的一对节点，处于上层的是父节点，处于下层的是子节点
5. 兄弟节点：由同一个父节点生出的不同节点互称兄弟节点
6. 节点层次：由根开始记为1层，其子节点为2层，孙子节点为3层……
7. 节点深度：节点所在的层次数
8. 树的深度/高度：树的最大层次数
9. 节点高度：以节点为根的子树的深度/高度
10. 有序树：以兄弟节点为根的子树交换位置得到的新树视作与原来的树不同的树
11. 无序树：以兄弟节点为根的子树交换位置得到的新树视作与原来的树相同的树
二叉树：一种每个节点度都不大于2的树。其中，每个节点的子节点有左右之分且左右
子节点所在的子树不可以交换位置，即二叉树是一棵有序树
特殊二叉树：
(1)满二叉树：所有叶子节点全部在最底层，且所有非叶子节点度都是2的树
(2)完全二叉树：记二叉树高度为h。从1开始，对二叉树从上到下，从左到右进行编号。对高度
同为h的满二叉树做同样的编号处理。如果二叉树中所有节点的编号都能与满二叉树中同样位置
的节点编号一致，则该二叉树是一棵完全二叉树
(3)二叉搜索树（BST）：二叉搜索树要么是空树，要么同时满足以下条件：
1. 左子树所有节点的关键字均小于根节点的关键字
2. 右子树所有节点的关键字均大于根节点的关键字
3. 左右子树也均为二叉搜索树
BST应用场景是存放有序数据，提升查找效率
(4)平衡二叉树（AVL）：如果二叉树中每个节点的左右子树高度差都不大于1，则这棵二叉树就
是平衡二叉树
平衡二叉树经典的应用场景就是与二叉搜索树结合，形成平衡二叉搜索树。在构建二叉搜索树
的同时借助调整策略使每个节点的左右子树高度差都不大于1，保证二叉搜素树中每个节点的
左右子树都规模相当，整个树看起来更加“匀称”
基本操作：
1.存储结构：顺序存储结构
2.链式存储结构
遍历：按照某种规则“访问”树中的每个节点，保证每个节点都会被“访问”到且每个节点只
会被“访问”一次
“访问”：程序与节点产生交互或者在节点进行某些操作
“进入”：程序来到了某个节点，并未与该节点产生任何交互
不同规则下，对同一个节点的“进入”次数可能有一次也可能有多次，但对同一个节点的“访
问”只会发生一次
二叉树的深度优先搜索DFS：
（1）必须以根节点为搜索起始节点并“进入”
（2）优先“进入”当前节点的左子节点，其次“进入”当前节点的右子节点
（3）如果当前节点为空节点或者左右子节点都被“进入”过，则再次“进入”父节点
先访问根，再访问左子树，最后访问右子树，即先序遍历
先访问左子树，再访问根，最后访问右子树，即中序遍历
先访问左子树，再访问右子树，最后访问根，即后序遍历
广度优先搜索BFS： 需要借助数据结构——队列
从根节点开始，按层次从上到下，同层次内从左到右“访问”每一个节点
也叫做层次遍历
每个节点只会“进入”一次
实现二叉树层次遍历的流程：
1. 初始化空队，将根节点入队
2. 当队列非空且队头元素非空时不断重复
以下操作：
（1）队头节点出队并设置为当前节点
（2）对当前节点进行“访问”
（3）如果当前节点左子节点存在则将左子节点入队
（4）如果当前节点右子节点存在则将右子节点入队
二进制技术的应用
计算机内部使用补码来表示
原码、反码和补码
按位非操作~ 按位与操作& 按位或操作 | 按位异操作^
异或操作满足交换律和结合律
按位左移操作<< 如： num<<i将num的二进制表示向左移动 i 位所得的值
按位右移操作>> 如： num<<i将num的二进制表示向右移动 i 位所得的值
双指针
