数据结构与算法第三部分字符串课件.ppt

数据结构与算法第三章 字符串,主讲人 张铭http:/,北京大学信息学院 版权所有，转载或翻印必究 Page 2,主要内容,3.1 字符串抽象数据类型3.2 字符串的存储结构和类定义3.3 字符串运算的算法实现3.4 字符串的模式匹配,北京大学信息学院 版权所有，转载或翻印必究 Page 3,3.1字符串抽象数据类型,3.1.1 基本概念3.1.2 String抽象数据类型,北京大学信息学院 版权所有，转载或翻印必究 Page 4,3.1.1 基本概念,字符串，由0个或多个字符的顺序排列所组成的复合数据结构，简称“串”。串的长度：一个字符串所包含的字符个数。空串：长度为零的串，它不包含任何字符内容。,北京大学信息学院 版权所有，转载或翻印必究 Page 5,3.1.1.1字符串常数和变量,字符串常数例如：n字符串变量,北京大学信息学院 版权所有，转载或翻印必究 Page 6,3.1.1.2 字符,字符(char)：组成字符串的基本单位。在C和C中单字节（8 bits）采用ASCII码对128个符号（字符集charset）进行编码,北京大学信息学院 版权所有，转载或翻印必究 Page 7,3.1.1.3 字符的编码顺序,为了字符串间比较和运算的便利，字符编码表一般遵循约定俗成的“偏序编码规则”。字符偏序：根据字符的自然含义，某些字符间两两可以比较次序。其实大多数情况下就是字典序中文字符串有些特例，例如“笔划”序,北京大学信息学院 版权所有，转载或翻印必究 Page 8,3.1.1.4 C+标准string,标准字符串：将C+的函数库作为字符串数据类型的方案。例如：char SM;串的结束标记：00是ASCII码中8位BIT全0码，又称为NULL符。,北京大学信息学院 版权所有，转载或翻印必究 Page 9,3.1.1.4 C+标准string(续),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);,北京大学信息学院 版权所有，转载或翻印必究 Page 10,3.1.1.4 C+标准string(续),5输入和输出函数6定位函数 char*strchr(char*s,char c);7右定位函数 char*strrchr(char*s,char c);,北京大学信息学院 版权所有，转载或翻印必究 Page 11,3.1.1.4 C+标准string(续),北京大学信息学院 版权所有，转载或翻印必究 Page 12,3.1.2 String抽象数据类型,字符串类（class String）：不采用char SM的形式而采用一种动态变长的存储结构。,北京大学信息学院 版权所有，转载或翻印必究 Page 13,3.1.2 String抽象数据类型(续),北京大学信息学院 版权所有，转载或翻印必究 Page 14,北京大学信息学院 版权所有，转载或翻印必究 Page 15,北京大学信息学院 版权所有，转载或翻印必究 Page 16,3.1.2.3 赋值算子、拼接算子和比较算子,赋值算子拼接算子比较算子=!=和=,北京大学信息学院 版权所有，转载或翻印必究 Page 17,3.1.2.4 输入输出算子,输入算子输出算子,北京大学信息学院 版权所有，转载或翻印必究 Page 18,3.1.2.5 处理子串(Substring)的函数,简称“子串函数”提取子串插入子串寻找子串删除子串,北京大学信息学院 版权所有，转载或翻印必究 Page 19,3.1.2.6 字符串中的字符,重载下标算子 char,北京大学信息学院 版权所有，转载或翻印必究 Page 20,3.2 字符串的存储结构和类定义,3.2.1字符串的顺序存储3.2.2字符串类class String的存储结构,北京大学信息学院 版权所有，转载或翻印必究 Page 21,3.2.1字符串的顺序存储,对于串长变化不大的字符串，可以有三种处理方案：（1）用S0作为记录串长的存储单元。缺点：限制了串的最大长度不能超过256。,北京大学信息学院 版权所有，转载或翻印必究 Page 22,3.2.1字符串的顺序存储(续),（2）为存储串的长度，另辟一个存储的地方。缺点：串的最大长度一般是静态给定的，不是动态申请数组空间。,北京大学信息学院 版权所有，转载或翻印必究 Page 23,3.2.1字符串的顺序存储(续),（3）用一个特殊的末尾标记0。例如：C+语言的string函数库（include）采用这一存储结构。,北京大学信息学院 版权所有，转载或翻印必究 Page 24,3.2.2 字符串类class String的存储结构,抽取子串函数 例如：String s1=value-;s2=s1.Substr(2,3);上述语句涉及的存储形式如下页所示。,北京大学信息学院 版权所有，转载或翻印必究 Page 25,3.2.2 字符串类class String的存储结构(续),北京大学信息学院 版权所有，转载或翻印必究 Page 26,3.2.2 字符串类class String的存储结构(续),微软VC的CString类介绍自动的动态存储管理，串的最大长度不超过2GB 容器型不必使用new和delete 使用特点：变量申明CString s6(x,6);/s6=xxxxxxCString city=Philadelphia;/串常数作为初值赋值语句s1=s2=hi there;变量比较 if(s1=s2)方法调用 s1.MakeUpper();内部字符比较 if(s20=h),北京大学信息学院 版权所有，转载或翻印必究 Page 27,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);,北京大学信息学院 版权所有，转载或翻印必究 Page 28,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;,北京大学信息学院 版权所有，转载或翻印必究 Page 29,3.3.1 C+标准串运算的实现(续),【算法3-2】字符串的比较int strcmp(char*d,char*s)int i=0;while(si!=0,北京大学信息学院 版权所有，转载或翻印必究 Page 30,3.3.1 C+标准串运算的实现(续),i+;if(di=0,北京大学信息学院 版权所有，转载或翻印必究 Page 31,3.3.1 C+标准串运算的实现(续),【算法3-3】求字符串的长度int strlen(char d)int i=0;while(di!=0)i+;return i;,北京大学信息学院 版权所有，转载或翻印必究 Page 32,3.3.1 C+标准串运算的实现(续),【算法3-4】寻找字符char*strchr(char*d,char ch)/按照数组指针d依次寻找字符ch，/如果找到ch，则将指针位置返回，/如果没有找到ch，则为0值。i=0;,北京大学信息学院 版权所有，转载或翻印必究 Page 33,3.3.1 C+标准串运算的实现(续),/循环跳过那些不是ch的字符while(di!=0,北京大学信息学院 版权所有，转载或翻印必究 Page 34,3.3.1 C+标准串运算的实现(续),【算法3-5】反向寻找字符char*strrchr(char*d,char ch)/按照数组指针d，从其尾部反着寻找字符ch，/如果找到ch，则将指针位置返回，/如果没有找到ch，则为0值。i=0;/找串尾 while(di!=0)i+;,北京大学信息学院 版权所有，转载或翻印必究 Page 35,3.3.1 C+标准串运算的实现(续),/循环跳过那些不是ch的字符while(i=0,北京大学信息学院 版权所有，转载或翻印必究 Page 36,3.3.2 String串运算的实现(续),【算法3-7】创建算子(constructor)String:String(char*s)/先要确定新创字符串实际需要的存储空间，s的类/型为(char*)，作为新创字符串的初值。确定/s的长度，用标准字符串函数strlen(s)计算长度size=strlen(s);/然后，在动态存储区域开辟一块空间，用于存/储初值s，把结束字符也包括进来str new char size1;,北京大学信息学院 版权所有，转载或翻印必究 Page 37,3.3.2 String串运算的实现(续),/开辟空间不成功时，运行异常，退出assert(str!=0);/用标准字符串函数strcpy，将s完全/复制到指针str所指的存储空间strcpy(str,s);,北京大学信息学院 版权所有，转载或翻印必究 Page 38,3.3.2 String串运算的实现(续),【算法3-8】销毁算子（destructor）String:String()/必须释放动态存储空间delete str;,北京大学信息学院 版权所有，转载或翻印必究 Page 39,3.3.2 String串运算的实现(续),【算法3-9】拼接算子String String:operator+(String,北京大学信息学院 版权所有，转载或翻印必究 Page 40,3.3.2 String串运算的实现(续),/若开辟动态存储空间不成功，则退出assert(temp.str!=0)；temp.size=len;/字符串str（以0结尾）存到tempstrcpy(temp.str,str);/再把参数s的str和本实例的str拼接为长串strcat(temp.str,s.str);return temp;,北京大学信息学院 版权所有，转载或翻印必究 Page 41,3.3.2 String串运算的实现(续),【算法3-10】赋值算子String String:operator=(String,北京大学信息学院 版权所有，转载或翻印必究 Page 42,3.3.2 String串运算的实现(续),/若开辟动态存储空间失败，则退出正常运行 assert(str!=0)；size=s.size;strcpy(str,s.str);/返回本实例，作为String类的一个实例return*this;,北京大学信息学院 版权所有，转载或翻印必究 Page 43,3.3.2 String串运算的实现(续),【算法3-11】抽取子串函数String String:Substr(int index,int count)/取出一个子串返回，自下标index开始，长度为count int i;/本串自下标index开始向右数直到串尾，长度为leftint left=size index;String temp;char*p,*q;/若下标index值太大，超过本串实际串长，则返回空串if(index=size)/注意不是 index=size-1 return temp;,北京大学信息学院 版权所有，转载或翻印必究 Page 44,3.3.2 String串运算的实现(续),/若count超过自index以右的实际子串长度，/则把count变小if(count left)count=left;/释放原来的存储空间delete temp.str;/张铭注释：注意此语句！/若开辟动态存储空间失败，则退出temp.str=new char count+1;assert(temp.str!=0)；/p的内容是一个指针，/指向目前暂无内容的字符数组的首字符处p=temp.str;,北京大学信息学院 版权所有，转载或翻印必究 Page 45,3.3.2 String串运算的实现(续),/q的内容是一个指针，/指向本实例串的str数组的下标index字符q=,北京大学信息学院 版权所有，转载或翻印必究 Page 46,3.3.2 String串运算的实现(续),【算法 3-12】查找字符int String:Find(char c,int start)/在本实例字符串寻找字符c，如果找到，则/将其下标位置作为整数函数值返回，如果/c没有找到，则为负值。参数start是下标，/从start下标开始寻找c的工作,若start为/0，则从头寻找int i=start;assert(i size);,北京大学信息学院 版权所有，转载或翻印必究 Page 47,3.3.2 String串运算的实现(续),/循环跳过那些不是c的字符while(stri!=0,北京大学信息学院 版权所有，转载或翻印必究 Page 48,3.4 字符串的模式匹配,模式匹配(pattern matching)一个目标对象S（字符串）一个模板（pattern）P（字符串）任务：用给定的模板P，在目标字符串S中搜索与模板P全同的一个子串，并求出S中第一个和P全同匹配的子串（简称为“配串”），返回其首字符位置。,北京大学信息学院 版权所有，转载或翻印必究 Page 49,S s0 s1 sisi+1 si+2 si+m-2 si+m-1 sn-1 P p0 p1 p2 pm-2 pm-1为使模式 P 与目标 S 匹配，必须满足 p0 p1 p2 pm-1=si si+1 si+2 si+m-1,北京大学信息学院 版权所有，转载或翻印必究 Page 50,朴素模式匹配,S=ababababababbP=abababb X abababb X abababb X abababb X abababb X abababb X abababb,北京大学信息学院 版权所有，转载或翻印必究 Page 51,【算法3-13】模式匹配原始算法（其一）,#include“String.h”/不是#includeint FindPat_1(String S,String P,int startindex)/从S末尾倒数一个模板长度位置 int LastIndex=S.strlen()-P.strlen();if(LastIndex startindex)return(-1);/g为S的游标，用模板P和S第g位置子串比较，/若失败则继续循环 for(int g=startindex;g=LastIndex;g+)if(P=S.Substr(g,P.strlen()return g;/若for循环结束，则整个匹配失败，返回值为负，return(-1);,北京大学信息学院 版权所有，转载或翻印必究 Page 52,3.4.1 模式匹配原始算法(续),【算法3-13】模式匹配原始算法（其二）int FindPat_2(String S,String P,int startindex)/从S末尾倒数一个模板长度位置 int LastIndex=S.strlen()-P.strlen();/开始匹配位置startindex的值过大，匹配无法成功 if(LastIndex startindex)return(-1);/i 是指向S内部字符的游标，/j 是指向P内部字符的游标 int i=startindex,j=0;,北京大学信息学院 版权所有，转载或翻印必究 Page 53,3.4.1 模式匹配原始算法(续),/下面开始循环匹配while(i LastIndex,北京大学信息学院 版权所有，转载或翻印必究 Page 54,3.4.1 模式匹配原始算法(续),/如果匹配成功，则返回该S子串的开/始位置；如果P和S匹配失败，函数/返回值为负 if(j P.strlen()/“”可以吗？return(i-1);else return-1;,北京大学信息学院 版权所有，转载或翻印必究 Page 55,3.4.1 朴素模式匹配(纠错),【算法3-13】模式匹配原始算法（纠错）int FindPat_2(String S,String P,int startindex)/从S末尾倒数一个模板长度位置 int LastIndex=S.strlen()-P.strlen();/开始匹配位置startindex的值过大，匹配无法成功 if(LastIndex startindex)return(-1);/i 是指向S内部字符的游标，/j 是指向P内部字符的游标 int i=startindex,j=0;,北京大学信息学院 版权所有，转载或翻印必究 Page 56,3.4.1 朴素模式匹配纠错(续),/下面开始循环匹配while(iS.strlen(),错误1：如果“i LastIndex”，那么后面的就匹配不到。例如，abababababb abababb S.strlen()=11，P.strlen()=7，LastIndex=4;“i=4，j=0”,匹配a，接着，“i=5，j=1”就进行不了。,错误2：如果“j=P.strlen()”，则P的结束符号0也拿来比较，除非正好匹配S的末端，否则出错！,北京大学信息学院 版权所有，转载或翻印必究 Page 57,3.4.1朴素模式匹配纠错(续),/如果匹配成功，则返回该S子串的开/始位置；如果P和S匹配失败，函数/返回值为负 if(j=P.strlen()/“”可以吗？return(i-j);else return-1;,错误3：如果“j P.strlen”，其实匹配结束时，正好j=P.size（因为匹配最后一个字符后，还j+）出错！其实“j=P.strlen”就可以！,错误4：return(i-1);匹配完成后，i指向S中最后一个字符的下一位，减去匹配串的长度，才是开始位。,北京大学信息学院 版权所有，转载或翻印必究 Page 58,3.4.1 模式匹配原始算法(续),例如，aaaaaaaaaab aaaaaab分析假定目标S的长度为n，模板P长度为m，mn 在最坏的情况下，每一次循环都不成功，则一共要进行比较（n-m+1）次每一次“相同匹配”比较所耗费的时间，是P和S逐个字符比较的时间，最坏情况下，共m次。因此，整个算法的最坏时间开销估计为O(m n)。,北京大学信息学院 版权所有，转载或翻印必究 Page 59,例1，a a a a a a a a a a b a a a a a a b a a a a a a b a a a a a a b例2，a b c d e f a b c d e f f a b c d e f f a b c d e f f,北京大学信息学院 版权所有，转载或翻印必究 Page 60,KMP算法思想,S s0 s1 si-j-1 si-j si-j+1 si-j+2 si-2 si-1 si sn-1 P p0 p1 p2 pj-2 pj-1 pj 则有 si-j si-j+1 si-j+2 si-1=p0 p1 p2 pj-1(1)如果 p0 p1 pj-2 p1 p2 pj-1(2)则立刻可以断定 p0 p1 pj-2 si-j+1 si-j+2 si-1(朴素匹配的)下一趟一定不匹配，可以跳过去,北京大学信息学院 版权所有，转载或翻印必究 Page 61,同样，若 p0 p1 pj-3 p2 p3 pj-1则再下一趟也不匹配，因为有 p0 p1 pj-3 si-j+2 si-j+3 si-1直到对于某一个“k”值(首尾串长度)，使得 p0 p1 pk pj-k-1 pj-k pj-1 且 p0 p1 pk-1=pj-k pj-k+1 pj-1则 p0 p1 pk-1=si-k si-k+1 si-1 si pj-k pj-k+1 pj-1 pj p0 p1 pk-1 pk,模式右滑j-k位,北京大学信息学院 版权所有，转载或翻印必究 Page 62,模式右滑j-k位,si-j si-j+1 si-j+2 si-k si-k+1 si-1 si p0 p1 p2 pj-k pj-k+1 pj-1 pj p0 p1 pk-1 pk,北京大学信息学院 版权所有，转载或翻印必究 Page 63,3.4.2 字符串的特征向量N,设模板P由m个字符组成：记为P=q0 q1q2q3qm-1令特征向量N用于表示模板P的字符分布特征，并简称N向量。它和P同长，由m个特征数n0 nm-1非负整数组成：记为N n0 n1n2n3nm-1,北京大学信息学院 版权所有，转载或翻印必究 Page 64,3.4.2 字符串的特征向量N(续),下面说明ni的含义和它的递归定义：列出模板P开头的任意t个字符，把它称为P的前缀子串。q0q1q2qt-1,北京大学信息学院 版权所有，转载或翻印必究 Page 65,3.4.2 字符串的特征向量N(续),在P的第i位置的左边，也取出t个字符，称为i位置的左子串。qi-t+1.qi-2qi-1qi,北京大学信息学院 版权所有，转载或翻印必究 Page 66,3.4.2 字符串的特征向量N(续),计算特征数ni设法求出最长的（t最大的）能够与前缀子串匹配的左子串（简称第i位的最长前缀串）。t就是要求的特征数ni。,北京大学信息学院 版权所有，转载或翻印必究 Page 67,3.4.2 字符串的特征向量N(续),特征数ni(0 ni i)是递归定义的，定义如下：n00，对于i 1的ni，假定已知前一位置的特征数ni-1，并且ni-1 k；如果qi qk，则ni k1；当qi qk 且 k0时，则 令k n k-1;让循环直到条件不满足；当qi qk 且 k 0时，则 ni 0;,北京大学信息学院 版权所有，转载或翻印必究 Page 68,3.4.2 字符串的特征向量N(续),举例：,北京大学信息学院 版权所有，转载或翻印必究 Page 69,3.4.2 字符串的特征向量N(续),北京大学信息学院 版权所有，转载或翻印必究 Page 70,3.4.2 字符串的特征向量N(续),【算法3-14】计算向量Nint*Next(String P)int m=P.strlen();/m为模板P的长度 assert(m 0);/若m0，退出 int*N=new intm;/动态存储区开辟整数数组 assert(N!=0);/若开辟存储区域失败，退出 N0=0;for(int i=1;i m;i+)/分析P的每个位置i int k=Ni-1;/第(i-1)位置的最长前缀串长度,北京大学信息学院 版权所有，转载或翻印必究 Page 71,3.4.2 字符串的特征向量N(续),/以下while语句递推决定合适的前缀位置k while(k 0,北京大学信息学院 版权所有，转载或翻印必究 Page 72,3.4.3 KMP模式匹配算法,【算法3-15】KMP模式匹配算法int KMP_FindPat(String S,String P,int*N,int startindex)/假定事先已经计算出P的特征数组N，作为输入参数/S末尾再倒数一个模板长度位置 int LastIndex=S.size-P.size;if(LastIndex-startindex)0)return(-1);/startindex过大，匹配无法成功 int i;/i 是指向S内部字符的游标，int j=0;/j 是指向P内部字符的游标，,北京大学信息学院 版权所有，转载或翻印必究 Page 73,3.4.3 KMP模式匹配算法(续),/S游标i循环加1 for(i=startindex;i 0)j=Nj-1;/Pj与Si相同，继续下一步循环 if(P.strj=S.stri)j+;/匹配成功，返回该S子串的开始位置 if(j=P.size)return(i-j+1);return(-1);/P和S整个匹配失败，函数返回值为负,讨论：如果“i LastIndex”，那么后面的就匹配不到。例如，aaaaaaaaaab aaaaaab S.size=11，P.size=7，LastIndex=4;“i=4，j=0”,匹配a，接着，“i=5，j=1”就进行不了。,北京大学信息学院 版权所有，转载或翻印必究 Page 74,KMP模式匹配示例（一）,0 1 2 3 4 5 6 P=a b a b a b b N=0 0 1 2 3 4 0 0 1 2 3 4 5 6 7 8 9 10 11 12S=a b a b a b a b a b a b b a b a b a b b X i=6,j=6,Nj-1=4 a b a b a b b X i=8,j=6,Nj-1=4 a b a b a b b X i=10,j=6,j=4 a b a b a b b,北京大学信息学院 版权所有，转载或翻印必究 Page 75,0 1 2 3 4 5 6 7 8 9P=a a a a b a a a a cN=0 1 2 3 0 1 2 3 4 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14S=a a b a a a a a a b a a a a c b c a a b a b c a a a a b a a a a c X i=2,j=2,Nj-1=1 a a a a b a a a a c X i=2,j=1,Nj-1=0 a a a a b a a a a c X i=7,j=4,Nj-1=3 a a a a b a a a a c X i=8,j=4,Nj-1=3 a a a a b a a a a c,北京大学信息学院 版权所有，转载或翻印必究 Page 76,0 1 2 3 4 5 6 7 8 9P=a a a a b a a a a cN=0 1 2 1 0 1 2 3 4 0 X(不是最长的，应该是3)0 1 2 3 4 5 6 7 8 9 10 11 12 13 14S=a a b a a a a a a b a a a a c b c a a b a b c a a a a b a a a a c X i=2,j=2,Nj-1=1 a a a a b a a a a c X i=2,j=1,Nj-1=0 a a a a b a a a a c X i=7,j=4,Nj-1=1 a a a a b a a a a c（错过了！）,北京大学信息学院 版权所有，转载或翻印必究 Page 77,KMP算法的效率,两重循环for循环最多执行nS.size次其内部的while循环，最长循环次数是mP.size次。初看起来其时间开销也可能达到O(nm)。,北京大学信息学院 版权所有，转载或翻印必究 Page 78,循环体中“j=Nj-1;”语句的执行次数不能超过n次。否则，由于“j=Nj-1;”每执行一次必然使得j减少(至少减1)而使得j增加的操作只有“j+”那么，如果“j=Nj-1;”的执行次数超过n次，最终的结果必然使得j为负数。这是不可能的。同理可以分析出求next数组的时间为O(m)因此，KMP算法的时间为(n+m),北京大学信息学院 版权所有，转载或翻印必究 Page 79,总结,字符串抽象数据类型字符串的存储结构和类定义字符串运算的算法实现字符串的模式匹配特征向量N及相应的KMP算法还有其他变种、优化http:/,北京大学信息学院 版权所有，转载或翻印必究 Page 80,优化,例，a a a a c a a a a a a b a a a a a a b a a a a a a b,