基础数据结构
什么是数据结构？
是计算机存储与组织数据的方式，是数据之间存在一种或多种特定关系的数据元素的集合
常见的数据结构的定义、原理、实现、应用
线性表
定义：一个具有n个数据元素的有限序列（同一个线性表所含数据元素类型一定是一致的）
常见的操作：创建/删除线性表、添加/删除个别/部分元素、合并两个线性表、将一个线性表拆分成两个线性表等
线性表的分类：按照相邻元素存储地址分可以分为顺序存储的线性表（数组）和链式存储的线性表（链表）
1.顺序存储（数组）定义：以连续地址按顺序存放数组中的元素 优点：可以随机的以时间复杂度位O(1)的效率得到某个指定位置存放的元素值 缺点：如果数组元素很多的情况下，在进行插入/删除元素的时候，需要移动大量的元素，效率低下。
注意：在添加元素的时候（特别是在数组中）一定要考虑到内存是否够用，因为一开始创建数组的时候一定已经确定了内存大小（数组容量）
2.链式存储（链表）--就是操作指针
定义：每个相邻的数组元素的存放地址可以连续也可以不连续，元素之间通过指针实现元素之间的关系排列 优点：可以以时间复杂度位O(1)的效率对线性表进行插入/删除元素，不需要移动大量的数据元素 缺点：不可以随机得到某个特定位置的元素值（即不能以O（1）的效率找到特定位置的元素值），每次查找元素值需要依次遍历链表才可找到！
在对链表进行一系列操作的时候，需要注意以下几点：
1、一般都会自定义个一个头结点，其作用是避免出现对原本链表的第一个节点进行操作导致需要分类讨论的情况
2、对于链表中，一定要先判断对应节点是否为空节点以后才可以继续查看其/其之后即诶单的指针/数据，否则会出错！
栈和队列
- 栈
定义：特殊的线性表，特殊性在于栈的操作是线性表操作的子集，是操作受限的线性表，只能在栈顶（表尾）进行数据的插入/删除，对应的栈底（表头）==》数据的进栈/出栈遵循先进后出，后进先出的原则
** 注意：对于数据出栈操作，一定要考虑到栈是否为空栈，否则会容易出错！ **
常用的函数：（stack<type> s）
s.empty()==>查看栈是否为空 s.size()==>查看栈里面有多少数据 s.top() ==>得到栈顶的元素值 s.push(val)==>在栈顶位置插入数据 s.pop()==>在栈顶位置移除数据
栈的常见应用
- 数值转换（如十进制转换成二进制）
- 括号匹配检验（遇到(放入栈中，遇到)查看栈顶位置元素是否为(）
- 表达式求值（利用两个栈，一个栈用来存放数据，另外一个栈用来存放运算符，需要注意的有1、注意出现（）的情况，需要优先处理2、遇到运算符比栈顶运算符优先级别低的情况，需要先运算以后再放入对应运算符）
- 队列
定义：特殊的线性表，特殊性在于栈的操作是线性表操作的子集，是操作受限的线性表，只能在队头将数据出队列，队尾将数据插入队列==》数据的进队列/出队列遵循先进先出的原则
** 注意：对于数据出队列操作，一定要考虑到队列是否为空，否则会容易出错！ **
常用的函数：（queue<type> q）
q.empty()==>查看队列是否为空 q.size()==>查看队列里面有多少数据 q.front() ==>得到队头的元素值 q.back()==>得到队尾的元素值 q.push(val)==>队尾位置插入数据 q.pop()==>在队头位置移除数据
循环队列
是在顺序存储结构的基础上进行分析，如下图所示：rear指向下一个能够存放数据的地址，front指向当前最先存放的元素地址，在连续存储结构中，本着先进先出的原则，每次将数据入队列，rear+1，指向下一个可以存放数据的地址，如果需要数据出队列的话，则将指向队头的指针front+1，指向当前存放最久的元素。===》这样会出现一个问题：一开始指定大小区域分配给队列以后，当rear指针到达最后区域的时候无法再进行数据添加，需要重新申请内存，但是往往很多时候并不是说这一块区域不能存放数据了，它的下面front下面区域是空的，实际可用的资源并未占满，这样会导致资源的浪费
因为上述原因，所以我们引入循环队列。如下图所示，当然，我们判断空间是空的还是已经满了，完全可以设置标志位/利用双指针来查看，如我们申请一个队列空间，rear在这里表示指向队尾元素的指针，front表示指向队头元素的指针，front==rear==0==base（队列的首地址），当front==rear的时候，表示是空的，如果是（rear+1）%maxsize==front，那么就代表队列空间占满了，否则表示还可以存放。
字符串
注意点：字符串默认的都是以'\0'字符结束的！
其中需要注意的kMP算法：（时间复杂度是O(n+m)）（暴力法的时间复杂度：O（nm））
KMP原理讲解
总结：
前提：我们假设模型子串第一个字符位置是从1开始的
从分析上看，除了与主串第一个字符进行比较以外（如果模型子串与主串的第一个字符不匹配，模型子串第一个字符与主串的下一个字符进行比较，直到找到匹配的/主串中不存在该子串为止），其余模型子串位置我们完全可以将每一趟所要进行的步骤归于以下几点：
1、找寻最长公共前后缀长度（0<=该长度<n(这个n指的是进行比较位置之前的模型子串长度)）
注意：这里的前后缀可以理解为指的是可以实现对称的子串部分
2、主串对应字符位置不变，从模型子串的最长公共前后缀长度+1位置开始与主串字符位置进行比较，直到最终找到/剩下的原子串长度小于模型子串长度为止======每一趟将前缀子串移动到后缀子串上，然后在此基础上继续进行比较。
如下图所示：
然后与模型字符串下标对应起来看，如下图所示：
当模型字符串的某个位置发生不匹配，我们可以知道下一步从哪里开始比较==》next数组
再规律性强一点的总结：（对应的是模型子串字符的位置所对应的next数组，模型子串第一个字符从0开始计算）
那么问题来了，如何求next数组中的每一位值呢？
next数组的值结合代码分析
可以结合上图来分析，编写对应的代码，求出最长前后缀的长度并赋值给对应next数组位置,对于next数组，我们只需要观察模型子串即可！
编写代码需要注意的以下几点：(i表示后缀的位置，j表示前缀的位置)
1、前后缀一定是在子串的两端==>每次前后缀位置字符相等的时候，只需要将i++，j++，继续下一趟比较即可，判断当前最长前后缀长度
2、每次前后缀的位置字符比较不等的情况下，一定是前缀发生回溯（就是前后缀匹配长度发生变化，变短，再次比较），这个前缀回溯的位置根据next[j]来定
3、模型子串第一个字符位置从1开始计算，0的位置我们一般存放的是模型子串的长度
对应的代码如下：
void get_nextarray(string &T，int next[])
{
int n=T[0];
next[1]=0;
int i=1,j=0;
while(i<n)
{
if(j==0||T[i]==T[j])
{
i++;
j++;
next[i]=j;//对应字符位置的如果出现与主串不匹配的情况，跳转的位置一定是最长前后缀长度+1
}
else
{
j=next[j];//j发生回溯，前后缀长度发生变化
}
}
}我们得到next数组以后，就可以于主串进行匹配计算，查看主串中是否包含模型子串,完整代码如下：
//
// main.cpp
// kmp
//
// Created by ABCDEFG. on 2020/6/1.
// Copyright © 2020 ABCDEFG. All rights reserved.
//
#include <iostream>
#include <string>
#include "vector"
#include "algorithm"
using namespace std;
void get_nextarray(string T,vector<int> next)
{
int n=T[0]-'0';
n++;
next[1]=0;
int i=1,j=0;
while(i<n)
{
if(j==0||T[i]==T[j])
{
i++;
j++;
next[i]=j;//对应字符位置的如果出现与主串不匹配的情况，跳转的位置一定是最长前后缀长度+1
}
else
{
j=next[j];//j发生回溯，前后缀长度发生变化
}
}
}
bool judge_include(string S,string T)
{
if(S==""&&T=="")
return true;
if(S==""||T=="")
return false;
int n=T[0]-'0';
vector<int> next(n+1,0);
get_nextarray(T,next);//得到next数组
auto len=S.size();
int i=0,j=0;//i表示遍历主串，j表示遍历模型子串
while(i<len&&j<=T.size() ) //模型子串第一个字符对应位置是1，主串第一个字符对应的位置是0
{
if(S[i]==T[j])
{
i++;
j++;
}
if(S[i]!=T[j])
{
j=next[j];
}
}
if(j==T.size()+1)
return true;
else
return false;
}
int main(int argc, const char * argv[])
{
string str="ABAAAAA";
string moudle="2AB";//模型子串第0个位置s表示的是模型子串的长度
bool flag=judge_include(str,moudle);
cout<<flag<<endl;
return 0;
}
树
一些术语的定义：
- 度：每个节点的子节点个数
- 叶子结点：度为0的结点
- 祖先：从根节点到该节点上所经历的所有节点（包含双亲）
一些二叉树常见的类型的定义及结构体使用
二叉树的定义：空树/每个节点的子节点数不超过2的有序树。
- 二叉搜索树：空树/每个节点如果存在左子树，其左子树的值小于该节点的值+如果存在右子树，每个节点右子树的值大于该节点的值
特点：即具有二分法的查找效率，又具有链表的随机插入删除元素的灵活性！
如果需要删除二叉搜索树上的某个节点：
- 删除叶子结点的情况
直接删除结点即可 - 删除含有一个子树的结点的情况
直接用下一个结点（左/右结点）替换该节点即可 - 删除含有两个子树的结点的情况
我们可以通过调用中序遍历后的该结点的后继结点来替换该节点位置，其余不变，来实现变动后仍然是二叉搜索树的目的。
- 平衡二叉树（AVL）：空树/每个节点的左子树深度-对应节点的右子树深度的绝对值不超过1
- 满二叉树：空树/每个节点的子节点都有2个。
- 完全二叉树：空树/每个节点的左子树深度==/==对应节点的右子树深度的（+1）
树节点结构体的编写
struct TreeNode
{
int val;
TreeNode *Node;
TreeNode (int x) :val(x),Node(NULL){}
};常见的二叉树的遍历方法及对应代码（cpp版本）
哈希表（如数组就是典型的哈希表）
定义：可以通过关键词一次找到与之对应的哈希值的表，这种关键词与哈希地址一一对应的关系我们称为哈希函数，本质上是通过关键词找到哈希地址，从而获取对应地址上的信息！
===》哈希冲突：不同的关键词得到同一个哈希地址，我们称其为发生哈希冲突
对于冲突，我们只能尽可能的去减少，不可能做到完全的避免，原因是：地址范围有限关键词序列是可以很大的！
哈希函数的构造方法：
- 直接定址法：去关键词或者关键词的某个线性函数值为哈希地址
地址与关键词的集合大小有关，一般不会发生冲突，但也因此导致用的比较少，因为一般关键词集合很大，地址集合有限 - 数字分析法：取关键词中的若干位组成哈希地址
该方法的前提是已知哈希表中可能出现的关键词 - 平方取中法：取关键词平方以后的后几位作为哈希地址。
- 折叠法：将关键词分割成等位的几个部分（最后一部分可以不等位），然后将几个部分对应相加求叠加和（舍去进位），求出的叠加和即为哈希地址
处理冲突的方法：（本质上就是为发生冲突的关键词找到‘空’地址，以此来减少冲突）
1.开放定址法：Hi=（H（key）+di）MOD m；m为表长
1.1线性探测再散列：di=1，2，3，4......
1.2二次探测再散列：di=1^2,-1^2,2^2,-2^2,3^2,-3^2......
1.3伪随机探测再散列：di=伪随机数序列
2.再哈希法
Hi=RHi（key）;I=1,2,3,4....
发生冲突以后，利用再哈希法找寻不同的哈希地址，直到找到空地址/遍历全部哈希表为止，不容易产生“聚集”，但增加了计算时间
3.链地址法
将所有关键词为同一类的同义词（即关键词不同哈希地址为i即相同的的这类关键词称为同义词）插入到同一单链表中（一般需要保证关键词有序排列），将每一类关键词对应单链表的头指针放入哈希表第i个位置中。经常用于需要插入/删除的情况
4.建立一个公共溢出区：额外的创建一个溢出表，将发生冲突的所有关键词都填入溢出表，不用去管同义词得到的哈希地址是什么。
腾讯公司福利 444人发布
