CH05-字符串.ppt

《CH05-字符串.ppt》由会员分享，可在线阅读，更多相关《CH05-字符串.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第5 5章章 字符串字符串1pC C语言字符和字符串语言字符和字符串p字符串的字符串的ADTADT描述描述p字符串的实现字符串的实现p标准标准StringString类类p模式匹配模式匹配主要内容主要内容21、C语言字符和字符串语言字符和字符串n数组定义数组定义l char buf20=“good morning”；lC语言中字符串的使用：语言中字符串的使用：for(int i=0;bufi!=0;i+)printf(“%c”,bufi);或者或者 printf(“%s”,buf);lC+中字符串的使用：中字符串的使用：coutbuf;get()、getline()等等3n计算字符串长度须自

2、己写程序或利用字符串函数计算字符串长度须自己写程序或利用字符串函数nWhile(While(stristri!=0)i+;!=0)i+;n存在的问题存在的问题:n安全检查问题安全检查问题?数组和指针数组和指针.n字符串的操作不方便字符串的操作不方便n串复制串复制?n需要定义一种字符串数据结构需要定义一种字符串数据结构1 1、C C语言字符和字符串语言字符和字符串42 2、字符串的、字符串的ADTADT描述描述数据元素集合：数据元素集合：从一些给定的字符集中抽取的有限的字符序列。从一些给定的字符集中抽取的有限的字符序列。基本操作：基本操作：输入和输出输入和输出 读取和显示字符串读取和显示字符串

3、长度长度 字符串中字符数目字符串中字符数目 比较比较 按字典序比较大小按字典序比较大小 连接连接 两个字符串连接两个字符串连接 复制复制 给定字符串或子串复制到另一个字符串给定字符串或子串复制到另一个字符串 查找查找 给定字符串中找另一个字符串或字符给定字符串中找另一个字符串或字符 插入插入 将一个字符串插入给定字符串中将一个字符串插入给定字符串中 删除删除 删除一个字符串的一部分删除一个字符串的一部分 替换替换 使用另一字符串替换字符串的某部分使用另一字符串替换字符串的某部分5 假设有三个字符串假设有三个字符串str1,str2,str3str1,str2,str3，初值分别为，初值分别为”

4、enen”,”listlist”,”lightlight”，则有以下操作：，则有以下操作：l 三个字符串的长度计算：三个字符串的长度计算：2 2，4 4，5 5l 三个字符串间的字典序比较：三个字符串间的字典序比较：str1str3str2str1str3=0);buflen=1+size;buffer=new charbuflen;/创建串创建串指针指针 assert(buffer!=0);/对缓冲区做初始化对缓冲区做初始化 for(unsigned i=0;ibuflen;i+)bufferi=0;字符串部分函数的实现字符串部分函数的实现10string:string(const stri

5、ng&initstr)/初始化数据域初始化数据域,从已有字符串从已有字符串initstr复制复制 buflen=1+initstr.length();/创建串数组创建串数组 buffer=new charbuflen;assert(buffer!=0);for(unsigned i=0;i=buflen)delete buffer;buflen=1+rightLength;buffer=new charbuflen;assert(buffer!=0);for(unsigned i=0;i=strlen(buffer)/如果超出范围如果超出范围,返回对全局返回对全局nothing的引用的引用 n

6、othing=0;return nothing;return bufferindex;下下标标运运算算15下标引用举例：将所有的小写字母变为大写下标引用举例：将所有的小写字母变为大写void toUpper(string&word)for(unsigned int i=0;wordi!=0;i+)if(isLower(wordi)wordi=(wordi a)+A;164 4、标准、标准StringString类类#include 基本构造函数基本构造函数:P196string s;string s(str/ca);string s(ca,n);string s(str,pos,n);stri

7、ng s(n,ch);string name1,name2(“”);char vowles=“abcdefgh”;string s(vowles,3);string s1(s),s2(s,2),s3(s,2,5);string s4(10,z);字符串对象创建字符串对象创建174 4、标准、标准StringString类类#include 存储函数存储函数:P197s.capacity();s.size()/s.length();s.empty();s.max_size();输入输入/输出函数输出函数:P198ostrs;/从从istr中提取字符到中提取字符到sgetline(istr,s,t

8、erm);/从从istr中提取字符到中提取字符到s？184 4、标准、标准StringString类类#include 编辑操作编辑操作:P200s+str/ca/chs.append(str/ca);s.append(ca,n);s.append(n,ch);s.insert(pos,str);s.insert(pos1,str,pos2,n);s.insert(pos,ca,n);s.insert(pos,n,ch);s.erase(pos,n);s.replace(pos1,n1,str);s.replace(pos1,n1,ca,n2);s.swap(str);swap(s,str);

9、194 4、标准、标准StringString类类#include 复制符复制符:P201s=str/ca/chs+=str/ca/chs.assign(str/ca);s.assign(ca,n);s.assign(n,ch);s.substr(pos,n);si/返回字符串返回字符串s s中位中位置置i i上的字符的上的字符的引用引用s.at(i);/同上同上，但若，但若i i越界越界会产生会产生异常异常访问单独字符访问单独字符:P201204 4、标准、标准StringString类类#include 查找操作查找操作:P202s.find(str/ca/ch,pos);s.find_f

10、irst_of(str/ca/ch,pos);s.find_first_not_of(str/ca/ch,pos);s.find_last_of(str/ca/ch,pos);s.find_last_not_of(str/ca/ch,pos);s.rfind(str/ca/ch,pos);str/ca1str/ca2str/ca1str/ca2str/ca1=str/ca2str/ca1=str/ca2str/ca1!=str/pare(str/ca);s.c_str();s.data();s.copy(charArray,pos,n);比较和转换比较和转换:P20421n nn定义定义定义定

11、义 在串中寻找子串（一个在串中寻找子串（一个在串中寻找子串（一个在串中寻找子串（一个,也可以多个）也可以多个）也可以多个）也可以多个）在串中的位置在串中的位置在串中的位置在串中的位置 n nn词汇词汇词汇词汇 在模式匹配中，子串称为在模式匹配中，子串称为在模式匹配中，子串称为在模式匹配中，子串称为模式模式模式模式，串称为，串称为，串称为，串称为目目目目标标标标。n nn示例示例示例示例 目标目标目标目标 T:T:T:T:“BeiBeiBeiBeijinjinjinjing g g g”模式模式模式模式 P:P:P:P:“jinjinjinjin”匹配结果匹配结果匹配结果匹配结果 =3=3=3=

12、3 5 5、模式匹配、模式匹配22第第1趟趟 T a b b a b a P a b a 第第2趟趟 T a b b a b a P a b a 第第3趟趟 T a b b a b a P a b a第第4趟趟 T a b b a b a P a b a 穷举的模式匹配过程穷举的模式匹配过程23 穷举的模式匹配算法时间代价：穷举的模式匹配算法时间代价：最坏情况比较最坏情况比较n-m+1趟，每趟，每趟比较趟比较m次，总次，总比较次数达比较次数达(n-m+1)*m。原因：原因：每趟重新比较时，模式串的检测指针每趟重新比较时，模式串的检测指针要回退。要回退。改进的模式匹配算法可使改进的模式匹配算法可

13、使模式串模式串的的检测指针检测指针每趟不回退。每趟不回退。24KMPKMP模式匹配算法模式匹配算法l l设主串设主串设主串设主串T=“tT=“tT=“tT=“t1 1 1 1t t t t2 2 2 2t t t tn n n n”,”,”,”,模式模式模式模式P=“pP=“pP=“pP=“p1 1 1 1p p p p2 2 2 2ppppm m m m”l lKMPKMPKMPKMP的基本思想：的基本思想：的基本思想：的基本思想：在匹配过程中，主串不进行回溯，即主串中的每在匹配过程中，主串不进行回溯，即主串中的每在匹配过程中，主串不进行回溯，即主串中的每在匹配过程中，主串不进行回溯，即主串

14、中的每个字符只参加一次比较，某趟匹配在个字符只参加一次比较，某趟匹配在个字符只参加一次比较，某趟匹配在个字符只参加一次比较，某趟匹配在t t t ti i i i和和和和p p p pj j j j匹配匹配匹配匹配失败后，指针失败后，指针失败后，指针失败后，指针i i i i不回溯，不回溯，不回溯，不回溯，模式向右滑动至某个位置模式向右滑动至某个位置模式向右滑动至某个位置模式向右滑动至某个位置k k k k，使得，使得，使得，使得p p p pk k k k对准对准对准对准t t t ti i i i继续进行匹配。继续进行匹配。继续进行匹配。继续进行匹配。25KK 依赖于模式自身前缀数组的计算

15、依赖于模式自身前缀数组的计算KMPKMP模式匹配算法模式匹配算法位置位置0 1 2 3 4 5 6 7 8 9 10正文字符串正文字符串 c a g a c a g a c a g a t a模式模式a g a c a g a t a匹配失败匹配失败(a g a )c a g a t a模式移动模式移动模式向右滑动至某个位置模式向右滑动至某个位置模式向右滑动至某个位置模式向右滑动至某个位置 k?0 0 1 0 1 2 3 0 1260prefix前缀数组：前缀数组：prefixprefix；模式数组：模式数组：patternpattern；模式数组下标：模式数组下标：i i；匹配位置计算：匹配

16、位置计算：k k；0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 a g c t a g c a g c t a g c t g ipattern0 0 0 1k2 3 1 2 3 4567 4 0k k kkK=prefixk-1 K=prefixi-1K+1Patlen=pattern.length();Prefix=new intpatlen;prefix0=0;/前缀数组第前缀数组第1位位/元素没有匹配元素没有匹配,初值为初值为0；27第第第第1 1趟趟趟趟 目标目标目标目标 a c c a b a a b a a b c a c a a b c 模式模式模

17、式模式 a b b a a b c a c k k=1=1 k k=prefixk-1=0=0第第第第2 2趟趟趟趟 目标目标目标目标 a c c a b a a b a a b c a c a a b c 模式模式模式模式 a a b a a b c a c k k=0 =0 目标指针加目标指针加目标指针加目标指针加 1 1 第第第第3 3趟趟趟趟 目标目标目标目标 a c a b a a b a a a b c a c a a b c 模式模式模式模式 a b a a b c c a c k k=5=5 k k=prefix4=2=2 第第第第4 4趟趟趟趟 目标目标目标目标 a c a b a a b a a a b c a c a a b c 模式模式模式模式 (a b)a a a b c a c 运用运用KMPKMP算法的匹配过程算法的匹配过程 0prefix0 1 1 2 0 1 029 改进的模式匹配改进的模式匹配(KMP)算法的时间代价：算法的时间代价：O(n+m)30