C语言 字符串匹配算法
字符串匹配算法（一）简介收藏
注：本文大致翻译自EXACT STRING MATCHING ALGORITHMS，去掉一些废话，增加一些解释。
文本信息可以说是迄今为止最主要的一种信息交换手段，而作为文本处理中的一个重要领域——字符串匹配，就是我们今天要说的话题。（原文还特意提及文本数据数量每18个月翻一番，以此论证算法必须要是高效的。不过我注意到摩尔定律也是18个月翻番，这正说明数据的增长是紧紧跟随处理速度的，因此越是使用高效的算法，将来待处理的数据就会越多。这也提示屏幕前的各位，代码不要写得太快了……）
字符串匹配指的是从文本中找出给定字符串（称为模式）的一个或所有出现的位置。本文的算法一律输出全部的匹配位置。模式串在代码中用x[m]来表示，文本用y[n]来，而所有字符串都构造自一个有限集的字母表Σ，其大小为σ。
根据先给出模式还是先给出文本，字符串匹配分为两类方法：
?第一类方法基于自动机或者字符串的组合特点，其实现上，通常是对模式进行预处理；
?第二类方法对文本建立索引，这也是现在搜索引擎采用的方法。
本文仅讨论第一类方法。
文中的匹配算法都是基于这样一种方式来进行的：设想一个长度为m的窗口，首先窗口的左端和文本的左端对齐，把窗口中的字符与模式字符进行比较，这称为一趟比较，当这一趟比较完全匹配或者出现失配时，将窗口向右移动。重复这个过程，直到窗口的右端到达了文本的右端。这种方法我们通常叫sliding window。
对于穷举法来说，找到所有匹配位置需要的时间为O(mn)，基于对穷举法改进的结果，我们按照每一趟比较时的比较顺序，把这些算法分为以下四种：
1.从左到右：最自然的方式，也是我们的阅读顺序
2.从右到左：通常在实践中能产生最好的算法
3.特殊顺序：可以达到理论上的极限
4.任意顺序：这些算法跟比较顺序没关系（例如：穷举法）
一些主要算法的简单介绍如下：
从左到右
采用哈希，可以很容易在大部分情况下避免二次比较，通过合理的假设，这种算法是线性时间复杂度的。它最先由Harrison提出，而后由Karp和Rabin全面分析，称为KR算法。
在假设模式长度不大于机器字长时，Shift-Or算法是很高效的匹配算法，同时它可以很容易扩展到模糊匹配上。MP是第一个线性时间算法，随后被改进为KMP，它的匹配方式很类似于自动机的识别过程，文本的每个字符与模式的每个字符比较不会超过logΦ(m+1)，这里Φ是黄金分隔比1.618，而随后发现的类似算法——Simon算法，使得文本的每个字符比较不超过1+log2m，这三种算法在最坏情况下都只要2n-1次比较。（抱歉限于我的水平这一段既没看懂也没能查证，大家就看个意思吧）
基于确定性有限自动机的算法对文本字符刚好只用n次访问，但是它需要额外的O(mσ)的空间。
一种叫Forward Dawg Matching的算法同样也只用n次访问，它使用了模式的后缀自动机。
Apostolico-Crochemore算法是一种简单算法，最坏情况下也只需要3n/2次比较。
还有一种不那么幼稚（Not So Naive）的算法，最坏情况下是n平方，但是预处理过程的时间和空间均为常数，而且平均情况下的性能非常接近线性。
从右到左
BM算法被认为是通常应用中最有效率的算法了，它或者它的简化版本常用于文本编辑器中的搜索和替换功能，对于非周期性的模式而言，3n是这种算法的比较次数上界了，不过对于周期性模式，它最坏情况下需要n的二次方。
BM算法的一些变种避免了原算法的二次方问题，比较高效的有：Apostolico and Giancarlo算法、Turbo BM算法和Reverse Colussi算法。
实验的结果表明，Quick Search算法（BM的一个变种）以及基于后缀自动机的Reverse Factor和Turbo Reverse Factor 算法算是实践中最有效的算法了。
Zhu and Takaoka算法和BR算法也是BM的变种，它们则需要O(σ2)的额外空间。
特殊顺序
最先达到空间线性最优的是Galil-Seiferas和Two Way算法，它们把模式分为两部分，先从左到右搜索右边的部分，如果没有失配，再搜索左边的部分。
Colussi和Galil-Giancarlo算法将模式位置分为两个子集，先从左至右搜索第一个子集，如果没有失配，再搜索剩下的。Colussi算法作为KMP算法的改进，使得最坏情况下只需要3n/2次比较，而Galil-Giancarlo算法则通过改进Colussi算法的一个特殊情况，把最坏比较次数减少到了4n/3。
最佳失配和M最大位移算法分别根据模式的字符频率和首字位移，对模式位置进行排序。
Skip Search，KMP Skip Search和Alpha Skip Search算法运用“桶”的方法来决定模式的起始位置。
任意顺序
Horspool算法也是BM的一个变种，它使用一种移位函数，而与字符比较顺序不相干。还有其他的变种如：Quick Search算法，Tuned Boyer-Moore算法，Smith算法，Raita算法。
在接下来的章节中，我们会给出上面这些算法的实现。我们把字母表限定为ASCII码或者它的任意子集，编程语言用C，这就意味着数组索引是从0开始，而字符串以NULL结尾。
（第一章完。好像这些算法被挨个夸了个遍，反而不知道该选哪一种了，老外介绍别人的东西时就是这样，尽来虚的。）
字符串匹配算法（二）穷举与自动机收藏
穷举法又叫暴力法。大多数程序员眼里，它是幼稚的，但大师们不这么认为。
Rob Pike, 最伟大的C 语言大师之一, 在《Notes on C Programming》中阐述了一个原则：花哨的算法比简单算法更容易出bug、更难实现，尽量使用简单的算法配合简单的数据结构。而Ken Thompson——Unix 最初版本的设计者和实现者，禅宗偈语般地对Pike 的这一原则作了强调：拿不准就穷举（When in doubt , use brute force）。而对于装13爱好者来说，更是自豪的称其使用的是BF算法。
穷举法用在字符串匹配上，简单的描述就是，检查文本从0到n-m的每一个位置，看看从这个位置开始是否与模式匹配。这种方法还是有一些优点的，如：不需要预处理过程，需要的额外空间为常数，每一趟比较时可以以任意顺序进行。
尽管它的时间复杂度为O(mn)，例如在文本"aaaaaaaaaaaaaaaaaaaaaaaaaaa"中寻找"aaaaab"时，就完全体现出来了。但是算法的期望值却是2n，这表明该算法在实际应用中效率不低。
C代码如下：
1.void BF(char *x, int m, char *y, int n) {
2. int i, j;
3.
4. /* Searching */
5. for (j = 0; j <= n - m; ++j) {
6. for (i = 0; i < m && x[i] == y[i + j]; ++i);
7. if (i >= m)
8. OUTPUT(j);
9. }
10.}
11.
如果我们注意到C库函数是汇编优化过的，并通常能提供比C代码更高的性能的话，我们可以用memcmp来完成每一趟比较过程，从而达到更好的性能：
1.#define EOS '\0'
2.
3.void BF(char *x, int m, char *y, int n) {
4. char *yb;
5. /* Searching */
6. for (yb = y; *y != EOS; ++y)
7. if (memcmp(x, y, m) == 0)
8. OUTPUT(y - yb);
9.}
10.
11.
自动机的方法其实和穷举法有点相似，都是用最简单直白的方式来做事情。区别在于穷举法是在计算，而自动机则是查表。尽管自动机的构造过程有一点点难解，要涉及到DFA的理论，但是自动机的比较过程那绝对是简单到无语。
简单说来，根据模式串，画好了一张大的表格，表格m+1行σ列，这里σ表示字母表的大小。表格每一行表示一种状态，状态数比模式长度多1。一开始的状态是0，也就是处在表格的第0行，这一行的每个元素指示了当遇到某字符时就跳转到另一个状态。每当跳转到最终状态时，表示找到了一个匹配。
语言表述起来还是比较啰嗦，看代码就知道了：
1.#define ASIZE 256
2.
3.int preAut(const char *x, int m, int* aut) {
4. int i, state, target, old;
5.
6. for (state = 0, i = 0; i < m; ++i) {
7. target = i + 1;
8. old = aut[state * ASIZE + x[i]];
9. aut[state * ASIZE + x[i]] = target;
10. memcpy(aut + target * ASIZE, aut + old * ASIZE, ASIZE*sizeof(int));
11. state = target;
12. }
13. return state;
14.}
15.
16.
17.void AUT(const char *x, int m, const char *y, int n) {
18. int j, state;
19.
20. /* Preprocessing */
21. int *aut = (int*)calloc((m+1)*ASIZE, sizeof(int));
22. int Terminal = preAut(x, m, aut);
23.
24. /* Searching */
25. for (state = 0, j = 0; j < n; ++j) {
26. state = aut[state*ASIZE+y[j]];
27. if (state == Terminal)
28. OUTPUT(j - m + 1);
29. }
30.}
（注：原文的代码使用一个有向图的数据结构，我遵循大师的指引，改用了更简单一点的数组）
从代码上我们很容易看出，自动机的构造需要时间是O(mσ)，空间也是O(mσ)（严格来说这份代码使用了O((m+1)σ)），但是一旦构造完毕，接下来匹配的时间则是O(n)。
匹配的过程前面已经说了，太简单了没什么好说的，这里就解释一下构造过程吧！
我们构造的目标是对应模式长度，构造出同样多的状态，用0表示初始状态，然后第一个字符用状态1表示，第二个用状态2表示，依次类推，直到最后一个字符，用m表示，也是最终状态。
一开始，数组全都置0，，这个时候的自动机遇到任何字符都转到初始状态。然后给它看模式的第一个字符，假设这是'a'吧，告诉它，状态0遇到'a'应该到一个新的状态——状态1，所以把第0行的第'a'列修改为1。而这个时候状态1还是空白的，怎么办呢？
这时候状态0就想呀，在我被告知遇到'a'要去状态1之前，我原本遇到'a'都要去状态0的，也就是修改之前第'a'列所指的那个状态，称为old状态吧；而现在我遇到'a'却要去一个新的状态，既然以前old状态能处理遇到'a'之后的事情，那么我让新的状态像old状态一样就好了。于是状态0把old状态拷贝到状态1。
现在轮到状态1了，给它看第二个字符，它也如法炮制，指向了状态2，又把old状态拷贝给了状态2。
于是，状态机就在这种代代传承的过程中构造完毕了。
虽然理论上自动机是最完美的匹配方式，但是由于预处理的消耗过大，实践中，主要还是用于正则表达式。
结语：穷举法与自动机各自走了两个极端，因此都没能达到综合性能的最佳，本文之后介绍的算法，可以看成是在穷举和自动机两者之间取舍权衡的结果。
字符串匹配算法（三）位运算的魔法——KR与SO 收藏
位运算经常能做出一些不可思议的事情来，例如不用临时变量要交换两个数该怎么做呢？一个没接触过这类问题的人打死他也想不出来。如果拿围棋来做比喻，那么位运算可以喻为编程中的“手筋”。
按位的存储方式能提供最大的存储空间利用率，而随着空间被压缩的同时，由于CPU硬件的直接支持，速度竟然神奇般的提升了。举个例子，普通的数组要实现移位操作，那是O(n)的时间复杂度，而如果用位运算中的移位，就是一个指令搞定了。
KR算法
KR算法之前第一章介绍中说是利用哈希，原文这么介绍的。而我的看法是，哈希只是一个幌子。这个算法的基本步骤同穷举法一样，不同在于每趟比较前先比较一下哈希值，hash值不同就不必比较了。而如果hash值无法高效计算，这样的改进甚至还不如不改进呢。你想想，比较之前还要先计算一遍hash值，有计算的功夫，直接比都比完了。
KR算法为了把挨个字符的比较转化为两个整数的比较，它把一个m长度的字符串直接当成一个整数来对待，以2为基数的整数。这样呢，在第一次算出这个整数后，以后每次移动窗口，只需要移去最高位，再加上最低位，就得出一个新的hash值。但是m太大，导致超出计算机所能处理的最大整数怎么办？不用担心，对整数最大值取模，借助模运算的特性，一切可以完美的进行。而且由于是对整数最大值取模，所以取模这一步都可以忽略掉。
这是KR算法的代码：
1.#define REHASH(a, b, h) ((((h) - (a)*d) << 1) + (b))
2.
3.void KR(char *x, int m, char *y, int n) {
4. int d, hx, hy, i, j;
5.
6. /* Preprocessing */
7. /* computes d = 2^(m-1) with
8. the left-shift operator */
9. for (d = i = 1; i < m; ++i)
10. d = (d<<1);
11.
12. for (hy = hx = i = 0; i < m; ++i) {
13. hx = ((hx<<1) + x[i]);
14. hy = ((hy<<1) + y[i]);
15. }
16.
17. /* Searching */
18. j = 0;
19. while (j <= n-m) {
20. if (hx == hy && memcmp(x, y + j, m) == 0)
21. OUTPUT(j);
22. hy = REHASH(y[j], y[j + m], hy);
23. ++j;
24. }
25.
26.}
27.
28.
我们可以看到，KR算法有O(m)复杂度的预处理的过程，总感觉它的预处理没有反映出模式本身的特点来，导致它的搜索过程依然是O(mn)复杂度的，只不过一般情况下体现不出来，在"aaaaaaaaaaaaaaaaaaaaaaaaa"中搜"aaaaa"就知道KR多慢了。
总的来说，KR算法比穷举强一点，比较次数的期望值是O(m+n)。
Shift Or 算法
为了最大限度的发挥出位运算的能力，Shift Or算法就有了一个最大缺陷：模式不能超过机器字长。按现在普遍的32位机，机器字长就是32，也就是只能用来匹配不大于32个字符的模式。而带来的好处就是匹配过程是O(n)时间复杂度的，达到自动机的速度了。而预处理所花费的时间与空间都为O(m+σ)，比自动机少多了。
我们来看看它怎么巧妙的实现“只看一遍”的：
假设我们有一个升级系统，总共有m个级别。每一关都会放一个新人到第0级上，然后对于系统中所有的人，如果通过考验，升一级，否则，咔嚓掉。而对于升到最高级的人，那说明他连续通过了m次考验，这就是我们要选拔的人。
KR算法的思路就是上面的升级规则，给出的考验就是你的位置上的字符与给出的文本字符是否一致。升满级了，说明在连续m个位置上与不断给出的文本字符一致，这也就是匹配成功了。
明白了这个思路后，疑问就开始出来了：检查哪些位置与文本字符一致，需要m次吧？那么整个算法就是O(mn)了？
现在就该位运算出场了，对，这个算法的思路是很笨，但是我位运算的效率高呀，事先我算出字母表中每个字符在模式中出现的位置，用位的方式存在整数里，出现的地方标为0，不出现的地方标为1，这样总共使用σ个整数；同样，我用一个整数来表示升级状态，某个级别有人就标为0，没人就标为1，整个系统升级就恰好可以用“移位”来进行，当检查位置的时候只需要与表示状态的整数“或”1次，所以整个算法就成O(n)了。Shift-Or算法名字就是这样来的。
有一个地方很奇怪，0和1的设定和通常的习惯相反呀，习惯上，喜欢把存在设为1，不存在设为0的。不过这里没有办法，因为移位新移出来的是0。
这时我们来看代码就容易理解多了：
1.#define WORDSIZE sizeof(int)*8
2.#define ASIZE 256
3.
4.int preSo(const char *x, int m, unsigned int S[]) {
5. unsigned int j, lim;
6. int i;
7. for (i = 0; i < ASIZE; ++i)
8. S[i] = ~0;
9. for (lim = i = 0, j = 1; i < m; ++i, j <<= 1) {
10. S[x[i]] &= ~j;
11. lim |= j;
12. }
13. lim = ~(lim>>1);
14. return(lim);
15.}
16.
17.void SO(const char *x, int m, const char *y, int n) {
18. unsigned int lim, state;
19. unsigned int S[ASIZE];
20. int j;
21. if (m > WORDSIZE)
22. error("SO: Use pattern size <= word size");
23.
24. /* Preprocessing */
25. lim = preSo(x, m, S);
26.
27. /* Searching */
28. for (state = ~0, j = 0; j < n; ++j) {
29. state = (state<<1) | S[y[j]];
30. if (state < lim)
31. OUTPUT(j - m + 1);
32. }
33.}
代码中lim变量其实就是一个标尺，例如出现最高级的状态是01111111，那么lim就成了10000000，因此只要小于lim，就表示最高级上的0出现了。
原文中对Shift-Or算法的描述还是很难懂的，如果对着那段说明去看代码，有点不知所云的感觉。我还是直接对着代码才想出这个升级的比喻来。
字符串匹配算法（四）可以滑动多远收藏
记得在穷举法中，每一趟比较后，无论成与不成，都将模式向右滑动一个位置，然后继续比较。有没有办法能利用之前的比较结果，使得模式滑动的更远一点呢？
在介绍经典的KMP算法前，我先介绍几个简单的滑动类算法。
Not So Naive
同名字一样，这个算法的确有点幼稚，它根据模式的前两个字符是否相同来滑动比穷举法稍长一点的距离：如果前两个字符相同，那么文本中与第二个字符不同则必然也与第一个不同；如果前两个字符不同，则与第二个相同的文本字符必然与第一个不同。
那么这两种情况下不用比较都可以断定，文本字符与模式的第一个字符肯定不相同，于是能比穷举法多滑动1个位置。
代码见下：
1.void NSN(char *x, int m, char *y, int n) {
2.int j, k, ell;
3.
4./* Preprocessing */
5.if (x[0] == x[1]) {
6. k = 2;
7. ell = 1;
8. }
9.else {
10. k = 1;
11. ell = 2;
12. }
13.
14./* Searching */
15. j = 0;
16.while (j <= n - m)
17.if (x[1] != y[j + 1])
18. j += k;
19.else {
20.if (memcmp(x + 2, y + j + 2, m - 2) == 0 &
21. x[0] == y[j])
22. OUTPUT(j);
23. j += ell;
24. }
25.}
26.
27.
这个算法仅需要常数时间和空间的预处理，比较过程中，先比较模式第二个字符，然后比较其余位置，为的就在某些情况下省掉第一个字符的比较，达到滑动的目的。不过复杂度依然是O(mn)的，比起穷举法或者有轻微改善吧。
想法的确够幼稚，仅仅只考虑了两个模式字符，滑动的步子也太小，能否考虑的更多一点呢？下面请看Quick Search算法。
Quick Search
见到这个名字，不禁让人想起快速排序了，快速排序在最坏情况下是n平方的复杂度，而通常情况下速度超级快，Quick Search莫非也是这样的？没错，就是这样，这个算法在模式长度短而字母表大时，有着优异的表现，尽管它的搜索时间复杂度是O(mn)。
算法的思想是这样，如果文本中某个字符根本就没在模式中出现过，那么就不需要再去和模式中的任何一个比较；如果该字符出现过，那么为了不漏掉可能的匹配，只好与最晚出现过的位置对齐进行比较了。
代码如下：
1.void preQsBc(char *x, int m, int qsBc[]) {
2.int i;
3.
4.for (i = 0; i < ASIZE; ++i)
5. qsBc[i] = m + 1;
6.for (i = 0; i < m; ++i)
7. qsBc[x[i]] = m - i;
8.}
9.
10.
11.void QS(char *x, int m, char *y, int n) {
12.int j, qsBc[ASIZE];
13.
14./* Preprocessing */
15. preQsBc(x, m, qsBc);
16.
17./* Searching */
18. j = 0;
19.while (j <= n - m) {
20.if (memcmp(x, y + j, m) == 0)
21. OUTPUT(j);
22. j += qsBc[y[j + m]]; /* shift */
23. }
24.}
25.
26.
理解这个算法，请看22行，无论这一趟比较是否成功，都进行模式串的滑动，这个滑动就是根据窗口之外的第一个字符位于模式串的位置来决定的，你可以把窗口外第一个字符是否能匹配看成下一趟比较的前提。
现在你知道为何这个算法最适合在短模式和大字母表下运行了，因为字母表大，模式短，则文本字符不在模式中出现的几率就大，因此更大可能性得进行最长距离的滑动，而且模式短，花在比较上的时间就短，可以尽量多滑动。
美中不足的是这个算法最坏情况下复杂度还是O(mn)，尽管预处理中已经利用上了每一个模式字符了。通过滑动能找到一个线性算法吗？仔细审视一下比较过程，造成算法非线性的根本原因是什么？没错，文本串回溯了。让我们来看看一个真正的线性算法——MP，以及它的改进——KMP。
MP/KMP
本着文本串不回溯的目标，MP算法横空出世，它的一个重要指导思想是，凡是比较过，被认定为相同的文本字符，绝不再拿出来比。道理上也是能说得通的，因为既然和模式串一部分相同，那么它的信息就已经存在于模式串中了。预处理时，模式串自己和自己的一部分进行比较，存储下自身的相似信息——Next数组。
以后在比较时，如果某处失配了，根据之前预处理的结果，可以直接滑动到自身相似的那一部分与文本串对齐，然后从失配处继续比较，避免了文本串回溯。
伟大的计算机科学家Knuth，就是写TAOUP的那位，对MP算法进行了些许修正，加上了自己的名字，成了KMP。Knuth注意到，如果滑动前的那个模式字符与滑动后的模式字符相同的话，那么再比较必然再次失配，导致又一次滑动，与其多级滑动，不如一滑到底。
代码：
1.void preMp(char *x, int m, int Next[]) {
2.int i, j;
3.
4. i = 0;
5. j = Next[0] = -1;
6.while (i < m) {
7.while (j > -1 && x[i] != x[j])
8. j = Next[j];
9. i++;
10. j++;
11.// 下面注掉的三行去掉注释就成KMP了
12.//if (x[i] == x[j])
13.// Next[i] = Next[j];
14.//else
15. Next[i] = j;
16. }
17.}
18.
19.
20.void MP(char *x, int m, char *y, int n) {
21.int i, j, Next[XSIZE];
22.
23./* Preprocessing */
24. preMp(x, m, Next);
25.
26./* Searching */
27. i = j = 0;
28.while (j < n) {
29.while (i > -1 && x[i] != y[j])
30. i = Next[i];
31. i++;
32. j++;
33.if (i >= m) {
34. OUTPUT(j - i);
35. i = Next[i];
36. }
37. }
38.}
39.
40.
MP和KMP算法都达到了O(m)的预处理时间和空间，O(n+m)的比较时间，算法实现是如此简单优美，算法思想是如此无可挑剔，还能滑的更远吗？我们拭目以待。
数据结构与算法C语言版期末复习题
《数据结构与算法》期末复习题 一、选择题。 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O(n2) 。 s =0; for( I =0; i 在前面的图文中，我们讲了“串”这种数据结构，其中有求“子串在主串中的位置”（字符串的模式匹配）这样的算法。解决这类问题，通常我们的方法是枚举从A串（主串）的什么位置起开始与B串（子串）匹配，然后验证是否匹配。假设A串长度为n，B串长度为m，那么这种方法的复杂度是O(m*n)的。虽然很多时候复杂度达不到m*n（验证时只看头一两个字母就发现不匹配了），但是我们有许多“最坏情况”，比如： A=“aaaaaaaaaaaaaaaaaaaaaaaaab”，B=“aaaaaaaab”。 大家可以忍受朴素模式匹配算法（前缀暴力匹配算法）的低效吗？也许可以，也许无所谓。 有三位前辈D.E.Knuth、J.H.Morris、V.R.Pratt发表一个模式匹配算法，最坏情况下是O(m+n)，可以大大避免重复遍历的情况，我们把它称之为克努特-莫里斯-普拉特算法，简称KMP算法。 假如，A=“abababaababacb”，B=“ababacb”，我们来看看KMP是怎样工作的。我们用两个指针i和j分别表示，。也就是说，i是不断增加的，随着i 的增加j相应地变化，且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前j个字符（j当然越大越好），现在需要检验A[i+1]和B[j+1]的关系。 例子： S=“abcdefgab” T=“abcdex” 对于要匹配的子串T来说，“abcdex”首字符“a”与后面的串“bcdex”中任意一个字符都不相等。也就是说，既然“a”不与自己后面的子串中任何一字符相等，那么对于主串S来说，前5位字符分别相等，意味着子串T的首字符“a”不可能与S串的第2到第5位的字符相等。朴素算法步骤2,3,4,5的判断都是多余，下次的起始位置就是第6个字符。 例子： S=“abcabcabc” T=“abcabx” 一、基本算法 1．交换（两量交换借助第三者） 例1、任意读入两个整数，将二者的值交换后输出。 main() {int a,b,t; scanf("%d%d",&a,&b); printf("%d,%d\n",a,b); t=a; a=b; b=t; printf("%d,%d\n",a,b);} 【解析】程序中加粗部分为算法的核心，如同交换两个杯子里的饮料，必须借助第三个空杯子。 假设输入的值分别为3、7，则第一行输出为3，7；第二行输出为7，3。 其中t为中间变量，起到“空杯子”的作用。 注意：三句赋值语句赋值号左右的各量之间的关系！ 【应用】 例2、任意读入三个整数，然后按从小到大的顺序输出。 main() {int a,b,c,t; scanf("%d%d%d",&a,&b,&c); /*以下两个if语句使得a中存放的数最小*/ if(a>b){ t=a; a=b; b=t; } if(a>c){ t=a; a=c; c=t; } /*以下if语句使得b中存放的数次小*/ if(b>c) { t=b; b=c; c=t; } printf("%d,%d,%d\n",a,b,c);} 2．累加 累加算法的要领是形如“s=s+A”的累加式，此式必须出现在循环中才能被反复执行，从而实现累加功能。“A”通常是有规律变化的表达式，s在进入循环前必须获得合适的初值，通常为0。例1、求1+2+3+……+100的和。 main() {int i,s; s=0; i=1; while(i<=100) {s=s+i; /*累加式*/ i=i+1; /*特殊的累加式*/ } printf("1+2+3+...+100=%d\n",s);} 【解析】程序中加粗部分为累加式的典型形式，赋值号左右都出现的变量称为累加器，其中“i = i + 1”为特殊的累加式，每次累加的值为1，这样的累加器又称为计数器。 2008-02-18 18:48 【程序1】 题目：有1、2、3、4个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？ 1.程序分析：可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排列后再去 掉不满足条件的排列。 2.程序源代码： main() { int i,j,k; printf("\n"); for(i=1;i<5;i++) ／*以下为三重循环*/ for(j=1;j<5;j++) for (k=1;k<5;k++) { if (i!=k&&i!=j&&j!=k) /*确保i、j、k三位互不相同*/ printf("%d,%d,%d\n",i,j,k); } } ============================================================== 【程序2】 题目：企业发放的奖金根据利润提成。利润(I)低于或等于10万元时，奖金可提10%；利润高 于10万元，低于20万元时，低于10万元的部分按10%提成，高于10万元的部分，可可提 成7.5%；20万到40万之间时，高于20万元的部分，可提成5%；40万到60万之间时高于 40万元的部分，可提成3%；60万到100万之间时，高于60万元的部分，可提成1.5%，高于 100万元时，超过100万元的部分按1%提成，从键盘输入当月利润I，求应发放奖金总数？ 1.程序分析：请利用数轴来分界，定位。注意定义时需把奖金定义成长整型。 2.程序源代码： main() { long int i; int bonus1,bonus2,bonus4,bonus6,bonus10,bonus; scanf("%ld",&i); bonus1=100000*0.1;bonus2=bonus1+100000*0.75; bonus4=bonus2+200000*0.5; bonus6=bonus4+200000*0.3; bonus10=bonus6+400000*0.15; if(i<=100000) Brute Force(BF或蛮力搜索) 算法： 这是世界上最简单的算法了。 首先将匹配串和模式串左对齐，然后从左向右一个一个进行比较，如果不成功则模式串向右移动一个单位。 速度最慢。 那么，怎么改进呢？ 我们注意到Brute Force 算法是每次移动一个单位，一个一个单位移动显然太慢，是不是可以找到一些办法，让每次能够让模式串多移动一些位置呢？ 当然是可以的。 我们也注意到，Brute Force 是很不intelligent 的，每次匹配不成功的时候，前面匹配成功的信息都被当作废物丢弃了，当然，就如现在的变废为宝一样，我们也同样可以将前面匹配成功的信息利用起来，极大地减少计算机的处理时间，节省成本。^_^ 注意，蛮力搜索算法虽然速度慢，但其很通用，文章最后会有一些更多的关于蛮力搜索的信息。 KMP算法 首先介绍的就是KMP 算法。 这个算法实在是太有名了，大学上的算法课程除了最笨的Brute Force 算法，然后就介绍了KMP 算法。也难怪，呵呵。谁让Knuth D.E. 这么world famous 呢，不仅拿了图灵奖，而且还写出了计算机界的Bible 1.定积分近似计算： /*梯形法*/ double integral(double a,double b,long n) { long i;double s,h,x; h=(b-a)/n; s=h*(f(a)+f(b))/2; x=a; for(i=1;i } 3.素数的判断： /*方法一*/ for (t=1,i=2;i MySQL中的字符串模式匹配 本文关键字：MySQL 字符串模式匹配 MySQL提供标准的SQL模式匹配，以及一种基于象Unix实用程序如vi、grep 和sed的扩展正则表达式模式匹配的格式。 标准的SQL模式匹配 SQL的模式匹配允许你使用“_”匹配任何单个字符，而“%”匹配任意数目字符(包括零个字符)。在 MySQL中，SQL的模式缺省是忽略大小写的。下面显示一些例子。注意在你使用SQL模式时，你不能使用=或!=；而使用LIKE或NOT LIKE比较操作符。 例如，在表pet中，为了找出以“b”开头的名字： +--------+--------+---------+------+------------+------------+ | name | owner | species | sex | birth | death | +--------+--------+---------+------+------------+------------+ | Buffy | Harold | dog | f | 1989-05-13 | NULL | | Bowser | Diane | dog | m | 1989-08-31 | 1995-07-29 | +--------+--------+---------+------+------------+------------+ 为了找出以“fy”结尾的名字： +--------+--------+---------+------+------------+-------+ | name | owner | species | sex | birth | death | +--------+--------+---------+------+------------+-------+ | Fluffy | Harold | cat | f | 1993-02-04 | NULL | | Buffy | Harold | dog | f | 1989-05-13 | NULL | +--------+--------+---------+------+------------+-------+ 为了找出包含一个“w”的名字： +----------+-------+---------+------+------------+------------+ | name | owner | species | sex | birth | death | +----------+-------+---------+------+------------+------------+ 个人觉得这篇文章是网上的介绍有关KMP算法更让人容易理解的文章了，确实说得很“详细”，耐心地把它看完肯定会有所收获的～～，另外有关模式函数值next[i]确实有很多版本啊，在另外一些面向对象的算法描述书中也有失效函数f(j)的说法，其实是一个意思，即next[j]=f(j-1)+1，不过还是next[j]这种表示法好理解啊： KMP字符串模式匹配详解 KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。 一.简单匹配算法 先来看一个简单匹配算法的函数： int Index_BF ( char S [ ], char T [ ], int pos ) { /* 若串S 中从第pos(S 的下标0≤pos C语言常用算法集合 1.定积分近似计算： /*梯形法*/ double integral(double a,double b,long n) { long i;double s,h,x; h=(b-a)/n; s=h*(f(a)+f(b))/2; x=a; for(i=1;i if(n==1||n==2) *s=1; else{ fib(n-1,&f1); fib(n-2,&f2); *s=f1+f2; } } 3.素数的判断： /*方法一*/ for (t=1,i=2;i 60.题目:古典问题:有一对兔子,从出生后第3个月 起每个月都生一对兔子,小兔 子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总 数 为多少? _________________________________________________________________ _ 程序分析:兔子的规律为数列1,1,2,3,5,8,13,21.... _________________________________________________________________ __ 程序源代码: main() { long f1,f2; int i; f1=f2=1; for(i=1;i<=20;i++) { printf("%12ld %12ld",f1,f2); if(i%2==0) printf("\n");/*控制输出,每行四个*/ f1=f1+f2;/*前两个月加起来赋值给第三个月*/ f2=f1+f2;/*前两个月加起来赋值给第三个月*/ } } 上题还可用一维数组处理,you try! 61.题目:判断101-200之间有多少个素数,并输出所有素数。 _________________________________________________________________ _ 1 程序分析:判断素数的方法:用一个数分别去除2到sqrt(这个数),如果能被 整 除,则表明此数不是素数,反之是素数。 _________________________________________________________________ __ 程序源代码: #include "math.h" main() { int m,i,k,h=0,leap=1; 数据结构面试之十四——字符串的模式匹配 题注：《面试宝典》有相关习题，但思路相对不清晰，排版有错误，作者对此参考相关书籍和自己观点进行了重写，供大家参考。 十四、字符串的模式匹配 1. 模式匹配定义——子串的定位操作称为串的模式匹配。 2. 普通字符串匹配BF算法（Brute Force 算法，即蛮力算法） 【算法思想】： 第（1）步；从主串S的第pos个字符和模式的第一个字符进行比较之，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式串的字符比较之。 第（2）步骤；依次类推，直至模式T中的每一个字符依次和主串S中的一个连续的字符序列相等，则称匹配成功；函数值为和模式T中第一个字符相等的字符在主串S中的序号，否则称为匹配不成功，函数值为0。 比如对于主串S=”abacababc”; 模式串T=”abab”; 匹配成功，返回4。 对于主串S=”abcabcabaac”; 模式串T=”abab”; 匹配不成功，返回0。 【算法实现】： //普通字符串匹配算法的实现 int Index(char* strS, char* strT, int pos) { //返回strT在strS中第pos个字符后出现的位置。 int i = pos; int j = 0; int k = 0; int lens = strlen(strS); int lent = strlen(strT); while(i < lens && j < lent) { if(strS[i+k] == strT[j]) { ++j; //模式串跳步 ++k; //主串(内)跳步 } else { i = i+1; j=0; //指针回溯，下一个首位字符 k=0; } }//end i if(j >= lent) { return i; } else { return 0; } }//end [算法时间复杂度]：设主串长度为m,模式串的长度为n。一般情况下n 实验7、字符串查找 目的 掌握字符串模式匹配的经典算法。 问题描述 分别用简单方法和KMP方法实现index在文本串中查找指定字符串的功能。 步骤 1.定义字符串类型 2.实现简单的index操作，从文本串中查找指定字符串。 3.实现KMP方法的index操作，从文本串中查找指定字符串。 4.[选]建立一个文本文件，读入每一行来测试自己完成的练习，观察并理解程序的各 个处理。 设备和环境 PC计算机、Windows操作系统、C/C++开发环境 结论 能够理解和掌握字符串模式匹配的典型算法。 思考题 1.对KMP算法分别用手工和程序对某个模式串输出next和nextval。 朴素算法： #include #define ERROR -2 #define MAXLEN 100//字符串的最大长度 char S[MAXLEN+10],T[MAXLEN+10],st[MAXLEN+10];//串S和串T int S0,T0; //S0：串S的长度 T0：串T的长度 int pos; //pos的起始位置 void Init(char *S,int &S0)//读入字符串 { int len,i; New_Input: scanf("%s",st);//读入字符串 len=strlen(st); if (len>MAXLEN)//如果字符串的长度大于规定的字符串最大长度 { printf("This String is too long,Please Input a new one.nn"); goto New_Input;//重新读入字符串 实验题目：字符串的模式匹配 一、实验描述 用BF算法实现字符串的模式匹配 二、实验目的和任务 从主串的第pos位置字符开始和模式子串字符比较，如果相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式子串的字符比较。直到找到匹配字符串或者是主串结尾。 三、概要设计 BF(Brute Force)算法是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串P的第一个字符进行匹配，若相等，则继续比较S的第二个字符和P的第二个字符；若不相等，则比较S的第二个字符和P的第一个字符，依次比较下去，直到得出最后的匹配结果。 四、运行与测试 #include { char *szSource = "ababcababa"; char *szSub = "ababa"; int index =BFMatch(szSource, szSub); printf("目标串包含匹配串的起始位置：%d",index); } 五、运行结果 六、实验心得 通过这次课程设计，让我了解了字符串的定位操作即字符串模式匹配的基本概念和算法,探讨了字符串模式匹配操作的最基本的BF匹配算法。虽然看起来很简单的程序，做起来却遇到了不少问题，编程中出行了一些小错误，多次查改之后再进行修改，所以我觉得在以后的学习中，我会更加注重实践，注重多练，多积累。 《KMP字符串模式匹配算法》教学课例 程玉胜 安庆师范学院计算机与信息学院 KMP字符串模式匹配是数据结构课程中一个重要的知识点，也是一个难点（学过KMP 算法的同学100％认为:KMP是数据结构课程中最难的部分）。为了消除他们对KMP算法学习的恐惧心理，激发他们的学习兴趣，调动其积极性，显得尤为重要。 基于以上，我们根据学生的认知特点和接受水平，对教材内容进行了重新构建，并按照数据结构中?时间复杂度?概念，增加了不同模式匹配算法的运行时间，动态逼真的显示了算法的?时间?性能，获得了较好的教学效果。 一、教学目标 知识目标：让学生了解KMP算法应用的普遍性。如：在目前众多的文字处理软件中得到广泛应用，如Microsoft Word中的?查找?或?替换?操作。而这种操作实现的机制，同学们特别是计算机专业的学生很少去想过。 能力目标：要求学生体验一个完整的抽象数据类型（ADT）的实现方法和过程，并学会判断、计算算法优劣的方法。 价值目标：消除恐怖的学习心态，让学生感悟数据结构算法实际应用价值，从而激发学习的兴趣，形成积极主动式学习的态度。 二、教材分析 使用教材是清华大学严蔚敏教授并由清华大学出版社出版的《数据结构（C语言版）》，该教材难度较大，其实验方法特别是ADT方法在教材中介绍较少，而且KMP算法更是从理论分析的角度介绍了匹配算法和next的计算，自学难度很大；虽然该节知识点属于?**（表示难度较大，可以不讲）?，但是其又是考研的一个热点，所以我们又不得不讲。 三、教学重点、难点 教学重点：KMP算法中的next和改进的nextval计算 教学难点：KMP算法中如何计算next值 四、教具准备 卡片：多个字符串，字符串指针 强力磁吸：6个 五、互动式教学过程 /* ===================================================================== ======== 相关知识介绍（所有定义只为帮助读者理解相关概念，并非严格定义）： 1、稳定排序和非稳定排序 简单地说就是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，我们就 说这种排序方法是稳定的。反之，就是非稳定的。 比如：一组数排序前是a1,a2,a3,a4,a5，其中a2=a4，经过某种排序后为 a1,a2,a4,a3,a5， 则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。假如变成a1,a4, a2,a3,a5就不是稳定的了。 2、内排序和外排序 在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序； 在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。 3、算法的时间复杂度和空间复杂度 所谓算法的时间复杂度，是指执行算法所需要的计算工作量。 一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。 ===================================================================== =========== */ /* ================================================ 功能：选择排序 输入：数组名称（也就是数组首地址）、数组中元素个数 ================================================ */ /* ==================================================== 算法思想简单描述： 串的模式匹配问题实验总结 1实验题目： 实现(,,) Index S T pos函数。其中，(,,) Index S T pos为串T在串S的第pos个字符后第一次出现的位置。 2实验目的： 熟练掌握串模式匹配算法。 3实验方法： 分别用朴素模式匹配和KMP快速模式匹配来实现串的模式匹配问题。具体方法如下： 朴素模式匹配：输入两个字符串，主串S和子串T，从S串的第pos个位置开始与T的第一个位置比较，若不同执行i=i-j+2；j=1两个语句；若相同，则执行语句++i; ++j;一直比较完毕为止，若S中有与T相同的部分则返回主串（S字符串）和子串（T字符串）相匹配时第一次出现的位置，若没有就返回0。 KMP快速模式匹配：构造函数get_next(char *T,int *next)，求出主串S串中各个字符的next值，然后在Index_KMP(char *S,char *T,int pos)函数中调用get_next(char *T,int *next)函数并调用next值，从S串的第pos 位置开始与T 的第一个位置进行比较，若两者相等或j位置的字符next值等于0，则进行语句++i;++j;即一直向下进行。否则，执行语句j=A[j]；直到比较完毕为止。 若S中有与T相同的部分则返回主串（S字符串）和子串（T字符串）相匹配时第一次出现的位置，若没有就返回0 4实验过程与结果： （1）、选择1功能“输入主串、子串和匹配起始位置”，输入主串S：asdfghjkl, 输入子串T：gh,输入pos的值为：2。 选择2功能“朴素的模式匹配算法”，输出结果为 5； 选择3功能“KMP快速模式匹配算法”，输出结果为 5； 选择0功能，退出程序。 截图如下： 模式匹配 参数扩展还包括了一些模式匹配功能，该功能带有在文件名扩展或globbing 中使用的通配符功能。注意：这不是grep 使用的正则表达式匹配。 表2. Shell 扩展模式匹配扩展目的 ${PARAMETER#WORD} shell 像文件名扩展中那样扩展WORD，并从PARAMETER 扩展后的值的开头删除最短的匹配模式（若存在匹配模式的话）。使用‘@’或‘$’即可删除列表中每个参数的模式。 ${PARAMETER##WORD} 导致从开头删除最长的匹配模式而不是最短的匹配模式。 ${PARAMETER%WORD} shell 像文件名扩展中那样扩展WORD，并从PARAMETER 扩展后的值末尾删除最短的匹配模式（若存在匹配模式的话）。使用‘@’或‘$’即可删除列表中每个参数的模式。 ${PARAMETER%%WORD} 导致从末尾删除最长的匹配模式而不是最短的匹配模式。 ${PARAMETER/PATTERN/STRING} shell 像文件名扩展中那样扩展PATTERN，并替换PARAMETER 扩展后的值中最长的匹配模式（若存在匹配模式的话）。为了在PARAMETER 扩展后的值开头匹配模式，可以给PATTERN 附上前缀#，如果要在值末尾匹配模式，则附上前缀%。如果STRING 为空，则末尾的/ 可能被忽略，匹配将被删除。使用‘@’或‘$’即可对列表中的每个参数迚行模式替换。 ${PARAMETER//PATTERN/STRING} 对所有的匹配（而不只是第一个匹配）执行替换。 清单11 给出了模式匹配扩展的一些基本用法。 清单11. 模式匹配示例 [ian@pinguino ~]$ x="a1 b1 c2 d2" [ian@pinguino ~]$ echo ${x#*1} b1 c2 d2 [ian@pinguino ~]$ echo ${x##*1} c2 d2 [ian@pinguino ~]$ echo ${x%1*} a1 b [ian@pinguino ~]$ echo ${x%%1*} C语言常用算法归纳 应当掌握的一般算法 一、基本算法： 交换、累加、累乘 二、非数值计算常用经典算法： 穷举、排序（冒泡，选择）、查找（顺序即线性） 三、数值计算常用经典算法： 级数计算（直接、简接即递推）、一元非线性方程求根（牛顿迭代法、二分法）、定积分计算（矩形法、梯形法） 四、其他： 迭代、进制转换、矩阵转置、字符处理（统计、数字串、字母大小写转换、加密等）、整数各数位上数字的获取、辗转相除法求最大公约数（最小公倍数）、求最值、判断素数（各种变形）、数组元素的插入（删除）、二维数组的其他典型问题（方阵的特点、杨辉三角形） 详细讲解 一、基本算法 1．交换（两量交换借助第三者） 例1、任意读入两个整数，将二者的值交换后输出。 main() { int a,b,t; scanf("%d%d",&a,&b); printf("%d,%d\n",a,b); t=a; a=b; b=t; printf("%d,%d\n",a,b); } 【解析】程序中加粗部分为算法的核心，如同交换两个杯子里的饮料，必须借助第三个空杯子。 假设输入的值分别为3、7，则第一行输出为3，7；第二行输出为7，3。 其中t为中间变量，起到“空杯子”的作用。 注意：三句赋值语句赋值号左右的各量之间的关系！ 【应用】 例2、任意读入三个整数，然后按从小到大的顺序输出。 main() { int a,b,c,t; scanf("%d%d%d",&a,&b,&c); /*以下两个if语句使得a中存放的数最小*/ if(a>b){ t=a; a=b; b=t; } if(a>c){ t=a; a=c; c=t; } /*以下if语句使得b中存放的数次小*/ if(b>c) { t=b; b=c; c=t; } printf("%d,%d,%d\n",a,b,c); } 2．累加 累加算法的要领是形如“s=s+A”的累加式，此式必须出现在循环中才能被反复执行，从而实现累加功能。“A”通常是有规律变化的表达式，s在进入循环前必须获得合适的初值，通常为0。 例1、求1+2+3+……+100的和。 main() { int i,s; s=0; i=1; while(i<=100) { s=s+i; /*累加式*/ i=i+1; /*特殊的累加式*/ } printf("1+2+3+...+100=%d\n",s); } 【解析】程序中加粗部分为累加式的典型形式，赋值号左右都出现的变量称为累加器，其中“i = i + 1”为特殊的累加式，每次累加的值为1，这样的累加器又称为计数器。 3．累乘 C程序设计的常用算法 算法（Algorithm）：计算机解题的基本思想方法和步骤。算法的描述：是对要解决一个问题或要完成一项任务所采取的方法和步骤的描述，包括需要什么数据（输入什么数据、输出什么结果）、采用什么结构、使用什么语句以及如何安排这些语句等。通常使用自然语言、结构化流程图、伪代码等来描述算法。 一、简单数值类算法 此类问题都要使用循环，要注意根据问题确定循环变量的初值、终值或结束条件，更要注意用来表示计数、和、阶乘的变量的初值。 1、求阶乘：n!=1*2*384…..*n; n!= n*(n-1)!= 下列程序用于求n的阶乘.在累乘之前,一定要将用于存放乘积的变量的值初始化为1. long func(int n) { int i; long t=1; for(i=2;i<=n;i++) t*=i; return t; } printf("\n"); } main() { int n; scanf("%d", &n); printf("n!=%ld\n", fac(n)); } 2、整数拆分问题：把一个整数各个位上的数字存到数组中 #define N 4 /* N代表整数位数*/ viod split(int n, int a[ ]） /* 1478: a[ 3]=8, a[2 ]=7, a[1 ]=4…*/ {int i; for(i=N-1;i!=0; i--) { a[i]=n%10; n=n/10; } } main() {int i,m=1478,b[N-1]; split(m, b）; for(i=0;i<4; i++) printf(“%5d”, b[i]); 八、常用算法 （一）考核知识要点 1．交换、累加、累乘、求最大（小）值 2．穷举 3．排序（冒泡、插入、选择） 4．查找（顺序、折半） 5．级数计算（递推法） 6．一元方程求解（牛顿迭代法、二分法） 7．矩阵（转置） 8．定积分计算（矩形法、梯形法） 9．辗转相除法求最大公约数、判断素数 10．数制转换 （二）重点、难点精解 教材中给出的算法就不再赘述了。 1．基本操作：交换、累加、累乘 1）交换 交换算法的要领是“借助第三者”（如同交换两个杯子里的饮料，必须借助第三个空杯子）。例如，交换两个整型变量里的数值：int a=7,b=9,t; t=a; a=b; b=t; (不借助第三者，也能交换两个整型变量里的数值，但不通用，只是一个题目而已。 例如：int a=7,b=9; a=a+b; b=a-b; a=a-b;) 2）累加 累加算法的要领是形如“s=s+A”的累加式，此式必须出现在循环中才能被反复执行，从而实现累加功能。“A”通常是有规律变化的表达式，s在进入循环前必须获得合适的初值，通常为0。 3）累乘 累乘算法的要领是形如“s=s*A”的累乘式，此式必须出现在循环中才能被反复执行，从而实现累乘功能。“A”通常是有规律变化的表达式，s在进入循环前必须获得合适的初值，通常为1。 2．非数值计算常用经典算法 1）穷举法 也称为“枚举法”，即将可能出现的各种情况一一测试，判断是否满足条件，一般采用循环来实现。 例如，用穷举法输出“将1元人民币兑换成1分、2分、5分硬币”的所有方法。 main() {int y,e,w; for(y=0;y<=100;y++) for(e=0;e<=50;e++) for(w=0;w<=20;w++) 《数据结构与算法》实验报告 一、需求分析 问题描述：在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。 基本要求： （l）对以下6种常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。 （2）待排序表的表长不小于100000；其中的数据要用伪随机数程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。（3）最后要对结果作简单分析，包括对各组数据得出结果波动大小的解释。数据测试：二．概要设计 1.程序所需的抽象数据类型的定义： typedef int BOOL; //说明BOOL是int的别名 typedef struct StudentData { int num; //存放关键字} Data; typedef struct LinkList { int Length; //数组长度 Data Record[MAXSIZE]; //用数组存放所有的随机数 } LinkList int RandArray[MAXSIZE]; //定义长度为MAXSIZE的随机数组void RandomNum() //随机生成函数 void InitLinkList(LinkList* L) //初始化链表 BOOL LT(int i, int j,int* CmpNum) //比较i和j 的大小 void Display(LinkList* L) //显示输出函数 void ShellSort(LinkList* L, int dlta[], int t,int* CmpNum, int* ChgNum) //希尔排序 void QuickSort (LinkList* L, int* CmpNum, int* ChgNum) //快速排序 void HeapSort (LinkList* L, int* CmpNum, int* ChgNum) //堆排序 void BubbleSort(LinkList* L, int* CmpNum, int* ChgNum) //冒泡排序 void SelSort(LinkList* L, int* CmpNum, int* ChgNum) //选择排序 void Compare(LinkList* L,int* CmpNum, int* ChgNum) //比较所有排序 2 .各程序模块之间的层次（调用）关系：字符串的模式匹配算法
非常全的C语言常用算法
C语言经典算法100例(1---30)
字符串匹配算法总结
C语言常用算法集合
MySQL中的字符串模式匹配.
KMP字符串模式匹配算法解释
最新C语言常用算法集合汇总
c语言经典算法100例
C语言字符串模式匹配
字符串模式匹配
字符串的模式匹配实验报告
《KMP 字符串模式匹配算法》教学课例
C语言常用排序算法
串的模式匹配问题实验总结(用C实现)
Shell正则表达式与模式匹配
最新C语言常用算法归纳
C语言常用算法程序汇总
(整理)C语言常用算法.
数据结构(C语言版)实验报告-(内部排序算法比较)