数据结构与算法

算法性能分析

算法是对特定问题求解方法和步骤的一种描述，它是指令的有限序列。其中每个指令表示一个或多个操作。

算法特性：

有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
确定性：算法中的每一条指令必须要有确定的含义，没有二义性，在任何条件下，只有唯一的一条执行路径，即对于相同的输入只能得到相同的输出。
可行性：算法是可执行的，算法描述的操作可以通过已经实现的基本操作执行有限次来实现。
输入：一个算法有零个或多个输入。
输出：一个算法有一个或多个输出。

算法设计要求：

正确性
可读性
健壮性
高效性

算法效率：

时间效率：指的是算法所耗费的时间
空间效率：指的是算法执行过程中所耗费的存储空间。
注意：时间效率和空间效率有时候是矛盾的。

时间复杂度的渐进表示法

为了便于比较不同算法的时间效率，我们仅仅比较他们的数量级。

例如：两个不同的算法，时间消耗分别是：T1(n)=10n² 与T2(n)=5n³，显然T1时间效率要比T2的高。所以如果选择会选择T1算法
若有某个辅助函数f(n),使得当n趋近与无穷大时，T(n)/f(n)的极限值为不等于0的常数，则称f(n)是T(n)的同数量级函数。记作：T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度(O是数量级符号)，简称时间复杂度。f(n)就是算法中执行次数最多的语句的执行次数，n为问题规模
排序：n为排序数据量，矩阵：n为矩阵的阶数，多项式：n为多项式的项数，集合：n为元素个数，树：n为树的结点个数，图：n为图的顶点数或边数

时间复杂度的计算

基本方法：

找出语句频度最大的那条语句作为基本语句
计算基本语句的频度得到问题规模问题n的某个函数f(n)（级数求和的方式)
取其数量级用符号”O”表示

例题：

for(int i=1;i<=n;i++){
    for(int j=1;j<=i;j++){
        for(int k=1;k<=j;k++){   
            x=x+1;
        }
    }
}

$$
语句频度=\sum_{i=1}^{n}{\sum_{j=1}^{i}{\sum_{k=1}^{j}{1}}}
$$

算法时间复杂度比较：

常数阶O(1)<对数阶O(logn)<线性阶O(n)<线性对数阶O(nlogn)<平方阶O(n²)<k方阶O(n^k)<指数阶O(2ⁿ)<阶乘阶O(n!) k>2
对于复杂的算法，可以将它分为几个容易估算的部分，然后利用大O加法法则和乘法法则，计算算法的时间复杂度
- 加法法则：T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))
- 乘法法则：T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n)*g(n))

例题：若f(n)=a_mn^m+a_m-1n^m-1+…+a₁n+a₀是m次多项式，忽略所有低次幂项和最高次幂项的系数，体现出增长率的含义，则T(n)=O(n^m).

递归算法时间复杂度计算：

递归算法时间复杂度等于每次递归的时间复杂度*递归总次数(递归树的总节点数)

空间复杂度的渐进表示法

空间复杂度：算法所需存储空间的度量，记作：S(n)=O(f(n)),其中n为问题的规模(或大小)
算法要占据的空间
- 算法本身要占据的空间，输入/输出，指令，常数，变量等
- 算法要使用的辅助空间(临时存储空间)

例题:

【算法1】
for(i=0;i<n/2;i++){
    t=a[i];
    a[i]=a[n-i-1];
    a[n-i-1]=t;
}
S(n)=O(1),就一个t是临时存储空间变量
    
【算法2】
for(i=0;i<n;i++){
    b[i]=a[n-i-1];
}
for(i=0;i<n;i++){
    a[i]=b[i];
}
S(n)=O(n),因为a数组有多少元素，则临时存储空间b数组也需要多少元素，则空间复杂度应该就与n有关

算法

最大子序列和求解问题

暴力求解

直接利用嵌套循环将每次序列和求出来，并跟当前最大序列和比较，得出最大序列和，时间复杂度为O(n³)

代码：

//算法1，暴力求解,时间复杂度为O(N?)
int Maxsum(const int an[],int size){
    int maxsum=0;
    for(int i=0;i<size;i++){
        for(int j=i;j<size;j++){
            int thissum=0;
            for(int k=i;k<=j;k++){
                thissum+=an[k];
                if(thissum>maxsum){
                    maxsum=thissum;
                }
            }
        }
    }
    return maxsum;
}

微优化解法

将比较部分的循环优化成一个边加边比较的算法，比暴力解法减少一层循环，时间复杂度为O(n²)

代码：

//算法2，微优化，边算边比较，时间复杂度为O(N²)
int Maxsum1(const int an[],int size){
    int maxsum=0;
    for(int i=0;i<size;i++){
        int thissum=0;
        for(int j=i;j<size;j++){
            thissum+=an[j];
            if(thissum>maxsum){
                maxsum=thissum;
            }
        }
    }
    return maxsum;
}

分治法求解

分治法概念：

就是将复杂的问题分成小问题，然后解决小问题在通过处理将小问题的解法合并在一起成为大问题的解法。

最大子序列和的解法

最大子序列和可能出现在三处，分别是左半部、右半部或者跨越输入数据的中部，前两种情况可以递归求解，第三种情况的最大和可以通过求出前半部分的最大和(包含前半部分的最后一个元素)以及后半部分的最大和(包含后半部分的第一个元素)相加得到，前半部分和后半部分的最大和也可以通过进行分成相对应的前后半部分然后求解。该算法的时间复杂度将会降低到O(nlogn)

代码：

//算法3，分治法求解，时间复杂度为O(nlogn)
int max3(int maxleft,int maxright,int maxcenter){
    int maxsum;
    maxsum=maxleft>maxright?maxleft:maxright;
    maxsum=maxsum>maxcenter?maxsum:maxcenter;
    return maxsum;
}

int maxsubsum(const int an[],int left,int right){
    int maxleftsum,maxrightsum;
    if(left==right){
        return an[left];
    }
    int center=(left+right)>>1;
    maxleftsum= maxsubsum(an,left,center);
    maxrightsum= maxsubsum(an,center+1,right);
    int leftsum=0,maxleft=INT_MIN;
    for(int i=center;i>=left;i--){
        leftsum+=an[i];
        if(leftsum>maxleft){
            maxleft=leftsum;
        }
    }
    int rightsum=0,maxright=INT_MIN;
    for(int i=center+1;i<=right;i++){
        rightsum+=an[i];
        if(rightsum>maxright){
            maxright=rightsum;
        }
    }
    return max3(maxleftsum,maxrightsum,maxleft+maxright);
}

int Maxsum2(const int an[],int size){
    return maxsubsum(an,0,size-1);
}

贪心解法(最快最简单解法)

该解法也是一种边加边比较，但是它只有一层循环，它的本质就是通过每次相加然后在比较的同时，当他的当前sum不大于最大sum时，并且该sum<0则我们将它归0，这样进行求解序列和时，就能保证它能主动找到正数和，正数和是最有可能成为最大序列和的，该算法的时间复杂度为O(n)

代码：

//最简单最快算法，时间复杂度为O(N)
int Maxsum3(int an[],int size){
    int maxsum=INT_MIN,thissum=0;
    for(int i=0;i<size;i++){
        thissum+=an[i];
        if(thissum>maxsum){
            maxsum=thissum;
        }
        if(thissum<0){
            thissum=0;
        }
    }
    return maxsum;
}

//这个代码虽多，但比上面的节约了一些时间。
int Maxsum3(int nums[],int size){
    int maxsum=0,thissum=0,cnt=0,msum=0;
    for(int i=0;i<size;i++){
        if(nums[i]<0){
            if(cnt==0){
                mnum=nums[i];
            }else if(nums[i]>msum){
                msum=nums[i];
            }
            cnt++;
        }
    }
    for(int i=0;i<size;i++){
        thissum+=nums[i];
        if(thissum>maxsum){
            maxsum=thissum;
        }else if(thissum<0){
            thissum=0;
        }
    }
    if(cnt==size&&maxsum==0){
        maxsum=msum;
    }
    return maxsum;
}

二分查找

概念：

针对于已经预先排序好的数据，每次将数据进行对半查找，然后看它中间的数据是否是要找的，如果是就返回中间位置，不是就判断该数据是在前半部分还是后半部，然后在进而取其中部，看其是否找到，然后如果还没找到就一直重复操作，直到找到为止，该算法时间复杂度为O(logn)

代码：

int search(vector<int>& nums, int target) {
        int l=0,r=nums.size()-1;
        while(l<=r){
            int mid=(l+r)>>1;
            if(nums[mid]<target) l=mid+1;
            else if(nums[mid]>target) r=mid-1;
            else return mid;
        }
        return -1;
    }

闭区间：

以左边界为求解的判断状态

int search(vector<int>& nums, int target) {
        int l=0,r=nums.size()-1;
        while (l < r){
            int mid = (l + r + 1) >> 1;
            if (nums[mid]<=target) l = mid;
            else r = mid - 1;
        }
        return nums[l]!=target?-1:l;
    }

以右边界为求解的判断状态

//可以用lower_bound()函数代替
int search(vector<int>& nums, int target) {
        int l=0,r=nums.size()-1;
        while (l < r){
            int mid = (l + r) >> 1;
            if (nums[mid]>=target) r = mid;
            else l= mid+1;
        }
        return nums[r]!=target?-1:r;
    }

开区间：将闭区间代码中if判断中的等号去掉即可

欧几里德算法

概念：

用于求两个数的最大公约数(两个数都可以共同整除的最大数)，利用不断相互取余，直到其中一个余数为0，则最大公约数为不为0的余数，该算法的时间复杂度为O(logn)

代码：

unsigned int gcd(unsigned int M,unsigned int N){
    unsigned int Rem;
    while(N>0){
        Rem=M%N;
        M=N;
        N=Rem;
    }
    return M;
}

//递归版(简洁)
int gcd(int a,int b){
    return !b ? a:gcd(b,a%b);
}

快速幂算法

概念：

计算X^N的最常见的算法是使用N-1次乘法自乘，但是可以使用一种将利用分治思想跟递归结合的算法更好，效率更高。判断N是偶数还是奇数，如果是偶数的话，我们有X^N=X^N/2*X^N/2，如果为奇数，我们有X^N=X^(N-1)/2*X^(N-1)/2*X，然后在不断的递归并将N等于0和N等于1为递归的基准情形，当N等于1返回X，该算法的时间复杂度为O(logn)

代码：

递归：

long int Pow(long int X,long int N){
    if(N==0)
        return 1;
    if(N==1)
        return X;
    if(X%2==0){
        return Pow(X*X,N/2);
    }else{
        return Pow(X*X,N/2)*X;
    }
}

非递归：

//有些题目数字过大防止溢出会对结果取模
long long quickpow(long long a,long long b,int mod){
    long long res=1;
    if(b==0) return 1;
    while(b){
        //b为奇数
        if(b%2==1){
            res=res*a%mod;
        }
        b/=2;
        a=a*a%mod;
    }
    return res;
}

位运算加速：假设我们要求a的11次方那么他会分解成8+2+1，那如何将其分解成8+2+1的情况，我们可以将其转换成二进制，11的二进制为1011，11=1*2³+0*2²+1*¹+1*2⁰，这样我们每次取11的二进制的最后一位这样就能分解成8+2+1了。

long long quickpow(long long a,long long b,int mod){
    long long res=1;
    if(b==0) return 1;
    while(b){
        //b&1就可以等价于b%2==1，如果b为偶数b&1==0，为奇数b&1==1
        if(b&1){
            res=res*a%mod;
        }
        b>>=1;  //等价于b/=2
        a=a*a%mod;
    }
    return res;
}

素数筛

引言：

素数(质数)：除了1和自己本身之外，没有任何因子的数叫做素数(质数)

朴素筛法(优化版)

概念：

朴素筛法：是直接暴力枚举2到当前判断的数x(不包括)，然后看在这范围内是否存在因子，如果存在就不是素数，不存在就是素数，时间复杂度为O(n*n)
优化版：优化版是用到了一个数学性质进行优化，使其只需要判断2到sqrt(x)的范围内，是否存在x的因子即可，时间复杂度为O(n*sqrt(n))

数学性质：如果一个数x能够被一个大于1且小于等于sqrt(x)的整数整除，那么x必定能够被另一个大于1且大于sqrt(x)的整数整除。

#include <iostream>
using namespace std;

//朴素筛素数判断算法时间复杂度：O(n)
bool isprime1(int x){
    if(x==1) return false;
    if(x==2) return true;
    for(int i=2;i<x;++i){
        if(x%i==0) return false;
    }
    return true;
}

//优化版素数判断算法时间复杂度：O(sqrt(n))
bool isprime(int x){
    if(x==1) return false;
    if(x==2) return true;
    for(int i=2;i<=x/i;++i){
        if(x%i==0) return false;
    }
    return true;
}




int main() {
    //假设筛选出1-1000的素数
    for(int i=1;i<=1000;i+=2){
        if(isprime(i)) cout<<i<<endl;
    }
    system("pause");
    return 0;
}

欧拉筛(线性筛)

概念：

欧拉筛：利用合数的数学性质，可以将素数筛的算法优化到时间复杂度为O(n)

合数：除了1和自身之外还有其他正因子(除了 1 和自身以外的能够整除它的正整数)，并且大于1的整数

数学性质：对于任意一个合数 x，它一定可以被其最小质因数(即最小的能整除 x 的质数)整除

算法具体操作：

初始化一个标记数组vis[]和记录素数数组prime，vis所有元素初始化为false
从2遍历到n(要筛选素数范围)，如果vis[i]为false，则将i标记为素数，并将i记录在prime数组中，并将i的倍数j(j=i*i，i*i+i…)标记为合数(true)
遍历完所有的数后，prime数组中的数都为素数

总结：

在这个过程中，每个合数都会被标记为其最小质因数，这样能够确保每个合数只会被标记一次。由于每个合数只会被其最小质因数标记，因此在遍历过程中，每个合数只会被标记一次，而非多次，从而避免了重复标记，提高了效率。

const int N=1e8+10;
int prime[N];
bool vis[N];

//欧拉筛总体时间复杂度为O(n)
void isprimes(int n){
    int cnt=0;
    for(int i=2;i<=n;++i){
        if(!vis[i]) prime[cnt++]=i;
        for(int j=0;prime[j]<=n/i;++j){
            vis[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }
    }
}

排序算法

概念：

我们在的排序工作能在主存中完成的，我们就叫这种算法叫做内部排序
不能在主存中完成而必须在磁盘或磁带上完成的排序算法叫做外部排序

冒泡排序

概念：

冒泡排序是一个很简单的排序算法，冒泡排序是比较相邻的元素，如果第一个比第二个大，就交换他们两个，对每一对相邻元素做同样的工作，执行完毕后，找到第一个最大值，重复以上步骤，每次比较次数-1，直到不需要比较为止。
冒泡排序是一种每一轮排序遍历时，抛出当前遍历时的最大值来进行一个到最后升序的排序方法
冒泡排序的时间复杂度为O(n²)

注意事项：

冒泡排序的时间复杂度不是很好，有时候数据量大就应该考虑其他线性时间复杂度的排序算法

实现代码：

//比较相邻的元素，如果第一个比第二个大，就交换他们两个
//对每一对相邻元素做同样的工作，执行完毕后，找到第一个最大值
//重复以上步骤，每次比较次数-1，直到不需要比较


//冒泡排序,升序排序
void bubbleSort(int an[],int len){
    for(int i=0;i<len-1;i++){
        for(int j=0;j<len-1-i;j++){
            if(an[j]>an[j+1]){
                int temp=an[j+1];
                an[j+1]=an[j];
                an[j]=temp;
            }
        }
    }
}

插入排序

概念：

插入排序(insertsort)：插入排序是一个基于比较移动数据来实现有序化的算法，时间复杂度为O(N²)
插入排序根据元素的个数N进行N-1趟排序，从第一趟开始，在第P趟，我们将数组索引第P位的元素或者元素位于第P+1位置上的元素与该元素前面的所有元素进行比较，比较后找到该元素存在的对应位置进行移动或者叫做插入(不是交换)
第P趟结束，无序的数组或者数据则变成有序化了。

代码：

//插入排序
void insertsort(int *an,int len){
    for(int i=1;i<len;i++){
        int temp=an[i];
        int j;
        for(j=i;j>0&&an[j-1]>temp;j--){
            an[j]=an[j-1];
        }
        an[j]=temp;
    }
}

希尔排序

概念：

希尔排序(shellsort)是基于插入排序所优化的算法，该算法依靠增量序列来使到减少相邻元素交换排序的机会以及减少排序执行的趟次，这将比插入排序所花费的时间减少，即使希尔排序的时间复杂度也为O(N²)
关于增量序列h，我们将数组的所有元素，按照索引号i,i+h,i+2h….(在数组索引范围0-N-1之内)作为一个序列进行排序，而这个排序是按照序列内的索引号排序因此不会影响到其他索引号的排序，而形成增量序列的h的选取可以自定义，但是希尔建议使用h1=(N-1)/2,h2=h1/2直到hk=1的方式进行形成增量序列(但不是很好)。
例如：一个无序数组的元素有12个，则排序该数组需要三趟，h(根据数组最大索引号也就是11除以2取得h1)分别为5，2，1，因此在以5为增量的趟次中，0，5，10为一个序列并将对应号上的元素进行插入排序，1，6，11又为1个序列进行排序。

代码：

使用Sedgewick增量作为希尔排序序列的时间复杂度为O(N^7/6)

//希尔排序
void shellsort(int *an,int len){
    for(int i=(len-1)/2;i>0;i/=2){
        //插入排序
        for(int j=i;j<len;j++){
            int temp=an[j],k;
            //根据增量i进行分序列排序
            for(k=j;k>=i&&temp<an[k-i];k-=i){
                an[k]=an[k-i];
            }
            an[k]=temp;
        }
    }
}

//使用Sedgewick增量的希尔排序
void shellsort_pro(int* an,int len){
    /* 初始的增量Sedgewick[Si]不能超过待排序列长度 */
    int Sedgewick[] = {260609,146305,64769,36289,
                       16001,8929,3905,2161,929, 505,
                       209, 109, 41, 19, 5, 1, 0};
    int k;
    for(k=0;Sedgewick[k]>=len;k++);
    for(int d=Sedgewick[k];d>0;d=Sedgewick[++k]){
        for(int i=d;i<len;i++){
            int temp=an[i];
            int j;
            for(j=i;j>=d&&an[j-d]>temp;j-=d){
                an[j]=an[j-d];
            }
            an[j]=temp;
        }
    }
}

堆排序

概念：

堆排序(heapsort)：是一个基于二叉堆的排序算法,但是他又跟二叉堆的不一样，二叉堆的数组索引为0的是个哑节点，但是堆排序是得从0开始的
堆排序的实现需要根据要实现顺序的方式，将无序的数组在原数组下重新构建成大根堆/小根堆数组，如果要实现升序，就需要构建成大根堆，实现降序，就需要构建成小根堆数组。构建完堆数组，然后以类似堆中操作删除最大元/最小元的方式，将数组实现有序。
构建堆(以升序为例)：我们需要拿取数组元素个数N，从(N-1)/2到0遍历(拿取堆中的根节点)，遍历时拿取该根节点的子节点中的最大值，如果最大值大于根节点，就进行根节点与该最大值交换，遍历完毕后就形成了大根堆
删除最大/最小元(以升序为例)：要实现升序，则需要拿取数组元素个数N并执行从N-1到1次的删除最大元操作，而最大元就是大根堆数组中的第一位元素，在遍历到索引号为i时，我们需要将最大元与数组索引号为N-i-1的元素进行交换，然后重新构建最大堆保证堆数组的第一位元素就是最大元，跟遍历完毕就得到升序的数组，反之就得到降序的数组。

代码：

#define leftchild(i) (2*(i)+1)    //定义宏函数，找到根节点的左孩子

//构建堆
void buildheap(int* an,int len,int index){
    int temp,child;
    for(temp=an[index];leftchild(index)<len;index=child){
        child=leftchild(index);
        if(child!=len-1&&an[child+1]>an[child]){
            child++;
        }
        if(an[child]>temp){
            an[index]=an[child];
        }else{
            break;
        }
    }
    an[index]=temp;
}

//堆排序
void heapsort(int* an,int len){
    for(int i=(len-1)/2;i>=0;i--){
        buildheap(an,len,i);
    }
    for(int i=len-1;i>0;i--){
        int temp=an[0];
        an[0]=an[i];
        an[i]=temp;
        buildheap(an,i,0);
    }
}

归并排序

概念：

归并排序(mergesort)：是基于递归和分治策略的排序算法，*其时间复杂度为O(nlogn)*，但是归并排序不利于主存内排序，因为合并数组需要线性附加内存，如果N很大，则需要的表很大。
归并算法是将一个无序要排序的数组，将其分半，然后用递归，将数组一次次分半，然后利用递归到最后一层也就是数组无法再分了，递归返回时，开辟一个新数组，就用合并的操作将其有序的放入新数组，最后递归完毕就会得到一个有序的数组了。

合并操作：

对于某一个合并操作来讲(以合成升序数组为例，两个数组前提是要有序的)，我们将数组分成了A，B两个数组(其实并没有分成两个，只是用lpos，rpos记录这两个数组在原来数组的起始位置)，用leftend，rightend记录两个数组结尾的数组索引，然后我们开辟一个能存下A和B数组两个数组元素的数组
然后，我们将lpos位置的元素跟rpos位置的元素比较，哪个小就放进tempos位置上的新数组temarr中，如果lpos位置小，则将lpos位置元素赋值到temarr中的tempos位置上，tempos和lpos++，然后lpos++完的位置上的元素再跟rpos比较，重复之前操作。
直到一个数组元素全部赋值完后，如果另一个数组还有剩下元素，则将剩下的数组赋值到temarr中，则合并操作就结束了。

代码：

//合并操作
void merge(int*an,int *temarr,int lpos,int rpos,int rightend){
    int leftend=rpos-1;
    int nums=(rightend-lpos)+1;
    int tempos=lpos;
    //进行比较lpos和rpos位上的元素
    while (lpos<=leftend&&rpos<=rightend){
        if(an[lpos]<an[rpos]){
            temarr[tempos++]=an[lpos++];
        }else{
            temarr[tempos++]=an[rpos++];
        }
    }
    while (lpos<=leftend){       //处理left数组的剩余元素
        temarr[tempos++]=an[lpos++];
    }
    while (rpos<=rightend){     //处理right数组的剩余元素
        temarr[tempos++]=an[rpos++];
    }
    //使用rightend保证给an数组赋值的正确位置
    for(int i=0;i<nums;i++,rightend--){
        an[rightend]=temarr[rightend];
    }
}


//递归分治调用
void midsort(int* an,int *temarr,int left,int right){
    if(left<right){
        int center=(left+right)/2;
        midsort(an,temarr,left,center);
        midsort(an,temarr,center+1,right);
        merge(an,temarr,left,center+1,right);
    }
}

//归并排序
void mergesort(int *an,int len){
    int *temarr=new int[len];
    midsort(an,temarr,0,len-1);
}

快速排序

概念：

**快速排序(quicksort)*：也是一种分治的递归算法，时间复杂度为O(nlogn)*，是实践中最快的已知排序算法
对数组S的快速排序的具体操作是：
1. 如果S中元素个数为0或1，则直接返回该数组
2. 取S中任一元素v，称之为枢纽元(pivot)
3. 将S-{v}(S中除去v的其余元素)分成两个不想交的集合：S₁={x∈S-{v}|x<=v}和S₂={x∈S-{v}|x>=v}.(这个操作就是分治操作，不断地递归取枢纽元将其分割为一个个小集合进行排序)
4. 返回{quicksort(S₁)后，继随v，继而quicksort(S₂)}
对于元素小于等于20的数组我们成为小数组，当数组为小数组时，快速排序不如插入排序好，这种情况下使用插入排序而不是使用递归的快速排序，将会节省大约15%的运行时间(相对于自始至终使用快速排序)

选取枢纽元：

随机选取法：一个比较安全的选取方法，通过使用随机数生成器进行随机产生枢纽元v，因为随机的枢纽元不可能总在接连不断地产生劣质的分割。但是随机数的生成时间比较长，无法降低算法的平均运行时间
三数中值分割法：一个比较好的选取方法，我们使用数组的左端、右端和中心位置上的三个元素的中间值(就是排序后第二大的元素)作为枢纽元v。使用该选取方法消除了预排序输入的坏情形，并且减少了快速排序大约5%的运行时间

分割策略：

当数组中的元素互异时，在分割阶段，我们将枢纽元跟数组最右端的元素进行交换，让枢纽元离开分区域内。我们需要将小于枢纽元和大于枢纽元的元素分布在区域的左右边。
利用i指向最左边的元素，j指向倒数第二个位置(也就是交换后枢纽元的左边位置)，如果i指向的元素小于枢纽元，i就向右移动，如果j指向的元素大于枢纽元，j就向左边移动，直到当i指向的位置不小于枢纽元，j指向的位置不大于枢纽元，就将i，j位置上的元素交换，但不交换i，j，交换完各自向右向左移动一位。
重复上述的操作，直到i和j交错，也就是当i在j的右边一位，j在i的左边一位的时候，不进行移动与交换，然后将枢纽元指向的元素和i所指的元素进行交换
对于i或者j指向元素跟枢纽元相等时，i和j停止移动进行交换位置上的元素，然后各自向右向左移动一位。

代码：

在实际操作中，我们在选取枢纽元的操作中，已经将left，center，right位置上的元素排好序了，而right位置上的元素本身就比枢纽元大，我们不直接交换center和right位置上的元素，而是交换center跟right-1上的元素，这样将会为后面根据枢纽元分割区域中少比较一位。优化了算法的性能

void insertsort(int* an,int low,int high){
    for(int i=low+1;i<=high;i++){
        int temp=an[i];
        int j;
        for(j=i;j>0&&an[j-1]>temp;j--){
            an[j]=an[j-1];
        }
        an[j]=temp;
    }
}

//三数中值分割法选取枢纽元
int midian3(int *an,int left,int right){
    int center=(left+right)/2;
    if(an[left]>an[center]){
        swap(an[left],an[center]);
    }
    if(an[left]>an[right]){
        swap(an[left],an[right]);
    }
    if(an[center]>an[right]){
        swap(an[center],an[right]);
    }
    //因为上述操作已经满足an[left]<an[center]<an[right]，an[right]大于枢纽元，我不需要进行交换让其在比较一位
    //因此让枢纽元跟right-1位置交换，这样在排序时减轻了右边数组的压力
    swap(an[center],an[right-1]);
    return an[right-1];   //返回枢纽元
}

void Qsort(int* an,int left,int right){
    if(left+10<=right){
        int pivot=midian3(an,left,right);
        int i=left,j=right-1;
        for(;;){
            while (an[++i]<pivot){}
            while (an[--j]>pivot){}
            if(i<j){
                swap(an[i],an[j]);
            }else{
                break;
            }
        }
        swap(an[i],an[right-1]);
        Qsort(an,left,i-1);
        Qsort(an,i+1,right);
    }
    else{
        insertsort(an,left,right);
    }
}

//快速排序
void quicksort(int *an,int len){
    Qsort(an,0,len-1);
}

另一种快速排序，每一次递归，我们将数组最左端就当作枢纽元，还是左端left开始跟right指向的元素跟枢纽元的值比较，an[left]<枢纽元left++，an[right]>枢纽元right–，直到找到an[left]>枢纽元，an[right]<枢纽元的时候进行交换an[left]和an[right]，直到left==right，就将枢纽元(也就是最左端的元素)与left当前所在位置进行交换，使得枢纽元放在正确的位置，然后在以left为界限分治。

void quicksort(int *an,int low,int high){
    int left=low,right=high;
    if(left<high) return;
    int temp=an[left];   //枢纽元
    while(left!=right){
        //找寻右边区域小于枢纽元的元素位置
        while(an[right]>=temp&&left<right){
            right--;
        }
        //找寻左边区域大于枢纽元的元素位置
        while(an[left]<=temp&&left<right){
            left++;
        }
        //将找到的进行交换使得左边区域小于枢纽元，右边区域大于枢纽元
        if(left<right){
            swap(an[left],an[right]);
        }
    }
    //将枢纽元换到正确的中间区域
    swap(an[low],an[left]);
    //以left也就是当前枢纽元所在位置为界限进行分治
    quicksort(an,low,left-1);
    quicksort(an,left+1,high);
}

桶式排序

概念:

桶排序(Bucket sort)：桶排序是一个非比较排序方法，它的排序是典型的用空间换时间的方法，它的时间复杂度甚至可能是线性复杂度(O(n))。如果我们有N个整数，数的大小范围为1~~M(或者0~~M-1),就可以根据数据大小范围创建一个空桶(可以看作数组)或者多个空桶，然后将数据分桶后，就可以将这些数据从头到尾输出，输出完就会发现数据已经排好序了！时间复杂度为O(M+N)

注意事项：

该类算法是典型的空间换时间，要注意空间的开销
该类算法排序的对象必须是整数，如果是浮点数和自定义类数据比较，就无法使用该类排序方法。
分完桶之后，排序的算法自行选择
分桶规则，根据数据自定义映射规则。

计数排序

概念：

假设要排序的数据为N个整数，数的大小范围为0~M-1,我们就创建一个空桶(数组)，数组的长度为该数据的最大值(将每一个元素看作是数组的下标,例如元素1就放在数组a[1]中)，数组的值全部初始化为0，然后利用循环如果出现一个元素，就将其对应数组的下标中的数据+1(例如有数据中1出现了两次，则a[1]==2)，然后再将根据排序方式将数组元素顺序/逆序打印，对应数组下标的值为多少就打印几次。该排序方法时间复杂度为*O(n)*。

注意事项：

元素一定要为整数且为正数！

代码：

//计数排序
void CountSort(int *an,int len) {
    int max=an[0];
    for(int i=0;i<len;i++){
        if(an[i]>max){
            max=an[i];
        }
    }
    int arr[max+1];
    memset(arr,0,sizeof(int)*(max+1));
    for(int i=0;i<len;i++){
        arr[an[i]]++;
    }
    int j=0;
    for(int i=0;i<max+1;i++){
        while (arr[i]>0){
            an[j]=i;
            arr[i]--;
            j++;
        }
    }
}

基数排序

概念：

当数据范围过大的时候，如果使用桶排序则需要创建的空桶太多了，因此我们使用多趟桶式排序—我们将会用最低(有效)位优先的方式进行桶式排序。
首先我们得先创建一个0-9的桶(线性表)，我们将会将数据分趟次(根据数据最大数的位次)排序，第一次就以每个数据的最低位排序依次放到其最低位对应的桶中，例如：数据231就放在数组a[2]中，然后再根据次低位进行第二趟排序，如果只有一位数的数据就根据第一趟排序的顺序依次放在第0位的桶中，然后如果还有百位的数据则就继续第三趟排序。
时间复杂度为O(n)

注意事项：

数据一定得是整数。
如果数据出现负数，则需要数组每个元素先加上最小值的绝对值，然后排序完后再减去最小值的绝对值就能实现负数也能排序。
该算法是基于计数排序的，所以会使用到计数排序的排序方法

代码：

void countsort(int *an,int len,int exp){
    int count[10]={0};  //计数数组
    int ret[len];  //结果数组
    for(int i=0;i<len;i++){
        count[(an[i]/exp)%10]++;
    }
    for(int i=1;i<10;i++){
        count[i]+=count[i-1];
    }
    //这个地方需要从尾遍历到头，因为如果从头遍历到尾时，我们就无法确定前面出现的数的正确位置！！！
    for(int i=len-1;i>=0;i--){
        ret[count[(an[i]/exp)%10]-1]=an[i];
        count[(an[i]/exp)%10]--;
    }
    for(int i=0;i<len;i++){
        an[i]=ret[i];
    }
}

void RadixSort(int *an,int len){
    int max=an[0];
    for(int i=1;i<len;i++){
        if(an[i]>max){
            max=an[i];
        }
    }
    //通过最大数的位数对数据分趟桶式排序
    for(int k=1;max/k>0;k*=10){
        countsort(an,len,k);
    }
}

能够对负数排序的改进基数排序代码：

//基数排序
void countsort(int *an,int len,int exp){
    int count[10]={0};  //计数数组
    int ret[len];  //结果数组
    for(int i=0;i<len;i++){
        count[(an[i]/exp)%10]++;
    }
    for(int i=1;i<10;i++){
        count[i]+=count[i-1];
    }
    //这个地方需要从尾遍历到头，因为如果从头遍历到尾时，我们就无法确定前面出现的数的正确位置！！！
    for(int i=len-1;i>=0;i--){
        ret[count[(an[i]/exp)%10]-1]=an[i];
        count[(an[i]/exp)%10]--;
    }
    for(int i=0;i<len;i++){
        an[i]=ret[i];
    }
}

void RadixSort(int *an,int len){
    int max=an[0];
    int min=an[0];
    for(int i=1;i<len;i++){
        if(an[i]>max){
            max=an[i];
        }
        if(an[i]<min){
            min=an[i];
        }
    }
    for(int i=0;i<len;i++){
        an[i]+=abs(min);
    }
    //根据位数进行分趟桶式排序
    for(int k=1;max/k>0;k*=10){
        countsort(an,len,k);
    }
    for(int i=0;i<len;i++){
        an[i]-=abs(min);
    }
}

图论算法

拓扑排序

概念：

拓扑排序是对有向无圈图的顶点的一种排序。排序不必是唯一的，任何合理的排序都是可以的。
具体做法是：先找出任意一个没有入边的顶点v(就是没有其他顶点指向的顶点)，将顶点v放入队列，然后将顶点v和它邻接的边从图中删除(其实就是将顶点v指向的顶点的入边数都-1，这样就可以代表删除边了)，然后用数组topnum来记录该顶点的排序位置。然后重复上述操作。顶点v的入度(indegree)为边(u,v)的条数。并用indegree数组来存储每个顶点的入度值。如果不存在入度为0的顶点，则该图是个有圈图。

代码：

struct listnode{
    int data;
    listnode* next;
};

class graph{
public:
    graph(int n){
        vnum=n;
        an=new listnode[n+1];
        indegree=(int*) malloc(sizeof(int)*(n+1));
        for(int i=0;i<n+1;i++){
            an[i].data=0;
            an[i].next= nullptr;
            indegree[i]=0;
        }
    }
    listnode* createNode(int data){
        auto p=new listnode;
        p->data=data;
        p->next= nullptr;
        return p;
    };
    void insert(int v,int data){
        auto add= createNode(data);
        if(an[v].next== nullptr){
            an[v].next=add;
        } else{
            listnode* p=an[v].next;
            while (p->next!= nullptr){
                p=p->next;
            }
            p->next=add;
        }
        indegree[data]++;
    }
    int findedgenull(){
        for(int i=1;i<=vnum;i++){
            if(indegree[i]==0){
                return i;
            }
        }
        return 0;
    }
    //拓扑排序
    void topsort(){
        queue<int>q;
        int v=findedgenull();
        if(v==0){
            cout<<"该图含有圈"<<endl;
            return;
        }else{
            q.push(v);
            if(q.empty()){
                cout<<"该图含有圈"<<endl;
                return;
            }
            while (!q.empty()){
                int w=q.front();
                cout<<w<<" ";
                q.pop();
                listnode* p=an[w].next;
                while (p!= nullptr){
                    if(--indegree[p->data]==0){
                        q.push(p->data);
                    }
                    p=p->next;
                }
            }
            cout<<endl;
        }
    }
private:
    listnode *an;
    int vnum;
    int *indegree;
};

最短路径算法

概念：

考查最短路径问题，可能会输入一个赋权图(也就是边带有权的图)，则一条路径的v1v2..vN的值就是对路径的边的权求和，这叫做赋权路径长，如果是无权路径长就是单纯的路径上的边数。
在赋权图，可能会出现负值边的情况，这样当我们去找最短路径时，可能会产生负值圈，毕竟一直走负值边可以将数值变得更短。

单源最短路径问题：

给定一个赋权图G=(V,E)和一个特定顶点s作为输入，找出从s到G中每一个其他顶点的最短赋权路径。

无权最短路径：

给定一个无权图G=(V,E)和一个起始顶点s作为输入，找出从s到G中每一个其他顶点的最短路径。

广度优先搜索算法(BFS)

概念：

广度优先搜索算法(BFS)用于在无权图或者边权相同的图中寻找最短路径。
该方法按层处理顶点，首先从起始点出发，进行发散找到与起始点邻接的顶点a,…，并将s到这些顶点的路径距离更新，然后将该点标记成已经访问的顶点并将该点的前一个顶点记录下来(被标记的顶点我们后面遇到就认为该点已经不需要再进行处理了)，然后再从顶点a,…发散，找到该顶点的邻接顶点，然后重复操作，直到所有顶点都被标记完，就完成了搜索。
具体代码实现，是用一个队列，在迭代开始时，队列中只含有距离为迭代距离currdist的那些顶点，然后执行操作时，将距离currdist+1的顶点的那些顶点添加到队列中，只要当前距离为currdist顶点处理完，就会处理距离为currdist+1(也就是当前顶点发散的顶点)的顶点添加到队列中。
在队列中其实可以将know域也就是标记去掉，因为队列的形式已经说明执行过了，就不会在执行，因此相当于标记了。

代码：

//图的邻接表的结点信息
struct listnode{
    int data;
    bool flag;    //判断是否访问过
    int path;     //存储上一个顶点
    int dist;     //距离
    listnode* next;
};

//图的信息
class graph{
private:
    listnode *an;   //邻接表形式存储图
    int vnum;     //图中结点数
};

//s为起点，an数组的邻接表表示图
void BFS(int s){
        queue<int>q;
        q.push(s);
        an[s].dist=0;
        while (!q.empty()){
            int v=q.front();
            q.pop();
            an[v].flag= true;
            listnode* p=an[v].next;
            while (p!= nullptr){
                if(an[p->data].dist==INT_MAX){
                    an[p->data].dist=an[v].dist+1;
                    an[p->data].path=v;
                    q.push(p->data);
                }
                p=p->next;
            }
        }
    }

Dijkstra算法

概念：

用于求解赋权图的最短路径(无负值边)，Dijkstra算法是解决单源最短路径问题的一般方法，并且该解法是贪心算法。Dijkstra只是BFS的升级版使他能够求赋权图的最短路径，如果求无权图Dijkstra跟BFS的做法一样！
Dijkstra算法是分阶段的，该算法认为每一个阶段，都将该阶段当作最好的情况处理，类似于BFS算法，但是还是有不同的地方，比起BFS多出了需要进行每个阶段出现最好情况就进行更新路径。
具体做法是，从图中选取起始点v，然后找出邻接点，并将当前起始点到邻接点v3,v4…的距离更新，如果是赋权图就是dv+C_v,v3(就是顶点v到v3的权)，如果是无权就是dv+1，并将v标记为已知。然后选取邻接点集中的一点再做为起始点，然后重复操作，将当前顶点的前一个顶点记录。当v到某个顶点的距离在当前阶段是最小的(最好情况)，那么就进行更新，如果不是就无需更新。
具体来说，当我们扩展一个新结点时，我们会考虑它的所有未访问过的邻接结点，并计算从起始结点经过当前结点到达邻接结点的路径长度。如果这个长度小于已知的最短路径长度（或者邻接结点的路径长度尚未初始化），我们就更新邻接结点的路径长度。这样做的目的是通过不断更新路径长度来找到起始结点到所有其他结点的最短路径。
实现的时候可以使用优先队列来进行优化算法，只将顶点和其最短路径值进入队列中当队列非空，执行以下操作：u等于队顶的节点，w等于队顶节点的最短路径值；遍历u的所有边，如果能找到节点v最短路径值小于v的当前值，更新v，将v压入队列。结束
没有用优先队列优化的Dijkstra算法的时间复杂度为O(N²)，如果使用优先队列，则**时间复杂度为O(nlogn)**，可以不用考虑已知域;

Dijkstra跟BFS区别：

处理顶点：
- 在BFS算法中，当一个顶点被扩展时，它的所有未访问过的邻居顶点都被添加到队列中，这样它们将按照遍历的顺序逐个被访问。
- 在Dijkstra算法中，当一个顶点被扩展时，它的邻居顶点也被考虑，但是Dijkstra算法会计算扩展的顶点与其邻居之间的边的权重，并根据这个权重来更新到达邻居顶点的最短路径长度。这个更新过程使得Dijkstra算法能够处理带有非负权重的图。
选择下一个顶点：
- 在BFS算法中，下一个要被扩展的顶点是队列中的下一个顶点，也就是按照队列的先进先出（FIFO）原则选择。
- 在Dijkstra算法中，下一个要被扩展的顶点是距离起始点路径长度最小的顶点，也就是根据已知的最短路径长度来选择。这需要使用优先队列或者最小堆来高效地选择路径长度最小的顶点。

代码：

//图的邻接表的结点信息
struct listnode{
    int data;
    int path;     //存储上一个顶点
    int dist;     //最短距离
    int weight;   //数组索引顶点跟该顶点的边的权重
    listnode* next;
};

//图的信息
class graph{
private:
    listnode *an;   //邻接表形式存储图
    int vnum;     //图中结点数
};

//v是起始点
void Dijkstra(int v){
        an[v].dist=0;
        queue<int>q;
        q.push(v);
        while (!q.empty()){
            int w=q.front();
            q.pop();
            listnode* p=an[w].next;
            while (p!= nullptr){
                if(an[w].dist+p->weight<an[p->data].dist){
                    an[p->data].dist=an[w].dist+p->weight;
                    an[p->data].path=w;
                    q.push(p->data);
                }
                p=p->next;
            }
        }
    }

题目模板：
有向边单源最短路径问题

#include <bits/stdc++.h>
using namespace std;

const int INF=0x3f3f3f3f;

const int N=10;
int n;

struct edge {
    int v, w;
};

bool vis[N+1];

int dijkstra(int start, const vector<vector<edge>>& graph) {
    int minroad[n+1];
    memset(minroad,INF,sizeof minroad);
    minroad[start] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if(vis[u]) continue;
        vis[u]=true;
        for (const auto& edges : graph[u]) {
            int v = edges.v;
            int w = edges.w;

            if (minroad[u] + w < minroad[v]) {
                minroad[v] = minroad[u] + w;
                pq.push({minroad[v], v});
            }
        }
    }

    return minroad[n]!=INF?minroad[n]:-1;
}

int main() {
    int m, start;
    cin >> n >> m >> start;

    vector<vector<edge>> graph(n + 1);

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
    }

    cout<<dijkstra(start, graph)<<endl;
    system("pause");
    return 0;
}

Floyd算法

概念：

Floyd(弗洛伊德)算法是基于动态规划思想的算法，也称插点法，是全源最短路算法(全源就代表经过一次Floyd算法，每个点到各个点的最短路径都能算出来)
用于求任意一对顶点间的最短路径，此时图中的边的权值可以出现负数，但不能出现负环
时间复杂度为O(n³)，n为点个数

基本思想：

对于从i到j的弧，进行n次试探
首先考虑i，0，j是否存在，如果存在，则比较i，j和i，0，j的路径长度，去最短者进行更新i，j的最短路径
然后再添加顶点1，依次类推。

具体过程：

当一个图里有n个城市，求全源最短路径问题
定义城市k为从当前图拿出来，并重新插入图中的城市，城市i，城市j分别为当前源城市和目的城市。dist[i\][j]表示城市i到城市j的最短路径
假设当前图中没有城市k，我们将城市k重新插入到图中
我们需要判断城市i到城市j的最短路径是否要更新，则比较路径经过城市k和原来的路径长度进行比较，如果**经过城市k的路径长度更短，则更新dist[i][j]**，因此就为dist[i][j]=min(dist[i][k]+dist[k][j],dist[i][j])
因此对这个图**执行n次上述操作(也就是插点法)**，得出的dist二维数组就为全源的最短路径。

代码模板：

//dist[n][n]用来记录图中各点到各点的最短路径
void Floyd(int **dist){
    for(int k=0;k<n;++k){
        for(int i=0;i<n;++i){
            for(int j=0;j<n;++j){
                if(dist[i][k]+dist[k][j]<dist[i][j]){
                    dist[i][j]=dist[i][k]+dist[k][j];
                }
            }
        }
    }
}

例题部分代码：

具体可看力扣1334. 阈值距离内邻居最少的城市，只包含求解全源最短路径代码

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;


void Floyd(int n, vector<vector<int>>& edges){
    const int INF=0x3f3f3f3f;
    int dist[n][n];
    memset(dist,INF, sizeof(dist));
    for(int i=0;i<n;++i){
        dist[i][i]=0;
    }
    for(auto edge:edges){
        dist[edge[0]][edge[1]]=edge[2];
        dist[edge[1]][edge[0]]=edge[2];
    }

    //Floyd算法计算全源最短路代码
    for(int k=0;k<n;++k){
        for(int i=0;i<n;++i){
            for(int j=0;j<n;++j){
                if(dist[i][k]+dist[k][j]<dist[i][j]){
                    dist[i][j]=dist[i][k]+dist[k][j];
                }
            }
        }
    }
    for(int i=0;i<n;++i){
        cout<<"第"<<i<<"城市到其他城市最短路径：";
        for(int j=0;j<n;++j)
            cout<<"("<<i<<","<<j<<","<<dist[i][j]<<")"<<" ";
        cout<<endl;
    }
}


int main() {
    vector<vector<int>>edges{{0,1,2},{0,4,8},{1,2,3},{1,4,2},{2,3,1},{3,4,1}};
    Floyd(5,edges);
    system("pause");
    return 0;
}

最小生成树

概念：

最小生成树是一颗连接图G所有顶点的边构成的一颗权最小的树，最小生成树一般是在无向图中寻找。
最小生成树**共有N-1条边(N为顶点数)**。

算法：

Prim算法

概念：

Prim(普里姆)算法是生成最小生成树的一种算法，该算法基本上和求最短路径的Dijkstra算法一样
具体操作：选取一个顶点作为树的根节点v1，然后从这个顶点发散，找到其邻接顶点(加入队列中)，然后选取根节点到邻接顶点中权最小的路径(也就是连接该路径的另一个顶点)进行添加到树中(也将连接的顶点除去v1的顶点的邻接顶点加入队列中)，然后初步形成一个图为u，然后再按顺序的查找图u与队列中的顶点的最小路径并加入树中，重复操作。
最小生成树信息打印，打印树中边的顶点对组。

实现代码：

使用优先队列

void Prim(int v){
        an[v].dist=0;
        //使用优先队列,定义参数<数据类型，容器类型，比较方法>
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
        //pair<int,int>对组的第一个为权，第二个为顶点。
        q.push(make_pair(0,v));
        while (!q.empty()){
            int w=q.top().second;
            q.pop();
            listnode* p=an[w].next;
            if(an[w].flag) continue;
            while (p!= nullptr){
                //选取最小权的边而不是顶点到顶点的最短距离
                if(p->weight<an[p->data].dist&&!an[p->data].flag){
                    an[p->data].dist=p->weight;
                    an[p->data].path=w;
                    q.push(make_pair(p->weight,p->data));
                }
                p=p->next;
            }
            an[w].flag= true;
        }
        int w=0;     //记录最小生成树的总权
        for(int i=1;i<=vnum;i++){
            if(an[i].path!=0){
                if(i>an[i].path)
                    cout<<"("<<an[i].path<<","<<i<<")"<<" 权:"<<an[i].dist<<endl;
                else
                    cout<<"("<<i<<","<<an[i].path<<")"<<" 权:"<<an[i].dist<<endl;
                w+=an[i].dist;
            }
        }
        cout<<"总权:"<<w;
        cout<<endl;
    }

使用vector容器模拟优先队列

struct edge{
    int v;    //顶点
    int weight;   //权
};
static bool cmp(const edge &a,const edge &b){
        return b.weight<a.weight;
    }
    void Prim(int v){
        an[v].dist=0;
        vector<edge>q;
        q.push_back({v,0});
        while (!q.empty()){
            sort(q.begin(),q.end(),cmp);
            int w=q.back().v;
            q.pop_back();
            listnode* p=an[w].next;
            if(an[w].flag) continue;
            while (p!= nullptr){
                //选取最小权的边而不是顶点到顶点的最短距离
                if(p->weight<an[p->data].dist&&!an[p->data].flag){
                    an[p->data].dist=p->weight;
                    an[p->data].path=w;
                    q.push_back({p->data,p->weight});
                }
                p=p->next;
            }
            an[w].flag= true;
        }
        int w=0;     //记录最小生成树的总权
        for(int i=1;i<=vnum;i++){
            if(an[i].path!=0){
                if(i>an[i].path)
                    cout<<"("<<an[i].path<<","<<i<<")"<<" 权:"<<an[i].dist<<endl;
                else
                    cout<<"("<<i<<","<<an[i].path<<")"<<" 权:"<<an[i].dist<<endl;
                w+=an[i].dist;
            }
        }
        cout<<"总权:"<<w;
        cout<<endl;
    }

Kruskal算法

概念：

Kruskal(克鲁斯卡尔)算法是连续地按照最小的权选择边，并且当所选的边不产生圈时就把它作为最小生成树中的边。
该算法是在处理一个森林–树的集合。开始的时候，存在|V|棵单节点树，而添加一边则将两棵树合并成一颗树。当算法终止时，就只有一棵树，就是最小生成树。

并查集

并：合并，查：查询连通关系，集：形成集合，用于处理连通性问题。
并查集：集合中的元素组织成树的形式：

查找两个元素是否属于同一集合：所在树的根结点是否相同
合并两个集合——将一个集合的根结点作为另一个集合根结点的孩子

具体操作：

该算法是根据选取边来进行生成最小生成树，那么我们就将图的信息用一个边集结构表示，我们需要进行一个循环，循环条件就是当最小生成树的边达到N-1条时就退出(N为元素个数)，每次循环我们都需要选取最小权重的边，并且判断在树中加入这条边会不会形成圈，如果形成圈就不进行加入，直到树的边条数达到N-1就形成了最小生成树。
该算法的关键是判断在树中加入边会不会形成圈–也就是判断两个顶点是否位于两个连通分量，这就需要并查集的操作：在图中我们将每个顶点都当作一个集合，我们插入边的时候，直接判断这两个顶点是否处于一个集合中，如何是一个集合就不进行加入，如果不是一个集合，就需要将两个集合进行合并，那么这就需要一个存储每个节点的根(父亲)节点的数组parent。我们将parent每个连通分量(集合)进行初始化为-1，表示没有父亲。

实现代码：

struct edge{
    int u,v,w;  //u，v为顶点的，w为权重,u为起始点，v为终点
};

static bool cmp(const edge &a,const edge &b){
        return a.w<b.w;
    }
    int findroot(int v,int parent[]){
        int t=v;
        while (parent[t]>-1){    //查找该集合的根节点。
            t=parent[t];
        }
        return t;
    }
    void Kruskal(int v){
        vector<edge>q;
        //存储每个连通变量的父亲节点的数组
        int parent[vnum+1];
        int w=0;     //记录最小生成树的总权
        memset(parent,-1, sizeof(int)*(vnum+1));
        //生成边集数组。
        for(int i=1;i<=vnum;i++) {
            listnode *p = an[i].next;
            while (p != nullptr) {
                if(i<p->data)
                    q.push_back({i, p->data, p->weight});
                p = p->next;
            }
        }
        //进行排序将最小权边放入第一位。
        sort(q.begin(),q.end(), cmp);
        for(int i=0,num=0;num<vnum-1;i++){
            int v1=findroot(q[i].u,parent);
            int v2= findroot(q[i].v,parent);
            //判断祖先节点是否相等--判断是否在一个集合.
            if(v1!=v2){
                cout<<"("<<q[i].u<<","<<q[i].v<<")"<<" 权:"<<q[i].w<<endl;
                w+=q[i].w;
                parent[v2]=v1;    //合并集合。
                num++;
            }
        }
        cout<<"总权:"<<w;
        cout<<endl;
    }

深度优先算法(DFS)

概念：

深度优先算法(DFS)跟BFS算法一样是用于遍历图的算法，但是DFS并不像BFS算法一样，它搜索出来的路径不具有最短性，并且dfs算法类似于枚举，因此**DFS算法一般用于求出问题的所有路径(例如全排列)**。
深度优先算法就是从起点出发，选择与其邻接的一条路径进行搜索，将该路径搜索完(没有路了或者是个回路)，再进行回退，重新选择其他路径搜索。这样就需要使用递归实现，而判断是否访问过顶点就需要一个bool类型的数组vis进行记录。
对于非强连通图，那么可能在某个节点开始的深度优先搜索可能访问不了所有的节点，在这种情况，我们选取某个未被访问的节点开始，再执行深度优先搜索。
dfs中最重要的算法思想是回溯和剪枝，dfs+回溯+剪枝也可以用于求解最短路径，但是BFS的时间复杂度更低。
1. 回溯是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
2. 剪枝，就是减小搜索树规模、尽早排除搜索树中不必要的分支的一种手段。形象地看，就好像剪掉了搜索树的枝条，故称之为“剪枝”

具体操作：

在访问图中某一起始点v后，由v出发，访问它的任一邻接点w1;
再从w1出发，访问与w1邻接但还未被访问过的顶点w2；
然后再从w2出发，进行类似的访问….
如此进行下去，直至到达所有的邻接顶点都被访问过的顶点u为止。
接着，退回一步，退到前一次刚访问过的顶点，看是否还有其他没有被访问的邻接顶点。
如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；
如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。

实现代码：

邻接矩阵表示图的算法实现

bool vis[g.vexnum];   //记录顶点访问信息，需要初始化为false

//图g为邻接矩阵类型，v为访问顶点
void dfs(Graph g,int v){
    cout<<v;
    vis[v]=true;
    //依次检查邻接矩阵v所在行。
    for(int w=0;w<g.vexnum;w++){
        //w是v的邻接点，如果w未访问，则递归调用dfs
        if(g.arcs[v][w]!=0&&!vis[w]){
            dfs(g,w);
        }
    }
}

邻接表表示图的算法实现

void DFS(int v){
        cout<<v;
        an[v].flag= true;
        listnode* p=an[v].next;
        while (p!= nullptr){
            if(!an[p->data].flag){
                DFS(p->data);
            }
            p=p->next;
        }
    }

双连通性

概念：

双连通性就是当删除图中的一个顶点，使图分割成两个图，则这个图就具有双连通性，而能导致图分割成多张图的顶点称为割点
背向边：当一个顶点被访问时，选取该顶点其中一个未访问过的邻接顶点进行访问，没被选取到的邻接顶点与当前顶点形成的边称为背向边

寻找割点：

从图中任一顶点开始，执行深度优先搜索并在顶点被访问时给它们编号。对于每一个顶点v我们称其先序编号为Num(v);
对于深度优先搜索生成树上的每一个顶点v，计算编号最低的顶点，我们称之为Low(v);对于求解每个顶点的Low，需要对深度优先生成树进行一次后序遍历算出，因为求出顶点v的Low的规则如下：
1. Num(v)
2. 所有背向边(v,w)中的最低Num(w)
3. 树的所有边(v,w)中的最低Low(w) –所以需要后序遍历
4. Low(v)等于前面三个变量中的最小值。
如果一个顶点v为割点，需要满足它的子节点w的Low(w)>=Num(v)

实现代码：

struct listnode{
    int data;     //num
    bool flag;    //判断是否访问过
    int parent;     //父节点
    int low;
    listnode* next;
};

int count=1;

void findart(int v){
        an[v].flag= true;
        an[v].low=an[v].data=count++;
        listnode* p=an[v].next;
        while (p!= nullptr){
            if(!an[p->data].flag){
                an[p->data].parent=v;
                findart(p->data);
                if(an[p->data].low>=an[v].data){
                    cout<<"V"<<v<<"为割点"<<endl;
                }
                an[v].low=min(an[v].low,an[p->data].low);
            }else if(an[v].parent!=p->data){
                an[v].low=min(an[v].low,an[p->data].data);
            }
            p=p->next;
        }
    }

图论技巧

超级源点/汇点

概念：

超级源点/汇点是模拟出来的虚拟点，多用于图中：
1. 同时有多个源点和多个汇点，建立超级源点和超级汇点
2. 同时有多个源点和一个汇点，建立超级源点
3. 同时有多个汇点和一个源点，建立超级汇点
总结：源点和汇点哪个有多个，就开哪个的超级点
介绍：我们平时所做的算法多是适用于一个源点到一个汇点或者是一个源点到多个汇点的类型，但是如果出现多个源点对应多个汇点时，我们会不知所措。跑多遍算法？那样会TLE，换个思维，既然是从多个源点出发到多个汇点，我们能不能建立一个点来代替多个源点/汇点的效果，而又不影响答案。

做法：

当我们具有多个源点和一个汇点，我们要求源点到汇点的最短路径，则可以建立一个超级源点，连接所有源点，并且路径长度为0，然后只需要跑超级源点到汇点这(n+1)个点的最短距离即可

例题：

ACWing 1488.最短距离

分析：

要求每次查询给出的村庄y到最近距离的商店的距离，对于每次查询，起点只有一个，汇点有多个，我们可以逆向思维，这样就变成商店作为源点，村庄y作为汇点，就变成了多个源点到单个汇点问题，这样我们创建一个超级源点，连接所有源点，并且路径长度为0，去跑dijkstra算法即可

#include <bits/stdc++.h>
using namespace std;
#define int long long

struct pii{
    int v,w;
};

struct edge{
    int d,u;
    bool operator>(const edge& other) const{
        return d>other.d;
    }
};


const int N=3e5+20;
const int INF=0x3f3f3f3f;
int n,m,k,q,a,b,c;
int dist[N];
bool vis[N];
vector<pii>g[N];

void dijkstra(){
    memset(dist,INF,sizeof dist);
    dist[0]=0;
    priority_queue<edge,vector<edge>,greater<edge>>pq;
    pq.push({0,0});
    while(!pq.empty()){
        edge p=pq.top();
        pq.pop();
        int u=p.u,d=p.d;
        if(vis[u]) continue;
        vis[u]=1;
        for(auto x:g[u]){
            int v=x.v,w=x.w;
            if(dist[v]>dist[u]+w){
                dist[v]=dist[u]+w;
                pq.push({dist[v],v});
            }
        }
    }
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    cin>>n>>m;
    while(m--){
        cin>>a>>b>>c;
        g[a].push_back({b,c});
        g[b].push_back({a,c});
    }
    cin>>k;
    while(k--){
        cin>>a;
        g[0].push_back({a,0});
    }
    dijkstra();
    cin>>q;
    while(q--){
        cin>>a;
        cout<<dist[a]<<endl;
    }
    system("pause");
    return 0;
}

贪心算法

概念：

贪心算法是一种思想，并不是一种算法，贪心算法是分阶段地工作，在每一个阶段，可以认为所作决定是好的，而不考虑将来地后果。
算法的每个阶段总是选择当前阶段最优，这种策略希望当算法终止时，能够将每一次的局部最优变成全局最优。

调度问题

概念：

调度问题就是安排一个完成任务的顺序使得全部任务完成的平均完成的时间能够最小化。

单个处理器

调度任务的方式我们一般使用非预占调度：一旦开始一个任务，就必须将这个任务运行到完成
调度问题一般都是最短任务最先进行，这样将会产生出每个阶段最优的调度，使得达到全局最优的调度。
操作系统调用程序一般把优先权赋予那些更短的任务。

多处理器：

如果我们有多个处理器，并且任务是有序的(按照最短时间排序)，这个时候的任务调度问题需要进行小部分的改变，但跟单个处理器的思想是一样的
假设我们有p个处理器，则我们选择前p个任务分配给各个处理器各一个，然后第p+1任务分配给第一个处理器，然后后面的就是按照这个规则分配。
第二个最优解，是将任务分组分配给各个处理器，且任务个数能整除处理器个数，是对于0<=i<N/p，p为处理器个数，N为任务总数，i为处理器序号，我们从任务i*p+1直到任务(i+1)*p的每个任务放到编号为i的处理器中。

Huffman编码

概念：

哈夫曼(Huffman)编码是一种压缩文件的编码，根据文件出现的字符使用一种将数据存在树叶上的二叉树来表示每个字符的二进制代码。
每个字符通过从根节点开始用0指示左分支用1表示右分支而以记录路径的方法表示出来。如果字符c_i在深度d_i处并且出现f_i次，那么该字符代码的值为对d_if_i的求和。
一个最优的哈夫曼编码是一种满二叉树：所有的节点或者是树叶，或者有两个子节点。
而贪心算法在这里就是根据字符出现的频率找出总价值最小的满二叉树，其中所有字符位于树叶。就是将出现次数少的放在深度深的地方(编码位数较多)，将出现最多放在最浅的地方(编码位数较少)
例如图10-9，字符a压缩后所表示的二进制代码为000

哈夫曼算法：

为了生成最优的哈夫曼编码树，哈夫曼提出了哈夫曼算法，这个算法也是使用了贪心的策略
假设字符个数为C，算法的描述如下：算法对一个由树组成的森林进行。一棵树的权等于它的树叶(字符)的频率的和。任意选取最小权的两棵树T1和T2，并任意形成以T1和T2为子树的新树，将这样的过程进行C-1次。在算法的开始，存在C课单节点树–每个字符一颗树。在算法结束时得到一棵树，这棵树就是最优哈夫曼编码树。

实现代码：

//树的结构体
struct tree{
    char data;   //存字符
    tree* left;
    tree* right;
    int weight;    //权重
};

//用来定义优先队列的比较规则
struct cmp{
    bool operator()(tree *a, const tree* b){
        return a->weight<b->weight;
    }
};

//需要将数据先存入优先队列中
priority_queue<tree*,vector<tree*>,cmp>pq;


tree* createNode(char data,int weight){
    tree* p=new tree;
    p->data=data;
    p->left= nullptr;
    p->right= nullptr;
    p->weight=weight;
    return p;
}

tree* merge(tree* &t1,tree* &t2){
    int n=t1->weight+t2->weight;
    tree* p= createNode(0,n);
    p->left=t1;
    p->right=t2;
    return p;
}

tree* Huffman(){
    tree* p;
    while (!pq.empty()){
        tree* t1=pq.top();
        pq.pop();
        tree* t2=pq.top();
        pq.pop();
        p=merge(t1,t2);
        pq.push(p);
    }
    return p;
}

分治算法

概念：

分治算法也是一种思想策略，分治算法就是将大问题不断地分成小问题解决后再重新构建原问题地解。一般地分治算法的时间复杂度为O(NlogN)
分：递归解决较小的问题；治：然后，从子问题的解构建原问题的解。分治算法中我们一直坚持子问题是不相交的(即基本不重叠)

选择问题

概念：

选择问题要求我们找出含N个元素的表S中的第k个最小的元素。
该问题的解法虽然使用了分治算法的策略，但是他在分之后只需要求解一个子问题，也不需要合并子问题求解，换句话来说，这个问题就是将大问题不断地分找到属于这个问题地解。

具体做法：

每次递归操作，选取一个枢纽元v，将集合S根据枢纽元分成S1，S2两个集合，S1的元素小于枢纽元，S2的元素大于枢纽元
如果k<=|S1| –|S1|为集合S1的元素个数，就递归集合S1求解集合S中的第k个最小元素。
如果k=|S1|+1，则枢纽元就是第k个最小元素。
否则，在S中的第k个最小元素是S2中的第(k-|S1|-1)个最小元素。

五分化中项法：

这也是一个选取枢纽元的方法，这个算法的性能更高

概念：

把N个元素分成向下取整(N/5)组，5个元素一组，忽略(最多4个)剩余的元素
找出每组的中项(中间值)，得到向下取整(N/5)个中项的表M
求出M的中项，将其作为枢纽元v返回

字符串算法

KMP算法

概念：

KMP算法是用于解决字符串匹配的问题的算法，也就是有一个文本串和一个模式串，求解这个模式串是否在文本串中出现或者匹配。
相对于暴力求解，KMP算法使用了前缀表来进行匹配，充分利用了之前匹配的字符，减少了重新匹配全部模式串的时间。
时间复杂度为O(m+n)，其中n为文本串长度，m为模式串长度。

前缀表：

例子：文本串：’aabaabaaf’ ，模式串：’aabaaf’

前缀表也就是记录模式串的各子串最长相等前后缀长度(即字符串的前缀和后缀相等并且长度最长)的数组，而在KMP算法中是对模式串求解前缀表
前缀：字符串除了尾字符的子字符串都是前缀，模式串的前缀有：a、aa、aab、aaba、aabaa
后缀： 字符串除了首字符的子字符串都是后缀，模式串的后缀有：f、af、aaf、baaf、abaaf
根据上述的例子可以列出表格：
这样就对应着：aabaaf 010120，这个就为前缀表，而前缀表在KMP算法中被称为next数组或者prefix数组。next的意思就是指通过这个数组可以知晓下一步指针会跳到哪一步。

求解next数组：

注：在遍历模式串的各个子串时，i为当前子串的后缀末尾索引，j为当前字串的前缀末尾索引并且为数组索引小于等于i之前的子串的最长相等前后缀长度。子串是连续的字符形成的

初始化：j初始化为0，因为模式串的第一个前缀子串为第一个字符，所以j索引指向0的位置，并且next[0]=0，i初始化为1，用一个循环从索引i开始遍历模式串。(因为只有一个字符的子串没有相等前后缀)
前后缀不相同情况：为了充分利用之前已经匹配的字符，我们将对发生冲突的地方也就是前后缀末尾字符不匹配的时候，我们将对前缀末尾索引进行回溯到索引为next[j-1]的位置。
前后缀相同情况：当前后缀末尾字符相等的时候，就可以将j++，不仅将当前子串更新到下一个子串，还更新了当前子串的最长相等前后缀长度也就是next[i]=j

实现代码:

void getnext(int *next,const string& s,int size){
    //初始化
    int j=0;
    next[0]=0;
    for(int i=1;i<size;i++){
        //前后缀不相等情况
        while (j>0&&s[i]!=s[j]){
            j=next[j-1];    //回溯找到相等位置或者回到0
        }
        //前后缀相同情况
        if(s[i]==s[j]) j++;
        next[i]=j;
    }
}

KMP具体操作：

求解next数组
然后利用求解next数组同等思路，求解文本串出现模式串位置的索引，求解next数组是模式串前后缀末尾字符的比较，而文本串模式串匹配过程，是文本串与模式串的字符比较过程。
当j也就是文本串在索引大于等于i之前的子串与模式串最长匹配字符长度等于模式串的长度，就说明文本串出现了模式串，然后返回文本串中出现模式串的第一个字符的索引值(i-j+1)。

KMP算法总体实现代码：

void getnext(int *next,const string& s,int size){
    //初始化
    int j=0;
    next[0]=0;
    for(int i=1;i<size;i++){
        //前后缀不相等情况
        while (j>0&&s[i]!=s[j]){
            j=next[j-1];    //回溯找到相等位置或者回到0
        }
        //前后缀相同情况
        if(s[i]==s[j]) j++;
        next[i]=j;
    }
}


int KMP(const string &text,const string &mode){
    int len=text.size();
    if(len==0) return 0;
    int size=mode.size();
    int j=0,next[size];
    getnext(next,mode,size);
    for(int i=0;i<len;i++){
        while (j>0&&text[i]!=mode[j]){
            j=next[j-1];
        }
        if(text[i]==mode[j]) j++;
        if(j==size) return (i-j+1);
    }
    return -1;    //未找到模式串
}

Manacher算法

概念：

Manacher算法是以线性时间复杂度来求解最长回文子串的相关问题
最长回文子串的相关问题的常见做法就是由中心扩展法和动态规划来解决，但是这两种算法的时间复杂度都需要O(n²)，其根本原因在于要对奇数偶数分别扩展两次以及对于回文半径内重复扩展问题
Manacher算法可以解决分别对奇数偶数进行扩展以及重复扩展问题，使得时间复杂度降为O(n)

最长回文子串问题：

回文是指逆序之后与原始字符串相等，例如(aba,abcba等等)
最长回文子串是一个字符串中所包含的最长的回文字符串，例如(abbbc的最长回文子串为bbb)

Manacher算法具体思想：

统一奇偶性：对于奇偶问题，Manacher算法的做法是将每个字符之间(空隙)插入一个’#’字符，这样就可以将奇偶问题统一成为奇数，避免了奇数和偶数两次扩展问题(例如：abbb –> #a#b#b#b#，abb –> #a#b#b#)
重复利用回文半径：利用已知的回文半径信息，以及回文子串对称的特性，避免重复计算。比方说，我有一个”abcbaeabcba…”的一个字符串，当前我已经计算出以字符’e’的回文半径为5,也就是”abcba e abcba”这样的回文子串，现在我求解到了右边字符’c’时，这个时候我们就没必要重复扩展了，而是利用回文半径中对称的左边字符’c’提供的回文半径
维护回文半径数组：既然我们需要利用到已经扩展好的信息，则我们就需要维护一个保存这些信息的数组，因此我们需要维护一个数组P，其中P[i]表示以字符i为中心的最长回文子串的半径 (不包括中心字符本身)

Manacher算法具体步骤：

统一奇偶性：对原字符串进行预处理，插入特殊字符’#’
简化边界判断：在预处理好后的字符串首部和末尾添加特殊字符，来简化边界判断，防止越界，我这里在首部添加”^”，末尾添加”$”符号
创建并初始化回文半径数组：创建回文半径数组p，设置回文中心c、回文覆盖最右边界r为0
计算回文半径：从前往后计算每个字符的回文半径的过程(计算回文半径还是使用中心扩展的方法进行计算)，分为以下几种情况，
1. 不在任何已经计算完成的回文串的回文半径范围内(i>r)，直接以当前位置i为中心进行扩散
2. 在一个已经计算完成的回文串的回文半径范围内(i<=r)
  - 在回文半径的最末端(i==r)，直接进行扩散
  - 前面对称位置的字符的回文半径L比较短(i+l<r)，也就是当前位置I加上L还是小于回文半径的最末端R，则当前位置的回文半径直接取L无需扩散
  - 前面对称位置的字符的回文半径L比较长(i+l>r)，也就是当前位置I加上L还是大于等于回文半径的最末端R，则利用中间计算结果，因此我们只需要从R+1开始扩散，则当前位置的回文半径为(r-i)+扩散结果
还原回文子串：通过得到的最大回文半径和中心点，我们可以得到回文子串在原字符串的起始索引((cidx-maxlen)/2)

算法模板：

// 进行预处理
string manacherss(const string& s){
    //添加"^"和末尾"$"简化边界判断
    string t="^#";
    for(char c:s){
        t+=c;
        t+="#";
    }
    t+="$";
    return t;
}

// 核心代码
string manacher(const string& str){
    string t= manacherss(str);
    int n=t.size();
    vector<int> p(n,0);
    // 回文中心点和最右边界
    int c=0,r=0;
    // 最长回文子串的回文半径和中心位置
    int maxlen=0,cidx=0;
    for(int i=1;i<n-1;++i){
        int mirror=2*c-i;   //i的对称位置计算(以中心点为对称轴)
        //i<r,有多种情况，i+l<r(l<r-i)则肯定取值为p[mirror],i+l>r(l>r-i)就肯定取值r-i作为初始值，然后通过while扩展得到当前p[i]
//        if(i<r) p[i]=min(r-i,p[mirror]);
        p[i]=(i<r)?min(r-i,p[mirror]):0;
        //尝试扩展回文子串
        while(t[i+p[i]+1]==t[i-p[i]-1]) ++p[i];
        // i+l>r，更新回文中心点位置和最右边界，这样保持i+l<r,然后在i<r中会让p[i]更新导致，扩展时是从r+1开始
        if(i+p[i]>r){
            c=i;
            r=i+p[i];
        }
        // 更新最大回文子串的回文半径和中心位置
        if(p[i]>maxlen){
            maxlen=p[i];
            cidx=i;
        }
    }
    // 根据中心和最大回文半径，提取原字符串中的回文子串
    int sidx=(cidx-maxlen)/2;
    return str.substr(sidx,maxlen);

}

例题：

力扣 5. 最长回文子串

// 模板题
class Solution {
public:
    string manacherss(const string& s){
        string t="^#";
        for(char c:s){
            t+=c;
            t+="#";
        }
        t+="$";
        return t;
    }
    string longestPalindrome(string s) {
        string t=manacherss(s);
        int n=t.size();
        vector<int> p(n,0);
        int c=0,r=0;
        int maxlen=0,cidx=0;
        for(int i=1;i<n-1;++i){
            int mirror=2*c-i;
            p[i]=(i<r)?min(r-i,p[mirror]):0;
            while(t[i+p[i]+1]==t[i-p[i]-1]) ++p[i];
            if(i+p[i]>r){
                c=i;
                r=i+p[i];
            }
            if(p[i]>maxlen){
                cidx=i;
                maxlen=p[i];
            }
        }
        int sidx=(cidx-maxlen)/2;
        return s.substr(sidx,maxlen);
    }
};

力扣 647. 回文子串：这题要求的并不是最长回文子串而是子串的个数，但是我们依然可以利用Manacher求解，因为当我知道一个最长回文字符串的长度可以推出它衍生的回文子串个数为(maxlen/2)

class Solution {
public:
    string manacherss(const string& s){
        string t="^#";
        for(char c:s){
            t+=c;
            t+="#";
        }
        t+="$";
        return t;
    }
    int countSubstrings(string s) {
        string t=manacherss(s);
        int n=t.size();
        int p[n];
        memset(p,0,sizeof(p));
        int c=0,r=0,res=0;
        for(int i=1;i<n-1;++i){
            int mirror=2*c-i;
            p[i]=(i<r)?min(r-i,p[mirror]):0;
            while(t[i+p[i]+1]==t[i-p[i]-1]) ++p[i];
            if(i+p[i]>r){
                c=i;
                r=i+p[i];
            }
            // 加上中心点才是回文字符串的长度
            res+=(p[i]+1)/2;
        }
        return res;
    }
};

最近公共祖先(LCA)

概念：

祖先节点：给定一棵多叉树，对于其中任意非根节点x，我们称从x的父节点到根节点的路径上的所有点为x的祖先节点
公共祖先：如果节点a同时是节点b和c的祖先，称a是b和c的公共祖先
最近公共祖先LCA:对于树上任意两点x和y，距离它们最近的公共祖先的节点就称为x和y的最近公共祖先(简称LCA)

朴素求解(暴力)

原理：我们只需要将x和y节点都升到同一深度或同一层，并让x和y同时向上走，直到x和y相等时，当前的x或y就是原先x和y节点的最近公共祖先

时间复杂度：最坏情况下，n为树上节点数，q为查询次数，则朴素求解的lca时间复杂度为O(q*n)

做法：

定义一个dep数组和p数组，分别用于存储树上节点的深度和每个树上节点的父节点
先用dfs预处理dep数组和p数组
对于每次查询，我们先判断dep[x]是否大于dep[y]，如果小于，则将x和y交换
将x上升到与y相同深度，也就是dep[x]==dep[y]的时候
然后令x和y一起上升，直到x==y，则x或y就是最近公共祖先，返回x或y

代码：

#include <bits/stdc++.h>
using namespace std;

const int N=5e5+20;
int n,m,s,a,b;  //n为节点数，m为查询次数，s为根节点编号,a和b用于临时存储节点的临时变量
int dep[N],p[N];
vector<int>g[N]; //存储边集

void dfs(int u,int d){
    dep[u]=d;
    int size=g[u].size();
    for(int i=0;i<size;++i){
        int v=g[u][i];
        if(v==p[u]) continue;
        p[v]=u;
        dfs(v,d+1);
    }
}

int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    while(dep[x]>dep[y]) x=p[x];
    while(x!=y){
        x=p[x];
        y=p[y];
    }
    return x;
}


int main() {
    cin>>n>>m>>s;
    for(int i=1;i<n;++i){
        cin>>a>>b;
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }
    dfs(s,0);
    while(m--){
        cin>>a>>b;
        cout<<lca(a,b)<<endl;
    }
    system("pause");
    return 0;
}

在线倍增算法

原理：

跟朴素求解一样的，我们也是需要将x和y置于同一深度，但是我们不再是简单的一个个去上升，而是利用倍增的思想，每次以2ⁱ(i∈[0,log2(dep[x]-dep[y])])的递增上升
同样的当x和y在同一深度上升时，也是利用倍增的递增上升，每次以2ⁱ(i∈[0,log2(dep[x])])的跨度递增，直到x和y相等
在线：就是输入数据，就直接通过计算得出结果

倍增：倍增就是递增速度是通过2^j(j=0,1,2,..)的速度递增的，一个倍增数组的元素f[i][j]，表示第i+2^j的元素

至于j为什么最大为log2(n+1)

解答：n为树上节点数，我们假设最坏情况为从根节点一直到最后一个节点x都是一条线连接，那最后一个节点x也必须能够通过倍增访问根节点，而倍增的速度是通过2^j(j=0,1,2,..)的速度递增的，因此最大的j就应该保证x+2^j等于根节点，因此我们发现根节点到x中间一共n-1(包括根节点)，因此最大的j要保证2^j=n-1，这样就可以得到最大的j=log2(n)+1了

做法：

定义一个dep[N]和f[N][log2(n+1)]，分别用于存储树上节点的深度、每个树上节点的父节点和存储每个节点i通过2^j(j=0,1,2,..log2(n)+1)的递增到达的节点
通过dfs预处理dep和f数组

预处理f数组时，假设当前节点为u，则将f[u][0]置为p[u](上升2的0次方就是上升一个，所以为父节点)，然后遍历递增倍数i从1到log2(dep[2])，然后将利用u的2ⁱ的祖先等于u的2^i-1的2^i-1祖先，也就是f[u][i]=f[f[u][i-1]][i-1]，得到当前节点u倍增到的各节点
对于每次查询，判断dep[x]是否大于dep[y]，如果小于，则将x和y交换
然后开始通过递增倍数i从log2(dep[x]-dep[y])到0的跨度递增，如果当前2ⁱ小于dep[x]-dep[y]，就让x上升到f[x][i]，让x与y深度相等
为啥i从log2(dep[x]-dep[y])到0，而不是从0开始

解答：
- 这是因为我们从0开始增加的跨度，很可能会使x的深度达不到y，为啥是达不到呢，因为我们需要判断当前dep[x]-dep[y]是否大于当前2ⁱ，如果从0开始就会产生x到dep[x]-dep[y]还有余数，而剩下的i太大，导致无法使用
- 至于为啥会有余数，我们可以从二进制进行证明，假设dep[x]-dep[y]=50，而50的二进制为110010，我们的i从log2(50)也就是5到0的过程中，假设当前i为5，2^5转为二进制就为100000，因此就将50中的最高位1消掉，假设当前i为3，此时的50只剩0010，而2^3为1000，0010<1000，所以不减，按照这种规则(如果2ⁱ大就不减，小就减)，50最终一定会变为0
- 而i从0开始递增，假设当前i=0，那相减，二进制就为110001，因为i是递增的，所以导致最低位的1一定会留下，就会产生余数，将这两种方法转换为10进制也是一样道理，50-32-16-2=0，而50-1-2-4-8-16=19，而19<32，导致无法继续减，所以可能导致x无法上升到y的高度
判断x是否等于y，如果等于，就返回x(这种情况就是y是x的祖先)
当dep[x]==dep[y]时，我们就可以让x和y同时倍增上升，按照步骤4的递增方法递增，当for循环中判断f[x][i]!=f[y][i]，如果不相等就让x和y一起上升到f[x][i]和f[y][i]，直到i=0时，根据4的性质证明，发现最后f[x][0]都会等于f[y][0]，所以i=0时，无法x和y无法上升，所以最后返回f[x][0]

代码：

#include <bits/stdc++.h>
using namespace std;

const int N=5e5+20;
int n,m,s,a,b;  //n为节点数，m为查询次数，s为根节点编号,a和b用于临时存储节点的临时变量
int dep[N],f[N][22]; //log2(N)算出来19，可以创建大于19的数组
vector<int>g[N]; //存储边集

void dfs(int u,int p,int d){
    dep[u]=d;
    f[u][0]=p;
    for(int i=1;i<=log2(dep[u]);++i){
        f[u][i]=f[f[u][i-1]][i-1];
    }
    int size=g[u].size();
    for(int i=0;i<size;++i){
        int v=g[u][i];
        if(v==p) continue;
        dfs(v,u,d+1);
    }
}



int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=log2(dep[x]-dep[y]);i>=0;--i){
        if((1<<i)<=dep[x]-dep[y]) x=f[x][i];
    }
    if(x==y) return x;
    for(int i=log2(dep[x]);i>=0;--i){
        if(f[x][i]!=f[y][i]){
            x=f[x][i];
            y=f[y][i];
        }
    }
    return f[x][0];
}


int main() {
    cin>>n>>m>>s;
    for(int i=1;i<n;++i){
        cin>>a>>b;
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }
    dfs(s,s,0);
    while(m--){
        cin>>a>>b;
        cout<<lca(a,b)<<endl;
    }
    system("pause");
    return 0;
}

动态规划(dp)

概念：

将递归算法重新写成非递归算法，让后者把那些子问题的答案系统地记录在一个表(dp数组)内，这种方法叫做动态规划
通常用于求解具有最优性质的问题(最优子结构&最优子问题)，希望找到具有最优值的解。
核心为穷举，动态规划问题往往具有最优子结构，重叠子问题和状态转移方程的特征。

基本思想：

适用于子问题不是独立的情况，也就是各子问题包含公共的子问题，鉴于会重复的求解各个子问题，对每个问题只求一遍，将其保存在一张表中，从而避免重复计算。

特征：

最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。
重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法利用这个子问题重叠性质，对每一个问题只解一次，而后将其解保存在一个表格(dp数组)中，在以后尽可能多地利用这些子问题的解。
**状态转移方程(最关键)**：
1. 是动态规划中本阶段的状态往往是上一阶段状态和上一阶段决策的结果。如果给定了第K阶段的状态Sk以及决策uk(Sk)，则第K+1阶段的状态Sk+1也就完全确定
2. 也就是递推方程，一个状态的解往往可以由前一个状态的解得出
3. 状态是由自己定义的通常可以认为是函数参数，dp数组的索引。
4. 状态转移就是从一个状态变成另一个状态，就例如本质为斐波那契数列的爬楼梯问题，从N-1阶或N-2的楼梯上到N阶的楼梯就称为状态转移.
5. 状态压缩：有时候并不需要保存所有状态，当保存的状态减少，导致算法的空间复杂度降低的技巧叫做状态压缩

能解决的问题：

计数
最值
存在性(是和否的问题，例如01背包)

解题步骤：

明确状态：也就是原问题和子问题中会变化的变量,状态的种数决定dp数组的维度。根据题意定义状态，这个状态可能是求解题目会变化的量，因为动态规划本质就是穷举，所以这个状态应该是穷举所有方案能够找到求解的目标
明确选择：也就是导致状态产生变化的行为。选择就是限制，当我们需要求解问题时，就需要不断地更新选择限制中的数据，来不断地产生多个方案，从而从中找到最优方案。
明确dp函数/数组的定义：就是求解的问题的函数，这个函数要求什么
base case：初始状态，根据题意找到初始状态，然后写出状态转移方程然后写出自顶向下或者自底向上递推的解法

分析问题：

先分析问题，用备忘录消除重叠子问题，写出自顶向下解法
进一步，可以写出自底向上解法
再进一步，可能可以优化空间复杂度

动态规划框架：

//初始化 base case
dp[0][0][...]=base;
//进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...]=求最值(选择1，选择2，...);

例子：

零钱兑换问题：

分析问题：

设F(n)为求解凑出目标金额为n的最少硬币数，通过分析问题，求解目标金额为n的最小硬币数F(n)=min(F(n-coin1),F(n-coin2)….)，当coins=[1,2,5]，目标金额为11时，则F(11)=min(F(11-1)，F(11-2),F(11-5))，然后依次递推下去，这样就形成了自顶向下的求法，但是会有重复计算，因此需要使用备忘录也就是记忆性递归来剪枝进行优化

自顶向下解法：

class Solution {
    //因为这是自顶向下递推，初始化则只需要初始化为达不到的值就行了
    vector<int>v;
    int dp(vector<int> coins,int amount){
        if(amount==0) return 0;
        if(amount<0) return -1;
        if(v[amount]!=-2) return v[amount];
        int res=INT_MAX;
        for(int coin:coins){
            int sub=dp(coins,amount-coin);
            if(sub==-1) continue;
            res=min(res,sub+1);
        }
        //存到备忘录中
        v[amount]=(res==INT_MAX)?-1:res;
        return v[amount];
    }
public:
    int coinChange(vector<int>& coins, int amount) {
        v.assign(amount+1,-2);
        return dp(coins,amount);
    }
};

自底向上解法：

class Solution {
public:
    //状态：目标金额 amount 因为每选择一枚硬币就会导致amount数值减少
    //选择：coins数组，包含着硬币面额，选择不同面额的硬币就会导致amount的不同，凑出amount的方案也不同
    //函数定义：coinChange函数，对于目标金额amount，至少需要coinChange(coins,amount)枚硬币
    //base case：当amount=0时，则最少需要0个硬币，当amount<0，则无法凑出目标金额

    int coinChange(vector<int>& coins, int amount) {
        //目标金额所用最多硬币数为amount，因为是求解最小硬币数问题,所以应该初始化比amount还大
        vector<int>dp(amount+1,amount+1);
        //base case
        dp[0]=0;
        //枚举所有状态
        for(int i=0;i<amount+1;i++){
            for(int j:coins){
                //判断当前amount是否小于选择的面额，如果小于就跳过
                if(i-j<0) continue;
                //状态转移，求出凑出当前面额i的最小硬币数
                dp[i]=min(dp[i],dp[i-j]+1);
            }
        }
        return (dp[amount]>=amount+1)?-1:dp[amount];
    }
};

01背包问题

经典的动态规划题目，01背包的01就对应着我是否将当前物品放入背包中，由题意可知，我们只需要求解dp[N] [W]就可以得到答案，分析题目对于选择i物品时，当前背包剩余重量为w时，我们将物品i放入背包则dp[i] [w]=dp[i-1] [w-wt[i-1]]+val[i-1]，我们不将物品i放入背包则dp[i] [w]=dp[i-1] [w]，因此我们取其最大值就可以求出对于前i个物品，当背包容量为w时，可以装的最大价值，因此状态转移方程为max(dp[i-1] [w],dp[i-1] [w-wt[i-1]]+val[i-1]);

#include <iostream>
using namespace std;

//状态：背包的空余容量剩多少，可选择的物品还有哪些
//选择：把这个物品是否放进背包
//dp[i][w]定义，对于前i个物品，当背包的容量为w时，可以装的最大价值是dp[i][w]
//base case:dp[0][...]=dp[...][0]=0,因为当选择物品为0的时候无论w多少都为0，当背包容量为0时，无论物品多少都无法放进
int main(){
    int N,W;
    cin>>N>>W;
    int val[N],wt[N];
    for(int i=0;i<N;i++){
        cin>>val[N]>>wt[N];
    }
    int dp[N+1][W+1];
    memset(dp,0, sizeof(int)*((N+1)*(W+1)));
    for(int i=1;i<=N;i++){
        for(int w=W;w>=wt[i-1];w--){
            dp[i][w]=max(dp[i-1][w],dp[i-1][w-wt[i-1]]+val[i-1]);
        }
    }
    cout<<dp[N][W];
    return 0;
}

完全背包问题：

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。

第 i 种物品的体积是 v_i，价值是 w_i。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

二维dp:

#include <bits/stdc++.h>
using namespace std;

const int N=1e3+1;
int n,m;
int v[N],w[N],dp[N][N];

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;++i) cin>>v[i]>>w[i];
    for(int i=1;i<=n;++i){
        for(int j=0;j<=m;++j){
            dp[i][j]=dp[i-1][j];
            if(j-v[i]>=0) dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);
        }
    }
    cout<<dp[n][m]<<endl;
    return 0;
}

状态压缩：

#include <bits/stdc++.h>
using namespace std;

const int N=1e3+1;
int n,m;
int v[N],w[N],dp[N];

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;++i) cin>>v[i]>>w[i];
    for(int i=1;i<=n;++i){
        for(int j=v[i];j<=m;++j){
            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    cout<<dp[m]<<endl;
    return 0;
}

记忆化搜索

概念：

记忆化搜索就是深度优先搜索的一种优化策略，记忆化搜索=深度优先搜索形式+动态规划思想
由于dfs本质是暴力搜索，没有很好地处理重叠子问题，因此很低效
记忆化算法在求解地时候还是按照自顶向下的顺序，但是每求解一个状态，就将它的解保存下来
求解最优解问题

优点：

解决了深度优先搜索中的重叠子问题要多次遍历的问题
搜索还可以剪枝，可能剪去大量不必要的状态

缺点：

对于同样的问题，如果用动态规划解决而是用了记忆化搜索会使得效率有所降低

dfs函数组成：

得有搜索边界即结束条件，以及处理
对当前状态的检查，如果结果已经记录，则直接返回返回
从当前状态到下一个状态的转移，当前状态最优解的记录
对结果的返回
核心点：状态转移方程的确定。dp[state]=optimal(dp[state],dfs(next state)+cost);

代码模板：

//type为类型，state为状态，在图论中一般都是横竖坐标
type dfs(state){
    if(结束条件){
        处理;
        return type; //返回对应类型的值
    }
    
    if(当前状态的解已被记录) return dp[state];
    //跟动态规划一样或者说跟dfs一样遍历下一个状态
    for each next state{
        if(检查当前状态是否符合约束条件){
            dp[state]=optimal(dp[state],dfs(next state)+cost);
        }
    }
    return dp[state];
}

例题代码实现：

蓝桥杯题：滑行

#include <iostream>
using namespace std;

int mp[105][105], n, m,dp[105][105];
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};

int dfs(int x,int y){
    if(dp[x][y]!=-1) return dp[x][y];
    dp[x][y]=1;
    for(int i=0;i<4;++i){
        int px=x+dx[i];
        int py=y+dy[i];
        if(px>=0&&py>=0&&px<n&&py<m&&mp[px][py]<mp[x][y]){
            dp[x][y]=max(dp[x][y],dfs(px,py)+1);
        }
    }
    return dp[x][y];
}

int main(){
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            cin>>mp[i][j];
            dp[i][j]=-1;
        }
    }
    int cnt=1;
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            cnt=max(cnt,dfs(i,j));
        }
    }
    cout<<cnt<<endl;
    return 0;
}

数位dp

概念：

数位dp是一种计数用的dp，一般是要统计一个区级[l,r]内满足一些条件的数的个数
所谓数位dp，就是对数位进行dp，也就是个位、十位等
相对于普通的暴力枚举，数位dp快就快在它的记忆化，也就是说后面可能会利用到前面已经计算好的东西
题型往往是：给定一个闭区间[L,R]，求这个区间中满足”某种条件”的数的总数量

题型特征：

要求统计满足一定条件的数的数量（即，最终目的为计数）；
这些条件经过转化后可以使用「数位」的思想去理解和判断；
输入会提供一个数字区间（有时也只提供上界）来作为统计的限制；
上界很大（比如10¹⁸），暴力枚举验证会超时。

总结：给定一个闭区间[L,R]，求这个区间中满足”某种条件”的数的总数量

基本原理：

考虑人类计数的方式，最朴素的计数就是从小到大开始依次加一。但我们发现对于位数比较多的数，这样的过程中有许多重复的部分。例如，从 7000 数到 7999、从 8000 数到 8999、和从 9000 数到 9999 的过程非常相似，它们都是后三位从 000 变到 999，不一样的地方只有千位这一位，所以我们可以把这些过程归并起来，将这些过程中产生的计数答案也都存在一个通用的数组里。此数组根据题目具体要求设置状态，用递推或 DP 的方式进行状态转移。，而我们的统计就是由记忆化搜索解决

具体实现：

数位dp首先通常把统计[L,R]范围内满足条件的数字转化为统计[1,N]内满足条件的数字数量，这样就将下界限制去掉,只考虑上边界。就变成：Ans[L,R]=Ans[1,R]-Ans[1,L-1]
将数字大小转换为数位字典序，也就是记录最大枚举到的数字每一位的数值(例如R为123456，那word[1]=6,word[2]=5依次类推)。我们称这个数组为word[n+1]
DFS要记录的状态:
1. 现在枚举到哪一位，记为pos
2. 前面一位的数字是多少，记为pre
3. 这一位可以填的最大数字，记为up，但是求解过程我们会以flag来表示是否需要更新up
我们开始从最高位到最低位枚举，对于当前位置x有两种填补可能性：
1. 如果x前面某一位已经小于对应位置的上限数字，则这一位可以填0-9
2. 如果x前面每一位都等于对应位置的上限数字，这一位可填数字范围为0-x对应位置的上限数字
所以，我们只需要维护前面每一位数字是否和上限数字一样，就可以得到这个位置数字可填范围
如果flag为false，那么dfs计算的过程就和up毫无关系，那么我们可以考虑把这个状态答案记录下来，用于后面复用

模板：

//pos为当前位数
//pre代表前一位所填数字
//flag代表前面每一位数字是否都等于对应的上限数字
int dfs(int pos,int pre,bool flag){
    //如果pos<=0表示枚举完每一位，那返回对应要返回的值
    if(pos<=0) return 需要返回值;
    //如果该状态已经计算过了就返回
    if(!flag&&dp[pos][pre]!=-1) return dp[pos][pre];
    //如果flag为true，up就为对应的上限数字，反之就为9
    int up=flag?word[pos]:9;
    int cnt=0; //计数
    for(int i=0;i<=up;++i){
        if(判断数位是否满足条件) cnt+=dfs(pos-1,i,flag&&(i==up)); //如果满足就继续搜索
    }
    //记录状态
    if(!flag) dp[pos][pre]=cnt;
    return cnt;
}

例题：

Windy数：定义不含前导0且相邻两个数字之差至少为2的正整数被称为windy数，比如5，36，192都是windy数，10，21不是windy数，求[L,R]范围内有多少个Windy数，1<=L,R<=1e18;

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll word[20];
ll dp[30][10];

//lead是用来判断前面一位是否为0
ll dfs(ll pos,ll pre,bool flag,bool lead){
   if(pos<=0) return 1;
    //因为不含前导0，所以pre要大于0
   if(!flag&&pre>0&&dp[pos][pre]!=-1) return dp[pos][pre];
   int up=flag?word[pos]:9;
   ll cnt=0;
   for(int i=0;i<=up;++i){
       //因为要求不含前导0，所以当前面一位为0，说明这一位就为数的开始，所以算是符合条件
       if(abs(i-pre)>=2||lead) cnt+=dfs(pos-1,i,flah&&(i==up),lead&&(i==0));
   }
   if(!flag) dp[pos][pre]=cnt;
   return cnt;
}

ll solve(ll x){
    int pos=0;
    memset(dp,-1,sizeof dp);
    while(x){
        word[++pos]=x%10;
        x/=10;
    }
    return dfs(pos,0,1,1);
}

int main(){
    ll a,b;
    while(cin>>a>>b) cout<<solve(b)-solve(a-1)<<endl;
    return 0;
}

统计整数数目：

class Solution {
public:
    int min_sum,max_sum;
    int dp[23][401];
    char word[25];
    const int mod=1e9+7;
    int dfs(int pos,int sum,bool flag){
        if(pos<=0) return sum>=min_sum;
        if(!flag&&dp[pos][sum]!=-1) return dp[pos][sum];
        int up=flag?word[pos]-'0':9;
        int res=0;
        for(int i=0;i<=up;++i){
            if(sum+i<=max_sum) res=(res+dfs(pos-1,sum+i,flag&&(i==up)))%mod;
        }
        if(!flag) dp[pos][sum]=res;
        return res;
    } 
    
    int solve(string x){
        int pos=0;
        for(int i=x.size()-1;i>=0;--i) word[++pos]=x[i];
        return dfs(pos,0,1);
    }
    
    int count(string num1, string num2, int min_sum, int max_sum) {
        int n=num1.size()-1;
        while(num1[n]=='0'){
            num1[n]='9';
            n--;
        }
        num1[n]--;
        memset(dp,-1,sizeof dp);
        this->min_sum=min_sum;
        this->max_sum=max_sum;
        return (solve(num2)-solve(num1)+mod)%mod;
    }
};

ST表

概念：

ST表适用于解决区间最值的问题(RMQ问题)的数据结构
ST表本质是dp算法，只不过dp是对数组一排一排更新，而RMQ是对数组一列一列动态规划的
预处理时间复杂度为O(nlogn)，查询时间复杂度为O(1)

操作：

例题：给一个数组，有n个数，有m个left，right(left和right为区间边界)，求出这m个区间的最值

首先引入状态f[i][j]，f[i][j]表示从第i个元素开始的长度为2^j个元素的最值
将第i个元素开始的2^j个元素分成长度相等的两部分，每部分的长度为2^j-1
状态转移方程就为：**f[i][j]=max(f[i][j-1]，f[i+2^j-1][j-1])**，即两部分的最大值
边界条件：f[i][0]=a[i]
要询问区间[L,R]的最大值，因区间[L,R]的长度为R-L+1，求出log₂(R-L+1)的值，设为x
因此区间[L,R]就可以分为[L,L+2^x-1]和[R-2^x+1,R]两个部分，根据状态转移方程可以得出区间[L,R]的最大值：RMQ(L,R)=max(f[L][x],f[R-2^x+1][x])
2^x可以用移位运算1<<x提高效率

int query(int l,int r){
    int x=(int)log(r-l+1)/log(2);    //在c++中log默认为以10为底，所以需要换底
    //或者直接使用log2函数
    int x=(int)log2(r-l+1);
    return max(f[l][x],f[r-(1<<x)+1][x]);
}

代码：

#include <iostream>
#include <math.h>
using namespace std;
//例子
const int N=1e6+10;
int f[N][20];  //20是由log2(n)+1算出来的
int n,m;

int query(int l,int r){
//    int x=(int)log(r-l+1)/log(2);
    int x=(int)log2(r-l+1);
    return max(f[l][x],f[r-(1<<x)+1][x]);
}


int main() {
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        int p;
        cin>>p;
        f[i][0]=p;
    }
    //外层循环是遍历列,列不需要遍历到n，而是2的j次方小于等于n
    // 因为f[i][j]代表的是从i开始的2的j次方个元素的最值，因此j最大只能取到log2(n)
    for(int j=1;(1<<j)<=n;++j){
        for(int i=1;i+(1<<j)-1<=n;++i){
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }

    while(m--){
        int x,y;
        cin>>x>>y;
        cout<<query(x,y)<<endl;
    }
    system("pause");
    return 0;
}

例题：

蓝桥杯2415：附近最小

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;


int n, k;

//ST算法
int query(int l, int r, vector<vector<int>> &f) {
    int x = (int)log2(r - l + 1);
    return min(f[l][x], f[r - (1 << x) + 1][x]);
}

int main() {
    cin >> n ;
    int logn = log2(n) + 1;
    vector<vector<int>>f(n + 1, vector<int>(logn));

    for (int i = 1; i <= n; ++i) {
        cin >> f[i][0];
    }

    for (int j = 1; (1 << j) <= n; ++j) {
        for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
            f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        }
    }
    cin >> k;
    for (int i = 1; i <= n; ++i) {
        int l = max(1, i - k);
        int r = min(n, i + k);
        cout << query(l, r, f) << " ";
    }
    cout << endl;
    return 0;
}

单调栈

概念：

单调栈是一种数据结构，但是因为经常使用就将其放入算法
单调栈就是栈内的元素呈单调递增或者单调递减的(一般指栈顶到栈底)
将一个元素插入单调栈时，为了维护栈的单调性，需要在保证将该元素插入到栈顶后整个栈满足单调性的前提下弹出最少的元素。
例如：例如，单调递增栈中自顶向下的元素为{0,11,45,81}，插入元素14时为了保持单调性需要依次弹出0、11，操作后栈变为{14,45,81}
时间复杂度为O(n)

适用场景：

单调栈可以求解出某个元素左边或者右边第一个比它大或者小的元素
可以将其分为具体四种问题：
1. 寻找左侧第一个比当前元素大的元素
2. 寻找左侧第一个比当前元素小的元素
3. 寻找右侧第一个比当前元素大的元素
4. 寻找右侧第一个比当前元素小的元素

各问题解决做法：

总结：

查找比当前大的元素用单调递增栈，查找比当前小的元素用单调递减栈
从左侧查找就看插入栈时的栈顶元素，从右侧查找就看弹出栈时即将插入的元素

寻找左侧第一个比当前元素大的元素：
- 构造一个单调递增栈(从栈顶到栈底)
- 从左到右遍历元素
- 如果当前元素大于栈顶元素，则将其加入(也就是将栈里面小于当前元素的都弹出再插入)；
- 如果小于，则当前栈顶元素就是当前遍历的元素左侧第一个比它大的元素
- 如果插入时的栈为空，则说明左侧不存在比当前元素大的元素
寻找左侧第一个比当前元素小的元素：
- 构造一个单调递减栈(从栈顶到栈底)
- 从左到右遍历元素
- 如果当前元素小于栈顶元素，就加入栈中
- 如果大于，则当前栈顶元素就是当前遍历元素左侧第一个比它小的元素
- 如果插入时的栈为空，则说明左侧不存在比当前元素小的元素
寻找右侧第一比当前元素大的元素：
- 构造一个单调递增栈(从栈顶到栈底)
- 从左到右遍历元素
- 如果当前遍历元素大于当前栈底元素，则当前栈顶元素的右侧第一个比它大的元素就是当前遍历元素
- 如果小于，则将其加入栈中
- 如果在栈中的元素没有被弹出，说明栈中剩下的元素没有右侧比它大的元素
寻找右侧第一个比当前元素小的元素：
- 构造一个单调递减栈(从栈顶到栈底)
- 从左到右遍历元素
- 如果当前遍历元素小于当前栈顶元素，则当前栈顶元素的右侧第一个比它小的元素就是当前遍历元素
- 如果大于，则加入栈中
- 如果在栈中的元素没有被弹出，说明栈中剩下的元素没有右侧比它小的元素

模板代码：

单调递增栈

int main(){
    stack<int>st;
    for(int i=0;i<nums.size();++i){
        while(!st.empty()&&nums[i]>nums[st.top()]){
            st.pop();
        }
        st.push(i);
    }
}

单调递减栈

int main(){
    stack<int>st;
    for(int i=0;i<nums.size();++i){
        while(!st.empty()&&nums[i]<nums[st.top()]){
            st.pop();
        }
        st.push(i);
    }
}

滑动窗口

概念：

滑动窗口算法是由双指针来维护窗口进行滑动的算法
该算法适用于求解包含以下关键词的问题：
1. 满足xxx条件(计算结果，出现次数，同时包含)
2. 最长/最短
3. 子串/子数组/子序列

**使用思路(寻找最长)**：

核心：左右双指针(L,R)在起始点，R向右逐位滑动循环
每次滑动过程中：
1. 如果窗内元素满足条件，R向右扩大窗口，并更新最优结果
2. 如果窗内元素不满足条件，L向右缩小窗口
直到R到达结尾结束
代码模板

初始化：左指针l,右指针r,当前结果res,最优结果bestres
while(右指针没有到结尾){
    窗口扩大，加入r对应的元素，更新当前res;
    while(res不满足条件){
        窗口缩小，移除l对应的元素，l右移;
    }
    更新最优结果bestres;
    r++;
}

**使用思路(寻找最短)**：

核心：左右双指针(L,R)在起始点，R向右逐位滑动循环
每次滑动过程中：
1. 如果窗内元素满足条件，L向右缩小窗口，并更新最优结果
2. 如果窗内元素不满足条件，R向右扩大窗口
直到R到达结尾结束
代码模板

初始化：左指针l,右指针r,当前结果res,最优结果bestres
while(右指针没有到结尾){
    窗口扩大，加入r对应的元素，更新当前res;
    while(res满足条件){
        更新最优结果bestres;
        窗口缩小，移除l对应的元素，l右移;
    }
    r++;
}

回溯算法

概念:

回溯算法是一种进行选择搜索然后再回退到选择点选择其他路径然后形成一个决策树的算法，例如在一个空间摆放家具就需要进行选择不同的家具然后看效果，如果选择其中一个家具的效果不好，则就回退到选择点选择除选择过以外的家具，如果客户认可就沿着这个路径继续搜索，然后达到一个穷举的效果。
回溯算法一般用于求解所有可行性解问题，例如全排列，N皇后等问题
回溯算法相当于穷举搜索的巧妙实现，但是性能一般不理想，但是可以通过剪枝来提升性能
回溯算法也是一种暴力穷举算法，穷举的过程就是遍历一颗多叉树的过程

求解问题：

用于求解所有可行性解的算法(例如全排列，组合，子集问题)

回溯算法框架：

List<value> result;  //用于存求解答案
void backtrack(路径,选择列表){
    if(满足结束条件){
        result.add(路径);
        return;
    }
    for(选择:选择列表){
        做选择;
        backtrack(路径,选择列表);
        撤销选择;
    }
}

例题：

全排列：给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

代码：

vector<vector<int>>res;   //存储结果

vector<vector<int>> permute(vector<int>& nums) {
        vector<int>track;
        backtrack(nums,track);
        return res;
    }

//回溯算法
void backtrack(vector<int>&nums,vector<int>track){
    if(track.size()==nums.size()){
        res.push_back(track);
        return;
    }
    for(int num:nums){
        //避免重复选择
        if(find(track.begin(),track.end(),num)!=track.end()) continue;
        //做选择
        track.push_back(num);
        backtrack(nums,track);
        //撤销选择
        track.pop_back();
    }
}

N皇后：

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

代码：

vector<vector<string>>res;

vector<vector<string>> solveNQueens(int n) {
        //初始化棋局
        vector<string>track(n,string(n,'.'));
        //每行每行放置皇后
        backtrack(0,track,n);
        return res;
}

bool check(vector<string> track,int row,int col,int n){
    //因为我们是每行每行的放置，因此当前行数一下都没有放置皇后所以扫描当前行数以上的就行了
    for(int i=0;i<row;i++){
        if(track[i][col]=='Q') return false;
    }
    //同理扫描当前位置斜上方有没有放置皇后就行了(左上，右上)
    for(int i=row,j=col;i>=0&&j>=0;i--,j--){
        if(track[i][j]=='Q') return false;
    }
    for(int i=row,j=col;i>=0&&j<=n;i--,j++){
        if(track[i][j]=='Q') return false;
    }
    return true;
}

void backtrack(int row,vector<string>& track,int n){
    if(track.size()==row){
        res.push_back(track);
        return;
    }
    for(int col=0;col<n;col++){
        if(!check(track,row,col,n)) continue;
        track[row][col]='Q';
        backtrack(row+1,track,n);
        track[row][col]='.';
    }
}

数据结构

抽象数据类型

概念：

抽象数据类型(abstract data type,ADT)是一些操作的集合。抽象数据类型是数学的抽象，只是描述ADT有啥功能，但是在ADT定义中根本没涉及到如何实现功能，这可以看作是模块化设计的补充，对于诸如表，集合、图和他们的操作一起看作是抽象数据类型，就像整数、实数和布尔量是数据类型一样.例如集合ADT，我们可以有诸如并、交、测定大小以及取余等操作。

线性表

定义：

我们将处理一般的形如A1,A2,A3….AN的表成为线性表，N为表的大小，我们称N=0的表为空表。对于除空表外的任何表，我们说A_i+1后继A_i并称A_i-1前驱A_i,表中的第一个元素为A₁,而最后一个元素为A_N.

简单数组实现表

概念：

表的实现可以通过数组进行实现，而表的插入和删除，就需要对数组元素进行移动，例如插入，如果向第一个位置插入，我们就需要数组元素都向后移动一位，又如删除第一个元素，就需要将第一个元素删掉，数组元素再向前移动一位。

#include <stdio.h?>
#define SIZE 100

struct List{
    int elements[SIZE];
    int len;  //表中元素的长度(即个数)
};

//创建一个空表对象
struct List* createList(){
    struct List *p;
    p=malloc(sizeof(struct List));
    p->len=0;
    return p;
}

//判断表是否为空
bool isEmpty(struct List* p){
    return p->len==0;
}

//头插法
void inserthead(struct List *p,int x){
    if(p->len>=SIZE){
        printf("表已满");
        return;
    }
    for(int i=p->len;i>0;i--){
        p->elements[i]=p->elements[i-1];
    }
    p->elements[0]=x;
    p->len++;
    return;
}

//尾插法
void insertlast(struct List*p,int x){
    if(p->len>=SIZE){
        printf("表已满");
        return;
    }
    p->elements[p->len]=x;
    p->len++;
    return;
}

//打印表中数据
void printList(struct List *p){
    for(int i=0;i<p->len;i++){
        printf("list element is:%d\n",p->elements[i]);
    }
}

//查找指定值，返回索引
int find(struct List *p,int x){
    for(int i=0;i<p->len;i++){
        if(p->elements[i]==x){
            return i;
        }
    }
    printf("没有找到值为%d的数据\n",x);
    return NULL;
}

//查找表中对应索引的值，返回值
int findkth(struct List *p,int pos){
    if(pos>p->len){
        printf("不存在索引为%d的数据\n",pos);
        return NULL;
    }
    return p->elements[pos];
}

//删除
void delete(struct List *p,int x){
    for(int i=0;i<p->len;i++){
        if(p->elements[i]==x){
            for(int j=i;j<p->len-1;j--){
                p->elements[j]=p->elements[j+1];
            }
            p->len--;
           	break;
        }
    }
}

链表

与简单数组实现的优缺点：

优点：简单数组实现表的插入和删除需要花费大量的时间，尤其当数据量大的时候，则程序的耗时将会难以接受，因此为了避免插入和删除的线性开销，我们需要允许表可以不连续存储，否咋表的部分或全部需要整体移动，因此我们将用链表进行实现
缺点：在查找数据的时候，链表所耗的时长更多，因为数组可以直接用索引来获取，但是链表需要遍历表连接的数据，直到找到数据为止。

概念：

链表由一系列不必在内存相连的结构组成，每一个结构均含有表元素和指向包含该元素后继元的结构的指针，我们称之为Next指针。最后一个单元的Next指针指向NULL，NULL是在c中的定义，c中规定为0.

struct Node{
    int data;
    struct Node* next;
};

struct Node *createNode(int data){
    struct Node *p=(struct Node* )malloc(sizeof(struct Node));
    p->data=data;
    p->next=NULL;
    return p;
}

//头插法
struct Node *inserthead(struct Node *head, int data) {
	struct Node *add = createNode(data);
	if (head == NULL) {
		return add;
	}
//	struct Node *p = head;
//	head = add;
//	head->next = p;
//	return head;
	add->next = head;
	return add;
}

//尾插法
struct Node *insert(Node *head,int data){
    struct Node *add=createNode(data);
    if(head==NULL){
        return add;
    }
    while(head->next!=NULL){
        head=head->next;
    }
    head->next=add;
    return head;
}

struct Node *search(Node *head,int data){
    if(head==NULL||head->data==data){
        return head;
    }
    struct Node *p=head;
    while(p->next!=NULL){
        if(p->data==data){
            return p;
        }
        p=p->next;
    }
    return NULL;
}

struct Node *del(Node *head,int data){
    if(head==NULL){
        return head;
    }
    if(head->data==data){
        struct Node *p=head->next;
        free(head);
        return p;
    }
    struct Node *tail=head;
    struct Node *p=head->next;
    while(p!=NULL){
        if(p->data==data){
            break;
        }
        tail=p;
        p=p->next;
    }
    if(p!=NULL&&p->data==data){
        tail->next=p->next;
        free(p);
    }
    return head;
}
//清除链表
struct destoty(Node *head){
    if(head!=NULL){
        destory(head->next);
        free(head);
    }
}

双向非循环链表

作用：

有时候以倒序扫描链表更方便，但是为了实现这个就会多出一条附加链的开销，他增加了空间的需求，同时使得插入和删除的开销增加一倍，但是又简化了删除操作。

概念：

双向非循环链表就是双向的链表，链表中的前后结点都有指向对方的指针，就是A₁的next为A₂，但是A₂又有指针指向A₁.

代码：

struct doublyNode{
    int data;
    struct doublyNode* next;
    struct doublyNode* prev;
};

struct doublyNode *createNode(int data){
    auto* p=(struct doublyNode*)malloc(sizeof(struct doublyNode));
    p->data=data;
    p->prev=NULL;
    p->next=NULL;
    return p;
}

//头插法
struct doublyNode*inserthead(struct doublyNode* head,int data){
    struct doublyNode*add= createNode(data);
    if(head==NULL){
        return add;
    }
    struct doublyNode*p=head;
    head=add;
    head->next=p;
    p->prev=head;
    return head;
}

//尾插法
struct doublyNode * insertlast(struct doublyNode* head,int data){
    struct doublyNode* add= createNode(data);
    if(head==NULL){
        return add;
    }
    struct doublyNode*p=head;
    while (p->next!=NULL){
        p=p->next;
    }
    p->next=add;
    p->prev=p;
    return head;
}

//删除
doublyNode * del(struct doublyNode* head,int data){
    if(head==NULL){
        cout<<"链表没有数据"<<endl;
        return head;
    }
    if(head->data==data){
        struct doublyNode* p=head->next;
        free(head);
        return p;
    }
    struct doublyNode* tail=head;
    struct doublyNode* p=head->next;
    while (p!=NULL){
        if(p->data==data){
            tail->next=p->next;
            free(p);
            return head;
        }
        tail=p;
        p=p->next;
    }
}

void printlist(struct doublyNode* head){
    if(head==NULL){
        cout<<"链表没有数据"<<endl;
    }
    struct doublyNode* p=head;
    while (p!=NULL){
        cout<<p->data<<" ";
        p=p->next;
    }
    cout<<endl;
}

循环链表

概念：

循环链表就是没有表头表尾的链表，例如一般的链表的表尾为NULL,但是循环链表的下一个指向的表头，不仅有单向循环链表，而且还有双向循环链表，双向循环链表就是表头的前一个指向表尾，表尾的下一个指向表头。
C++中的STL库中就已经封装了双向循环链表的类(list)

代码：

//单向循环链表
struct CirNode{
    int data;
    struct CirNode* next;
    struct CirNode *prev;
};

struct CirNode* createNode(int data){
    struct CirNode* p=(struct CirNode*)malloc(sizeof(struct CirNode));
    p->data=data;
    p->next=NULL;
    p->prev=NULL;
    return p;
}

struct CirNode* inserthead(CirNode* head,int data){
    struct CirNode* add= createNode(data);
    if(head==NULL){
        add->next=add;
        add->prev=add;
        return add;
    }
    struct CirNode* p=head;
    struct CirNode* p1=head->next;
    while (p1!=head){
        p1=p1->next;
    }
    head=add;
    head->next=p;
    p1->next=head;
    head->prev=p1;
    p->prev=head;
    return head;
}

//尾插法
struct CirNode* insertlast(CirNode* head,int data){
    struct CirNode* add= createNode(data);
    if(head==NULL){
        add->prev=add;
        add->next=add;
        return add;
    }
    struct CirNode* p=head;
    while(p->next!=head){
        p=p->next;
    }
    p->next=add;
    add->prev=p;
    add->next=head;
    return head;
}

struct CirNode* del(CirNode* head,int data){
    if(head==NULL){
        cout<<"链表没有数据"<<endl;
        return head;
    }
    if(head->data==data){
        struct CirNode* p=head->next;
        p->prev=head->prev;
        free(head);
        return p;
    }
    struct CirNode* tail=head;
    struct CirNode* p=head->next;
    while (p!=head){
        if(p->data==data){
            tail->next=p->next;
            p->next->prev=tail;
            free(p);
            return head;
        }
        tail=p;
        p=p->next;
    }
}

void printlist(CirNode* head){
    if(head==NULL){
        cout<<"链表没有数据"<<endl;
    }
    struct CirNode* p=head;
    do{
        cout<<p->data<<" ";
        p=p->next;
    } while (p!=head);
    cout<<endl;
}

跳跃表(跳表)

概念：

跳跃表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。
跳表在原有的有序链表的基础上面通过随机化算法产生随机级数的节点使其通过节点的索引来实现快速查找，提高了插入，删除，查找操作的性能
跳表数据结构是以O(logN)期望时间进行查找和删除操作的数据结构

特性：

有序性
插入新元素通过随机化算法随机分配存储该新元素值的节点级数，而级数就代表着这个节点有多少个指针，例如调表的第k位4阶节点，从最高层到最后一层，每个指针指向第2ⁱ+k节点(也就是跳过2ⁱ个节点，i为层数)

随机化算法：

该算法用于给跳表插入新元素时，进行随机产生k阶节点用于作为新元素值得载体插入在跳表中。
虽然是随机的，但是各阶节点的产生是有概率性的，1/2是一阶节点，1/4是2阶节点，大约1/2ⁱ的节点是i阶节点。

查找操作：

首先在最高级索引上查找最后一个小于当前查找元素的位置，然后再跳到次高级索引继续查找，直到跳到最底层为止。
跳表的数据结构大大提高了查找操作，跳表的查找操作类似于二分查找。

插入操作：

随机产生阶数，然后根据阶数跟数值创建节点
如果新创建的表头，则直接令表头的第一层索引指针指向新创建的节点，如果不是就根据上步产生的阶数创建prev数组用来存储每层要插入节点位置的前继节点，遍历每一层，将prev赋值完。
然后根据阶数遍历，插入到存储到prev的前继节点的下一个位置。

删除操作：

跟插入操作差不多，先进行将prev数组赋值
然后遍历每层，将每层的前继节点指向被删除节点的下一个节点。
释放被删除节点的空间。

代码：

struct Node{
    int val;     //存储元素值
    vector<Node*>next;   //存储各层数指针的数组
    int level;  //阶数
};


class skiplist{
public:
    skiplist(int level):Maxlevel(level){
        head= createNode(NULL,Maxlevel);
    }
    ~skiplist() {
        Node* tail=head;
        Node* p;
        while (tail!= nullptr){
            p=tail;
            tail=tail->next[0];
            delete p;
        }
        head= nullptr;
    };

    Node* find(int data);
    void insert(int data);
    void del(int data);
    void print();

private:
    Node* head;
    int Maxlevel;

    Node* createNode(int data,int level){
        auto p = new Node;
        p->val=data;
        p->level=level;
        p->next.resize(level,NULL);
        return p;
    }

    int rand_level(){
        int level=1;
        while(rand()%2&&level<=Maxlevel){
            level++;
        }
        return level;
    }


};

Node *skiplist::find(int data) {
    Node* p=head;
    for(int i=Maxlevel-1;i>=0;i--){
        while (p->next[i]!= nullptr&&p->next[i]->val<data){
            p=p->next[i];
        }
    }
    if(p->next[0]!= nullptr&&p->next[0]->val==data){
        return p->next[0];
    }
    return nullptr;
}

void skiplist::insert(int data) {
    int level=rand_level();
    Node* add= createNode(data,level);
    if(head->next[0]== nullptr){
        head->next[0]=add;
        return;
    }
    Node* p=head;
    Node* prev[level];
    for(int i=level-1;i>=0;i--){
        while (p->next[i]!= nullptr&&p->next[i]->val<data){
            p=p->next[i];
        }
        prev[i]=p;
    }
    for(int i=0;i<level;i++){
        add->next[i]=prev[i]->next[i];
        prev[i]->next[i]=add;
    }
}

void skiplist::del(int data) {
    Node* p=head;
    Node* prev[Maxlevel];
    for(int i=Maxlevel-1;i>=0;i--){
        while (nullptr!=p->next[i]&&p->next[i]->val<data){
            p=p->next[i];
        }
        prev[i]=p;
    }
    if(p->next[0]!= nullptr&&p->next[0]->val==data){
        Node* tail=p->next[0];
        for(int i=Maxlevel-1;i>=0;i--){
            if(prev[i]->next[i]!= nullptr&&prev[i]->next[i]->val==data)
                prev[i]->next[i]=prev[i]->next[i]->next[i];
        }
        delete tail;
    }
}

void skiplist::print() {
    Node* p=head->next[0];
    while (p!= nullptr){
        cout<<p->val<<" ";
        p=p->next[0];
    }
    cout<<endl;
}

栈(stack)

概念

栈(stack)是限制插入和删除只能在一个位置上的进行的表，而这个模型唯一的开口位置是表的末端，叫做栈顶(top)，相反表的首部，叫做栈底。对于栈的基本操作有**Push(进栈)和Pop(出栈)**，前者相当于插入，后者则是删除表中最后一个元素(也就是处在栈顶位置的元素)。
栈是一个先进后出的模型

注意事项：

虽然这里将栈放在线性表外，但是栈模型也属于线性表。
栈是既可以用数组实现也可以用链表实现
- 如果栈的大小已知且固定，或者对随机访问元素效率有较高要求，使用数组实现栈可能更合适。
- 如果栈的大小不确定，或者插入和删除操作频繁且在栈顶之外发生，使用链表实现栈可能更有优势。

链表实现代码：

struct Node{
    int data;
    Node *next;
};
typedef Node* Stack;

Stack createStack(int data){
    struct Node* p=new struct Node;
    p->data=data;
    p->next=NULL;
    return p;
}

//进栈
void Push(Stack &head,int data){
    Stack add= createStack(data);
    if(head==NULL){
        head=add;
    }else{
        Node* p=head;
        add->next=p;
        head=add;
    }
}

//出栈
void Pop(Stack &head){
    if(head==NULL){
        cout<<"栈中没有数据"<<endl;
        return;
    }
    Node* p=head;
    head=p->next;
    delete p;
}

//获取栈顶元素
int top(Stack head){
    return head->data;
}


//打印栈
void printStack(Stack head){
    if(head==NULL){
        cout<<"栈中没有数据"<<endl;
        return;
    }
    Node* p=head;
    while (p!=NULL){
        cout<<p->data<<" ";
        p=p->next;
    }
    cout<<endl;
}

//获取栈的大小
int Size(Stack head){
    Node* p=head;
    int cnt=0;
    if(p->data&&p->next==NULL){
        cnt=1;
    } else{
        while (p!=NULL){
            cnt++;
            p=p->next;
        }
    }
    return cnt;
}

//判断栈是否为空
bool empty(Stack head){
    if (head!=NULL){
        return false;
    }else{
        return true;
    }
}

//清空栈
void destroy(Stack &head){
    if(head==NULL){
        cout<<"栈中没有数据"<<endl;
        return;
    }
    Node* tail=head->next;
    while (head!=NULL){
        delete head;
        head=tail;
        if(tail!=NULL)
            tail=tail->next;
        else
            return;
    }
}

数组实现代码：

class stack{
public:
    //入栈
    void Push(int data){
        head.push_back(data);
    }

    //出栈
    void Pop(){
        if(head.empty()){
            cout<<"栈中没有数据！"<<endl;
            return;
        } else
            head.pop_back();
    }

    //获取栈顶元素
    int top(){
        if(head.empty()){
            cout<<"栈中没有数据！"<<endl;
            return NULL;
        }
        return head.back();
    }

    //打印栈
    void printstack(){
        if(head.empty()){
            cout<<"栈中没有数据"<<endl;
            return;
        }else{
            for(vector<int>::const_iterator it=head.end()-1;it>=head.begin();it--){
                cout<<*it<<" ";
            }
            cout<<endl;
        }
    }

    //清空栈
    void destory(){
        head.clear();
    }

    //获取栈的大小
    int Size(){
        return head.size();
    }

    //判断栈是否为空
    bool empty(){
        if(head.empty()){
            return true;
        } else{
            return false;
        }
    }
private:
    vector<int>head;
};

逆波兰转换式

概念：

一种后缀表达式，例如a+b+c*d，转换成逆波兰表达式就为：a b + c d * +，然后我们将逆波兰表达式压入栈中(将元素压入栈中遇到运算符号就将栈中的两个元素进行出栈在进行运算，运算完后再压入栈中，重复操作就能得到逆波兰表达式的结果)，逆波兰表达式中没有括号！
转换成逆波兰表达式，需要一个空栈跟一个临时输出区(但不直接输出)，将运算元素放进临时输出区，将运算符号压入栈中。
- 如果运算符的优先级大于上一个运算符，就进行入栈。
- 如果运算符的优先级小于等于上一个运算符，就将前面的运算符出栈放在临时输出区，再将该运算符入栈。
- 如果栈中有左括号，后面入栈的运算符不是右括号的话，左括号就不出栈，而是继续重复上两个规则，直到右括号出现就将左括号出栈，但括号不放入临时输出区
- 当运算元素都放入临时输出区时，栈区还有运算符就直接出栈放入临时存放区，最终将临时存放区按顺序输出出来就是转换的逆波兰表达式

代码：

bool flag(char a,char b){
    int a1,b1;
    if(a=='+'||a=='-'){
        a1=1;
    }else if(a=='*'||a=='/'){
        a1=2;
    }else if(a=='('||a==')'){
        a1=3;
    }
    if(b=='+'||b=='-'){
        b1=1;
    }else if(b=='*'||b=='/'){
        b1=2;
    }else if(b=='('||b==')'){
        b1=3;
    }
    return a1>=b1;
}

vector<char> reversePolan(char *an,int len){
    stack<char>s;
    vector<char>v;
    int cnt=0;
    for(int i=0;i<len;i++){
        if(an[i]!='+'&&an[i]!='-'&&an[i]!='*'&&an[i]!='/'&&an[i]!='('&&an[i]!=')'){
            v.push_back(an[i]);
        }else if(an[i]=='+'||an[i]=='-'||an[i]=='*'||an[i]=='/'||an[i]=='('||an[i]==')'){
            if(s.empty()){
                s.push(an[i]);
            }else if(an[i]=='('){
                s.push(an[i]);
                cnt=1;
            }else if(an[i]==')'&&cnt==1){
                while (s.top()!='('){
                    v.push_back(s.top());
                    s.pop();
                }
                s.pop();
                cnt=0;
            } else if(flag(s.top(),an[i])){
                while (!s.empty()){
                    if(s.top()=='('){
                        break;
                    }
                    v.push_back(s.top());
                    s.pop();
                }
                s.push(an[i]);
            }else{
                s.push(an[i]);
            }
        }
    }
    if(!s.empty()){
        while (!s.empty()){
            v.push_back(s.top());
            s.pop();
        }
    }
    return v;
}


int main() {
    char an[]={'a','+','b','*','c','+','(','d','*','e','+','f',')','*','g'};
    int len= sizeof(an)/ sizeof(an[0]);
    auto a= reversePolan(an,len);
    for(char i:a){
        cout<<i<<" ";
    }
    cout<<endl;
    system("pause");
    return 0;
}

队列(queue)

概念：

队列也是一种线性表，使用队列时插入在一端进行而删除则在另一端进行，队列的基本操作是入队，它是在表的末端(也叫做队尾)插入一个元素，出队，它是删除在**表的开头(**队头)的元素。

数组实现：

//数组实现
class queue{
public:
    //入队(向数组末尾插入数据)
    void Push(int data){
        head.push_back(data);
    }

    //出队(将数组第一个元素删除)
    void Pop(){
        if(head.empty()){
            cout<<"队列中没有数据！"<<endl;
            return;
        } else{
            auto it=head.begin();
            head.erase(it);
        }
    }

    //获取队首元素
    int front(){
        if(head.empty()){
            cout<<"队列中没有数据！"<<endl;
            return NULL;
        }
        return head[0];
    }

    //打印队列
    void print(){
        if(head.empty()){
            cout<<"队列中没有数据！"<<endl;
            return;
        }
        for(int i:head){
            cout<<i<<" ";
        }
        cout<<endl;
    }

    //清空队列
    void destroy(){
        head.clear();
    }

    //获取队列大小
    int size(){
        return head.size();
    }

    //判断队列是否为空
    bool empty(){
        if(head.empty()){
            return true;
        } else{
            return false;
        }
    }

private:
    vector<int>head;
};

链表实现：

//链表实现
struct Queue{
    int data;
    Queue* next;
};

Queue* createNode(int data){
    auto p=new Queue;
    p->data=data;
    p->next=NULL;
    return p;
}

//入队
void push(Queue* &head,int data){
    Queue* add= createNode(data);
    if (head==NULL){
        head=add;
    }else{
        Queue* p=head;
        while (p->next!=NULL){
            p=p->next;
        }
        p->next=add;
    }
}

//出队
void pop(Queue* &head){
    if(head==NULL){
        cout<<"队列中没有元素"<<endl;
        return;
    }
    Queue* p=head;
    head=p->next;
    delete p;
}

//获取队首元素
int front(Queue* &head){
    if(head==NULL){
        cout<<"队列中没有元素"<<endl;
        return NULL;
    }
    return head->data;
}

//打印队列
void print(Queue* &head){
    if(head==NULL){
        cout<<"队列中没有元素"<<endl;
        return;
    }
    Queue* p=head;
    while (p!=NULL){
        cout<<p->data<<" ";
        p=p->next;
    }
    cout<<endl;
}

//清空队列
void destroy(Queue* &head){
    if(head==NULL){
        cout<<"队列中没有元素"<<endl;
        return;
    }
    Queue* tail=head->next;
    while (head!=NULL){
        delete head;
        head=tail;
        if(tail!=NULL)
            tail=tail->next;
        else
            return;
    }
}

树

普通树(多叉树)

概念：

树就是由根节点(父亲)分出多个分支节点(儿子)，然后分支又分出多个分支，我们将这种结构称为树,树也可以这么定义：一棵树由称作根的节点r以及0个或多个非空的(子)树T1，T2，T3…Tk组成，这些子树每一棵的根都被来自根r的一条有向的边所连接。
从递归定义中我们发现，一颗树是N个节点和N-1条边的集合，其中的一个节点叫做根。每条边都将某个节点连接到它的父亲，而除去根接待你外每一个节点都有一个父亲。没有子节点的节点叫做树叶(叶节点)，具有相同父节点称为兄弟节点。节点深度就是该节点到根节点的长度是多少，节点高度就是该节点到最近叶节点的长度。

代码:

//通过链表的形式，表头就是根节点，通过找到第一个子节点，就能找到其他的子节点。
struct treeNode{
    int data;
    treeNode* firstchild;    //用于指向该节点的第一个子节点
    treeNode* nextsibling;   //用于指向该节点的下一个兄弟节点
};

treeNode* createNode(int data){
    auto p=new treeNode;
    p->data=data;
    p->firstchild=NULL;
    p->nextsibling=NULL;
    return p;
}

//插入节点
void addChild(treeNode* &root,int data){
    treeNode* add=createNode(data);
    if(root==NULL){
        root=add;
    }else{
        if(root->firstchild==NULL){
            root->firstchild=add;
        }else{
            treeNode* p=root->firstchild;
            while(p->nextsibling!=NULL){
                p=p->nextsibling;
            }
            p->nextsibling=add;
        }
    }
}

//先序查找
treeNode* preorderSearch(treeNode* root,int data){
    if(root==NULL){
        return NULL;
    }
    if(root->data==data){
        return root;
    }
    treeNode* res;
    res=preorderSearch(root->firstchild,data);
    if(res!=NULL){
        return res;
    }
    res=preorderSearch(root->nextsibling,data);
    if(res!=NULL){
        return res;
    }
    return NULL;
}

//后序查找
treeNode* postorderSearch(treeNode* root,int data){
    if(root==NULL){
        return NULL;
    }
    treeNode* res;
    res=postorderSearch(root->firstchild,data);
    if(res!=NULL){
        return res;
    }
    res=postorderSearch(root->nextsibling,data);
    if(res!=NULL){
        return res;
    }
    if(root->data==data){
        return root;
    }
    return NULL;
}

//删除节点
void del(treeNode* &root,int data){
    if(root==NULL){
        return NULL;
    }
    treeNode* p=NULL;
    treeNode* tail=root->firstchild;
    while(tail!=NULL){
        if(tail->data==data){
            if(p==NULL){
                root->firstchild=tail->nextsibling;
            }else{
                p->nextsibling=tail->nextsibling;
            }
            delete tail;
            return;
        }
        del(tail,data);
        p=tail;
        tail=tail->nextsibling;
    }
    return NULL;
}

//先序遍历
void preorderprint(treeNode *root){
    if(root==NULL){
        return;
    }
    cout<<root->data<<" ";
    preorderprint(root->firstchild);
    preorderprint(root->nextsibling);
}


//后序遍历
void postorderprint(treeNode* root){
    if(root==NULL){
        return;
    }
    postorderprint(root->firstchild);
    postorderprint(root->nextsibling);
    cout<<root->data<<" ";
}


//清空树
void destroy(treeNode* root){
    if(root==NULL){
        return;
    }
    destroy(root->firstchild);
    destroy(root->nextsibling);
    delete root;
}

树的遍历

树有很多应用。流行的用法之一是包括UNIX、VAX/VMS和DOS在内的许多常用操作中的目录结构。

核心思想：

树的遍历的核心是递归
树的遍历的核心思想还有遍历的方式(先序遍历，后序遍历….)

先序遍历：

先从根节点，处理完根节点，再去处理子树
先处理子树的根节点，才处理子节点
先序遍历总是处理根节点，再处理子节点

后序遍历：

先处理子树的子节点，再处理子树的根节点
把全部小子树处理完，就处理树的根节点
后序遍历总是先处理子节点，再处理根节点

二叉树

概念：

二叉树(binary tree)是一颗每个节点都不能多于两个子节点的树，左边的子树称为左子树，右边的子树称为右子树

性质：

二叉树实际上是图，二叉树相对于树更常用。
平衡二叉树的深度要比节点数小很多，平均深度为O(n^1/2)
对于特殊类型的二叉树，即**二叉查找树(binary search tree)，平均深度为O(logN)**，最坏情况的二叉树深度能达到N-1。

先序遍历：

先处理根节点，再处理左子树，最后处理右子树
处理左子树的时候，也是先处理左子树的根节点，再处理剩下的左子节点(或者子树)，最后处理右节点(子树)
处理右子树跟处理左子树的操作一样。

中序遍历：

先处理左子树，再处理根节点，最后处理右子树
处理左子树时，也是先处理左子树的左子节点(子树),再处理左子树的根节点，最后处理左子树的右子节点(子树)
处理完左子树，处理根节点
处理完根节点，就处理右子树(跟处理左子树的操作一致)

后序遍历：

先处理左子树，再处理右子树，最后处理根节点
处理左子树的时候，也是先处理左子树的左子节点(子树)，再处理左子树的右子节点(子树)，最后处理左子树的根节点。
处理完左子树，再处理右子树(跟处理左子树的操作一致)
处理完右子树，最后处理树的根节点

代码：

//二叉树,用left指向左子树节点，用right指向右子树节点
struct binarytree{
    int data;
    binarytree* left;
    binarytree* right;
};

binarytree* createNode(int data){
    auto p=new binarytree;
    p->data=data;
    p->left=NULL;
    p->right=NULL;
    return p;
}

//插入节点
void addchild(binarytree* &root,int data){
    binarytree* add= createNode(data);
    if(NULL == root) {
        root = add;
    }else{
        if(NULL == root->left){
            root->left=add;
        }else if(NULL==root->right){
            root->right=add;
        }else{
            cout<<"该根节点的子节点已满！"<<endl;
        }
    }
}


//先序查找
binarytree* preorderSearch(binarytree* root,int data){
    if(NULL == root){
        return NULL;
    }
    if(root->data==data){
        return root;
    }
    binarytree* res;
    res=preorderSearch(root->left,data);
    if(NULL!=res){
        return res;
    }
    res=preorderSearch(root->right,data);
    if(NULL!=res){
        return res;
    }
    return NULL;
}

//中序查找
binarytree* inorderSearch(binarytree* root,int data){
    if(NULL == root){
        return NULL;
    }
    binarytree* res;
    res=inorderSearch(root->left,data);
    if(NULL!=res){
        return res;
    }
    if(root->data==data){
        return root;
    }
    res=inorderSearch(root->right,data);
    if(NULL!=res){
        return res;
    }
    return NULL;
}

//后序查找
binarytree* postorderSearch(binarytree* root,int data){
    if(NULL==root){
        return NULL;
    }
    binarytree* res;
    res= postorderSearch(root->left,data);
    if(NULL!=res){
        return res;
    }
    res= postorderSearch(root->right,data);
    if (NULL!=res){
        return res;
    }
    if(root->data==data){
        return root;
    }
    return NULL;
}

//清空树
void destroy(binarytree* &root){
    if(NULL==root){
        return;
    }
    destroy(root->left);
    destroy(root->right);
    delete root;
}

//删除节点
void del(binarytree* &root,int data){
    if(NULL == root){
        return;
    }
    binarytree* p=root;
    binarytree* tail=root->left;
    while (tail!=NULL){
        if(tail->data==data){
            if(NULL!=p->right){
                p->left=p->right;
                p->right=NULL;
                delete tail;
                return;
            }else{
                delete tail;
                p->left=NULL;
                return;
            }
        }
        del(tail,data);
        binarytree* temp=p;
        p=tail;
        tail=temp->right;
    }
    return;
}

//先序遍历
void preorderprint(binarytree* root){
    if(NULL==root){
        return;
    }
    cout<<root->data<<" ";
    preorderprint(root->left);
    preorderprint(root->right);
}

//中序遍历
void inorderprint(binarytree* root){
    if(NULL==root){
        return;
    }
    inorderprint(root->left);
    cout<<root->data<<' ';
    inorderprint(root->right);
}

//后序遍历
void postorderprint(binarytree* root){
    if(NULL==root){
        return;
    }
    postorderprint(root->left);
    postorderprint(root->right);
    cout<<root->data<<' ';
}

二叉查找树(二叉排序树)

概念：

二叉树的一个重要应用是它们在查找中的使用—二叉查找树
二叉查找树每个节点的值都不同，以后再处理值相同的情况
对于二叉查找树的每个节点，它的左子树中所有关键字值小于该节点的关键字值，而它的右子树中所有的关键字值大于该节点的关键字值
该数的所有元素可以用某种统一的方式排序—-二叉查找树有序
二叉查找树的平均深度为O(logN)
二叉查找树应该用中序遍历方式遍历

代码:

struct binarysearch{
    int data;
    binarysearch* left;
    binarysearch* right;
};

binarysearch* createNode(int data){
    auto p=new binarysearch;
    p->data=data;
    p->right=NULL;
    p->left=NULL;
    return p;
}


//插入节点
binarysearch* insert(binarysearch* &root,int data){
    if (NULL==root){
        binarysearch* add= createNode(data);
        root=add;
    }else if(data<root->data){
        root->left= insert(root->left,data);
    }else if(data>root->data){
        root->right= insert(root->right,data);
    }
    return root;
}


//查找,直接判断大小然后递归分树查找(小就左子树，大就右子树，不然就是中间的树根节点)
binarysearch* Search(binarysearch* root,int data){
    if(NULL==root){
        return NULL;
    }
    if(data<root->data){
        return Search(root->left,data);
    } else if(data>root->data){
        return Search(root->right,data);
    }else{
        return root;
    }
}


//查找树的最小值,二叉查找树只需顺着左子树一路到最左就是最小
int findmin(binarysearch* root){
//    递归形式
    if(NULL==root){
        return root->data;
    }
    if(root->left==NULL){
        return root->data;
    }else{
        return findmin(root->left);
    }

    //非递归形式
//    if(NULL!=root){
//        while (root->left!=NULL){
//            root=root->left;
//        }
//    }else{
//        return NULL;
//    }
//    return root->data;
}

//查找树的最大值，二叉查找树只需顺着右子树一路到最右就是最大
int findmax(binarysearch* root){
    //递归形式
//    if(NULL==root){
//        return NULL;
//    }
//    if(root->right==NULL){
//        return root->data;
//    }else{
//        return findmax(root->right);
//    }

    //非递归形式
    if(NULL!=root){
        while (root->right!=NULL){
            root=root->right;
        }
    }else{
        cout<<"树没有数据"<<endl;
    }
    return root->data;
}


//遍历(使用中序遍历)
void inorderprint(binarysearch* root){
    if(NULL == root){
        return;
    }
    inorderprint(root->left);
    cout<<root->data<<" ";
    inorderprint(root->right);
}

//删除节点，如果只有一个节点就分析是左子树还是右子树，然后将子树代替该根节点
//如果既有左节点(子树)和右节点(子树)，就找到右子树的最小值节点代替该根节点！
binarysearch* del(binarysearch* &root,int data){
    if(NULL==root){
        return NULL;
    }else if(data<root->data){
        root->left= del(root->left,data);
    }else if(data>root->data){
        root->right=del(root->right,data);
    }else if(root->left&&root->right){     //找寻右子树的最小值节点，删除最小值节点只有两种情况就是只有右子树(节点)或者没有节点。
        int temp= findmin(root->right);
        root->data=temp;
        root->right=del(root->right,temp);
    }else{   //只有一个子节点或者没有子节点的情况
        binarysearch* p=root;
        if(NULL==root->left){
            root=root->right;
        }else if(NULL==root->right){
            root=root->left;
        }
        delete p;
    }
    return root;
}


//清空树
binarysearch* destroy(binarysearch* &root){
    if(NULL!=root){
        destroy(root->left);
        destroy(root->right);
        delete root;
    }
    return NULL;
}

平衡查找树(AVL树)

概念：

为了防止因为插入删除而导致的树结构不平衡(通常我们删除节点总是对右子树的最小值节点替代操作，而不是交替的利用左子树的最大值节点替代，这就将导致左子树的平均深度大于右子树平均深度，直接导致整颗树平均深度的增加，导致对树节点的操作时间增长)，导致对树的操作所用时间成倍数增长的问题，我们采用平衡二叉树—左右子树的平均深度差不多，达到一种平衡的操作，平衡二叉树希望对树的任意节点的操作时间为O(logN)
AVL(Adelson-Velskii和Landis)树是带有平衡条件的二叉查找树。这个平衡条件需要容易保持，而且需保证树的深度是O(logN)。
一颗AVL树是其每个节点的左子树和右子树的高度最多差1的二叉查找树，空树的高度定义为-1
在高度为h的AVL树中，最少节点数S(h)由S(h)=S(h-1)+S(h-2)+1算出。该h为该数最大高度。

旋转：

功能：对被破坏平衡的AVL树进行修正，使得重新平衡
对于我们对树的插入操作，破坏AVL树的平衡，我们则需要对树进行简单的修正来保持平衡，这个操作我们称其为旋转
我们把必须重新平衡的节点(就是造成AVL树不平衡的插入点跟因此被打破平衡的另外一个节点(也就是插入点跟树中的一个节点高度差大于1)的共同根节点)叫做α，由于任意节点最多有两个儿子，因此高度不平衡时，α点的两颗子树的高度差2，这种不平衡的情形有四种：

1.对α的左儿子的左子树进行一次插入

2.对α的左儿子的右子树进行一次插入

3.对α的右儿子的左子树进行一次插入

4.对α的右儿子的右子树进行一次插入
对于1和4的情形称为插入发生在”外边”的情况(即左-左的情况或右-右的情况)，该情况需要通过对树的一次单旋转而完成调整
对于2和3的情形称为插入发生在”内部”的情况(即左-右的情况或右-左的情况)，这个情况需要通过对树的双旋转来处理

单旋转

对于情形1(如图4-31)，我们需要将造成不平衡的插入点上移一层，另外那个跟它高度差为2的节点下移一层(就是将α点跟其左节点进行单旋转(单旋转就是类似将左节点拎起来，其他的节点根据重量下坠，然后再根据二叉查找树的特性排序形成新的平衡二叉树))，并形成一个新的平衡二叉查找树，具体操作就如图4-32，插入6会破坏AVL树的特性，因为6是插入点，而8没有子节点(这个空的子节点其实就是被破坏平衡的高度差为2的节点)，它们的共同根节点就为8，所以8为α点，我们需要将α点的左节点也就是7跟α点也就是8进行单旋转，然后形成新的平衡查找树

具体操作为：
1. 向α点的左儿子的左子树插入节点造成不平衡
2. 将α点跟α点的左儿子做单旋转
3. 原先α点的左儿子的左子树根节点成为现在α点(之前的α点的左儿子)的左儿子，原先的α点作为现在α点的右儿子，原先α点的左儿子的右子树根节点成为现在α点的右儿子的左子树根节点
4. 重新形成一个新的AVL树
对于情形4(如图4-33)，其实情形4跟情形差不多的做法就是方向改变了，我们需要将造成不平衡的插入点上移一层，另外那个跟它高度差为2的节点下移一层(就是将α点跟其右节点进行单旋转(单旋转就是类似将右节点拎起来，其他的节点根据重量下坠，然后再根据二叉查找树的特性排序形成新的平衡二叉树))，并形成新的平衡二叉查找树

具体操作为：
1. 向α点的右儿子的右子树插入节点造成不平衡
2. 对α点跟α点的右儿子进行单旋转
3. 原先的α点成为现在的α点(之前的α点的右儿子)的左儿子，原先的α点的右儿子的右子树根节点成为现在的α点的右儿子，原先α点的右儿子的左子树根节点成为了现在α点的左儿子的右子树根节点
4. 重新形成一颗新的AVL树

双旋转

对于情形2和3，单旋转无法修正被破坏的AVL树，对于图4-34子树Y太深，单旋转无法减低它的深度
对于情形2，例如图4-35(k1<k2<k3)，我们需要用到双旋转(让α的左儿子的右子树根节点跟α的左儿子做一次单旋转，旋转完后，α的左儿子的右子树就是α的左儿子，原来α的左儿子变成了α的左儿子的右子树根节点，然后现在的α的左儿子(也就是原来的α的左儿子的右子树根节点)跟α点做一次单旋转)，具体步骤就是
1. 向α的左儿子的右子树插入节点
2. 就双旋转后，让α的左儿子的右子树根节点(这里成为k2)旋转到α点(这里称为k3)的位置，α的左儿子(称为k1)成为k2的左儿子，k3成为k2的右儿子
3. 如果插入的是左节点，就让它成为k1的右儿子，如果插入的是右节点就让它成为k3的左儿子。
4. 然后就形成了新的AVL树
对于情形三(图4-36，k1<k2<k3)，跟情形二做法差不多只是方向改变了，我们需要用到双旋转(让α的右儿子的左子树根节点跟α的右儿子做一次单旋转，旋转完后，α的右儿子的左子树就是α的右儿子，原来α的右儿子变成了α的右儿子的左子树根节点，然后现在的α的右儿子(也就是原来的α的右儿子的左子树根节点)跟α点做一次单旋转)，具体步骤就是
1. 向α的右儿子的左子树插入节点
2. 就双旋转后，让α的右儿子的左子树根节点(这里成为k2)旋转到α点(这里称为k1)的位置，α的右儿子(称为k3)成为k2的右儿子，k1成为k2的左儿子
3. 如果插入的是左节点，就让它成为k1的右儿子，如果插入的是右节点就让它成为k3的左儿子。
4. 然后就形成了新的AVL树

代码:

//平衡查找树是其每个节点的左子树和右子树的高度最多差1的二叉查找树
struct AVL{
    int data;
    AVL* left;
    AVL* right;
    int height;  //节点高度
};

AVL* createNode(int data){
    auto p=new AVL;
    p->data=data;
    p->right=NULL;
    p->left=NULL;
    p->height=0;
    return p;
}

//防止出现空的高度
int Height(AVL* root){
    if(root==NULL){
        return -1;
    }else{
        return root->height;
    }
}

//左左情况单旋转函数
AVL* SingleRotatewithLeft(AVL* &k1){
    AVL* k2;
    k2=k1->left;
    k1->left=k2->right;
    k2->right=k1;
    k1->height= max(Height(k1->left), Height(k1->right))+1;
    k2->height= max(Height(k2->left), Height(k2->right))+1;
    return k2;
}

//右右情况单旋转函数
AVL* SingleRotatewithRight(AVL* &k1){
    AVL* k2;
    k2=k1->right;
    k1->right=k2->left;
    k2->left=k1;
    k1->height= max(Height(k1->left), Height(k1->right))+1;
    k2->height= max(Height(k2->left), Height(k2->right))+1;
    return k2;
}

//左右情况双旋转
AVL* DoubleRotatewithLeft(AVL* &k1){
    //非递归形式
//    AVL* k2;
//    AVL* k3;
//    k2=k1->left;
//    k3=k1->left->right;
//    k1->left=k3->right;
//    k2->right=k3->left;
//    k3->left=k2;
//    k3->right=k1;
//    k1->height=max(Height(k1->left), Height(k1->right))+1;
//    k2->height=max(Height(k2->left), Height(k2->right))+1;
//    k3->height=max(Height(k3->left), Height(k3->right))+1;
//    return k3;
    //递归形式，建议用递归，好记
    k1->left= SingleRotatewithRight(k1->left);   //k2跟k3单旋转
    return SingleRotatewithLeft(k1);       //k1跟现在的k2(原来的k3)单旋转
}

//右左情况双旋转
AVL* DoubleRotatewithRight(AVL* &k1){
    //非递归形式
//    AVL* k2;
//    AVL* k3;
//    k2=k1->right;
//    k3=k1->right->left;
//    k1->right=k3->left;
//    k2->left=k3->right;
//    k3->left=k1;
//    k3->right=k2;
//    k1->height=max(Height(k1->left), Height(k1->right))+1;
//    k2->height=max(Height(k2->left), Height(k2->right))+1;
//    k3->height=max(Height(k3->left), Height(k3->right))+1;
//    return k3;
    //递归形式
    k1->right= SingleRotatewithLeft(k1->right);       //k2跟k3单旋转
    return SingleRotatewithRight(k1);           //k1跟现在的k2(原来的k3)单旋转
}


//插入
AVL* insert(AVL* &root,int data){
    if(NULL==root){
        AVL* add= createNode(data);
        root=add;
    }else if(data<root->data){
        root->left= insert(root->left,data);
        //判断高度差
        if(2== Height(root->left)- Height(root->right)){
            //左左情况，情形1,单旋转
            if(data<root->left->data){
                root=SingleRotatewithLeft(root);
            }else{   //左右情况，情形2，双旋转
                root=DoubleRotatewithLeft(root);
            }
        }
    }else if(data>root->data){
        root->right= insert(root->right,data);
        if(2== Height(root->right)- Height(root->left)){
            //右右情况，情形4，单旋转
            if(data>root->right->data){
                root=SingleRotatewithRight(root);
            }else{    //右左情况,情形3，双旋转
                root=DoubleRotatewithRight(root);
            }
        }
    }
    //通过递归，从后序开始往上回，这样就能保证树的高度的正确性,这样子到了根节点就拿到了最大的高度
    root->height= max(Height(root->left), Height(root->right))+1;
    return root;
}


//查找
AVL* Search(AVL* root,int data){
    if(NULL==root){
        return NULL;
    }
    if(data<root->data){
        root->left= Search(root->left,data);
    }else if(data>root->data){
        root->right= Search(root->right,data);
    }else
        return root;
}


//查找最小值
int findmin(AVL* root){
    //递归形式
    if(NULL==root){
        return root->data;
    }
    if(root->left!=NULL){
        return findmin(root->left);
    }else{
        return root->data;
    }

    //非递归形式
//    if(NULL!=root){
//        while (root->left!=NULL){
//            root=root->left;
//        }
//        return root->data
//    }
//    return NULL;
}

//查找最大值
int findmax(AVL* root){
    //递归形式
//    if(NULL==root){
//        return NULL;
//    }
//    if(NULL!=root->right){
//        return findmax(root->right);
//    }else{
//        return root->data;
//    }

    //非递归形式
    if(NULL!=root){
        while (root->right!=NULL){
            root=root->right;
        }
    }
    return root->data;
}


//删除节点，删除操作也会导致AVL树平衡破坏，所以删除操作也需要对AVL树做判断
AVL* del(AVL* &root,int data){
    if(NULL==root){
        return NULL;
    }else if(data<root->data){
        root->left= del(root->left,data);
        if(2== Height(root->left)- Height(root->right)){
            if(data<root->left->data){
                root= SingleRotatewithLeft(root);
            }else{
                root= DoubleRotatewithLeft(root);
            }
        }
    }else if(data>root->data){
        root->right=del(root->right,data);
        if(2== Height(root->right)- Height(root->left)){
            if(data>root->right->data){
                root= SingleRotatewithRight(root);
            }else{
                root= DoubleRotatewithRight(root);
            }
        }
    }else if(root->left&&root->right){
        int temp= findmin(root);
        root->data=temp;
        root->right=del(root->right,temp);
    }else{
        AVL* p=root;
        if(NULL==root->left){
            root=root->right;
        }else if(NULL==root->right){
            root=root->left;
        }
        delete p;
    }
    if(root!=NULL)
        root->height=max(Height(root->left), Height(root->right))+1;
    return root;
}


//清空树
void destroy(AVL* &root){
    if(NULL==root){
        return;
    }
    destroy(root->left);
    destroy(root->right);
    delete root;
}

//打印，中序遍历
void inorderprint(AVL* root){
    if(NULL==root){
        return;
    }
    inorderprint(root->left);
    cout<<root->data<<" ";
    inorderprint(root->right);
}

伸展树

概念：

伸展树是一颗对任意一个节点被访问后，就经过一系列的AVL树的旋转操作将该节点放到根上的特殊二叉查找树。
伸展树能保证对树操作M次的时间复杂度为O(MlogN)，而当一个查找树的一个节点刚好处于查找树最坏的情形，我们每次访问都需要按照最坏情形的时间计算，这将耗费O(M*N)的时间，伸展树就是要将访问的节点进行移动，使它不一直存在一个地方，避免了多次操作最坏情形的出现，而伸展树访问的节点比较深，经过移动，对该节点的原先子树节点访问也会避免往更深处进行操作
伸展树不要求保留高度或平衡信息，因此能够节省空间以及简化代码

查找操作：

关于访问节点，然后对其进行一系列旋转操作，将该节点放到根上，我们需要对访问该节点的路径上(从下到上)每一个节点都需要和它们的父节点实施单旋转，直到将该节点推到根
但是如果只进行单旋转情况，并直接从下到上的话，则会浪费大部分时间
因此我们需要使用展开操作，而展开操作其实就是根据路径树的结构分情况进行操作
具体步骤：
1. 判断路径的结构，分为“之字形”和“一字形”
2. 如果是“之字形”，就需要对要访问的节点进行双旋转操作，如果访问的节点不是根的孙节点，则进行双旋转操作后，会将路径结构转换为“一字形”，然后再进行“一字形”操作，将其放在根上
3. 如果是“一字形”，就需要路径从下到上逐一进行单旋转操作，直至要访问的节点成为根才结束

删除操作：

我们可以通过访问要被删除的节点然后访问后进行删除，这样的话，被删除节点就会被推到根上，将该节点删除，树就会分为两颗子树T_L和T_R(左子树和右子树)
要想将T_L和T_R重新合成为一个树，就需要找到T_L的最大值，并进行旋转操作，将其作为T_L的根节点，而此时T**_L将是一个没有右儿子的树，然后将T_R的根节点作为现在T_L根节点的右儿子**

代码：

struct splay{
    int data;
    splay* left;
    splay* right;
};

splay* createNode(int data){
    auto p=new splay;
    p->data=data;
    p->left=NULL;
    p->right=NULL;
    return p;
}

splay* SingleRotatewithLeft(splay* &k1){
    splay* k2;
    k2=k1->left;
    k1->left=k2->right;
    k2->right=k1;
    return k2;
}

splay* SingleRotatewithRight(splay* &k1){
    splay* k2;
    k2=k1->right;
    k1->right=k2->left;
    k2->left=k1;
    return k2;
}

splay* DoubleRotatewithLeft(splay* &k1){
    k1->left= SingleRotatewithRight(k1->left);
    return SingleRotatewithLeft(k1);
}

splay* DoubleRotatewithRight(splay* &k1){
    k1->right= SingleRotatewithLeft(k1->right);
    return SingleRotatewithRight(k1);
}

//插入
splay* insert(splay* &root,int data){
    if(NULL==root){
        splay* add= createNode(data);
        root=add;
    }else if(data<root->data){
        root->left= insert(root->left,data);
    }else if(data>root->data){
        root->right= insert(root->right,data);
    }
    return root;
}

//查找
//因为查找data很有可能是相等的，所以要分开这种情况，如果root的下一个是要找的我们就往上返，令节点差为2个保证了判断路径结构的正确性
splay* search(splay* &root,int data){
    if(NULL==root||root->data==data){
        return root;
    }else if(data<root->data){
        root->left= search(root->left,data);
        if(data<root->left->data){
            root= SingleRotatewithLeft(root);
        }else if(data>root->left->data){
            root= DoubleRotatewithLeft(root);
        }
    }else if(data>root->data){
        root->right= search(root->right,data);
        if(data>root->right->data){
            root= SingleRotatewithRight(root);
        }else if(data<root->right->data){
            root= DoubleRotatewithRight(root);
        }
    }
    return root;
}

//查找最小值
int findmin(splay* root){
    if(NULL==root){
        return root->data;
    }
    if (root->left!=NULL){
        return findmin(root->left);
    }else{
        return root->data;
    }
}

//查找最大值
int findmax(splay* root){
    if(NULL==root){
        return root->data;
    }
    if(root->right!=NULL){
        return findmax(root->right);
    }else{
        return root->data;
    }
}

//删除树节点
void del(splay* &root,int data){
    search(root,data);
    if(NULL==root){
        return;
    }else{
        splay* t1=root->left;
        splay* t2=root->right;
        root->left=NULL;
        root->right=NULL;
        delete root;
        int temp= findmax(t1);
        t1= search(t1,temp);
        t1->right=t2;
        root=t1;
    }
}

void inorderprint(splay* root){
    if(NULL==root){
        return;
    }
    inorderprint(root->left);
    cout<<root->data<<" ";
    inorderprint(root->right);
}

//清空树
void destroy(splay* &root){
    if(NULL==root){
        return;
    }
    destroy(root->left);
    destroy(root->right);
    delete root;
}

B-树(B-tree)

概念：

B-树是一个非二叉树的多路平衡查找树(数据有序)，是一颗所有数据都存储在树叶节点上的树，不一定存储具体的数据，也可以是指向包含数据的记录的指针或地址
对于**阶为M(子节点数量在2和M之间)**的B-树具有一下结构特性：
1. 树的根节点或者叶子节点，或者子节点数的范围为[2,M]
2. B树每个结点关键字数量为[ceil(2/M)-1,M-1]
3. 除根外，所有非树叶节点的子节点数在[ceil(2/M),M]之间，ceil为向上取整函数
4. 所有的树叶都在相同的深度上
非叶子节点也有存储关键词的地方，这个地方是来表示范围的(如果要查找的数据小于该关键字就找关键字左边的子节点数据，大于就右边的子节点数据)，如果叶子节点数据按照升序排列，则非叶子节点的关键词有m-1个(m为该非叶子节点的子节点个数)，如果按照降序排列，则非叶子节点的关键字有m个，例如图4-58为升序排列的B树

插入操作

插入在叶子节点进行
向B树中插入数据，根据非叶子节点的关键字找到正确的存储数据的叶子节点。
如果节点内的数据小于M-1(M为阶数)，就根据排列规则插入；如果节点能够存储的数据已经满了，就进行分裂节点(叶子节点)
分裂节点操作步骤：
1. 先看看该叶子节点的关键字数量是否小于M-1(M为阶数)
2. 按顺序插入进去，节点的关键字数量如果大于M-1，就将该叶子节点分裂成两个叶子节点，两个叶子节点的数据各占原叶子节点的一半，中间的关键字(数据)作为根节点的关键字，剩下分成两部分的节点作为其(中间关键字形成的根节点)左右节点。当根节点大于M-1的时候，就分裂根节点！
3. 如果小于则根据插入的关键字大小按顺序插入。

删除操作

通过递归找到指定删除的节点
删除的关键字在非叶子节点上，就将其左边的指向叶子节点中的最大值跟要删除的关键字互换，就递归进去删除最大值。
删除的关键字在叶子节点上
1. 叶子节点的关键字个数大于ceil(M/2-1),直接删除
2. 叶子节点的关键字个数等于ceil(M/2-1),向父节点借关键字
递归返回上一层后检查该节点的关键字数，如果小于ceil(M/2-1)，就向父节点借关键字，合并该关键字的左右节点，然后不断返回上一层，不断地检查，向父节点借关键字，合并子节点直到返回到根节点。

代码：

#include <iostream>
#include <vector>
using namespace std;

struct btree{
    int level;  //树的阶数
    vector<int>keys;  //关键字数组
    vector<btree*>child; //子节点数组
    int keynum;   //节点的关键字数目
    btree* parent;    //子节点的父节点
};

//创造节点
btree* createNode(int level){
    auto p=new btree;
    p->level=level;
    p->keynum=0;
    p->parent= nullptr;
    for(int i=0;i<=p->level;i++){
        p->child.push_back(nullptr);
        p->keys.push_back(0);
    }
    return p;
}

//查找指定值，返回一个包含节点指针，和指定值的位置的对组
pair<btree*,int> find(btree* root,int key){
    int i;
    for(i=root->keynum;i>0;i--){
        if(key<root->keys[i]){
            continue;
        }else if(key>root->keys[i]){
            break;
        }else{
            return make_pair(root,i);
        }
    }
    pair<btree*,int>p=find(root->child[i],key);
    return p;
}

//分裂节点
void splitNode(btree* &root,btree* p,int index){
    if(p!=nullptr){
        if(p->keynum==p->level){
            //分裂节点
            int mid=p->keynum/2+p->keynum%2;
            btree* newnode= createNode(p->level);
            newnode->parent=p->parent;
            for(int j=root->keynum;j>index-1;j--){
                root->keys[j+1]=root->keys[j];
            }
            root->keys[index]=p->keys[mid];
            root->keynum++;
            for(int j=mid+1;j<=p->keynum;j++){
                newnode->keys[j-mid]=p->keys[j];
                newnode->keynum++;
            }
            p->keynum=p->keynum-newnode->keynum-1;
            int k;
            for(k=root->level-1;k>index-1;k--){
                root->child[k+1]=root->child[k];
            }
            k++;
            root->child[k]=newnode;
        }
    }
    if(root->keynum==root->level) {
        btree *newchild = createNode(root->level);
        int mid = root->keynum / 2 + root->keynum % 2;
        for (int i = mid + 1; i <= root->level; i++) {
            newchild->keys[i - mid] = root->keys[i];
            newchild->keynum++;
        }
        for (int j = newchild->keynum; j <= newchild->level; j++) {
            if(root->child[j])
                root->child[j]->parent=newchild;
            newchild->child[j - newchild->keynum] = root->child[j];
            root->child[j] = nullptr;
        }
        if (root->parent == nullptr) {
            btree *newnode = createNode(root->level);
            newnode->keys[1] = root->keys[mid];
            newnode->keynum++;
            root->keynum = root->level - newchild->keynum - 1;
            newnode->child[0] = root;
            newnode->child[1] = newchild;
            root->parent = newnode;
            newchild->parent = newnode;
            root = newnode;
        } else {
            newchild->parent = root->parent;
            root->keynum = root->level - newchild->keynum - 1;
            int a = root->parent->keynum;
            while (a > 0 && root->keys[mid] < root->parent->keys[a]) {
                root->parent->keys[a + 1] = root->parent->keys[a];
                root->parent->child[a + 1] = root->parent->child[a];
                a--;
            }
            a++;
            root->parent->keys[a] = root->keys[mid];
            root->parent->keynum++;
            root->parent->child[a] = newchild;
        }
    }
}

//插入节点
btree* insert(btree* &root,int key){
    if(0==root->keynum){
        root->keys[1]=key;
        root->keynum++;
        return root;
    }
    int index=root->keynum;
    while (index>0&&key<root->keys[index]){
        root->keys[index+1]=root->keys[index];
        index--;
    }
    index++;
    if(root->child[0]!=nullptr){
        btree* p;
        if(index==root->keynum){
            p=root->child[index+1];
        }else{
            p=root->child[index-1];
        }
        if(root->child[0]->child[0]!=nullptr){
            p= insert(p,key);
        }else if(root->child[0]->child[0]==nullptr){
            int i=p->keynum;
            while (i>0&&key<p->keys[i]){
                p->keys[i+1]=p->keys[i];
                i--;
            }
            i++;
            p->keys[i]=key;
            p->keynum++;
        }
        splitNode(root,p,index);
    }else{
        root->keys[index]=key;
        root->keynum++;
        splitNode(root, nullptr,-1);
    }
    return root;
}

//查找最大值
int findmax(btree* root){
    if(nullptr==root){
        return 0;
    }else if(root->child[0]!= nullptr){
        return findmax(root->child[root->keynum]);
    }
    return root->keys[root->keynum];
}

//合并节点
void merge(btree* &root,int key,int min,int n){
    int n1 = root->child[n-1]->keynum;
    int n2 = root->child[n]->keynum;
    if (n1 > min) {
        for (int j = n2; j > 0; j--) {
            root->child[n]->keys[j + 1] = root->child[n]->keys[j];
            root->child[n]->child[j + 1] = root->child[n]->child[j];
        }
        root->child[n]->child[1] = root->child[n]->child[0];
        root->child[n]->keys[1] = root->keys[n];
        root->keys[n]=root->child[n-1]->keys[n1];
        root->child[n]->child[0] = root->child[n-1]->child[n1];
        root->child[n-1]->child[n1] = nullptr;
        root->child[n-1]->child[0]->parent = root->child[n-1];
        root->child[n-1]->keynum--;
        root->child[n-1]->keys[n1] = NULL;
        root->child[n]->keynum++;
    } else if (n2 > min) {
        root->child[n-1]->keys[n1+1]=root->keys[n];
        root->keys[n]=root->child[n]->keys[1];
        root->child[n-1]->child[n1 + 1] = root->child[n]->child[0];
        root->child[n-1]->child[n1 + 1]->parent = root->child[n-1];
        root->child[n-1]->keynum++;
        for (int j = 1; j < n2; j++) {
            root->child[n]->keys[j] = root->child[n]->keys[j + 1];
            root->child[n]->child[j - 1] = root->child[n]->child[j];
        }
        root->child[n]->child[n2-1]=root->child[n]->child[n2];
        root->child[n]->keys[n2] = NULL;
        root->child[n]->child[n2] = nullptr;
        root->child[n]->keynum--;
    } else {
        root->child[n-1]->keys[n1+1]=root->keys[n];
        root->child[n-1]->keynum++;
        int n3 = n2 + n1+1;
        for (int j = n1 + 2; j <= n3; j++) {
            root->child[n-1]->keys[j] = root->child[n]->keys[j - n1-1];
            root->child[n-1]->child[j-1]=root->child[n]->child[j];
            root->child[n-1]->keynum++;
        }
        root->child[n]=nullptr;
        int index = root->keynum;
        while (index > n && key < root->keys[index]) {
            root->keys[index-1]=root->keys[index];
            root->child[index-1]=root->child[index];
            index--;
        }
        root->child[root->keynum]= nullptr;
        root->keynum--;
        if(root->parent== nullptr&&root->keynum==0){
            root->child[0]->parent= nullptr;
            root=root->child[0];
        }
    }
}

//删除节点
void del(btree* &root,int key){
    if(nullptr==root){
        return;
    }else{
        int i;
        for(i=root->keynum;i>0;i--){
            if(key<root->keys[i]){
                continue;
            }else if(key>root->keys[i]){
                del(root->child[i],key);
            }else{
                break;
            }
        }
        int min=(root->level/2+root->level%2)-1;
        if(0==i){
            if(root->child[i]->keynum>=min&&root->child[i+1]->keynum>=min){
                del(root->child[i],key);
            }
            i++;
        }
        if(root->child[0]!= nullptr){
            if(root->keynum>=min){
                if(root->keys[i]==key){
                    int temp= findmax(root->child[i-1]);
                    root->keys[i]=temp;
                    del(root->child[i-1],temp);
                    merge(root,key,min,i);
                }else if(key<root->keys[i]){
                    if(root->child[i-1]->keynum<min){
                        merge(root,key,min,i);
                    }
                }else{
                    if(root->child[i]->keynum<min){
                        merge(root,key,min,i);
                    }
                }
            }else{
                merge(root,key,min,i);
            }
        }else{
            int j;
            for(j=1;j<root->keynum;j++){
                if(root->keys[j]==key){
                    break;
                }
            }
            for(int d=j;d<root->keynum;d++){
                root->keys[d]=root->keys[d+1];
            }
            root->keys[root->keynum]=NULL;
            if(root->keynum>min){
                root->keynum--;
            }else{
                root->keynum--;
                int index=root->parent->keynum;
                for(int k=root->keynum;k>0;k--){
                    root->keys[k+1]=root->keys[k];
                }
                while (index>0&&key<=root->parent->keys[index]){
                    index--;
                }
                if(0==index){
                    root->keys[root->keynum+1]=root->parent->keys[1];
                }else{
                    root->keys[root->keynum+1]=root->parent->keys[index];
                }
            }
        }
    }
}

//中序遍历
void inorderprint(btree* root){
    if(nullptr!=root){
        int i;
        for(i=0;i<root->keynum;i++){
            if(root->child[i]!= nullptr){
                inorderprint(root->child[i]);
            }
            cout<<root->keys[i+1]<<" ";
        }
        if(root->child[i]!= nullptr)
            inorderprint(root->child[i]);
    }
}

红黑树(RB-tree)

概念：

红黑树是AVL树的变种，它是每一个节点或者着成红色，或者着成黑色的一棵二叉查找树。
对红黑树的操作在最坏情形下花费O(logN)时间，它的插入操作使用的是非递归形式实现
红黑树的高度最多是2log(N+1)

特性：

红黑树是具有着色性质的二叉查找树，也就意味着树的节点值是有序的，且每个节点只可能是红色或者黑色
红黑树的根是黑色的
如果一个节点是红色的，那么它的子节点必须是黑色的
从一个节点到一个空指针的每一条路径必须包含相同数目的黑色节点

自顶向下插入操作：

如果使用自底向上插入的话还需要进行逐步递归是他们保证满足红黑树特性，效率就降低了。
令X为新插入节点(在下面的第三操作中为当前节点)，P为X的父节点，G为P的父节点(也就是X的祖父节点)，GP为G的父节点(也就是P的祖父节点，X的曾祖父节点)
因为红黑树是一颗二叉查找树，因此在插入时需要查找要插入的值的正确位置，在这个查找路径中，如果遇到节点(X)为黑色而子节点全部为红色，我们就进行翻转操作，也就是将该节点(X)着成红色，子节点全部着成黑色。翻转后:
如果翻转后发现P和X节点都是红色就需要根据树的结构进行旋转操作
1. 如果X，P，G形成”一字形”，则对P的父节点G(也就是X的祖父节点)与P进行单旋转，并将新根也就是P着成黑色，新根的子节点都着成红色。
2. 如果X，P，G形成”之字形”，则对G与X节点进行双旋转，并将新根着成黑色(也就是X节点)，然后将新根的子节点着成红色
如果该节点(X)是黑色则继续将X下降，直到找到红色节点继续翻转，或者找到指定插入位置，找到指定位置也就是当前节点位置X就进行插入，新节点也是红色，需要重新判断其父节点是否为红色，为红色又需要进行翻转操作来调整。

自顶向下删除操作

自顶向下删除也需要保证红黑树的性质，插入是插入一片红色的叶子节点，那么反过来我们删除一个红色叶子节点就不会破坏红黑树性质，自顶向下插入的翻转操作是将红色节点减少，并将红色节点上浮，因为删除是插入的逆过程，因此删除的翻转操作就是要将树中的红色节点增多，并将红色节点下沉，这样我们删除红色叶子节点的概率更大，并且不会破坏红黑树性质
删除操作一共有5种情况需要解决
1. 要删除节点cur跟其兄弟节点s原本颜色为黑色，父亲节点p为红色
2. s的两个儿子都是红色，这样双旋转和单旋转都可以，这里优先选择ps单选转调整，情况1-case4
3. s的左儿子为红色，需要ps.l双旋转调整(s.l为s的左儿子)，情况2-case1
4. s的右儿子为红色，需要ps单旋转调整，情况3-case2
5. s有两个黑色儿子，直接cur,p,s颜色翻转操作调整，情况4-case3
6. p和cur为黑色，s为红色，需要交换sp节点的颜色，并且sp单旋转调整，情况5-case5
7. cur为红色，可以继续将cur下降，也就是当前cur指向原本cur的子节点，如果为红色继续下降，如果为黑色就判断是否需要操作
tomove指向要删除节点也就是目标节点，而p指向真正要删除的叶子节点，cur则while循环完后则是指向nil节点，因为将tomove标记完，就进行cur和p就查找tomove右子树的最小值节点进行删除，而while循环终止条件为cur==nil情况，因此p指向真正要删除的节点
找到tomove和p后，将tomove的data等于p的data，将p删除，因为p为叶子节点，将p的父节点指向nil。

情况2-case1

情况3-case2

情况4-case3

情况1-case4

情况5-case5

计算红黑树层数：

需要对log2(树中总共节点数+1)向上取整

代码：

1
2
3

int Height(const int count){
    return std::ceil(std::log2(count+1));
}

代码实现：

#include <iostream>
#include <queue>
#include <math.h>
#include <limits.h>
using namespace std;

typedef enum {red,black} colortype;

struct RBNode{
    int data;
    RBNode *left,*right,*parent;
    colortype color;   //颜色
    RBNode(const int val,RBNode* l,RBNode* r,RBNode* p,colortype c=red):data(val),
                                                                        left(l),right(r),parent(p),color(c){};
};

class RBtree{
public:
    RBtree(){
        nil=new RBNode(INT_MAX, nullptr, nullptr, nullptr,black);
        root= nullptr;
        t=new RBNode(INT_MIN,nil,nil,nil,black);
        size=0;
    }

    ~RBtree(){
        clear();
        delete t;
        delete nil;
    };
    void insert(const int val);      //插入操作
    void del(const int val);       //删除操作
    RBNode* find(const int val);   //查找操作
    void print();     //打印操作,层序遍历
    //清空操作
    void clear(){
        clear(root);
        root= nullptr;
        t->right=nil;
        size=0;
    }

protected:
    void overturnred(const int val,RBNode* &cur);    //翻转操作,将当前节点变成红色，子节点变成黑色
    void overturnblack(int val,RBNode* &cur);   //翻转操作，将当前节点变成黑色，子节点变成红色
    RBNode* SingleRotatewithleft(RBNode* &k1);
    RBNode* SingleRotatewithright(RBNode* &k1);
    RBNode* Rotate(const int val,RBNode* &k1){
        if(val<k1->data){
            return k1->left=val<k1->left->data? SingleRotatewithleft(k1->left): SingleRotatewithright(k1->left);
        }else{
            return k1->right=val<k1->right->data? SingleRotatewithleft(k1->right): SingleRotatewithright(k1->right);
        }
    }
    void clear(RBNode* &rt);
    // 计算红黑树层数
    int Height(int nodeCount) {
        // 红黑树的层数为 log2(nodeCount+1)
        return (int)std::ceil(std::log2(nodeCount+1));
    }
private:
    RBNode* root;
    RBNode* nil;   //空节点，color为黑色
    RBNode* t;  //根标记，用于删除操作的便捷
    int size;
};

RBNode* RBtree::SingleRotatewithleft(RBNode *&k1) {
    RBNode* k2;
    k2=k1->left;
    k1->left=k2->right;
    k2->right=k1;
    return k2;
}

RBNode* RBtree::SingleRotatewithright(RBNode *&k1) {
    RBNode* k2;
    k2=k1->right;
    k1->right=k2->left;
    k2->left=k1;
    return k2;
}

//翻转操作
void RBtree::overturnred(const int val,RBNode* &cur) {
    cur->color=red;
    cur->left->color=cur->right->color=black;
    RBNode* p=cur->parent;
    if(p->color==red){
        RBNode* g=p->parent;
        g->color=red;
        if((val<g->data)!=(val<p->data)){     //双旋转
            p= Rotate(val,g);
        }
        cur= Rotate(val,g->parent);
        cur->color=black;
    }
    root->color=black;
}


//插入操作
void RBtree::insert(const int val) {
    if(root== nullptr){
        root=new RBNode(val,nil,nil, t,black);
        t->right=root;
        size++;
        return;
    }
    RBNode *cur,*p;
    cur=p=root;
    while (cur!=nil){
        p=cur;
        if(cur->left->color==red&&cur->right->color==red){
            overturnred(val,cur);
        }
        cur=val<p->data?p->left:p->right;
    }
    if(cur!=nil){
        return;
    }
    cur=new RBNode(val, nil, nil, p);
    if(val<p->data){
        p->left=cur;
    }else{
        p->right=cur;
    }
    overturnred(val,cur);
    size++;
}

void RBtree::overturnblack(int val, RBNode *&cur) {
    cur->color=red;
    RBNode* p=cur->parent;
    RBNode* s=val<p->data?p->left:p->right;
    //case4:要删除节点cur跟其兄弟节点s原本颜色为黑色，父亲节点p为红色，s的两个儿子都是红色，这样双旋转和单旋转都可以，这里优先选择ps单选转
    //case2:要删除节点cur跟其兄弟节点s原本颜色为黑色，父亲节点p为红色，s的右儿子为红色情况，需要ps单旋转调整
    if(s->right->color==red){
        val=s->right->data;
    }
    //case1:要删除节点cur跟其兄弟节点s原本颜色为黑色，父亲节点p为红色，s的左儿子为红色的情况,需要ps.l双旋转调整
    else if(s->left->color==red){
        val=s->left->data;
    }
        //case3:要删除节点cur跟其兄弟节点s原本颜色为黑色，父亲节点p为红色，s有两个黑儿子(nil节点也是黑色),直接将颜色翻转即可
    else{
        //翻转操作
        if(s!=nil){
            s->color=red;
        }
        p->color=black;
        return;
    }
    if((val<s->data)!=(val<p->data)){
        Rotate(val,p);
    }
    RBNode* g=p->parent;
    Rotate(val,g);
    //将调整完的cur的新祖父也就是s或者s的左儿子变成红色，也就是删除完cur后将颜色调整到之前cur在翻转前的情况
    g->color=red;
    g->left->color=g->right->color=black;
}


void RBtree::del(const int val) {
    RBNode* tomove=nil;  //找到删除节点
    RBNode *g,*p,*s,*cur;
    g=p=t,s=t->left,cur=root;
    while (cur!=nil){
        //翻转颜色
        if(cur->left->color==black&&cur->right->color==black){
            overturnblack(val,cur);
        }else{
            g=p;p=cur;
            if(val<p->data){
                cur=p->left,s=p->right;
            }else{
                tomove=cur,cur=p->right,s=p->left;
            }
            //case5:此时肯定p和cur都为黑色，因为如果p为红色早就翻转了，s肯定是红色，将s变成黑色，p变为红色，sp单旋转调整
            if(cur->color==black){
                s->color=black;
                p->color=red;
                //单旋转完，cur新祖父变为s,将s重新更改
                g= Rotate(val,g);
                s=val<p->data?p->left:p->right;
                //调整完该情况就重新检查上述操作
                continue;
            }
            //else，cur一定为红色，则可以直接继续将cur继续下降
        }
        g=p;p=cur;
        if(val<p->data){
            cur=p->left,s=p->right;
        }else{
            tomove=cur,cur=p->right,s=p->left;
        }
    }
    root->color=black;   //保证红黑树性质2不被破坏，也就是根一定为黑色

    //判断是否找到真正要删除的节点，如果找不到就退出
    if(tomove==nil&&tomove->data!=val){
        cout<<"未找到要删除对应值的节点";
        return;
    }

    //tomove是要删除的节点，而p指向的是真正要删除的节点
    tomove->data=p->data;
    if(g->left==p) g->left=nil;
    else g->right=nil;
    delete p;
    size--;
}

RBNode* RBtree::find(const int val) {
    if(root!= nullptr){
        RBNode* cur=root;
        while (cur!=nil){
            if(cur->data==val) return cur;
            cur=val<cur->data?cur->left:cur->right;
        }
        if(cur==nil){
            cout<<"树中没有指定值节点"<<endl;
        }
    }
    return root;
}

void RBtree::print() {
    if(root== nullptr){
        cout<<"树为空"<<endl;
        return;
    }
    queue<RBNode*>q;
    q.push(root);
    int cnt=1;
    int ans=0;
    int h= Height(size);
    while (!q.empty()){
        if(ans==h+1) break;
        RBNode* cur=q.front();
        q.pop();
        if(cur== nullptr){
            cout<<"null"<<" ";
            continue;
        }
        q.push(cur->left);
        q.push(cur->right);
        if(cur->color==red){
            cout<<"\033[31m"<<cur->data<<"\033[0m"<<" ";
        }else if(cur==nil) cout<<"nil"<<" ";
        else cout<<cur->data<<" ";
        if(cnt==pow(2,ans)){
            cout<<endl;
            cnt=0,ans++;
        }
        cnt++;
    }
    return;
}


void RBtree::clear(RBNode* &rt) {
    if(rt!=nil){
        clear(rt->left);
        clear(rt->right);
        delete rt;
        rt=nil;
    }
    return;
}

int main() {
    RBtree rBtree;
    rBtree.insert(30);
    rBtree.insert(15);
    rBtree.insert(65);
    rBtree.insert(10);
    rBtree.insert(20);
    rBtree.insert(5);
    rBtree.insert(60);
    rBtree.insert(70);
    rBtree.insert(50);
    rBtree.insert(64);
    rBtree.insert(66);
    rBtree.insert(85);
    rBtree.insert(40);
    rBtree.insert(55);
    rBtree.insert(63);
    rBtree.insert(80);
    rBtree.insert(90);
    rBtree.insert(45);
    rBtree.del(65);
    rBtree.del(50);
    rBtree.del(30);
    rBtree.print();
    return 0;
}

散列表(哈希表)

概念

散列(hashing)是一种用于以常数平均时间执行插入、删除和查找的技术。
散列不支持排序，所以散列表是无序的。
散列是一种存储结构(实质是一个数组，用于存储关键字值，关键字的存储下标就是根据关键字映射(通过散列函数也就是哈希函数)出来的位置)，**根据记录的存储位置与关键字之间存在对应关系(散列(哈希)函数)**，–也就是通过哈希函数对关键字值的处理，得出该关键字值在散列表中的存储位置

散列函数(哈希函数)

散列函数特性：

简单快速

均匀性：需要让关键字均匀分布在哈希表中

用于将关键字值映射到数组中的一个函数，一般的方法为关键字%表的大小
该函数我们需要在单元之间均匀地分配关键字，好的办法就是表的大小是素数，这将让散列函数算起来简单并且关键字分配比较均匀
如果关键字是字符串的时候，通常我们将字符串中的每个字符转换为ASCII码并求和，得到一个int型的数，就可以对它进行散列函数映射到哈希表中，一个更好的方法是：根据horner法则，计算一个（32的）多项式函数。
多个关键字映射到同一个数组下标或者数组单元的情况叫做冲突

常用哈希函数：

关键字是字符串：根据horner法则，计算一个（32的）多项式函数。

介绍：如果关键字特别长，那么散列函数计算起来会花过多的时间，而且前面的字符还会左移出最终的结果。因此这样情况下，不使用所有的字符。此时关键字的长度和性质会影响选择。例如只取奇数位置上的字符来实现散列函数。这里的思想是用计算散列函数省下来的时间来补偿由此产生的对均匀分布函数的轻微干扰

int hash(const char* key,int tablesize){
    unsigned int hashval=0;
    while(*key!='\0'){
        hashval=(hashval<<5)+*key;    //右移五次等于乘2的五次方也就是32
    }
    return hashval%tablesize;
}

直接寻址法
介绍:取关键字或关键字的某个线性函数值为散列地址，即H(key)=key或者H(key)=a*key+b（a,b为常数）。
举例:[‘A’,‘B’,‘D’,‘A’,‘C’,‘E’,‘F’,‘C’] ,求该字符数组里每个字符的出现次数(数组中只有大写字母)。
分析:我们可以知道’A’-‘Z’的ASCLL码是65-90,则哈希函数可以通过直接寻址法H(key)=key-‘A’（对应定义中的a=1,b=-‘A’即65）,这样针对每一个key,都可以将它的H(key)值当成数组下标放在一个长度为26的int数组中统计长度
假设字符数组为a,int数组为b。即b[a[i]-‘A’]++(i表示a数组的下标索引)。
结果
b[0]=2(代表A出现两次)；b[1]=1(代表B出现一次)，b[2]=2(代表C出现两次)…
数字分析法
介绍:分析一组数据中相同位(个位,十位,百位…)的数字出现频率，如果该位数字出现结果较为集中，如果取其作为构造散列地址的依据则很容易出现哈希冲突,反之，如果该位数字出现结果较为平均,则取其作为构造散列地址的依据则不容易出现哈希冲突。
举例:某公司招聘了一些实习生,其生日分别为[19990104,20000910,20000315,20001128,20001014,19990413,19990920,20000517],对其进行hash处理。
分析
如果取8位数作为散列地址,虽然很难出现哈希冲突,但是空间浪费很大，因此考虑只取其中几位作为散列地址,即能减少空间浪费又能降低哈希冲突的可能性,观察上面8组数据，前4位集中在1999,2000，如果取前4位则很容易出现哈希冲突，而后四位分布相对分散，不容易出现哈希冲突，因此取后四位比较符合。
结果
H(19990104)=104,H(20000910)=910,H(20000315)=315…
折叠法
介绍:折叠法是把关键字值分成自左向右分成位数相等的几部分，每一部分的位数应与散列表地址(也就是数组下标)的位数相同，只有最后一部分的位数可以短一些。把这些部分的数据叠加起来（去除进位），就可以得到关键字值的散列地址。
有两种叠加方法：
(1)**移位法(shift floding)**：把各部分的最后一位对齐相加。
(2)**分界法(floding at the boudaries)**：沿各部分的分界来回折叠(即第偶数个加数和移位法反过来)，然后对其相加。
举例:key=1234791，散列地址为2位
分析
将key分成12,34,79,1四部分
(1)移位法:12+34+79+1
(2)分界法:12+43+79+1(即第偶数个加数和移位法反过来)
结果
(1)移位法:H(1234791)=35(相加为135，去除进位1)
(2)分界法:H(1234791)=44(相加为144，去除进位1)
平方取中法
介绍：当无法确定关键字中哪几位分布较均为时，可以求出关键字的平方值，然后按需要取平方值的中间几位作为散列地址。这是因为:平方后中间几位和关键字中每一位都有关，故不同关键字会以较高的概率产生不同的散列地址。
举例:关键字序列:{3213,3113,3212,4312}。
分析:
3213^2=10323369
3113^2=9690769
3212^2=10316944
4312^2=18593344
取平方值中间4位为散列地址(3113的平方值前面补0凑成8位)
结果
H(3213)=3233,H(3113)=6907,H(3212)=3169,H(4312)=5933

解决冲突

负载因子(local factor)为散列表中的元素个数与散列表的大小的比值。
1. 负载因子为0.7-0.75比较合理，负载因子在哈希表中的意义就是当你这个哈希表的负载因子达到你设定的值就进行扩容为后面的存储更多数据做准备。
2. java封装的数据结构也是使用的分离链接法，但是其不同的是，他不是完全的数组加链表的形式，它是当链表达到一定长度时就将链表转化为红黑树。
3. java封装的哈希表的数据结构的负载因子为什么为0.75呢
- 是因为当负载因子等于1的时候也就意味着关键字均匀分布并且几乎存满了哈希表(数组的每个下标都有关键字填充)才进行扩容的情况，关键字数量多就会造成大量的哈希冲突，这也造成了数组加红黑树的情况出现的更多，而这样底层的红黑树变得更加复杂，大大降低了查询速度，这种情况就是牺牲了时间来保证空间的利用率.
- 当负载因子为0.5时，也就意味着当数组中的元素达到一半就开始扩容，虽然填充的元素少了，哈希冲突减少了，查询速度提高了，但是空间利用率降低了，原本1m的数据现在需要2m的空间存储，这就是牺牲空间来保证时间的效率
- 当负载因子为0.75，时间和空间达到了平衡，所以java封装的哈希表结构的负载因子默认为0.75.
分离链接法：就是一个数组加链表来解决冲突问题的，将映射到同一个数组下标的所有关键字保留在一个表中，而这个表就是链表，将同一个数组下标的所有关键字通过链表连接起来，该方法使用的比较多。分离链接散列的基本法则是使得表的大小尽量与预料的关键字个数差不多(也就是负载因子约等于1)，这样也就是能够保证关键字均匀分布在散列表中，使得查找时间减少。
1. 插入：插入时可以选择头插法插入链表中，如果插入重复元素，定义链表时可以选择多增加一个计数的域，来记录这个元素出现次数
2. 查找：对要查找的关键字进行哈希函数的操作，得到映射的数组下标，然后在该下标指向的链表中查找指定关键字
3. 删除：找到对应的数组下标，遍历链表找到要删除的关键字的节点，然后判断它的存储个数(cnt)，如果大于1就让cnt-1，如果等于1就是删除该节点
4. 缺点：需要指针，给新单元分配空间需要时间，导致算法的速度减慢，与此同时还需要对链表的数据结构进行实现。

//分离链接法
//定义链表
template<class T>
struct listnode{
    T data;
    listnode* next;
    int cnt;
};


template<class T>
class hashtable{
public:
    int isPrime(int num) {
        if(num <= 1) {
            return 0;
        }
        int i;
        for(i = 2; i*i <= num; i++) {
            if(num % i == 0) {
                return 0;
            }
        }
        return 1;
    }
    //找出大于tablesize最近的素数
    int prime(int size){
        while (!isPrime(size)) {
            size++;
        }
        return size;
    }
    float loadfactor(){
        return (float)count/(float)tablesize;
    }
    listnode<T>* createNode(T data){
        listnode<T>* list=(listnode<T>*)malloc(sizeof(listnode<T>));
        list->data=data;
        list->next= nullptr;
        list->cnt=1;
        return list;
    }
    hashtable(int size){
        this->count=0;
        this->tablesize=prime(size);
        for(int i=0;i< this->tablesize;i++){
            listnode<T>*list=(listnode<T>*)malloc(sizeof(listnode<T>));
            list->next=NULL;
            list->cnt=0;
            v.push_back(list);
        }
    }
    //散列函数(哈希函数)，用于将关键字处理得到映射的数组下标，这里用了简单的哈希函数，在不同场景有不同的函数设计
    int hash(T data){
        return data%this->tablesize;
    }

    listnode<T>* findnode(listnode<T>* head,T data){
        if(head!= nullptr){
            listnode<T>* p=head;
            while (p!= nullptr){
                if(p->data==data){
                    return p;
                }
                p=p->next;
            }
        }
        return NULL;
    }

    void insert(T data){
        if(loadfactor()>1||loadfactor()==1){
            int size= this->tablesize;
            this->tablesize=prime(count*2);
            for(int i=size;i< this->tablesize;i++){
                listnode<T>*list=(listnode<T>*)malloc(sizeof(listnode<T>));
                list->next=NULL;
                list->cnt=0;
                v.push_back(list);
            }
        }
        int index= hash(data);
        if(nullptr==v[index]->next){
            listnode<T>* list= createNode(data);
            v[index]->next=list;
        } else{
            listnode<T>* tail=findnode(v[index]->next,data);
            if(tail==NULL){
                listnode<T>* list= createNode(data);
                listnode<T>* p=v[index]->next;
                v[index]->next=list;
                v[index]->next->next=p;
            }else{
                tail->cnt++;
            }
        }
        this->count++;
    }
    listnode<T>* find(T data){
        int index= hash(data);
        listnode<T>* p=findnode(v[index]->next,data);
        return p;
    }
    void print(){
        for(int i=0;i< this->tablesize;i++){
            listnode<T>* p=v[i]->next;
            cout<<"索引为"<<i<<":"<<" ";
            if(p== nullptr){
                cout<<endl;
                continue;
            }
            while (p!= nullptr){
                for(int j=0;j<p->cnt;j++)
                    cout<<p->data<<" ";
                p=p->next;
            }
            cout<<endl;
        }
    }
    void del(T data){
        int index= hash(data);
        listnode<T>* tail=v[index]->next;
        listnode<T>* p=v[index];
        while (tail->next!= nullptr){
            if(tail->data==data){
                break;
            }
            p=tail;
            tail=tail->next;
        }
        if(tail->data==data){
            if(tail->cnt>1){
                tail->cnt--;
                count--;
                return;
            }
            p->next=tail->next;
            delete tail;
            count--;
        }
        return;
    }
private:
    int count;
    vector<listnode<T>*>v;
    int tablesize;
};

开放定址法：该算法的结构就只有一个数组。如果有哈希冲突发生，那么就尝试选择其他的单元，直到找到空单元就进行插入。函数F是冲突解决的办法。对于开放定址法来说，负载因子应该低于0.5（只要表足够大，这样总能够找到一个空单元才能解决冲突），而该方法的删除操作建议是懒惰删除，也就是删除对应的值，但是数组的长度不会变。开放地址法也分为三个方法：
1. 线性探测法：通过哈希函数，找到关键字对应的数组下标，如果该单元非空，则我们进行向后查找(也就是在这个数组下标的后面进行查找空单元)，如果达到数组的最后一个单元都没找到空单元就返回到数组的第一个单元(也就是数组下标为0)再进行向后查找；如果该单元是空单元，则直接进行插入。如果表可以多于一半被填满，线性探测就不是好方法，如果元素较少使用线性探测法，如果数据量大就不建议使用
2. 平方探测法：是用来消除线性探测中一次聚集问题的冲突解决方法，平方探测法就是冲突函数为二次函数的探测方法，流行的选择是F(i)=i²(i为冲突次数)，通过哈希函数，找到关键字对应的数组下标，如果该单元是空的就插入，如果该单元非空，则该单元的冲突次数+1也就是i=1，通过F(i)计算得到向后移动的单元，所以算出等于1就向后移动一单元，如果所处的单元还是非空，则冲突次数再次+1,然后再向后移动F(i)位，i为2则移动四个单元(移动的单元不是从所处的单元在移动4位，而是从原本的单元也就是开始通过哈希函数计算出来的单元开始移动四位)，如此递推下去，直到找到空的单元，如果达到最后一单元，则从数组下标0重新开始。
3. 双散列：双散列的意思是映射数组下标时，使用两个散列函数进行计算映射位置，对于双散列，流行的一种选择是F(i)=i*hash₂(X)，hash₂(X)为第二个哈希函数，i为探测次数，也就是当我插入时，通过第一个哈希函数计算出映射的数组下标，如果该单元是空单元，就直接插入，如果非空，则通过第二哈希函数计算向后移动的位数，比方说，当我插入映射到数组下标8的位置，但是下标为8的单元非空，则需要向后移动，而此时i为1，然后通过哈希2计算出移动位置，如果移动后的单元还是非空，则此时i等于2，计算出移动位数后，需要重新回到数组下标8进行移动，直到找到空单元为止。哈希2函数的选取很重要，如果选择的不好则将会是灾难性的，像hash₂(X)=R-(X mod R)这种函数会比较好，R的选择需要根据情况设定，然后保证表的大小为素数很重要
再散列：对于使用平方探测的开放定址法，如果表的元素填的太满，性能则会大大降低，则我们就新建立一个原来的散列表的两倍大小的散列表(并且使用一个相关的新散列函数)，然后扫描原始的散列表，通过新的散列函数计算每个已经插入在原表中的数据的新的映射下标并将其插入新表之中，双散列建立的时机可以实时根据负载因子决定，当负载因子到达指定值就进行再散列操作。

//开放定址法
class hashtable{
public:
    bool isprime(int n){
        if(n<=1)
            return false;
        for(int i=2;i*i<n;i++){
            if(n%i==0){
                return false;
            }
        }
        return true;
    }

    int prime(int size){
        while (!isprime(size)){
            size++;
        }
        return size;
    }
    hashtable(int size){
        this->tablesize= prime(size);
        for(int i=0;i<tablesize;i++){
            v.push_back(NULL);
        }
    }
    //线性探测法
    int hash1(int key){
        int index=key%tablesize;
        int cnt=0;
        while (v[index]!=NULL){
            if(cnt>1){
                cout<<"没有空余的位置插入"<<endl;
                return -1;
            }
            if(index==tablesize-1){
                cnt++;
                index=0;
                continue;
            }
            index++;
        }
        return index;
    }

    //平方探测法
    int hash2(int key){
        int index=key%tablesize;
        int cnt=0,n=0,i=0;
        while (v[index]!=NULL){
            if(i>1){
                cout<<"没有空余的位置插入"<<endl;
                return -1;
            }
            cnt++;
            cnt*=cnt;
            index=index+cnt-n;
            n=cnt;
            if(index>tablesize-1){
                i++;
                index=index-tablesize;
            }
        }
        return index;
    }
    float localfactor(){
        return (float)count/(float)tablesize;
    }
    void insert(int key){
        if(localfactor()>0.5||localfactor()==0.5){
            int size=tablesize*2;
            for(int i=tablesize;i<size;i++){
                v.push_back(NULL);
            }
            tablesize=size;
        }
        int index=hash2(key);
        if(index!=-1){
            v[index]=key;
            count++;
        }
    }
    int find(int key){
        int index=key%tablesize;
        int size=tablesize;
        for(int i=index;i<=size+index;i++){
            if(v[i]==key){
                return i;
            }
            if(i==tablesize-1){
                size=0;
                i=0;
            }
        }
        cout<<"为找到"<<endl;
        return -1;
    }
    void del(int key){
        int index=find(key);
        if(index!=-1){
            count--;
            v[index]=NULL;
        }
        return;
    }
    void print(){
        for(int i=0;i<tablesize;i++){
            cout<<"索引为"<<i<<": "<<v[i]<<endl;
        }
    }

private:
    int count;
    vector<int>v;
    int tablesize;
};

可扩散列：当处理数据量太大以至于装不进主存的情况下，此时主要考虑是检索数据所需的磁盘存取次数，而可扩散列，它允许用两次磁盘访问就能够执行一次查找操作，插入操作也是很少的磁盘访问。可扩散列有点类似于B树的结构。可扩散列无法存在重复关键字
1. 在可扩散列中，我们用D表示根所使用的比特数(也称其为目录)，目录的所存的元素个数为2^D，d_L为树叶节点中的元素共有的最高位位数，因此d_L应该小于等于D
2. D就是用来区分存储节点的位置的依据，例如我们的数据由前俩个比特进行区分，则该结构的节点应该能够存储4个元素，然后d_L应该等于2，因为数据需要根据前两位跟目录的元素进行匹对来存储到对应的节点，因此它的共有最高位应该为2，如图5-23
3. 如果插入数据时，节点元素已经满了，我们就需要进行分裂节点来存储，例如上述讲的图5-23当D=2时，我们插入100100时，发现10为根节点的叶子节点元素已经满了，就分裂该叶子节点，分裂完发现根节点也满了则需要对根节点分裂，因此根节点分裂后应该以3比特进行将数据分开存储，因为2³等于8，因此根节点分裂后为8个元素(如图5-24)，但是叶子节点只有5个，因此有一些根节点跟其他根节点共用一个叶子节点，直到再次插入让它们共用的节点，才进行更改根节点指向(如图5-25)。

堆(优先队列)

二叉堆

概念：

优先队列是一个根据优先性而先去执行操作的一种特殊队列，平常队列是先进先出，但是优先队列是根据优先级选择先出的元素。优先队列的主要操作有插入和删除最小值
堆(heap)通常是指二叉堆，因为二叉堆的使用次数最频繁，所以我们平常认为的堆就是二叉堆
二叉堆：二叉堆是由一颗完全二叉树实现的，完全二叉树是**一颗底层必须从左往右依次插入且底层以上的节点都是填满的树(最后一层也就是叶子节点可以不是填满的，但是已经插入的元素必须是从左到右的中间不空缺元素的)**称为完全二叉树
完全二叉树是一个很有规律的树，因此用一个动态数组实现是效率最好的选择，在动态数组中是按照从上到下从左到右依次插入数组中，数组下标为0处不放元素。
用数组实现的完全二叉树的性质有：
1. 对于数组中任意一个位置i上的元素，其左儿子在数组位置2i上，右儿子在左儿子后的单元也就是数组下标为(2i+1)的位置，它的父亲在i/2的位置上。
2. 数组下标为0的地方是不放我们要存的元素的

性质：

堆也就是通常认为的二叉堆(binary heap)，是由一颗完全二叉树实现的
堆中的主要操作有插入和删除最小值操作，堆的删除其实就是删除最小值而不是删除指定值
堆有堆序性质，也就是堆中的任意子树也是一个堆，因此任意节点就应该小于它的子节点，因为堆需要快速查找最小元，因此我们将最小元放在根节点上。
其结构体应该包含一个数组(动态)，堆中存储的有效元素个数，数组的容量以便于扩容

最大堆/大根堆：任意节点应该大于它的所有后裔

最小堆/小根堆：任意节点应该小于它的所有后裔

**插入操作(上浮)**：

先遵从堆从上到下，从左到右依次插入，我们将数据按照这个准则插入到数组。
然而，插入后，我们还需要进行检查这个堆是否有堆序性，如果没有就需要进行调整
插入数据跟根节点进行比较，如果根节点的值比插入数据大，就需要交换，然后一路向上检查比较，直到根节点。

**删除操作(下沉)**：

堆的删除操作是删除最小值的操作，而不是删除指定值的操作
我们创建堆时，都将最小值放到根节点，因此删除我们只需要将根节点删除掉
但是删除根节点后，我们的堆序性就无法保证，如何保证堆序性以及堆的性质(也就是完全二叉树的性质)呢
我们需要将根节点的值与叶子层的最右边元素进行交换，然后删除交换后处在叶子节点(也就是原来的根节点)的节点，然后让现在的根节点跟左右子节点的最小节点比较，如果大于就交换，直到检查到叶子节点，则就调整成功了。

构建堆

构建堆的操作就是将一个无序的树，构造成一个堆
一个堆满足完全二叉树的特性以及堆序性，因此我们需要对这个无序树进行调整，让其成为一个堆。

实现代码：

class heap{
public:
    heap(int maxsize){
        key=new int[maxsize+1];
        key[0]=0;
        for(int i=1;i<maxsize+1;i++){
            key[i]=0;
        }
        size=0;
        capacity=maxsize;
    }
    int find(int data){
        for(int i=1;i<size;i++){
            if(key[i]==data){
                return i;
            }
        }
        cout<<"没有找到"<<endl;
        return -1;
    }
    void adjust(int data){
        key[size+1]=data;
        int index=size+1;
        while(index>0){
            int i=index;
            index=index/2;
            if(key[index]>key[i]){
                int temp=key[index];
                key[index]=key[i];
                key[i]=temp;
            }
        }
    }
    void insert(int data){
        if(size==capacity){
            int *an=new int[2*capacity];
            capacity=capacity*2;
            for(int i=0;i<=size;i++){
                an[i]=key[i];
            }
            delete[] key;
            key=an;
        }
        if(key[1]==0){
            key[1]=data;
        }else{
            adjust(data);
        }
        size++;
    }
    void deladjust(int index){
        if(index*2<=size){
            int mn;
            if(key[index*2+1]==NULL){
                mn=index*2;
            }
            else if(key[index*2]>key[index*2+1]){
                mn=index*2+1;
            }else{
                mn=index*2;
            }
            if(key[index]>key[mn]){
                int temp=key[index];
                key[index]=key[mn];
                key[mn]=temp;
            }
            deladjust(mn);
        }
        return;
    }
    void delmin(){
        key[1]=key[size];
        key[size]=0;
        size--;
        deladjust(1);
    }
    void destroy(){
        for(int i=1;i<=size;i++){
            key[i]=0;
        }
        size=0;
        cout<<"成功清除堆中数据"<<endl;
    }
    void print(){
        int cnt=1,ans=1;
        for(int i=1;i<=size;i++){
            cout<<key[i]<<" ";
            if(i==ans){
                cout<<endl;
                ans=pow(2,cnt)+i;
                cnt++;
            }
        }
    }
private:
    int *key;    //动态数组，用来存储树节点的元素
    int size;    //堆中存在的有效元素个数
    int capacity;    //数组容量
};

d-堆

概念：

d-堆是二叉堆的简单推广，它的所有的节点都有d个子节点，d-堆的底层也是由一颗完全树构成的，二叉堆是由完全二叉树构成，3-堆则就是由完全三叉树构成
当堆太大不能完全装入主存的时候，d-堆就很有用，因为d-堆能够以与B-树大致相同的方式发挥作用
d-堆的高度比较浅
d-堆的性质跟二叉堆相同。因为二叉堆是d-堆的一种特殊情况。

左式堆

概念：

左式堆是一种能够高效的支持合并操作的堆，左式堆的底层也是由二叉树实现，但是左式堆不是平衡的(不由完全二叉树实现的)，左式堆趋向于不平衡。
左式堆也像二叉堆一样拥有着堆的特性(有序性和结构性)，左式堆是最小堆
左式堆是一个拥有堆序性的二叉树(不是二叉堆)加上NPL特性的一棵树，任意节点X的NPL(X)(零路径长)为从X到一个没有两个儿子的节点的最短路径的长，因此，具有0个或1个儿子的节点的Npl为0，而Npl(NULL)=-1.

性质：

任意一个节点的零路径长比它的子节点的零路径长的最小值+1
对于堆中的每一个节点X，左儿子的零路径长大于等于右儿子的零路径长
在右路径上有r个节点的左式树必然至少有2^r-1个节点
对左式堆的右路径的插入和合并操作可能会破坏左式堆的性质，需要进行调整

合并操作

插入其实就是合并的一个特殊情况
如果两个左式堆合并，有一个堆为空就返回另外一个堆，否则比较两个堆的根值
递归进去，我们将大的根值的堆与小的根值的堆的右子堆合并
然后递归返回后，**将新的堆作为原来小的根值的堆的右孩子(也叫合并)**。
如果这样形成的堆的右子堆的零路径长大于左子堆的，就将左子堆跟右子堆交换，并且更新零路径长，就完成了合并的操作。

实现代码：

#include <iostream>
using namespace std;

struct heapNode{
    int data;    //数据
    heapNode* left;    //左子节点指针
    heapNode* right;   //右子节点指针
    int Npl;     //零路径长
};

class leftheap{
public:
    leftheap(){
        root=new heapNode;
        root->left= nullptr;
        root->right= nullptr;
        root->data=INT_MAX;
        root->Npl=0;
    }
    heapNode* createNode(int data){
        auto p=new heapNode;
        p->data=data;
        p->left= nullptr;
        p->right= nullptr;
        p->Npl=0;
        return p;
    }
    heapNode* merge(heapNode* h1,heapNode* h2){
        if(h1->left== nullptr){
            h1->left=h2;
        }else{
            h1->right= findmerge_node(h1->right,h2);
            if(h1->left->Npl<h1->right->Npl){
                heapNode* p=h1->left;
                h1->left=h1->right;
                h1->right=p;
            }
            h1->Npl=h1->right->Npl+1;
        }
        return h1;
    }
    heapNode* findmerge_node(heapNode* h1,heapNode* h2){
        if(nullptr==h1){
            return h2;
        }else if(nullptr==h2){
            return h1;
        }
        if(h1->data<h2->data){
            return merge(h1,h2);
        }else{
            return merge(h2,h1);
        }
    }
    void insert(int data){
        heapNode* add= createNode(data);
        if(root->data==INT_MAX){
            root=add;
        } else
            root=findmerge_node(root,add);
    }
    void delmin(){
        if(root== nullptr){
            return;
        }
        heapNode* h1=root->left;
        heapNode* h2=root->right;
        delete root;
        root= findmerge_node(h1,h2);
    }
    int getmin(){
        return root->data;
    }
    heapNode* print(heapNode* p){
        if(p!= nullptr){
            cout<<p->data<<" ";
            print(p->left);
            print(p->right);
        }
        return p;
    }
    void print(){
        if(root== nullptr){
            return;
        }
        print(root);
    }
private:
    heapNode* root;
};

斜堆

概念：

斜堆是左式堆的自调节形式，斜堆和左式堆间的关系类似于伸展树和AVL树间的关系
斜堆是具有堆序性的二叉树，但是不存在对树的结构限制
不同于左式堆，关于任意节点的零路径长的任何信息都不保留，因为斜堆的右路径在任何时刻都可以任意长

合并操作

斜堆的合并大概都跟左式堆的合并操作一样，但是交换操作不一样，斜堆的交换是无条件的
就是说当进行将大的根值的堆与小的根值的堆的右子堆合并后，我们就需要进行左子树跟右子树交换的操作，并不是只有到最后小的根值的堆跟新的堆合并后在进行交换
就是每个合并的步骤就需要交换左右子树。

实现代码：

struct heapNode{
    int data;
    heapNode* left;
    heapNode* right;
};

class skewheap{
public:
    skewheap(){
        root=new heapNode;
        root->data=INT_MAX;
        root->left= nullptr;
        root->right= nullptr;
    }
    heapNode* createNode(int data){
        auto p=new heapNode;
        p->data= data;
        p->left= nullptr;
        p->right= nullptr;
        return p;
    }
    heapNode* merge(heapNode* h1,heapNode* h2){
        if(h1->left== nullptr){
            h1->left=h2;
        }else{
            h1->right= findmerge_node(h1->right,h2);
            heapNode* p=h1->left;
            h1->left=h1->right;
            h1->right=p;
        }
        return h1;
    }
    heapNode* findmerge_node(heapNode* h1,heapNode* h2){
        if(nullptr==h1){
            return h2;
        }
        if(nullptr==h2){
            return h1;
        }
        if(h1->data<h2->data){
            return merge(h1,h2);
        }else{
            return merge(h2,h1);
        }
    }
    void insert(int data){
        heapNode* add= createNode(data);
        if(root->data==INT_MAX){
            root=add;
        }else
            root=findmerge_node(root,add);
    }
    void delmin(){
        if(nullptr==root){
            return;
        }
        heapNode* h1=root->left;
        heapNode* h2=root->right;
        delete root;
        root= findmerge_node(h1,h2);
    }
    int getmin(){
        return root->data;
    }
    heapNode* print(heapNode* p){
        if(p!= nullptr){
            cout<<p->data<<" ";
            print(p->left);
            print(p->right);
        }
        return p;
    }
    void print(){
        if(root== nullptr){
            return;
        }
        print(root);
    }
private:
    heapNode* root;
};

图

概念：

一个图(graph)G=(V,E)由顶点集V和边集E组成，每一条边就是一个点对(u,w)，其中u，w∈V，有时边称作弧，如果点对是有序的，那么组成的图叫做有向图，反之就是无向图。有时候边还具有第三种成分，称作权或值。
图中的一条路径是一个顶点序列w1,w2,w3….wn，使得(w_i,w_i+1)∈E，1<i<N；这样一条路径的长度就为该路径的边数。如果图中含有一条从顶点到自身的边(u,u)，那么路径v,v称作为环。而我们讨论的图一般是无环的。
简单路径是一条路径上的所有顶点都是互异的，但第一个顶点和最后一个顶点可能相同。
当一个长至少为1的路径中的第一个顶点等于最后一个顶点时，则称为圈，对于无向图的圈，要求边是互异的，意思就是u到v跟v到u是一条边形成的不满足无向图的圈。
无向图中的每一个顶点到其他顶点都有一条路径的称作这个无向图连通的，具有这种性质的有向图称为强连通，反之就是弱连通。
完全图的每一对顶点间都存在一条边的图

图的表示：

表示的图的一种简单方法是使用一个二维数组，称为邻接矩阵表示法，对于每条边(u,v)，我们将数组an[u] [v]=1；否则数组的元素等于0，如果边有权，我们就令an[u] [v]的值等于该权，而用一个很大或者很小的权作为标记表示不存在的边。但是该方法的空间代价太大，如果图是稠密的，可以用这种方法。空间需求O(|V|²)；
如果图是稀疏的，我们就用邻接表(数组+链表)来表示，数组的元素个数代表着图中有多少个节点，每个索引的链表存该索引顶点邻接的所有顶点。顶点的名称不一定是数字，因此需要将顶点通过哈希函数映射到数组中。

数据结构与算法

#后台开发 #C/C++ #数据结构与算法

数据结构与算法

https://moonfordream.github.io/posts/数据结构与算法/

作者

Moon

发布于

2024年5月19日

许可协议

Linux系统编程下一篇

数据结构与算法

算法性能分析

时间复杂度的渐进表示法

空间复杂度的渐进表示法

算法

最大子序列和求解问题

暴力求解

微优化解法

分治法求解

贪心解法(最快最简单解法)

二分查找

欧几里德算法

快速幂算法

素数筛

朴素筛法(优化版)

欧拉筛(线性筛)

排序算法

冒泡排序

插入排序

希尔排序

堆排序

归并排序

快速排序

桶式排序

计数排序

基数排序

图论算法

拓扑排序

最短路径算法

广度优先搜索算法(BFS)

Dijkstra算法

Floyd算法

最小生成树

Prim算法

Kruskal算法

并查集

深度优先算法(DFS)

双连通性

图论技巧

超级源点/汇点

贪心算法

调度问题

Huffman编码

分治算法

最近点问题

选择问题

字符串算法

KMP算法

Manacher算法

最近公共祖先(LCA)

朴素求解(暴力)

在线倍增算法

动态规划(dp)

记忆化搜索

数位dp

ST表

单调栈

滑动窗口

回溯算法

数据结构

抽象数据类型

线性表

简单数组实现表

链表

双向非循环链表

循环链表

跳跃表(跳表)

栈(stack)

概念

逆波兰转换式

队列(queue)

树

普通树(多叉树)

树的遍历

二叉树

二叉查找树(二叉排序树)

平衡查找树(AVL树)

单旋转

双旋转

伸展树