北大数据结构与算法课件03字符串

数据结构与算法第三章字符串信息科学与技术学院“数据结构与算法”教学小组北京大学信息学院张铭编写©版权所有，转载或翻印必究Page2nextback主要内容„3.1字符串抽象数据类型„3.2字符串的存储结构和类定义„3.3字符串运算的算法实现„3.4字符串的模式匹配北京大学信息学院张铭编写©版权所有，转载或翻印必究Page3nextback3.1字符串抽象数据类型„3.1.1基本概念„3.1.2String抽象数据类型北京大学信息学院张铭编写©版权所有，转载或翻印必究Page4nextback3.1.1基本概念„字符串，由0个或多个字符的顺序排列所组成的复合数据结构，简称“串”。„串的长度：一个字符串所包含的字符个数。„空串：长度为零的串，它不包含任何字符内容。北京大学信息学院张铭编写©版权所有，转载或翻印必究Page5nextback3.1.1.1字符串常数和变量„字符串常数„例如：\n„字符串变量北京大学信息学院张铭编写©版权所有，转载或翻印必究Page6nextback3.1.1.2字符„字符(char)：组成字符串的基本单位。„在C和C＋＋中„单字节（8bits）„采用ASCII码对128个符号（字符集charset）进行编码北京大学信息学院张铭编写©版权所有，转载或翻印必究Page7nextback3.1.1.4C++标准string„标准字符串：将C++的string.h函数库作为字符串数据类型的方案。„例如：charS[M];„串的结束标记：'\0'„'\0'是ASCII码中8位BIT全0码，又称为NULL符。北京大学信息学院张铭编写©版权所有，转载或翻印必究Page8nextback3.1.1.4C++标准string(续)„1.串长函数intstrlen(char*s);„2.串复制char*strcpy(char*s1,char*s2);„3．串拼接char*strcat(char*s1,char*s2);„4．串比较intstrcmp(char*s1,char*s2);北京大学信息学院张铭编写©版权所有，转载或翻印必究Page9nextback3.1.1.4C++标准string(续)„5．输入和输出函数„6．定位函数char*strchr(char*s,charc);„7．右定位函数char*strrchr(char*s,charc);北京大学信息学院张铭编写©版权所有，转载或翻印必究Page10nextback3.1.2String抽象数据类型„字符串类（classString）：„不采用charS[M]的形式„而采用一种动态变长的存储结构。北京大学信息学院张铭编写©版权所有，转载或翻印必究Page11nextback3.1.2String抽象数据类型(续)classString//字符串类//它的存储结构和实现方法使用了C++标准string(简称标准串),//为了区别,类String所派生创建的实例对象,简称‘本串’,或‘实例串’//在程序首,要#includestring.h和#includeiostream.h及//及#includestdlib.h，以及#includeassert.h{//1.字符串的数据表示：//字符串S通常用顺序存放，用数组S[]存储，元素的类型为char//字符串为变长，使用变量size记录串的当前长度//2.使用变量访问字符串：//字符串变量能参与运算,例如S1+S2表示两个字符串首尾拼接在一起//用数组str[]存储字符串，在内部可以用str[i]访问串的第i个字符,//3.字符串类的运算集：请参看下面的成员函数北京大学信息学院张铭编写©版权所有，转载或翻印必究Page12nextbackprivate:char*str;//私有的指针变量，用于指向存储向量str[size+1]intsize；//本串的当前实际长度public:String(char*s='');//创建一个空的字符串String(char*s);//创建新字符串，并将标准字符串s拷贝为初值~String()//销毁本串，从计算机存储空间删去本串//下面是函数的定义，包括赋值函数＝拼接函数＋和比较函数等String&operator=(char*s）；//赋值操作=，标准串s拷贝到本串String&operator=(String&s）;//赋值操作=，串s复制到本串Stringoperator＋(char*s）;//拼接函数＋，本串拼接标准串sStringoperator＋(String&s）；//拼接函数＋，本串拼接串sfriendStringoperator+(char*s1,String&s）；//友函数作为拼接函数+其返回值是一个实例串,等于标准串str拼接串s北京大学信息学院张铭编写©版权所有，转载或翻印必究Page13nextback//‘关系’函数，用于比较相等、大、小，例如intoperator(char*s）;//比较大小,本串小于标准串s则返回非0intoperator(String&s）;//比较大小，本串小于串s则返回非0friendintoperator(char*s1,String&s）；//友函数用于比较,//,标准串s1小于串s,则返回非0//‘输入输出’函数和以及读子串等，例如友函数friendistream&operator(isteream&istr,String&s）；friendostream&operator(osteream&istr,String&s）；//‘子串函数’：插入子串、寻找子串、提取子串、删除子串等，例如StringSubstr(intindex，intcount）;//它们的功能参见下文//‘串与字符’函数：按字符定位等，例如intFind(charc,intstart);//在本串中寻找字符c,从下标start开始找,//寻找到c后,返回字符c在本串的下标位置//其他函数：求串长、判空串、清为空串、intstrlen();//返回本串的当前串长intIsEmpty();//判本串为空串?voidclear();//清本串为空串};北京大学信息学院张铭编写©版权所有，转载或翻印必究Page14nextback3.1.2.3赋值操作符、拼接操作符和比较操作符„赋值操作符＝„拼接操作符＋„比较操作符==!=和==北京大学信息学院张铭编写©版权所有，转载或翻印必究Page15nextback3.1.2.4输入输出操作符和„输入操作符„输出操作符北京大学信息学院张铭编写©版权所有，转载或翻印必究Page16nextback3.1.2.5处理子串(Substring)的函数„简称“子串函数”„提取子串„插入子串„寻找子串„删除子串„…北京大学信息学院张铭编写©版权所有，转载或翻印必究Page17nextback3.1.2.6字符串中的字符„重载下标操作符[]char&operator[](intn);„按字符定位下标intFind(charc,intstart);„反向寻找，定位尾部出现的字符intFindLast(charc);北京大学信息学院张铭编写©版权所有，转载或翻印必究Page18nextback3.2字符串的存储结构和类定义„3.2.1字符串的顺序存储„3.2.2字符串类classString的存储结构北京大学信息学院张铭编写©版权所有，转载或翻印必究Page19nextback3.2.1字符串的顺序存储„用S[0]作为记录串长的存储单元„缺点：串的最大长度不能超过256„另辟一个存储的地方存储串的长度„缺点：串的最大长度静态给定„用一个特殊的末尾标记'\0'„例如：C++语言的string函数库（＃includestring.h）采用这一存储结构北京大学信息学院张铭编写©版权所有，转载或翻印必究Page20nextback3.2.2字符串类classString的存储结构(续)„微软VC＋＋的CString类介绍„自动的动态存储管理，串的最大长度不超过2GB„容器型„不必使用new和delete„使用特点：„变量申明„CStrings6('x',6);//s6=xxxxxx„CStringcity=Philadelphia;//串常数作为初值„赋值语句„s1=s2=hithere;„变量比较if(s1==s2)„方法调用s1.MakeUpper();„内部字符比较if(s2[0]=='h')北京大学信息学院张铭编写©版权所有，转载或翻印必究Page21nextback3.3字符串运算的算法实现„1.串长函数intstrlen(char*s);„2.串复制char*strcpy(char*s1,char*s2);„3．串拼接char*strcat(char*s1,char*s2);„4．串比较intstrcmp(char*s1,char*s2);北京大学信息学院张铭编写©版权所有，转载或翻印必究Page22nextbackintstrcmp_1(char*d,char*s){for(inti=0;d[i]==s[i];++i){if(d[i]=='\0'&&s[i]=='\0')return0;//两个字符串相等}//不等,比较第一个不同的字符return(d[i]-s[i])/abs(d[i]-s[i]);}北京大学信息学院张铭编写©版权所有，转载或翻印必究Page23nextback3.3字符串运算的算法实现„3.3.1C++标准串运算的实现„3.3.2String串运算的实现北京大学信息学院张铭编写©版权所有，转载或翻印必究Page24nextback3.4字符串的模式匹配„模式匹配(patternmatching)„一个目标对象S（字符串）„一个模板（pattern）P（字符串）„任务：求出S中第一个与P全同匹配的子串（简称为“配串”），返回其首字符位置北京大学信息学院张铭编写©版权所有，转载或翻印必究Page25nextbackSs0s1…sisi+1si+2…si+m-2si+m-1…sn-1‖‖‖‖‖Pp0p1p2…pm-2pm-1为使模式为使模式PP与目标与目标SS匹配，必须满足匹配，必须满足p0p1p2…pm-1=sisi+1si+2…si+m-1sisi+1si+2…si+m-2si+m-1北京大学信息学院张铭编写©版权所有，转载或翻印必究Page26nextback3.4字符串的模式匹配„3.4.1朴素模式匹配„3.4.2字符串的特征向量N„3.4.3KMP模式匹配算法北京大学信息学院张铭编写©版权所有，转载或翻印必究Page27nextback朴素模式匹配S=P=ababababababbabababbabababbabababbabababbXXXXabababbXabababbXabababb北京大学信息学院张铭编写©版权所有，转载或翻印必究Page28nextback朴素模式匹配代码（简洁）intFindPat_2(StringS,StringP,intstartindex){//g为S的游标，用模板P和S第g位置子串比较，//若失败则继续循环for(intg=startindex;g=S.strlen()-P.strlen();g++){for(intj=0;((jP.strlen())&&(S[g+j]==P[j]));j++);if(j==P.strlen())returng;}return(-1);//for结束，或startindex值过大,则匹配失败}北京大学信息学院张铭编写©版权所有，转载或翻印必究Page29nextback朴素模式匹配算法代价例如，aaaaaaaaaabaaaaaab„目标S的长度为n，模板P长度为m，m≤n„在最坏的情况下，每一次循环都不成功，则一共要进行比较（n-m+1）次„每一次“相同匹配”需要P和S逐个字符比较的时间，最坏情况下，共m次„整个算法的最坏时间开销估计为O(