数据结构与算法-北京大学2008-张铭-字符串-4

数据结构与算法第4章字符串本章由赵海燕主写://张铭，王腾蛟，赵海燕高等教育出版社，2008.6。“十一五”国家级规划教材“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6主要内容字符串基本概念字符串的存储结构字符串运算的算法实现字符串的模式匹配“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.64.1字符串基本概念字符编码字符编码顺序字符串抽象数据类型“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6基本概念字符串，由0个或多个字符/符号的顺序排列所组成的复合数据结构，简称“串”（string）串的长度：一个字符串所包含的字符个数空串：长度为零的串，它不包含任何字符内容特殊的线性表，即元素为字符的线性表n(≥0)个字符的有限序列，一般记作S:“c0c1c2…cn-1”•其中，S是串名字•“c0c1c2…cn-1”是串值•ci是串中的字符•n是串的长度（即字符个数），长度为0则为空串“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6字符/符号字符(char)：组成字符串的基本单位取值依赖于字符集Σ（同线性表，结点的有限集合）二进制字符集：Σ={0,1}生物信息中DNA字符集：Σ={A,C,G,T}英语语言：Σ={26个字符，标点符号}……“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6字符编码单字节（8bits）采用ASCII码对128个符号（字符集charset）进行编码在C和C++中均采用其他编码方式GBCJKUNICODE“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6字符的编码顺序为了字符串间比较和运算的便利，字符编码表一般遵循约定俗成的“偏序编码规则”字符偏序：根据字符的自然含义，某些字符间两两可以比较次序其实大多数情况下就是字典序中文字符串有些特例，例如“笔划”序“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6字符串长度理论上一个字符串的长度是任意且有限的，但在实际的语言中总有一定的长度：定长：具有一个固定的最大长度，所用内存量始终如一变长：根据实际需要伸缩。尽管命名为变长，但实际长度也有限（取决于可用的内存量）“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6字符串的数据类型因语言而不同简单类型复合类型字符串常数和变量字符串常数（stringliteral）•例如：“\n”,“a”，“student”…字符串变量“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6C++的标准string标准字符串：将C/C++的string.h函数库作为字符串数据类型的方案例如：charS[M];定义了字符串变量e.g.,chars1[7]=“value”;串的结束标记：'\0'‘\0’是ASCII码中8位BIT全0码，又称为NULL符，专门用来作结束标志字符串的实际长度为M-1注意：s1=s2“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6C++标准string串长函数intstrlen(char*s);串复制char*strcpy(char*s1,char*s2);串拼接char*strcat(char*s1,char*s2);串比较(注意)intstrcmp(char*s1,char*s2);“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6C++标准string输入和输出函数cincout定位函数char*strchr(char*s,charc);右定位函数char*strrchr(char*s,charc);“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6C++标准stringe.g,字符串s:寻找字符o,strchr(s,’o’)结果返回4；反方向寻找r,strrchr(s,’o’)结果返回7Helolwrol\0d01243568791110Sstrchr(s,’o’)strrchr(s,’o’)“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6String抽象数据类型字符串类（classString）：适应字符串长度动态变化的复杂性不再以字符数组charS[M]的形式出现，而采用一种动态变长的存储结构“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6String抽象数据类型//basic_string模板及其功能都定义在名字空间std中，由string给出。namespacestd{templateclasscharT,classtraits=char_traitscharT,classAllocator=allocatorcharTclassbasic_string{public:……}}typedefbasic_stringcharString；“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6C++String部分操作列表操作类别方法描述子串substr()返回一个串的子串拷贝/交换swap()交换两个串的内容copy()将一个串拷贝到另一个串中赋值assign()把一个串、一个字符、一个子串赋值给另一个串中=把一个串或一个字符赋值给另一个串中插入/追加insert()在给定位置插入一个字符、多个字符或串+=将一个字符或串追加到另一个串后append()将一个或多个字符、或串追加在另一个串后拼接+通过将一个串放置在另一个串后面来构建新串查询find()找到并返回一个子序列的开始位置替换/清除replace()替换一个指定字符或一个串的字串clear()清除串中的所有字符统计size()返回串中字符的数目length()返回size()max_size()返回串允许的最大长度“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6处理子串(Substring)的函数假设s1，s2是两个串：s1=a0a1a2…an-1s2=b0b1b2…bm-1其中0≤m≤n,若存在整数i(0≤i≤n-m)，使得bj=ai+j,j=0,1,…,m-1同时成立，则称串s2是串s1的子串，或称s1包含串s2真子串：非空且不为自身的子串。空串是任意串的子串任意串S都是S本身的子串简称“子串函数”提取子串插入子串寻找子串删除子串…“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6字符串中的字符重载下标算子[]char&operator[](intn);按字符定位下标intFind(charc,intstart);反向寻找，定位尾部出现的字符intFindLast(charc);“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.64.2字符串的存储结构和实现字符串的顺序存储字符串类classString的存储结构C++标准串的运算实现String类的运算实现“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6字符串的顺序存储对于串长变化不大的字符串，可以有三种处理方案：（1）用S[0]作为记录串长的存储单元(Pascal)缺点：限制了串的最大长度不能超过256（2）为存储串的长度，另辟一个存储的地方缺点：串的最大长度一般是静态给定的，不是动态申请数组空间（3）用一个特殊的末尾标记'\0‘(C/C++)例如：C++语言的string函数库（＃includestring.h）采用这一存储结构“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6classString的存储结构微软VC++的CString类介绍自动的动态存储管理，串的最大长度不超过2GB容器型不必使用new和delete使用特点：变量申明•CStrings6('x',6);//s6=xxxxxx•CStringcity=Philadelphia;//串常数作为初值赋值语句•s1=s2=hithere;变量比较if(s1==s2)方法调用s1.MakeUpper();内部字符比较if(s2[0]=='h')“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6字符串类classString的存储结构Helol\0012435Helol\0012435……5size:str:s1……5size:str:s1private://具体实现的字符串存储结构char*str;//字符串的数据表示intsize;//串的当前长度例如，Strings1=Hello;“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6字符串运算的算法实现1.串长函数intstrlen(char*s);2.串复制char*strcpy(char*s1,char*s2);3．串拼接char*strcat(char*s1,char*s2);4．串比较intstrcmp(char*s1,char*s2);“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6C++标准串运算的实现//字符串的复制char*strcpy(char*d,char*s){inti=0;while(s[i]!='\0'){d[i]=s[i];i++;}d[i]='\0';returnd;}//问题？“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6C++标准串运算的实现//字符串的比较intstrcmp(constchar*s1,constchar*s2){inti=0;while(s2[i]!='\0'||s1[i]!='\0'){if(s1[i]s2[i])return1;elseif(s1[i]s2[i])return-1;i++;}if(s1[i]=='\0'&&s2[i]!='\0')return-1;elseifs2[i]=='\0'&&s1[i]!='\0')return1;return0;}“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6C++标准串运算的实现//求字符串的长度intstrlen(chard[]){inti=0;while(d[i]!=0)i++;returni;}“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6C++标准串运算的实现//寻找字符char*strchr(char*d,charch){//按照数组指针d依次寻找字符ch，如果找到ch，则将指针位置返回，//如果没有找到ch，则为0值i=0;//循环跳过那些不是ch的字符while(d[i]!=0&&d[i]!=ch)i++;//当本串不含字符ch，则在串尾结束；//当成功寻找到ch，返回该位置指针if(d[i]==0)return0;elsereturn&d[i];}“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6C++标准串运算的实现//反向寻找字符char*strrchr(char*d,