算法 - 八大类算法原理与例子

目录

算法设计与基础 ............................................................................................. 错误！未定义书签。 目录 .................................................................................................................................................. 1 一、蛮力法....................................................................................................................................... 2

原理........................................................................................................................................... 2 例子 平面最近的点对 ............................................................................................................. 2 二、动态规划 ................................................................................................................................... 4

原理........................................................................................................................................... 4 例子：最长公共子序列 ........................................................................................................... 5 三、分治算法 ................................................................................................................................... 8

原理........................................................................................................................................... 8 例子 棋盘覆盖 ......................................................................................................................... 8 四、贪心算法 ................................................................................................................................. 10

原理......................................................................................................................................... 10 例子 背包问题 ....................................................................................................................... 10 五、回溯法..................................................................................................................................... 13

原理......................................................................................................................................... 13 例子 八皇后问题 ................................................................................................................... 13 六、分支界限法 ............................................................................................................................. 15

原理......................................................................................................................................... 15 例子 装载问题 ....................................................................................................................... 15 七、时空权衡 ................................................................................................................................. 16

原理......................................................................................................................................... 16 例子 KMP字符串匹配算法 ................................................................................................. 17 八、变治法..................................................................................................................................... 24

原理......................................................................................................................................... 24 例子 堆排序 ........................................................................................................................... 24

一、蛮力法

原理

顾名思义，蛮力法即是顺序往下寻找方法，直到问题的解决。它所依赖的技术是扫描技术，关键是依次处理所有元素。蛮力法的思想非常简单，没有很多条件的限制，比如动态划法， 必须满足最有性原理才可以使用。它的方法上也没有缺陷，对于分治法，一旦子问题的规模不同，便不能在使用。而蛮力法则没有这个要求。因此，简单，易上手，是蛮力法的 基本原理。蛮力法是我们算法中最常使用的算法，虽然巧妙和高效的算法很少来自于蛮力法，但是蛮力法依然是一种重要的算法设计技术。在实际理论上，蛮力法可以解决可计算领域的各种问题，只是效率的高低不同而已。因此蛮力法经常用来解决一些较小规模的问题。蛮力法对于一些重要的问题可以产生一些合理的算法，他们具备一些实用价值，而且不受问题规模的限制。蛮力法也可以作为某类问题时间性能的底限，来衡量同样问题的更高效算法。

例子 平面最近的点对

问题：

设p1=(x1, y1), p2=(x2, y2), , pn=(xn, yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。

蛮力算法描述：

int ClosestPoints(int n, int x[ ], int y[ ]){ minDist=Double.POSITIVE_INFINITY;; for (i=1; i< n; i++)

for (j=i+1; j<=n; j++) {

d=(x[i]-x[j])* (x[i]-x[j])+(y[i]-y[j])* (y[i]-y[j]); if (d< minDist) { minDist=d; index1=i; index2=j; } }

return minDist; }

程序：

import java.util.*;

public class ClosestPair1{

public static void main(String[] args) { /**

*输入需要比较的点的对数存在变量n中 */

Scanner in=new Scanner(System.in);

System.out.println("How many pairs of points to compare?(有多少对点需要比较?)");

int n=in.nextInt();

int[] x=new int[n]; int[] y=new int[n]; /**

*输入这些点的横坐标和纵坐标分别存储在x[n]和y[n] */

System.out.println("Please enter these points,X-coordinate(请输入这些点,横坐标):");

for(int i=0;i< n;i++) {

x[i]=in.nextInt(); }

System.out.println("Please enter these points,Y-coordinate(请输入这些点,纵坐标):");

for(int i=0;i< n;i++) {

y[i]=in.nextInt(); }

double minDist=Double.POSITIVE_INFINITY; double d;

int indexI=0; int indexJ=0; /**

*求解最近对距离存于minDist中 */

double startTime=System.currentTimeMillis();//startTime for(int i=0;i< n-1;i++) {

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

d=Math.sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])); if(d< minDist) {

minDist=d; indexI=i; indexJ=j;

} } }

double endTime=System.currentTimeMillis();//endTime /**

*打印输出最后求出的结果，最近的是哪两个点，以及最近距离和程序用的时间 */

System.out.println("The closest pair is:("+x[indexI]+","+y[indexI]+") and ("+x[indexJ]+","+y[indexJ]+")");

System.out.println("The closest distance is "+minDist);

System.out.println("Basic Statements take(基本语句用时) "+(endTime-startTime)+" milliseconds!"); } }

运行：

二、动态规划

原理

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的

答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

例子：最长公共子序列

什么是最长公共子序列呢？举个简单的例子吧，一个数列S，若分别是两个或多个已知序列的子序列，且是所有符合条件序列中最长的，则S称为已知序列的最长公共子序列。

举例如下，如：有两个随机数列，1 2 3 4 5 6 和 3 4 5 8 9，则它们的最长公共子序列便是：3 4 5。

1、序列str1和序列str2

·长度分别为m和n；

·创建1个二维数组L[m.n]； ·初始化L数组内容为0

·m和n分别从0开始，m++，n++循环：

- 如果str1[m] == str2[n]，则L[m,n] = L[m - 1, n -1] + 1； - 如果str1[m] != str2[n]，则L[m,n] = max{L[m,n - 1]，L[m - 1, n]} ·最后从L[m,n]中的数字一定是最大的，且这个数字就是最长公共子序列的长度

·从数组L中找出一个最长的公共子序列

2、从数组L中查找一个最长的公共子序列

i和j分别从m，n开始，递减循环直到i = 0，j = 0。其中，m和n分别为两个串的长度。

·如果str1[i] == str2[j]，则将str[i]字符插入到子序列内，i--，j--； ·如果str1[i] != str[j]，则比较L[i,j-1]与L[i-1,j]，L[i,j-1]大，则j--，否则i--；（如果相等，则任选一个）

图1 效果演示图

根据上图，我们可以得到其中公共子串：B C B A 和 B D A B。

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

int main(int argc, char **argv) {

string str1 = "ABCBDAB"; string str2 = "BDCABA";

int x_len = str1.length(); int y_len = str2.length();

int arr[50][50] = {{0,0}};

int i = 0; int j = 0;

for(i = 1; i <= x_len; i++) {

for(j = 1; j <= y_len; j++) {

if(str1[i - 1] == str2[j - 1]) {

arr[i][j] = arr[i - 1][j - 1] + 1; } else {

if(arr[i][j - 1] >= arr[i - 1][j]) {

arr[i][j] = arr[i][j - 1]; } else {

arr[i][j] = arr[i -1][j]; } }

} }

for(i = 0 ; i <= x_len; i++) {

for( j = 0; j <= y_len; j++) {

cout << arr[i][j] << " "; }

cout << endl; }

for(i = x_len, j = y_len; i >= 1 && j >= 1;) {

if(str1[i - 1] == str2[j - 1]) {

cout << str1[i - 1] << " ";//倒序打印的 i--; j--; } else {

// if(arr[i][j -1] >= arr[i - 1][j])//打印：B A D B if(arr[i][j -1] > arr[i - 1][j]) //打印:A B C B { j--; } else {

i--; }

} }

cout << endl; return 0; }

三、分治算法

原理

基本思想

当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出。对于这类问题，我们往 往先把它分解成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。如果这些子问题还较大，难以解决，可以再把 它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。这就是分治策略的基本思想。 二分法

利用分治策略求解时，所需时间取决于分解后子问题的个数、子问题的规模大小等因素，而二分法，由于其划分的简单和均匀的特点，是经常采用的一种有效的方法，例如二分法检索。 解题步骤 分治算法

解题的一般步骤：

（1）分解，将要解决的问题划分成若干规模较小的同类问题； （2）求解，当子问题划分得足够小时，用较简单的方法解决；

（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。

例子 棋盘覆盖

题目：在一个(2^k)*(2^k)个方格组成的棋盘上，有一个特殊方格与其他方格不同，称为特殊方格，称这样的棋盘为一个特殊棋盘。现在要求对棋盘的其余部分用L型方块填满（注：L型方块由3个单元格组成。即围棋中比较忌讳的愚形三角，方向随意），且任何两个L型方块不能重叠覆盖。L型方块的形态如下：

题目的解法使用分治法，即子问题和整体问题具有相同的形式。我们对棋盘做一个分割，切割一次后的棋盘如图1所示，我们可以看到棋盘被切成4个一样大小的子棋盘，特殊方块必定位于四个子棋盘中的一个。假设如图1所示，特殊方格位于右上角，我们把一个L型方块（灰色填充）放到图中位置。这样对于每个子棋盘又各有一个“特殊方块”，我们对每个子棋盘继续这样分割，知道子棋盘的大小为1为止。

用到的L型方块需要（4^k-1)/3 个，算法的时间是O（4^k)，是渐进最优解法。 本题目的C语言的完整代码如下（TC2.0下调试），运行时，先输入k的大小，(1<=k<=6)，然后分别输入特殊方格所在的位置(x,y), 0<=x,y<=(2^k-1)。

#include <stdio.h> int title=1;

int board[64][64];

void chessBoard(int tr,int tc,int dr,int dc,int size){ int s,t;

if(size==1) return; t=title++; s=size/2; if(dr<tr+s && dc<tc+s)

chessBoard(tr,tc,dr,dc,s); else

{ board[tr+s-1][tc+s-1]=t;

chessBoard(tr,tc,tr+s-1,tc+s-1,s); }

if(dr<tr+s && dc>=tc+s)

chessBoard(tr,tc+s,dr,dc,s); else { board[tr+s-1][tc+s]=t;

chessBoard(tr,tc+s,tr+s-1,tc+s,s); } if(dr>=tr+s && dc<tc+s)

chessBoard(tr+s,tc,dr,dc,s); else

{ board[tr+s][tc+s-1]=t;

chessBoard(tr+s,tc,tr+s,tc+s-1,s); } if(dr>=tr+s && dc>=tc+s)

chessBoard(tr+s,tc+s,dr,dc,s); else { board[tr+s][tc+s]=t;

chessBoard(tr+s,tc+s,tr+s,tc+s,s); }} void main(){int dr=0,dc=0,s=1,i=0,j=0; printf("print in the size of chess:\n"); scanf("%d",&s);

printf("print in specal point x,y:\n"); scanf("%d%d",&dr,&dc); if(dr<s && dc<s)

{ chessBoard(0,0,dr,dc,s); for(i=0;i<s;i++)

{ for(j=0;j<s;j++) {

printf("%4d",board[i][j]); } printf("\n"); }

} else

printf("the wrong specal point!!\n"); getch();}

四、贪心算法

原理

贪婪算法（Greedy algorithm）是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。

贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。

对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。

一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。最优解可以通过一系列局部最优的选择即贪婪选择来达到，根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优解。

例子 背包问题

有N件物品和一个容量为V的背包。第i件物品的重量是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。 基本思路

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。

用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。可以压缩空间，f[v]=max{f[v],f[v-c[i]]+w[i]}

这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f [i-1][v-c[i]]再加上通过放入第i件物品获得的价

值w[i]。

注意f[v]有意义当且仅当存在一个前i件物品的子集，其费用总和为v。所以按照这个方程递推完毕后，最终的答案并不一定是f[N] [V]，而是f[N][0..V]的最大值。如果将状态的定义中的“恰”字去掉，在转移方程中就要再加入一项f[v-1]，这样就可以保证f[N] [V]就是最后的答案。至于为什么这样就可以，由你自己来体会了。 空间复杂

以上方法的时间和空间复杂度均为O(N*V），其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(N）。

先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[i][0..V]的所有值。那么，如果只用一个数组f [0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？ f[i][v]是由f[i-1][v]和f [i-1][v-c[i]]两个子问题递推而来，能否保证在推f[v]时（也即在第i次主循环中推f[v]时）能够得到f[v]和f[v -c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。伪代码如下： for i=1..N for v=V..0

f[v]=max{f[v],f[v-c[i]]+w[i]};

其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因为的

f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了f[i][v]由f[i][v-c[i]]推知，与本题意不符，但它却是另一个重要的背包问题P02最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。 示例程序

#include "stdafx.h" #include <iostream> using namespace std; #define MAXSIZE 1000

int f[MAXSIZE + 1],c[MAXSIZE + 1],w[MAXSIZE + 1]; int _tmain(int argc,_TCHAR* argv[]) {

int N,V;

cin >> N >> V; int i = 1;

for (; i <= N; ++i) {

cin >> c[i] >> w[i]; }

for (i = 1; i <= N; ++i) {

for (int v = V; v >= c[i]; --v) //c[i]可优化为bound,bound = max {V - sum c[i,...n],c[i]} {

f[v] = (f[v] > f[v - c[i]] + w[i]?f[v] : f[v - c[i]] + w[i]);

} }

//当i=N时，可以跳出循环单独计算F[V] cout << f[V] << '\n'; system("pause"); return 0; }

递归实现

//现在设A[i][v]表示在剩余空间为v时选取当前物品i的最大值，B[i][v]表示不选取当前物品i的最大值，所以总的最大值必然是max(A[n][v],B[n][v]），详细程序见如下：

//BY wanda1416

#include <fstream>

#includusing namespace std; #define MAXSIZE 1000

int A[MAXSIZE+1][MAXSIZE+1],B[MAXSIZE+1][MAXSIZE+1]; int c[MAXSIZE+1],w[MAXSIZE+1]; int F(int n,int v){ if(n==0) return 0;

if(!A[n][v] && v >= c[n])

A[n][v] = F(n-1,v-c[n]) +w[n]; if(!B[n][v]) B[n][v] = F(n-1,v);

return A[n][v]>B[n][v]?A[n][v]:B[n][v]; }

int main(int argc,char *argv[]) {

int n,v;

memset(A,0,sizeof(A)); memset(B,0,sizeof(B)); ifstream in("in.txt"); ofstream out("out.txt"); in>>n>>v;

for(int i=1;i<=n;i++) in>>c[i]>>w[i]; out<<F(n,v); return 0; }

五、回溯法

原理

基本思想

在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。 若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束 一般表达

可用回溯法求解的问题P，通常要能表达为：对于已知的由n元组（x1，x2， ，xn）组成的一个状态空间E={（x1，x2， ，xn）∣xi∈Si ，i=1，2， ，n}，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中Si是分量xi的定义域，且 |Si| 有限，i=1，2， ，n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。

解问题P的最朴素的方法就是枚举法，即对E中的所有n元组逐一地检测其是否满足D的全部约束，若满足，则为问题P的一个解。但显然，其计算量是相当大的。

例子 八皇后问题

八皇后问题是一个古老而著名的问题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一对角线上，问有多少种摆法。 用回溯法解决八皇后问题的C语言程序 #include<stdio.h> #include<stdlib.h> int col[9]={0},a[9]; int b[17],c[17]; main() {

int m,good; int i,j,k; char q;

for(i=0;i<17;i++) {

if(i<9) a[i]=1; b[i]=1;c[i]=1; }

good=1;

col[1]=1; m=1;

while(col[0]!=1) {

if(good) if(m==8) {

for(i=1;i<9;i++)

printf("col[%d] %d\n",i,col[i]); printf("input 'q' to quit\n"); scanf("%c",&q); getchar();

if(q=='q'||q=='Q') exit(0); while(col[m]==8) { m--;

a[col[m]]=b[m+col[m]]=c[8+m-col[m]]=1; }

a[col[m]]=b[m+col[m]]=c[8+m-col[m]]=1; col[m]++; } else {

a[col[m]]=b[m+col[m]]=c[8+m-col[m]]=0; m++;

col[m]=1; } else {

while(col[m]==8) { m--;

a[col[m]]=b[m+col[m]]=c[8+m-col[m]]=1; }

col[m]++; }

good=a[col[m]]&&b[m+col[m]]&&c[8+m-col[m]]; } }

六、分支界限法

原理

分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。

由于求解目标不同，导致分支限界法与回溯法在解空间树T上的搜索方式也不相同。回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。分支限界法的搜索策略是：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。

例子 装载问题

有一批共n个集装箱要装上2艘载重量分别为c1，c2的轮船，其中集装箱i的重量为wi，且要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。

可证明，采用如下策略可以得到一个最优装载方案：先尽可能的将第一艘船装满，其次将剩余的集装箱装到第二艘船上。 //分支限界法解装载问题

//子函数，将当前活节点加入队列 template<class Type>

void EnQueue(Queue<Type> &Q, Type wt, Type &bestw, int i, int n) {

if(i == n) //可行叶结点 {

if(wt>bestw) bestw = wt ; }

else Q.Add(wt) ; //非叶结点 }

//装载问题先尽量将第一艘船装满 //队列式分支限界法，返回最优载重量 template<class Type>

Type MaxLoading(Type w[],Type c,int n) {

//初始化数据

Queue<Type> Q; //保存活节点的队列 Q.Add(-1); //-1的标志是标识分层

int i=1; //i表示当前扩展节点所在的层数 Type Ew=0; //Ew表示当前扩展节点的重量 Type bestw=0; //bestw表示当前最优载重量

//搜索子集空间树 while(true) {

if(Ew+w[i]<=c) //检查左儿子

EnQueue(Q,Ew+w[i],bestw,i,n); //将左儿子添加到队列

//将右儿子添加到队列 即表示不将当前货物装载在第一艘船 EnQueue(Q,Ew,bestw,i,n);

Q.Delete(Ew); //取下一个节点为扩展节点并将重量保存在Ew if(Ew==-1) //检查是否到了同层结束 {

if(Q.IsEmpty()) return bestw; //遍历完毕，返回最优值 Q.Add(-1); //添加分层标志

Q.Delete(Ew); //删除分层标志，进入下一层 i++; } } }

七、时空权衡

原理

时空权衡基于“空间充裕廉价，时间宝贵”以及“空间极其有限，时间要求不高”的思想，要么以牺牲空间的代价换取时间的高效，要么以牺牲时间的代价换取空间的要求。前者在桌面PC领域更加常见，后者在单片机、嵌入式等产品中体现较明显。

典型的例子： 计数排序： 使用一个数组来存储比元素大或者小的元素个数，根据这些值来确定元素在最终列表中的位置。

散列法： 使用数组和链表的结合来实现字典的高效。首先，采用某种哈希函数hash(x) 将 基于键key 的记录映射到哈希表的相应位置hashtable[hash(key)]中，如果有冲突（多个键的记录被映射到同一个下标），则使用附在该下标的链表存储冲突的记录。这也是一个显示数据结构组合应用能够产生强大功能的令人深刻的例子。

递归/非递归遍历： 使用额外的栈或者标记来存储遍历过程中已经遍历了的元素，从而避免重复遍历。

例子 KMP字符串匹配算法

字符串匹配是计算机的基本任务之一。

举例来说，有一个字符串"BBC ABCDAB ABCDABCDABDE"，我想知道，里面是否包含另一个字符串"ABCDABD"？许多算法可以完成这个任务，Knuth-Morris-Pratt算法（简称KMP）是最常用的之一。它以三个发明者命名，起头的那个K就是著名科学家Donald Knuth。 算法描述

1.

首先，字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。

2.

因为B与A不匹配，搜索词再往后移。 3.

就这样，直到字符串有一个字符，与搜索词的第一个字符相同为止。

4.

接着比较字符串和搜索词的下一个字符，还是相同。

5.

直到字符串有一个字符，与搜索词对应的字符不相同为止。

6.

这时，最自然的反应是，将搜索词整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把"搜索位置"移到已经比较过的位置，重比一遍。

7.

一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是"ABCDAB"。KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。

8.

怎么做到这一点呢？可以针对搜索词，算出一张《部分匹配表》（Partial Match Table）。这张表是如何产生的，后面再介绍，这里只要会用就可以了。

9.

已知空格与D不匹配时，前面六个字符"ABCDAB"是匹配的。查表可知，最后一个匹配字符B对应的"部分匹配值"为2，因此按照下面的公式算出向后移动的位数：

移动位数 = 已匹配的字符数 - 对应的部分匹配值 因为 6 - 2 等于4，所以将搜索词向后移动4位。

10.

因为空格与Ｃ不匹配，搜索词还要继续往后移。这时，已匹配的字符数为2（"AB"），对应的"部分匹配值"为0。所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移2位。

11.

因为空格与A不匹配，继续后移一位。

12.

逐位比较，直到发现C与D不匹配。于是，移动位数 = 6 - 2，继续将搜索词向后移动4位。 13.

逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数 = 7 - 0，再将搜索词向后移动7位，这里就不再重复了。

14.

下面介绍《部分匹配表》是如何产生的。

首先，要了解两个概念："前缀"和"后缀"。 "前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。

15.

"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例，

本文来源：https://www.bwwdw.com/article/4kzm.html