数据结构与算法第三章2013ppt课件

1、3.1 字符串抽象数据类型字符串抽象数据类型3.2 字符串的存储结构和类定义字符串的存储结构和类定义3.3 字符串运算的算法实现字符串运算的算法实现3.4 字符串的模式匹配字符串的模式匹配3.1字符串抽象数据类型字符串抽象数据类型3.1.1 基本概念基本概念3.1.2 String抽象数据类型抽象数据类型 3.1.1 基本概念 字符串：由0个或多个字符的顺序排列所组成的复合数据结构，简称“串”。串的长度：一个字符串所包含的字符个数。空串：长度为零的串，它不包含任何字符内容。3.1.1.1字符串常数和变量字符串常数和变量 字符串常数 例如： n 字符串变量3.1.1.2 字符字符 字符(char

2、) ：组成字符串的基本单位。 在C和C中 单字节8 bits） 采用ASCII码对128个符号字符集charset进行编码3.1.1.3 字符的编码顺序字符的编码顺序 为了字符串间比较和运算的便利，字符编码表一般遵循约定俗成的“偏序编码规则”。 字符偏序：根据字符的自然含义，某些字符间两两可以比较次序。 其实大多数情况下就是字典序 中文字符串有些特例，例如“笔划序3.1.1.4 C+标准标准string 标准字符串：将C+的函数库作为字符串数据类型的方案。 例如：char SM; 串的结束标记：0 0是ASCII码中8位BIT全0码，又称为NULL符。3.1.1.4 C+标准标准string(

3、续续) 1. 串长函数串长函数 int strlen(char *s); 2. 串复制串复制 char *strcpy(char *s1, char*s2); 3串拼接串拼接 char *strcat(char *s1, char *s2); 4串比较串比较 int strcmp(char *s1, char *s2);3.1.1.4 C+标准标准string(续续) 5输入和输出函数 6定位函数 char *strchr(char *s, char c); 7右定位函数 char *strrchr(char *s, char c);3.1.1.4 C+标准标准string(续续)3.1.2

4、String抽象数据类型抽象数据类型 字符串类class String）： 不采用char SM的形式 而采用一种动态变长的存储结构。class String /字符串类字符串类/它的存储结构和实现方法使用了它的存储结构和实现方法使用了C+标准标准string(简称标准简称标准串串),/为了区别为了区别,类类String所派生创建的实例对象所派生创建的实例对象,简称简称本串本串,或或实实例串例串/在程序首在程序首,要要#include 和和#include 及及/ 及及#include ，以及，以及#include /1.字符串的数据表示：字符串的数据表示：/字符串字符串S 通常用顺序存放，用

5、数组通常用顺序存放，用数组S存储，元素的类型为存储，元素的类型为char/字符串为变长，使用变量字符串为变长，使用变量size记录串的当前长度记录串的当前长度/ 2.使用变量访问字符串：使用变量访问字符串：/字符串变量能参与运算字符串变量能参与运算,例如例如S1 + S2表示两个字符串首尾拼表示两个字符串首尾拼接在一起接在一起/用数组用数组str存储字符串，在内部可以用存储字符串，在内部可以用stri访问串的第访问串的第i个个字符字符,/ 3.字符串类的运算集：请参看下面的成员函数字符串类的运算集：请参看下面的成员函数private: char *str; /私有的指针变量，用于指向存储向量私

6、有的指针变量，用于指向存储向量strsize+1 int size； /本串的当前实际长度本串的当前实际长度public:String(char *s = “”); /创建一个空的字符串创建一个空的字符串String(char *s); / 创建新字符串，并将标准字符串创建新字符串，并将标准字符串s拷贝为初值拷贝为初值String(const String &copy);/拷贝构造函数拷贝构造函数String() / 销毁本串，从计算机存储空间删去本串销毁本串，从计算机存储空间删去本串/下面是算子的定义，包括赋值算子下面是算子的定义，包括赋值算子 拼接算子拼接算子 和比较算子和比较算子

7、 等等const String& operator= (const char *s）；）； /赋值操作赋值操作=，标准串，标准串s拷贝到本串拷贝到本串const String& operator= (const String& s）; /赋值操作赋值操作=，串，串s复制到本串复制到本串String operator (char *s）;/拼接算子，本串拼接标准串拼接算子，本串拼接标准串sString operator (String& s）；）；/拼接算子，本串拼接串拼接算子，本串拼接串sfriend String operator+ (char *s1, St

8、ring& s）；）；/友函数作为拼接算子友函数作为拼接算子+ 其返回值是一个实例串其返回值是一个实例串,等于标准串等于标准串str拼接串拼接串s/关系算子，用于比较相等、大、小，例如bool operator (char *s）;/比较大小,本串小于标准串s则返回非0bool operator (String& s）;/比较大小，本串小于串s则返回非0friend bool operator和 (isteream& istr,String& s）；friend ostream& operator (osteream& ostr,String&a

9、mp; s）；/ 子串函数：插入子串、寻找子串、提取子串、删除子串等，例如String Substr(int index，int count）; /它们的功能参见下文/串与字符函数：按字符定位等，例如int Find(char c,int start);/在本串中寻找字符c,从下标start开始找,/ 寻找到c后,返回字符c在本串的下标位置/其他函数：求串长、判空串、清为空串、int strlen(); /返回本串的当前串长int IsEmpty(); /判本串为空串?void clear(); /清本串为空串char &operator(int x); /左操作数const char

10、 &operator(int x)const; /右操作数;3.1.2.3 赋值算子、拼接算子赋值算子、拼接算子和比较算子和比较算子 赋值算子 拼接算子 比较算子 = !=和=3.1.2.4 输入输出算子输入输出算子 输入算子 输出算子3.1.2.5 处理子串处理子串(Substring)的函数的函数 简称“子串函数” 提取子串 插入子串 寻找子串 删除子串 3.1.2.6 字符串中的字符字符串中的字符 重载下标算子 char& operator (int n); 按字符定位下标 int Find(char c,int start); 反向寻找，定位尾部出现的字符 int Fi

11、ndLast(char c);3.2 字符串的存储结构和类定义字符串的存储结构和类定义 3.2.2字符串类字符串类class String的存储结构的存储结构 3.2.1字符串的顺序存储字符串的顺序存储3.2.1字符串的顺序存储字符串的顺序存储 对于串长变化不大的字符串，可以有三种处理方案： （1用S0作为记录串长的存储单元。 缺点：限制了串的最大长度不能超过256。3.2.1字符串的顺序存储字符串的顺序存储(续续)（2为存储串的长度，另辟一个存储的地方。 缺点：串的最大长度一般是静态给定的，不是动态申请数组空间。3.2.1字符串的顺序存储字符串的顺序存储(续续)（3用一个特殊的末尾标记0。

12、例如：C+语言的string函数库（include ）采用这一存储结构。3.2.2 字符串类字符串类class String的存储的存储结构结构 抽取子串函数 例如： String s1 = value-; s2 = s1.Substr(2,3); 上述语句涉及的存储形式如下页所示。3.2.2 字符串类字符串类class String的存储的存储结构结构(续续)微软VC的CString类介绍 自动的动态存储管理，串的最大长度不超过2GB 容器型 不必使用new和delete 使用特点： 变量申明 CString s6( x, 6 ); / s6 = xxxxxx CString city =

13、Philadelphia; / 串常数作为初值 赋值语句 s1 = s2 = hi there; 变量比较if( s1 = s2 ) 方法调用s1.MakeUpper(); 内部字符比较if( s20 = h )3.3 字符串运算的算法实现字符串运算的算法实现 1. 串长函数串长函数 int strlen(char *s); 2. 串复制串复制 char *strcpy(char *s1, char*s2); 3串拼接串拼接 char *strcat(char *s1, char *s2); 4串比较串比较 int strcmp(char *s1, char *s2);3.3.1 C+标准串运

14、算的实现标准串运算的实现3.3.2 String串运算的实现串运算的实现3.3.1 C+标准串运算的实现标准串运算的实现 【算法【算法3-1 】字符串的复制】字符串的复制 char *strcpy(char *d, char *s) /这个程序的毛病是，如果字符串这个程序的毛病是，如果字符串s比字符串比字符串d要长，要长， /这个程序没有检查拷贝出界，没有报告错误。这个程序没有检查拷贝出界，没有报告错误。 /可能会造成可能会造成d的越界的越界 int i =0; while (si != 0) di = si; i+; di = 0; return d; 3.3.1 C+标准串运算的实现标准串

15、运算的实现(续续) 【算法3-2 】字符串的比较 int strcmp( char *d, char *s) int i =0; while (si != 0 & di != 0 ) if (di si) return 1; else if (di =0 & di != ch ) i-;/当本串不含字符当本串不含字符ch，则在串尾结束；，则在串尾结束；/当成功寻找到当成功寻找到ch，返回该位置指针，返回该位置指针if (i0) return 0;else return &di ;3.3.2 String串运算的实现串运算的实现(续续) 【算法3-7 】创建算子(cons

16、tructor) String:String(char *s) /先要确定新创字符串实际需要的存储空间，s的类 /型为(char *)，作为新创字符串的初值。确定 /s的长度，用标准字符串函数strlen(s)计算长度 size = strlen(s) ; /然后，在动态存储区域开辟一块空间，用于存 /储初值s，把结束字符也包括进来 str new char size1;/开辟空间不成功时，运行异常，退出开辟空间不成功时，运行异常，退出assert(str != 0);/用标准字符串函数用标准字符串函数strcpy，将，将s完全完全/复制到指针复制到指针str所指的存储空间所指的存储空间str

17、cpy( str, s );拷贝构造函数拷贝构造函数String: String(const String &copy); size=copy.size ; str new char size1; assert(str != 0); strcpy( str, copy.str );3.3.2 String串运算的实现串运算的实现(续续) 【算法3-8 】销毁算子destructor） String:String() /必须释放动态存储空间 delete str; 3.3.2 String串运算的实现串运算的实现(续续) 【算法【算法3-9】拼接算子】拼接算子 String String

18、:operator+ (String& s) /把字符串把字符串s和本实例拼接成为一个长串返回和本实例拼接成为一个长串返回 String temp; /创建一个串创建一个串temp int len; /准备工作，计算拼接后的长串的长度准备工作，计算拼接后的长串的长度 len = size + s.size; /把把temp串创建时申请的存储空间全部释放串创建时申请的存储空间全部释放 delete temp.str; /准备工作，开辟空间，为存放长串之用准备工作，开辟空间，为存放长串之用 temp.str= new char len+1;/若开辟动态存储空间不成功，则退出若开辟动态存储空

19、间不成功，则退出assert(temp.str!= 0)；temp.size= len;/字符串字符串str以以0结尾存到结尾存到tempstrcpy(temp.str, str);/再把参数再把参数s的的str和本实例的和本实例的str拼接为长串拼接为长串strcat(temp.str, s.str);return temp;3.3.2 String串运算的实现串运算的实现(续续) 【算法3-10】赋值算子 const String& String:operator= (const String& s) /参数s将被赋值到本串 /若本串的串长和s的串长不同，则应该释放本串的

20、/str存储空间，并开辟新的空间 if(this != &s) delete str ; /释放原存储空间 str = new char s.size+1;/若开辟动态存储空间失败，则退出正常运若开辟动态存储空间失败，则退出正常运行行assert(str != 0)；size = s.size;strcpy(str , s.str ); /返回本实例，作为返回本实例，作为String类的一个实例类的一个实例return *this;bool String: operator (String& s） return strcmp(str,s.str) (isteream&

21、istr,String& s） char temp1000;istrtemp;s=temp;return istr;friend ostream& String: operator (osteream& ostr,String& s） ostr temp; delete s.str; s.size=strlen(temp); s.str=new chars.size+1; assert(s.str !=0); strcpy(s.str,temp); return istr;3.3.2 String串运算的实现串运算的实现(续续) 【算法3-11】抽取子串函数 S

22、tring String:Substr(int index , int count ) /取出一个子串返回，自下标index开始，长度为count int i; /本串自下标index开始向右数直到串尾，长度为left int left = size index ; String temp; char *p, *q; /若下标index值太大，超过本串实际串长，则返回空串 if(index = size) return temp;/若若count超过自超过自index以右的实际子串长度，以右的实际子串长度，/ 则把则把count变小变小if(count left )count = left;/

23、释放原来的存储空间释放原来的存储空间delete temp.str; /若开辟动态存储空间失败，则退出若开辟动态存储空间失败，则退出temp.str = new char count+1;assert(temp.str != 0)；/p的内容是一个指针，的内容是一个指针，/指向目前暂无内容的字符数组的首字符处指向目前暂无内容的字符数组的首字符处p = temp.str;/q的内容是一个指针，的内容是一个指针，/指向本实例串的指向本实例串的str数组的下标数组的下标index字符字符q = &strindex;/用用q指针取出它所指的字符内容后，指针加指针取出它所指的字符内容后，指针加1

24、/ 用用p该指针所指的字符单元接受拷贝，该指针也该指针所指的字符单元接受拷贝，该指针也加加1for (i =0; i count; i+)*p+ = *q+;/循环结束后，让循环结束后，让temp.str的结尾为的结尾为0*p = 0;temp.size = count;return temp;3.3.2 String串运算的实现串运算的实现(续续) 【算法3-12 】查找字符 int String:Find(char c,int start) /在本实例字符串寻找字符c，如果找到，那么 /将其下标位置作为整数函数值返回，假如 /c没有找到，则为负值。参数start是下标， /从start下标

25、开始寻找c的工作,若start为 /0，则从头寻找 int i = start; assert( i =0&x=0&xsize);return strx;3.4 字符串的模式匹配字符串的模式匹配 模式匹配(pattern matching) 一个目标对象S字符串） 一个模板patternP字符串） 任务：用给定的模板P，在目标字符串S中搜索与模板P全同的一个子串，并求出S中第一个和P全同匹配的子串简称为“配串”），返回其首字符位置。 s=“ababcabcacbab” t=“abcac” i01234tjabcacNj-10001Nj-100-11朴素模式匹配：例如朴素模式匹配

26、：例如l把模式与目标逐一进行比较首位置开始），直到碰到不匹配的字符把模式与目标逐一进行比较首位置开始），直到碰到不匹配的字符为止模式右移一位再次开始匹配）为止模式右移一位再次开始匹配）l算法可在第一个匹配或是目标的结束处停止算法可在第一个匹配或是目标的结束处停止abacababacababacaacabcabacabaa01234587691011121314151617abacababacababacababacababacab朴素模式匹配(Brute Force)3.4.1 模式匹配原始算法模式匹配原始算法(续续)_BF算法算法 【算法3-13 】模式匹配原始算法其一） #include

27、#include int FindPat_1(String S, String P, int startindex) / 从S末尾倒数一个模板长度位置 int LastIndex = S.strlen() - P.strlen(); /开始匹配位置startindex的值过大，匹配无法成功 if (LastIndex startindex) return (-1);/g为为S的游标，用模板的游标，用模板P和和S第第g位置子串比较，位置子串比较，若失若失/败则继续循环败则继续循环for (int g= startindex; g = LastIndex; g+) if ( P = S.Subst

28、r(g, P.strlen()return g;/若若for循环结束，则整个匹配失败，返回值为负，循环结束，则整个匹配失败，返回值为负，return (-1);【算法3-13】模式匹配原始算法（其二）/ 从从S末尾倒数一个模板长度位置末尾倒数一个模板长度位置int LastIndex = S. strlen() - P. strlen();/开始匹配位置开始匹配位置startindex的值过大，匹配无法成功的值过大，匹配无法成功if (LastIndex startindex)return (-1);/ i 是指向是指向S内部字符的游标，内部字符的游标，/ j 是指向是指向P内部字符的游标内部

29、字符的游标int i=startindex, j = 0;/下面开始循环匹配下面开始循环匹配while (i S. strlen() & j = P. strlen() /return (i - j);elsereturn -1;朴素匹配算法：效率分析朴素匹配算法：效率分析 假定目标假定目标T的长度为的长度为n，模式，模式P长度为长度为m，且且 m n 在最坏的情况下，每一次循环都不成功，在最坏的情况下，每一次循环都不成功，则一共要进行比较则一共要进行比较n-m+1次次 每一次每一次“相同匹配比较所耗费的时间，相同匹配比较所耗费的时间，是是P和和T逐个字符比较的时间，最坏情况逐个字符比

30、较的时间，最坏情况下，共下，共m次次 因而，整个算法的最坏时间开销估计为因而，整个算法的最坏时间开销估计为O(mn)朴素匹配算法：最差情况朴素匹配算法：最差情况 模式与目标的每一个长度为模式与目标的每一个长度为m的子串进行比较的子串进行比较l目标形如目标形如an, 模模式形如式形如am-1bl总比较次数：总比较次数：lO(n-m+1)l时间复杂度：时间复杂度：lO(mn)AAAAAAAAAAAAAAAAAAAAAAAAAAB 5次比较AAAAAAAAAAAAAAAAAAAAAA AAAAB 5次比较AAAAAAAAAAAAAAAAAAAAAA AAAAB 5次比较AAAAAAAAAAAAAAA

31、AAAAAAA AAAAB 5次比较AAAAAAAAAAAAAAAAAAAAAA AAAAB 5次比较朴素匹配算法：朴素匹配算法：最佳情况最佳情况-没找到模式没找到模式 总是在第一个字符上不匹配总是在第一个字符上不匹配l总比较次数：总比较次数：ln-m+1l时间复杂度：时间复杂度：lO(n)AAAAAAAAAAAAAAAAAAAAAHOOOOH 1次比较AAAAAAAAAAAAAAAAAAAAAH OOOOH 1次比较AAAAAAAAAAAAAAAAAAAAAHOOOOH 1次比较AAAAAAAAAAAAAAAAAAAAAH OOOOH 1次比较AAAAAAAAAAAAAAAAAAAAAH 1

32、次比较 OOOOH朴素模式匹配算法：朴素模式匹配算法：最佳情况最佳情况-找到模式找到模式 在目标的前在目标的前m个位置上找到模式，设个位置上找到模式，设 m = 5l总比较次数：总比较次数：ml时间复杂度：时间复杂度：O(m)AAAAAAAAAAAAAAAAAAAAABAAAAA 5次比较次比较 朴素算法的问题：回溯朴素算法的问题：回溯 朴素算法之所以效率不高的原朴素算法之所以效率不高的原因在于匹配过程中目标串有回因在于匹配过程中目标串有回溯，且这些回溯并非必要溯，且这些回溯并非必要 e.g., 由由1可知：可知： P5 T5， P0=T0, P1 = T1,同时由同时由 P0 P1可得知可得

33、知P0T1 故将故将 P 右右移一位后第移一位后第2趟比较一定不趟比较一定不等等; 比较冗余比较冗余 那么把那么把P右移几位合适？右移几位合适？ 既能既能消除冗余比较又保证不丢失配消除冗余比较又保证不丢失配串呢？串呢？T a b a c a a b a c c a b a c a b a aP a b a c a b 1P5 T5 P右移一位右移一位T a b a c a a b a c c a b a c a b a aP a b a c a b 2P0 T1 P右移一位右移一位T a b a c a a b a c c a b a c a b a aP a b a c a b 3P1 T3

34、 P右移一位右移一位T a b a c a a b a c c a b a c a b a aP a b a c a b.无回溯匹配算法无回溯匹配算法关键在于匹配过程中，一旦关键在于匹配过程中，一旦Pi 和和Tj比较不等时，比较不等时，即即 substr(P,1,i-1) = substr(T, j-i+1,i-1) 且且Pi Tj 要能立即确定右移的位数和继续比较的字符，要能立即确定右移的位数和继续比较的字符，即该用即该用P中的哪个字符和中的哪个字符和Tj进行比较？进行比较？ 如何定位如何定位? 保留之前比较的结果保留之前比较的结果?若把这个字符记为若把这个字符记为Pk，显然有，显然有k 0

35、，k 0 且且 Pj = Pk ，则，则nj+1 = k+1；当当k 0, 且且P j Pk 时，则令时，则令k = nk，并让，并让 步步骤骤3循环直到条件不满足变为循环直到条件不满足变为P j = Pk 或或 k = -1）；）；当当 k0 (此时，此时，k -1), 那么那么 nj1= 0。otherwise 0,existsk asuchif,1)-k.j-P(j 1)-P(0.k & jk0 :maxk0jfor1, j next对应的求特征向量算法框架在在KMP快速模式匹配中，若用快速模式匹配中，若用ni表示第表示第i位的特征值，位的特征值，特征数特征数ni +1( -1

36、ni 0的的ni+1，假定已知前一位置没有，假定已知前一位置没有优化以前的特征数优化以前的特征数 ni = k；2. 当当k =0，且，且Pi Pk 时，则令时，则令k = nk，并让步骤，并让步骤2循循环直到条件不满足变为环直到条件不满足变为Pi = =Pk ，或上一步骤，或上一步骤k = 0而导致而导致k = nk步骤后步骤后k = -1了）；了）；3. ni+1 = k+1这是没有优化以前的特征数，在优化前这是没有优化以前的特征数，在优化前传到第一步用于计算下一个特征值）；传到第一步用于计算下一个特征值）；4. 若若Pi+1 = =Pk+1 ，则，则ni+1 = nk+1此步骤为优此步骤

37、为优化）。化）。一般把模式的第一个字符的特征数设置为一般把模式的第一个字符的特征数设置为-1，以尽可能地减少，以尽可能地减少冗余比较：冗余比较： 特征向量的计算特征向量的计算 求求p0, p1,pj-1 中最大相同的前缀与后中最大相同的前缀与后缀的长度缀的长度t nextj = t 计算计算nextj时充分利用了位置时充分利用了位置j之前的各之前的各个字符的个字符的next值值特征向量的计算特征向量的计算int *findNext(String P) / 计算向量计算向量N int m = P.length(); / m为模板为模板P的长度的长度 assert( m 0); / 若若m0，退出

38、，退出 int *next = new intm; / 动态存储区开辟整数数组动态存储区开辟整数数组 assert( next != 0); / 若开辟存储区域失败，退出若开辟存储区域失败，退出 next0 = -1;int i = 0; int k = -1; while (i = 0 & P i != Pk) k= nextk;i+; k+;nexti = k; return next;i012345PjabacabNj-100101特征向量的计算：优化版特征向量的计算：优化版?当当 j = 0时，令时，令nextj = -1其实，若其实，若Pk = Pj ，则有，则有pk Ti；

39、此时应再右移，使；此时应再右移，使 Pnextk与与 Tj 比较，故比较，故 第第2步可进一步优化为：步可进一步优化为： if (Pk = Pj) nextj = nextk; else nextj = k;j012345PjabacabNj-100101Nj-10-11-10特征向量的计算：优化版特征向量的计算：优化版int *findNext(String P) int i = 0; int k = -1; int m = P.length(); / m为字符串为字符串P的长度的长度 assert(m 0); / 若若m0，退出，退出 int *next = new intm; / 动态存储区开辟整数数组动态存储区开辟整数数组assert(next != 0); / 若开辟存储区域失败，退出若开辟存储区域失败，退出 next0 = -1;while (i = 0 & Pi != Pk) / 求最大首尾子串求最大首尾子串k = nextk;i+; k+;if (Pi = Pk ) nexti = nextk;/ Pi和和Pk相等，优化相等，优化else nexti = k;/ 不需要优化，就是位置不需要优化，就是位置i的首尾子串长度的首尾子串长度return next;特征向量计算示例特征向量计算示例iknextP-0