首页 算法和数据结构

# 算法

# 一、排序（升序）

  1. 选择排序

  • 寻找数组中最小的元素，将起与数组的第一个元素交换位置。再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此，知道整个数组排完序。

  • 对于长度为 N 的数组，选择排序需要打约N2/2N^2/2 次比较和 N 次交换

  • 代码

    template <typename T>
void selection_sort(T *array)
{
    if(array.size()<=1)
        return;
    else
    {
          for(int i=0;i<array.size();i++)
      {
        int min=i;
        for(int j=i+1;j<array.size();j++)
        {
            if(array[min]>=array[j])
            {
                min=j;
            }
        }
        swap(array[min],array[j]);
     }
    }

}
  1. 插入排序

  • 在数组中，将数组元素插入到有序的数组元素之中，在插入之前，其余元素向右移一位

  • 对于随机排列的长度为 N 的且主键不重复的数组，平均情况下插入排序需要N2/4N^2/4 次比较以及～N2/4N^2/4 次交换。最坏的情况下需要N2/2N^2/2 次比较和N2/2N^2/2 交换，最好情况下需要 N-1 次比较和 0 次交换。

  • 代码

    template <typename T>
void insertion_sort(T *array)
{
    if(array.size()<=1)
        return;
    else
    {
        for(int i=0;i<array.size();i++)
        {
            for(int j=i;j>0&&array[j]<=array[j-1];j--)
            {
                swap(array[j],array[j-1]);
            }
        }
    }
}
  1. 希尔排序

  • 将数组分为几个间隔为 h 的元素子数组，用插入排序为每个子数组进行排序，之后队 h 进行减少，再对分好的子数组进行插入排序，直到 h=1；

  • 使用递增序列 1，4，13，40，121，364，…… 的希尔排序所需要的比较次数不会超出 N 的若干倍乘以递增序列的长度

  • 代码

    template <typename T>
void shell_sort(T *array)
{
    int N=array.size();
    int h=1;
    if(n<=1)
        return;
    else
    {
         while(h<N/3) h=3*h+1；
         while(h>=1)
         {
             for(int i=h;i<N;i++)
             {
                 for(int j=i;j>=h&&array[j]<=array[j-h];j-=h)
                 {
                     swap(array[j],array[j-h]);
                 }
             }
             h/=3;
         }
    }

}
  1. 归并排序
  • 将一个数组，递归地分成两半数组并排序，然后将结果归并起来。

​ (1) 原地归并的抽象方法

  • 创建一个大小适当的数组，将两个数组的元素分别有序地放入这个数组中

  • 代码

    template <typename T>
void merge(T *array)
{
    int l=0;
    int h=array.size()-1;
    int mid=array.size()/2;
    T auk[h-l+1];

    for(int k=l;k<=h;k++)
    {
        auk[k]=array[k];
    }

    int i=l;
    int j=mid;
    for(int k=l;k<=h;k++)
    {
        if(i>mid)
        {
            array[k]=auk[j++];
        }
        else if(j>h)
        {
            array[k]=auk[i++];
        }
        else if(auk[j]<=auk[i])
        {
            array[k]=auk[j++];
        }
        else
        {
            array[k]=auk[i++];
        }
    }
}

​ (2) 自顶向下的归并排序

  • 对于长度为 N 的任意数组，自定向下的归并方法需要1/2NlgN1/2NlgN 至NlgNNlgN 次比较，最多访问数组6NlgN6NlgN 次

  • 代码

    template <typename T>
void merge_sort(T *array)
{
    if(array.size()<=1) return;
    else
    {
        int l=0;
        int h=array.size()-1;
        int mid=array.size()/2;
        array.sort(l,mid);
        ayrry.sort(mid+1,h);
        merge(array);
    }
}

​ (3) 自底向上的归并排序

  • 将数组分递归分为两半数组，然后再对数组两两归并，四四归并，八八归并，一直下去。

  • 对于长度为 N 的任意数组，自底向上的归并排序需要1/2NlgN1/2NlgN 至NlgNNlgN 次比较，最多访问数组6NlgN6NlgN 次

  • 代码

    template <typename T>
void mergerBU(T *array,int len)
{
    T *a = array;
    T *b = new T[len];
    for (int seg = 1; seg < len; seg += seg) {
        for (int start = 0; start < len; start += seg + seg) {
            int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        T *temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) {
        for (int i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    delete[] b;
}
  1. 快速排序

  • 寻找一个分界点 K，将分界点移动到恰当位置，将数组分为两个部分，左边部分全部小于 K，右边部分全部大于 K。对两部分的数组元素进行再进行分界，直到数组排序完成。

  • 长度为 N 的无重复数组排序，快速排序平均需要～2NlnN2NlnN 次比较 (以及 1/6 的交换)。

  • 代码

    template <typename T>
void quick_sort(T *arr, T l, T r)
{
    if(l<r)
    {
         int i=0;
         int j=arr.size()-1;
        while(i<j)
        {
            while(j>i&&arr[j]>=l)
            {
                j--;
            }
            while(i<j&&arr[i]<l)
            {
                i--;
            }
            if(j>i)
            {
                T temp=arr[j];
                arr[j]=arr[i];
                arr[j]=temp;
            }
        }
        arr[0]=arr[i];
        arr[i]=l;
        quick_sort(arr,l,i-1);
        quick_sort(arr,i+1,r);
    }
}
  1. 冒泡排序

  • 对每一对相邻的元素进行比较，较大的元素往后移动，小的元素往前移动，做完一步，最后的元素是最大的数，重复操作，直到排序完成

  • 代码

    template <typename T>
void bubble_sort(T *arr)
{
    for(int i=0;i<arr.szie();i++)
    {
        for(int j=0;i<arr.szie()-1-i;j++)
        {
            if(arr[j]>arr[j+1])
            {
                swap(arr[j],arr[j+1]);
            }
        }
    }
}

    优化版本

    template <typename T>
void bubble_sort(T *arr)
{
    int len=arr.size();
    bool flag=false;

    for(int i=0;i<len-1;i++)
    {
        for(int j=0;j<len-1-i;j++)
        {
            if(arr[j]>arr[j+1])
            {
                swap(arr[j],arr[j+1])
                flag=true;
            }
        }
        if(!flag) {break;}
    }
}
  1. 计数排序

  • 计数排序一般是基于对整数进行排序，且范围在 (0,k) 之间

  • 计数排序通过对数组中的元素进行计数，并且创建辅助数组按元素顺序大小存储元素的个数，随后将辅助数组的元素序号和元素大小反向填充目标数组。

  • 代码

    template <typename T>
int* countSort(int* arr,int len)
{
	int max = arr[0];//记录数列的最大值
	int min = arr[0];//记录数列的最小值
	for(int i=0;i<len-1;i++)
	{
		if(arr[i]>max)
		{
			max = arr[i];
		}
		if(arr[i]<min)
		{
			min = arr[i];
		}
	}
	int l = max-min;//计算出数列最大最小值得差值
	int* couarr = new int[l+1];
	for(int i=0;i<len;i++)
	{
		couarr[arr[i]-min]++;//统计元素个数
	}

	int sum = 0;
	for(int i=0;i<l+1;i++)//统计数组做变形，后面的元素等于前面元素的和
	{
		sum += couarr[i];
		couarr[i]=sum;
	}
	int* sortarr = new int[len];
	for(int i=len-1;i>=0;i--)//倒序遍历原始数组，从统计数组中找到正确位置
	{
		sortarr[couarr[arr[i]-min]-1]=arr[i];
		couarr[arr[i]-min]--;
	}
	delete couarr;
	return sortarr;
}
  1. 堆排序

  • 堆

    • 堆是一棵完全二叉树

    • 堆中的每一个父节点要大于其每一个子节点

    • 代码

      template <typename T>
void heapify(T * arr,int n,int i) //对于父节点为i的堆的修复
{

     if(i>=n) {return;}

    int lchild=2*i+1;
    int rchild=2*i+2;
    int max=i;

    if(lchild>n&&arr[lchild]>arr[max])
    {
        max=lchild;
    }

     if(rchild>n&&arr[rchild]>arr[max])
    {
        max=rchild;
    }

    if(max!=i)
    {
        swap(arr[max],arr[i]);
        heapify(arr,n,max);
    }
}

template <typename T>
void build_heap(T *arr,n)
{
    int last_node=n-1;
    int parent=(last_node-1)/2;

    foe(int i=parent;i>=0;i--)
    {
        hapify(arr,n,i);
    }
}

  • 将堆中的最后一个节点与根节点进行交换，将最后一个节点取出，再将二叉树中复原成堆，将堆中的最后一个节点与根节点进行交换，将最后一个节点取出，再复原堆，继续执行，直到二叉树中的节点全部取出。

  • 代码

    template <typename T>
void heap_sort(T * arr,n)
{
    build_heap(arr,n);

    for(int i=n-1;i>=0;i--)
    {
        swap(arr[i],arr[0]);
        heapify(arr,i,0);
    }
}
  1. 桶排序

  • 设置一个定量的数组当作空桶子，寻访序列，并且把项目一个一个放到对应的桶子去。对每个不是空的桶子进行排序，从不是空的桶子里把项目再放回原来的序列中。

  • 代码

    template <typename T>
void bksort(T A[],int l,int h){
    int size = h-l+1;
    vector<T> b[size];//有size个数据，就分配size个桶
    for(int i=l;i<=h;i++){
        int bi = size*A[i];//元素A[i]的桶编号
        b[bi].push_back(A[i]);//将元素A[i]压入桶中
    }
    for(int i=0;i<size;i++)
        sort(b[i].begin(),b[i].end());//桶内排序
    int idx = l;//指向数组A的下标
    for(int i=0;i<size;i++){//遍历桶
        for(int j=0;j<b[i].size();j++){//遍历桶内元素
            A[idx++] = b[i][j];
        }
    }
}
  1. 基数排序

  • 对待排序的数字先按个位数排序，再按十位数排序，以此来推，直到待排序的数字每一位数都能进行排序。

  • 代码

    template <typename T>
int maxbit(T *arr,int n)
{
    int maxData=data[0];
    for(int i=1;i<n;i++)
    {
        if(arr[i]>maxData)
        {
            maxData=arr[i];
        }
    }

    int d=1;int p=10;
    while(maxData>=p)
    {
         maxData /= 10;
        ++d;
    }
    return d;
}

template <typename T>
void radix_sortT *arr, int n)
{
    int d=maxbit(arr,n);
    int *tmp=new int[n];
    int *count=new int[10];
    int i,j,k;
    int radix=1;

    for(i=1;i<=d;i++)
    {
        for(j=0;j<10;j++)
        {
            count[j]=0;
        }
        for(j=0;j<n;j++)
        {
            k=(arr[j]/radix)%10;
            count[k]++;
        }
        for(j=1;j<10;j++)
        {
            count[j]=count[j-1]+count[j];
        }

        for(j=n-1;j>=0;j--)
        {
             k=(arr[j]/radix)%10;
            tmp[count[k]-1]=arr[j];
            count[k]--;
        }

        for(j=0;j<n;j++)
        {
            arr[j]=tmp[j];
        }
        radix=radix*10;
    }
    delete []tmp;
    delete []count;
}

# 二、贪心算法

  1. 思想
  • 贪心算法总是做出在当前看来得最好选择，可以说，贪心算法并不从整体考虑最优，而是在某种意义上得局部最优选择。从而贪心算法得最终结果也是整体最优的。即使贪心算法不能得到整体最优解，其结果也是最优解的很好近似。
  1. 基本要素
  • 贪心选择性质：贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。是贪心算法可行性的第一个基本要素，也是贪心与动态规划的主要区别。
  • 当一个问题的最优解包含其子问题的最优解是，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划或是贪心算法求解的关键特征
  1. 基本思路

  • 从问题的某一初始解逐步逼近给定目标，以尽可能快地求得更好地解 / 当到达算法中地某一步不能继续前进时，算法停止

  • 算法存在问题：

    1. 不能保证求得地最后解时最佳地
    2. 不能用来求最大或是最小解问题
    3. 只能求某些约束条件地可行解地 范围

  • 算法地实现过程：
    while 能朝给定目标前进一步 do
    求出可行解地一个解元素；
    由所有解元素组合成问题地一个可行解

  • 用背包问题来介绍贪心算法：

    背包问题：有一个背包，背包容量是 M=150。有 7 个物品，物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。

    ​ 物品 A B C D E F G

    ​ 重量 35 30 60 50 40 10 25

    ​ 价值 10 40 30 50 35 40 30

    分析如下

    ​ 目标函数： ∑pi 最大

    约束条件是装入的物品总重量不超过背包容量：∑wi<=M ( M=150)。

    ​ （1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？

    ​ （2）每次挑选所占重量最小的物品装入是否能得到最优解？

    ​ （3）每次选取单位重量价值最大的物品，成为解本题的策略。

    ​ 值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。

    ​ 贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。

    ​ 可惜的是，它需要证明后才能真正运用到题目的算法中。

    ​ 一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。

    ​ 对于背包问题中的 3 种贪心策略，都是无法成立（无法被证明）的，解释如下：

    ​ 贪心策略：选取价值最大者。反例：

    ​ W=30

    ​ 物品：A B C

    ​ 重量：28 12 12

    ​ 价值：30 20 20

    根据策略，首先选取物品 A，接下来就无法再选取了，可是，选取 B、C 则更好。

    （2）贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。

    （3）贪心策略：选取单位重量价值最大的物品。反例：

    ​ W=30

    ​ 物品：A B C

    ​ 重量：28 20 10

    ​ 价值：28 20 10

    ​ 根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择 A，则答案错误。但是果在条件中加一句当遇见单位价值相同的时候，优先装重量小的，这样的问题就可以解决.

    ​ 贪心算法可以与随机化算法一起使用，具体的例子就不再多举了。（因为这一类算法普及性不高，而且技术含量是非常高的，需要通过一些反例确定随机的对象是什么，随机程度如何，但也是不能保证完全正确，只能是极大的几率正确）。

    假设条件是什么？假设条件是上述几种反例的情况不存在的时候该如何求解:

    #include <iostream>
using namespace std;

struct Node
{
	float weight;
	float value;
	bool mark;
	char char_mark;
	float pre_weight_value;
};

int main(int argc, char* argv[])
{
	float Weight[7] = {35,30,60,50,40,15,20};
	float Value [7] = {10,40,30,50,35,40,30};
	Node array[7];
	for(int i=0; i<7; i++)
	{
		array[i].value = Value[i];
		array[i].weight = Weight[i];
		array[i].char_mark = 65 + i;
		array[i].mark = false;
		array[i].pre_weight_value = Value[i] / Weight[i];
	}
for(i=0;i<7;i++)
	cout<<array[i].pre_weight_value<<" ";
cout<<endl;

float weight_all=0.0;
float value_all = 0.0;
float max = 0.0;
char charArray[7];
int flag,n = 0;

while(weight_all <= 150)
{
	for(int index=0;index < 7; ++index)
	{
		if(array[index].pre_weight_value > max && array[index].mark == false)
		{
			max = array[index].pre_weight_value ;
			flag = index;
		}
	}

	charArray[n++] = array[flag].char_mark;
	array[flag].mark = true;
	weight_all += array[flag].weight;
	value_all += array[flag].value;
	max = 0.0;
}

for(i=0;i<n-1;i++)
	cout<<charArray[i]<<" ";
cout<<endl;
cout<<"weight_all:"<<weight_all- array[n-1].weight<<endl;
cout<<"value_all:"<<value_all<<endl;

system("pause");
return 0;
}

# 三 、动态规划

  1. 思想
  • 动态规划是通过拆分问题、定义问题状态与状态之间的关系，使得问题能够以递推 (或是分治) 的方法去解决。
  • 动态规划规划算法的思想与分治算法的思想有些相似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
  1. 适用情况

  • 能采用动态规划求解的问题的一般要具有 3 个性质：

    1. 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。

    2. 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。

    3. 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）

  1. 求解步骤

  • 动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线 (通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式，一般要经历以下几个步骤，如下图所示：

    初始状态 →│ 决策 1│→│ 决策 2│→…→│ 决策 n│→ 结束状态

  • 划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。

  • 确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。

  • 确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。

  • 寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。

    一般，只要解决问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程（包括边界条件）。实际应用中可以按以下几个简化的步骤进行设计：

    1. 分析最优解的性质，并刻画其结构特征。
    2. 递归的定义最优解。
    3. 以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值
    4. 根据计算最优值时得到的信息，构造问题的最优解
  1. 实现步骤

  • 动态规划的主要难点在于理论上的设计，也就是上面 4 个步骤的确定，一旦设计完成，实现部分就会非常简单。使用动态规划求解问题，最重要的就是确定动态规划三要素：

    （1）问题的阶段

    （2）每个阶段的状态

    （3）从前一个阶段转化到后一个阶段之间的递推关系。

  • 递推关系必须是从次小的问题开始到较大的问题之间的转化，从这个角度来说，动态规划往往可以用递归程序来实现，不过因为递推可以充分利用前面保存的子问题的解来减少重复计算，所以对于大规模问题来说，有递归不可比拟的优势，这也是动态规划算法的核心之处。

  • 确定了动态规划的这三要素，整个求解过程就可以用一个最优决策表来描述，最优决策表是一个二维表，其中行表示决策的阶段，列表示问题状态，表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值（如最短路径，最长公共子序列，最大价值等），填表的过程就是根据递推关系，从 1 行 1 列开始，以行或者列优先的顺序，依次填写表格，最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。

  • f(n,m)=max

    for(j=1; j<=m; j=j+1) // 第一个阶段
   xn[j] = 初始值;

 for(i=n-1; i>=1; i=i-1)// 其他n-1个阶段
   for(j=1; j>=f(i); j=j+1)//f(i)与i有关的表达式
     xi[j]=j=max（或min）{g(xi-1[j1:j2]), ......, g(xi-1[jk:jk+1])};

t = g(x1[j1:j2]); // 由子问题的最优解求解整个问题的最优解的方案

print(x1[j1]);

for(i=2; i<=n-1; i=i+1）
{
     t = t-xi-1[ji];

     for(j=1; j>=f(i); j=j+1)
        if(t=xi[ji])
             break;
}

  • 自顶向下版本
    按照自然递归的形式编写代码，过程中会保存每个子问题的解。当需要某个子问题的解时，过程会首先检查是否保存过此解。如果是，则直接返回保存的值。

  • 自底向上版本

    将子问题按照规模大小从小到大排序，进行求解。当求解某个问题时，它所依赖的子问题都已经得到求解，结果已经保存。每个子问题都只用求解一遍。

# 四、双指针

  1. 思想
  • 双指针即用两个不同速度或不同方向的指针对数组或对象进行访问，通过两个不同指针的碰撞从而达到特定的目的。
  1. 快慢指针

​ (1) 思想

  • 快慢指针也是双指针，但是两个指针从同一侧开始遍历数组，将这两个指针分别定义为 快指针（fast） 和 慢指针（slow） ，两个指针以不同的策略移动，直到两个指针的值相等（或其他特殊条件）为止，如 fast 每次增长两个，slow 每次增长一个。

​ (2) 用法

  • 快慢指针一般都初始化指向链表的头结点 head，前进时快指针 fast 在前，慢指针 slow 在后，巧妙解决一些链表中的问题。
    1. 判定链表中是否含有环
    2. 已知链表中含有环，返回这个环的起始位置
    3. 寻找链表的中点
    4. 寻找链表的倒数第 k 个元素

​ (3) 示例

  • 判定链表中是否含有环

    • 单链表的特点是每个节点只知道下一个节点，所以一个指针的话无法判断链表中是否含有环的。

      如果链表中不包含环，那么这个指针最终会遇到空指针 null 表示链表到头了，这还好说，可以判断该链表不含环

      bool hasCycle(ListNode *head) {
    while (head != null)
        head = head->next;
    return false;
}

      但是如果链表中含有环，那么这个指针就会陷入死循环，因为环形数组中没有 null 指针作为尾部节点。

      经典解法就是用两个指针，一个每次前进两步，一个每次前进一步。如果不含有环，跑得快的那个指针最终会遇到 null，说明链表不含环；如果含有环，快指针最终会和慢指针相遇，说明链表含有环。

  • 已知链表中含有环，返回这个环的起始位置

    • img

      代码：

      ListNode*  detectCycle(ListNode *head)
{
    ListNode* fast, *slow;
    fast = slow = head;
    while (fast != null && fast->next != null)
    {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow)
            break;
    }

    slow = head;
    while (slow != fast)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

      当快慢指针相遇时，让其中任一个指针重新指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。

  • 寻找链表的中点

    • 我们还可以让快指针一次前进两步，慢指针一次前进一步，当快指针到达链表尽头时，慢指针就处于链表的中间位置。

      ListNode* slow, *fast;
slow = fast = head;
while (fast != null && fast.next != null) {
    fast = fast->next->next;
    slow = slow->next;
}
// slow 就在中间位置
return slow;

      当链表的长度是奇数时，slow 恰巧停在中点位置；如果长度是偶数，slow 最终的位置是中间偏右：

      img

      寻找链表中点的一个重要作用是对链表进行归并排序。

      回想数组的归并排序：求中点索引递归地把数组二分，最后合并两个有序数组。对于链表，合并两个有序链表是很简单的，难点就在于二分。

  • 寻找链表的倒数第 k 个元素

    • 快慢指针，让快指针先走 k 步，然后快慢指针开始同速前进。这样当快指针走到链表末尾 null 时，慢指针所在的位置就是倒数第 k 个链表节点（为了简化，假设 k 不会超过链表长度）：

      ListNode *slow, *fast;
slow = fast = head;
while (k-- > 0)
    fast = fast->next;

while (fast != null) {
    slow = slow->next;
    fast = fast->next;
}
return slow;

  1. 对撞指针

    (1) 思想

  • 对撞指针是指在数组中，将指向最左侧的索引定义为 左指针(left) ，最右侧的定义为 右指针(right) ，然后从两头向中间进行数组遍历。

    (2) 用法

  • 对撞数组适用于连续数组和字符串，也就是说当遇到题目给定连续数组和字符床时，应该第一时间想到用对撞指针解题

  • 代码

    void find (int list[]) {
  auto left = 0;
   auto right = list.length() - 1;

  //遍历数组
  while (left <= right) {
    left++;
    // 一些条件判断 和处理
    ... ...
    right--;
  }
}
  1. 滑动窗口

​ (1) 思想

  • 滑动窗口算法是在给定特定窗口大小的数组或字符串上执行要求的操作。该技术可以将一部分问题中的嵌套循环转变为一个单循环，因此它可以减少时间复杂度。
  • 就是有一个大小可变的窗口，左右两端方向一致的向前滑动（右端固定，左端滑动；左端固定，右端滑动）

​ (2) 用法

  1. 一般是字符串或者列表
  2. 一般是要求最值（最大长度，最短长度等等）或者子序列

​ (3) 实现

  1. 在序列中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为一个窗口。
  2. 先不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的序列符合要求。
  3. 此时，停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的序列不再符合要求。同时，每次增加 left 前，都要更新一轮结果。
  4. 重复第 2 和第 3 步，直到 right 到达序列的尽头。

# 五、数组

  1. ** 数组是存放在连续内存空间上的相同类型数据的集合。** 数组可以方便的通过下标索引的方式获取到下标下对应的数据。

  2. 举一个字符数组的例子，如图所示：

    算法通关数组

    需要两点注意的是

    • 数组下标都是从 0 开始的。
    • 数组内存空间的地址是连续的

    正是因为数组的在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址。数组的元素是不能删的，只能覆盖。

  3. 二维数组在 C++ 中在地址空间上是连续的。在 Java 中数值也是 16 进制，这不是真正的地址，而是经过处理过后的数值了，每一行头结点的地址是没有规则的，更谈不上连续。

# 六、链表

  1. 链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向 null（空指针的意思）。

    链接的入口节点称为链表的头结点也就是 head。

  2. 类型

    • 单链表：链表1
    • 双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。双链表 既可以向前查询也可以向后查询。
      链表2
    • 循环链表：循环链表，顾名思义，就是链表首尾相连。循环链表可以用来解决约瑟夫环问题。

  3. 链表存储方式

    数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。

    链表是通过指针域的指针链接在内存中各个节点。

    所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

    如图所示：

    链表3

    这个链表起始节点为 2， 终止节点为 7， 各个节点分布在内存的不同地址空间上，通过指针串联在一起。

  4. 链表的定义
    C/C++ 的定义链表节点方式，如下所示：

    //单链表
struct ListNode
{
    int val;  //节点上存储的元素
    ListNode *next;  //指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL){}  //节点的构造函数
};

  5. 链表的操作

    • 删除节点：链表-删除节点
    • 添加节点
      链表-添加节点

  6. 性能对比
    链表-链表与数据性能对比

    数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。

    链表的长度可以是不固定的，并且可以动态增删， 适合数据量不固定，频繁增删，较少查询的场景。

# 七、哈希表

  1. 哈希表是根据关键码的值而直接进行访问的数据结构。
    哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素，如下图所示：
    哈希表1
    哈希表一般都是用来快速判断一个元素是否出现集合里。

  2. 哈希函数
    哈希函数，把学生的姓名直接映射为哈希表上的索引，然后就可以通过查询索引下标快速知道这位同学是否在这所学校里了。

    哈希函数如下图所示，通过 hashCode 把名字转化为数值，一般 hashcode 是通过特定编码方式，可以将其他数据格式转化为不同的数值，这样就把学生名字映射为哈希表上的索引数字了。

    哈希表2

    如果 hashCode 得到的数值大于 哈希表的大小了，也就是大于 tableSize 了，怎么办呢？

    此时为了保证映射出来的索引数值都落在哈希表上，我们会在再次对数值做一个取模的操作，就要我们就保证了学生姓名一定可以映射到哈希表上了。

  3. 哈希碰撞如图所示，小李和小王都映射到了索引下标 1 的位置，这一现象叫做哈希碰撞。

    哈希表3

    一般哈希碰撞有两种解决方法， 拉链法和线性探测法。

    • 拉链法

      刚刚小李和小王在索引 1 的位置发生了冲突，发生冲突的元素都被存储在链表中。 这样我们就可以通过索引找到小李和小王了

      哈希表4

      （数据规模是 dataSize， 哈希表的大小为 tableSize）

      其实拉链法就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。

    • 线性探测法

      使用线性探测法，一定要保证 tableSize 大于 dataSize。 我们需要依靠哈希表中的空位来解决碰撞问题。

      例如冲突的位置，放了小李，那么就向下找一个空位放置小王的信息。所以要求 tableSize 一定要大于 dataSize ，要不然哈希表上就没有空置的位置来存放 冲突的数据了。如图所示：

      哈希表5

    1. 常见的三种哈希结构

      • 数组
      • set (集合)
      • map (映射)

      在 C++ 中，set 和 map 分别提供以下三种数据结构，其底层实现以及优劣如下表所示：

      集合底层实现是否有序数值是否可以重复能否更改数值查询效率增删效率
      std::set红黑树有序否否O(log n)O(log n)
      std::multiset红黑树有序是否O(logn)O(logn)
      std::unordered_set哈希表无序否否O(1)O(1)

      std::unordered_set 底层实现为哈希表，std::set 和 std::multiset 的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以 key 值是有序的，但 key 不可以修改，改动 key 值会导致整棵树的错乱，所以只能删除和增加。

      映射底层实现是否有序数值是否可以重复能否更改数值查询效率增删效率
      std::map红黑树key 有序key 不可重复key 不可修改O(logn)O(logn)
      std::multimap红黑树key 有序key 可重复key 不可修改O(log n)O(log n)
      std::unordered_map哈希表key 无序key 不可重复key 不可修改O(1)O(1)

      std::unordered_map 底层实现为哈希表，std::map 和 std::multimap 的底层实现是红黑树。同理，std::map 和 std::multimap 的 key 也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）。

      当我们要使用集合来解决哈希问题的时候，优先使用 unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用 set，如果要求不仅有序还要有重复数据的话，那么就用 multiset。

      那么再来看一下 map ，在 map 是一个 key value 的数据结构，map 中，对 key 是有限制，对 value 没有限制的，因为 key 的存储方式使用红黑树实现的。

      其他语言例如：java 里的 HashMap ，TreeMap 都是一样的原理。可以灵活贯通。

      虽然 std::set、std::multiset 的底层实现是红黑树，不是哈希表，但是 std::set、std::multiset 依然使用哈希函数来做映射，只不过底层的符号表使用了红黑树来存储数据，所以使用这些数据结构来解决映射问题的方法，我们依然称之为哈希法。 map 也是一样的道理。

      这里在说一下，一些 C++ 的经典书籍上 例如 STL 源码剖析，说到了 hash_set hash_map，这个与 unordered_set，unordered_map 又有什么关系呢？

      实际上功能都是一样一样的， 但是 unordered_set 在 C11 的时候被引入标准库了，而 hash_set 并没有，所以建议还是使用 unordered_set 比较好，这就好比一个是官方认证的，hash_set，hash_map 是 C11 标准之前民间高手自发造的轮子。

      哈希表6

# 八、KMP 算法

  1. KMP 主要应用早字符串匹配上。

    KMP 算法的主要思想就是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配。

  2. 前缀表
    前缀表是用来回退的，它记录了模式串与主串 (文本串) 不匹配的时候，模式串应该从哪里开始重新匹配。

    前缀表可以暂时理解为：字符串最长公共前缀后缀长度。记录下标 i 之前（包括 i）的字符串中，有多大长度的相同前缀后缀。 "前缀" 指除了最后一个字符以外，一个字符串的全部头部组合；"后缀" 指除了第一个字符以外，一个字符串的全部尾部组合。字符串最长公共前缀后缀长度则表示在字符串的所有前缀和所有后缀中都出现的字符的长度。

    找到了最长相等的前缀和后缀，匹配失败的位置是后缀子串的后面，那么我们找到与其相同的前缀的后面从新匹配就可以了。

  3. 计算前缀表

    接下来就要说一说怎么计算前缀表。

    如图：

    <img src='https://code-thinking.cdn.bcebos.com/pics/KMP 精讲 5.png' width=600 alt='KMP 精讲 5'> </img></div>

    长度为前 1 个字符的子串 a ，最长相同前后缀的长度为 0。（注意字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串；后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。）

    <img src='https://code-thinking.cdn.bcebos.com/pics/KMP 精讲 6.png' width=600 alt='KMP 精讲 6'> </img></div>
    长度为前 2 个字符的子串 aa ，最长相同前后缀的长度为 1。

    <img src='https://code-thinking.cdn.bcebos.com/pics/KMP 精讲 7.png' width=600 alt='KMP 精讲 7'> </img></div>
    长度为前 3 个字符的子串 aab ，最长相同前后缀的长度为 0。

    以此类推：
    长度为前 4 个字符的子串 aaba ，最长相同前后缀的长度为 1。
    长度为前 5 个字符的子串 aabaa ，最长相同前后缀的长度为 2。
    长度为前 6 个字符的子串 aabaaf ，最长相同前后缀的长度为 0。

    那么把求得的最长相同前后缀的长度就是对应前缀表的元素，如图：
    <img src='https://code-thinking.cdn.bcebos.com/pics/KMP 精讲 8.png' width=600 alt='KMP 精讲 8'> </img></div>

    可以看出模式串与前缀表对应位置的数字表示的就是：下标 i 之前（包括 i）的字符串中，有多大长度的相同前缀后缀。

    再来看一下如何利用 前缀表找到 当字符不匹配的时候应该指针应该移动的位置。如动画所示：

    KMP精讲2

    找到的不匹配的位置， 那么此时我们要看它的前一个字符的前缀表的数值是多少。

    为什么要前一个字符的前缀表的数值呢，因为要找前面字符串的最长相同的前缀和后缀。

    所以要看前一位的 前缀表的数值。

    前一个字符的前缀表的数值是 2， 所有把下标移动到下标 2 的位置继续比配。 可以再反复看一下上面的动画。

    最后就在文本串中找到了和模式串匹配的子串了。

  4. 前缀表与 next 数组

    next 数组就可以是前缀表，但是很多实现都是把前缀表统一减一（右移一位，初始位置为 - 1）之后作为 next 数组。

    其实这并不涉及到 KMP 的原理，而是具体实现，next 数组即可以就是前缀表，也可以是前缀表统一减一（右移一位，初始位置为 - 1）。

  5. 构造 next 数组

  6. 我们定义一个函数 getNext 来构建 next 数组，函数参数为指向 next 数组的指针，和一个字符串。 代码如下：

    void getNext(int* next, const string& s)

    构造 next 数组其实就是计算模式串 s，前缀表的过程。 主要有如下三步：

    1. 初始化
    2. 处理前后缀不相同的情况
    3. 处理前后缀相同的情况

    接下来我们详解详解一下。

    1. 初始化：

    定义两个指针 i 和 j，j 指向前缀末尾位置，i 指向后缀末尾位置。

    然后还要对 next 数组进行初始化赋值，如下：

    int j = -1;
    next[0] = j;

    j 为什么要初始化为 -1 呢，因为之前说过 前缀表要统一减一的操作仅仅是其中的一种实现，我们这里选择 j 初始化为 - 1，下文我还会给出 j 不初始化为 - 1 的实现代码。

    next [i] 表示 i（包括 i）之前最长相等的前后缀长度（其实就是 j）

    所以初始化 next [0] = j 。

    1. 处理前后缀不相同的情况

    因为 j 初始化为 - 1，那么 i 就从 1 开始，进行 s [i] 与 s [j+1] 的比较。

    所以遍历模式串 s 的循环下标 i 要从 1 开始，代码如下：

    for (int i = 1; i < s.size(); i++) {

    如果 s [i] 与 s [j+1] 不相同，也就是遇到 前后缀末尾不相同的情况，就要向前回退。

    怎么回退呢？

    next [j] 就是记录着 j（包括 j）之前的子串的相同前后缀的长度。

    那么 s [i] 与 s [j+1] 不相同，就要找 j+1 前一个元素在 next 数组里的值（就是 next [j]）。

    所以，处理前后缀不相同的情况代码如下：

    while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
        j = next[j]; // 向前回退
    }
    1. 处理前后缀相同的情况

    如果 s [i]  与 s [j + 1] 相同，那么就同时向后移动 i 和 j 说明找到了相同的前后缀，同时还要将 j（前缀的长度）赋给 next [i], 因为 next [i] 要记录相同前后缀的长度。

    代码如下：

    if (s[i] == s[j + 1]) { // 找到相同的前后缀
    j++;
}
next[i] = j

    最后整体构建 next 数组的函数代码如下：

    void getNext(int* next, const string& s){
    int j = -1;
    next[0] = j;
    for(int i = 1; i < s.size(); i++) { // 注意i从1开始
        while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
            j = next[j]; // 向前回退
        }
        if (s[i] == s[j + 1]) { // 找到相同的前后缀
            j++;
        }
        next[i] = j; // 将j（前缀的长度）赋给next[i]
    }
}

    得到了 next 数组之后，就要用这个来做匹配了。

    前缀表（不减一）实现：

    void getNext(int* next, const string& s)
{
        int j = 0;
        next[0] = 0;
        for(int i = 1; i < s.size(); i++)
        {
            while (j > 0 && s[i] != s[j])
            { // j要保证大于0，因为下面有取j-1作为数组下标的操作
                j = next[j - 1]; // 注意这里，是要找前一位的对应的回退位置了
            }
            if (s[i] == s[j])
            {
                j++;
            }
            next[i] = j;
        }
    }

# 九、栈

  1. 栈的定义
    栈（Stack）：是只允许在一端进行插入或删除的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作。

在这里插入图片描述

​ 栈顶（Top）：线性表允许进行插入删除的那一端。
​ 栈底（Bottom）：固定的，不允许进行插入和删除的另一端。
​ 空栈：不含任何元素的空表。

​ 栈又称为后进先出（Last In First Out）的线性表，简称 LIFO 结构

  1. 栈的常见基本操作

    • InitStack (&S)：初始化一个空栈 S。
    • StackEmpty (S)：判断一个栈是否为空，若栈为空则返回 true，否则返回 false。
    • Push (&S, x)：进栈（栈的插入操作），若栈 S 未满，则将 x 加入使之成为新栈顶。
    • Pop (&S, &x)：出栈（栈的删除操作），若栈 S 非空，则弹出栈顶元素，并用 x 返回。
    • GetTop (S, &x)：读栈顶元素，若栈 S 非空，则用 x 返回栈顶元素。
    • DestroyStack (&S)：栈销毁，并释放 S 占用的存储空间（“&” 表示引用调用）。

  2. 栈的顺序存储结构

    • 栈的顺序存储
      采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶元素的位置。
      若存储栈的长度为 StackSize，则栈顶位置 top 必须小于 StackSize。当栈存在一个元素时，top 等于 0，因此通常把空栈的判断条件定位 top 等于 - 1。
      栈的顺序存储结构可描述为：

      #define MAXSIZE 50  //定义栈中元素的最大个数
typedef int ElemType;   //ElemType的类型根据实际情况而定，这里假定为int
typedef struct{
    ElemType data[MAXSIZE];
    int top;    //用于栈顶指针
}SqStack;

      若现在有一个栈，StackSize 是 5，则栈的普通情况、空栈、满栈的情况分别如下图所示：

      img

    • 顺序栈的基本算法
      （1）初始化
      void InitStack (SqStack *S){
      S->top = -1; // 初始化栈顶指针
      }

      （2）判栈空

      bool StackEmpty(SqStack S){
    if(S.top == -1){
        return true;    //栈空
    }else{
        return false;   //不空
    }
}

      （3）进栈

      进栈操作 push，代码如下：

      /*插入元素e为新的栈顶元素*/
Status Push(SqStack *S, ElemType e){
    //满栈
    if(S->top == MAXSIZE-1){
        return ERROR;
    }
    S->top++;   //栈顶指针增加一
    S->data[S->top] = e;    //将新插入元素赋值给栈顶空间
    return OK;
}

      （4）出栈
      出栈操作 pop，代码如下：

      /*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/
Status Pop(SqStack *S, ElemType *e){
    if(S->top == -1){
        return ERROR;
    }
    *e = S->data[S->top];   //将要删除的栈顶元素赋值给e
    S->top--;   //栈顶指针减一
    return OK;
}

      （5）读栈顶元素

      /*读栈顶元素*/
Status GetTop(SqStack S, ElemType *e){
    if(S->top == -1){   //栈空
        return ERROR;
    }
    *e = S->data[S->top];   //记录栈顶元素
    return OK;
}

  3. 共享栈（两栈共享空间）

    • 共享栈概念
      利用栈底位置相对不变的特征，可让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸，如下图所示：
      img

      两个栈的栈顶指针都指向栈顶元素，top0=-1 时 0 号栈为空，top1=MaxSize 时 1 号栈为空；仅当两个栈顶指针相邻（top0+1=top1）时， 判断为栈满。当 0 号栈进栈时 top0 先加 1 再赋值，1 号栈进栈时 top1 先减一再赋值出栈时则刚好相反。

    • 共享栈的空间结构
      代码如下：

      /*两栈共享空间结构*/
#define MAXSIZE 50  //定义栈中元素的最大个数
typedef int ElemType;   //ElemType的类型根据实际情况而定，这里假定为int
/*两栈共享空间结构*/
typedef struct{
	ElemType data[MAXSIZE];
	int top0;	//栈0栈顶指针
	int top1;	//栈1栈顶指针
}SqDoubleStack;

    • 共享栈进栈
      对于两栈共享空间的 push 方法，我们除了要插入元素值参数外，还需要有一个判断是栈 0 还是栈 1 的栈号参数 stackNumber。
      共享栈进栈的代码如下：

      /*插入元素e为新的栈顶元素*/
Status Push(SqDoubleStack *S, Elemtype e, int stackNumber){
    if(S->top0+1 == S->top1){   //栈满
        return ERROR;
    }
    if(stackNumber == 0){   //栈0有元素进栈
        S->data[++S->top0] = e; //若栈0则先top0+1后给数组元素赋值
    }else if(satckNumber == 1){ //栈1有元素进栈
        S->data[--S->top1] = e; //若栈1则先top1-1后给数组元素赋值
    }
    return OK;
}

    • 共享栈出栈

      /*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/
Status Pop(SqDoubleStack *S, ElemType *e, int stackNumber){
    if(stackNumber == 0){
        if(S->top0 == -1){
            return ERROR;   //说明栈0已经是空栈，溢出
        }
        *e = S->data[S->top0--]; //将栈0的栈顶元素出栈，随后栈顶指针减1
    }else if(stackNumber == 1){
        if(S->top1 == MAXSIZE){
            return ERROR;   //说明栈1是空栈，溢出
        }
        *e = S->data[S->top1++];    //将栈1的栈顶元素出栈，随后栈顶指针加1
    }
    return OK;
}

  4. 栈的链式存储结构

    • 链栈
      采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现，并规定所有操作都是在单链表的表头进行的。这里规定链栈没有头节点，Lhead 指向栈顶元素，如下图所示。
      img

      对于空栈来说，链表原定义是头指针指向空，那么链栈的空其实就是 top=NULL 的时候。
      链栈的结构代码如下：

      /*栈的链式存储结构*/
/*构造节点*/
typedef struct StackNode{
    ElemType data;
    struct StackNode *next;
}StackNode, *LinkStackPrt;
/*构造链栈*/
typedef struct LinkStack{
    LinkStackPrt top;
    int count;
}LinkStack;

      • 链栈的基本算法

        • 链栈的进栈
          对于链栈的进栈 push 操作，假设元素值为 e 的新节点是 s，top 为栈顶指针，示意图如下：
          在这里插入图片描述

        代码如下：

        /*插入元素e为新的栈顶元素*/
Status Push(LinkStack *S, ElemType e){
    LinkStackPrt p = (LinkStackPrt)malloc(sizeof(StackNode));
    p->data = e;
    p->next = S->top;    //把当前的栈顶元素赋值给新节点的直接后继
    S->top = p; //将新的结点S赋值给栈顶指针
    S->count++;
    return OK;
}

        • 链栈的出栈
          链栈的出栈 pop 操作，也是很简单的三句操作。假设变量 p 用来存储要删除的栈顶结点，将栈顶指针下移以为，最后释放 p 即可，如下图所示：
          img
          代码如下：

          /*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/
Status Pop(LinkStack *S, ElemType *e){
    LinkStackPtr p;
    if(StackEmpty(*S)){
        return ERROR;
    }
    *e = S->top->data;
    p = S->top; //将栈顶结点赋值给p
    S->top = S->top->next;  //使得栈顶指针下移一位，指向后一结点
    free(p);    //释放结点p
    S->count--;
    return OK;
    }

  5. 性能分析
    链栈的进栈 push 和出栈 pop 操作都很简单，时间复杂度均为 O (1)。
    对比一下顺序栈与链栈，它们在时间复杂度上是一样的，均为 O (1)。对于空间性能，顺序栈需要事先确定一个固定的长度，可能会存在内存空间浪费的问题，但它的优势是存取时定位很方便，而链栈则要求每个元素都有指针域，这同时也增加了一些内存开销，但对于栈的长度无限制。所以它们的区别和线性表中讨论的一样，如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些。

  6. 栈的应用 —— 递归

    • 递归的定义
      递归是一种重要的程序设计方法。简单地说，若在一个函数、过程或数据结构的定义中又应用了它自身，则这个函数、过程或数据结构称为是递归定义的，简称递归。
      它通常把一个大型的复杂问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的代码就可以描述岀解题过程所需要的多次重复计算，大大减少了程序的代码量但在通常情况下，它的效率并不是太高。

    • 斐波那契数列
      用程序实现时如下：

      /*斐波那契数列的实现*/
int Fib(int n){
    if(n == 0){
        return 0;   //边界条件
    }else if(n == 1){
        return 1;	//边界条件
    }else{
        return Fib(n-1) + Fib(n-2); //递归表达式
    }
}

      必须注意递归模型不能是循环定义的，其必须满足下面的两个条件递归表达式 (递归体)
      边界条件 (递归出口)
      递归的精髓在于能否将原始问题转换为属性相同但规模较小的问题
      在递归调用的过程中，系统为每一层的返回点、局部变量、传入实参等开辟了递归工作栈来进行数据存储，递归次数过多容易造成栈溢出等。而其效率不高的原因是递归调用过程中包含很多重复的计算。下面以 n=5 为例，列出递归调用执行过程，如图所示：
      img 如图可知，程序每往下递归一次，就会把运算结果放到栈中保存，直到程序执行到临界条件，然后便会把保存在栈中的值按照先进后出的顺序一个个返回，最终得出结果。

  7. 栈的应用 —— 四则运算表达式求值

    • 后缀表达式计算结果
      表达式求值是程序设计语言编译中一个最基本的问题，它的实现是栈应用的一个典型范例。中缀表达式不仅依赖运算符的优先级，而且还要处理括号。后缀表达式的运算符在操作数后面，在后缀表达式中已考虑了运算符的优先级，没有括号，只有操作数和运算符。例如中缀表达式 A + B ∗ (C − D) − E / F A+B (C-D)-E/FA+B∗(C−D)−E/F 所对应的后缀表达式为 A B C D − ∗ + E F / − ABCD-+EF/-ABCD−∗+EF/−。
      后缀表达式计算规则：从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进项运算，运算结果进栈，一直到最终获得结果。
    • 中缀表达式转后缀表达式
      我们把平时所用的标准四则运算表达式，即 a + b − a ∗ (( c + d) /e − f ) + g a+b-a       ((c+d)/e-f)+ga+b−a∗((c+d)/e−f)+g 叫做中缀
      表达式。因为所有的运算符号都在两数字的中间，现在我们的问题就是中缀到后缀的转化。规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后
      缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号 (乘除优先加减) 则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。