《数据结构a》第04章——02课件

《《数据结构a》第04章——02课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构DataStructuresinC++内容提要字符串ADT字符串的存储表示字符串基本运算的实现模式匹配算法（简单模式匹配算法和KMP算法）4.4字符串4.4.1字符串ADT字符串的定义字符串(简称为串)是由n(0)个字符组成的有限序列。S=“a0a1…an－1”(n≥0)其中，S是串名，单引号括起来的字符序列是串S的值。n是串中字符个数，又称串长度，n=0的串称为空串。要注意区分空串和空白串。串中任意连续个字符组成的子序列称为该串的子串，包含子串的串称为主串。通常以子串的首字符在主串中的位置作为子串在主串中的位置。S=‘abcab

2、caabcbcde’P=‘aabc’ADTString{数据：字符串是由n(≥0)个字符组成的有限序列S="a0a1…an-1"，0i

3、i开始的len个字符组成的子串。Find(i,P):返回子串P在当前串对象中的位置。若当前串对象不包含串P，则返回-1。}4.4.2字符串的存储表示顺序存储表示串的顺序表示可用C++的一维字符数组来描述。定义长度实际长度#includechars[20]="cdabcde“；链接存储表示#includeclassString{public:String();String(constchar*p);~String(){delete[]str;};intFind(inti,String&P);priva

4、te:intn;//当前串长char*str;//动态一维字符数组的指针};String::String(constchar*p){n=strlen(p);str=newchar[n+1];strcpy(str,p);}4.4.3简单模式匹配算法设有两个字符串s和p，在串s中找串p的过程被称为模式匹配。这里s为主串，p为子串，又称为模式。#include#includevoidmain(){charp[10]="abc",s[20]="cdabcde",*t;if(t=strstr(s,p))co

5、ut<<"Thestringfromstrstris:"<

6、

7、i>n-1){//越界检查cout<<"Outofbounds!"<

8、//模式串回到第1个字符t=str+(++i);//主串回到i+1的位置}if(*pp=='')returni;return-1;}简单匹配算法的渐近时间复杂度：设主串和模式串的长度为n和m，while循环最多进行n-m+1趟，每趟最多比较m次，这样总的比较次数最多是(n-m+1)×m。由于(n-m+1)×m≤(n-m+m)×m=n×m，因此简单模式匹配算法在最坏情况下的时间复杂度是O(n×m)。例如：n=14,m=4,while循环执行14-4+1趟，每趟比较4次。主串S=‘aaaaaaaaaaaaab’子串P=‘aaab’4.4.4

9、模式匹配的KMP算法S=“abaabaabababb”P=“abaababa”‘a‘ab‘abaababa’失败函数的定义设有长度为m的模式串p＝p0p1…pm－1，失败函数f定义为：设比较在sipj处失败，f(j)0表示，下一趟从si与pf(j)开始，f(j)=-1表示p0si,下一趟从p0与si＋1开始从定义计算失败函数KMP算法KMP匹配算法intString::FindKMP(inti,String&P){if(i<0

10、

11、i>n-1){cout<<"Outofbounds!"<

12、,m=P.n;while(i

13、

14、str[i]==P.str[j]){i++;j++;}elsej=P.f[j];return((j==m)?i-m