算法与数据结构（C++语言版）（第2版） 课件 第4章-串

DataStructureandAlgorithmdesign|analyze|experiment|implement数据结构与算法第四章串开始学习本章前要知道从数据结构角度看，串也属于线性结构，具有线性结构的共同特征；学习本章时，要注意到串所具有的线性结构的共性，更要掌握其个性；串的特殊性主要是：串的元素是字符；操作的对象往往不再是单个数据元素，而是一组数据元素4.1串的基本概念4.2串的表示和实现串的顺序存储表示和实现串的链式存储结构4.3串的模式匹配*4.4算法拓展*4.5STL应用*4.6你怎么看？目录CONTENTS知识点和难点重点知识点基本概念串操作模式匹配难点重点根据给定操作，编写其它操作的算法

(如，根据前5个基本操作，编写index,replace操作)

KMP算法模式串的next和nextval函数值手工模拟KMP算法的执行过程串的其它算法。概念和术语

子串：串中任意连续个字符组成的子序列被称为该串的子串，包含子串的串又被称为该子串的主串真子串：非空且不为自身的子串，称为真子串。子串定位：子串在主串中的位置串的相等：两个串的串值相等（即：两个串的长度相等，并且各个对应的字符也都相同）概念和术语下面关于串的的叙述中，哪一个是不正确的？串是字符的有限序列空串是由空格构成的串模式匹配是串的一种重要运算串既可以采用顺序存储，也可以采用链式存储ABCD提交单选题10分串是一种特殊的线性表，下面哪个叙述体现了这种特殊性？数据元素是一个字符可以顺序存储数据元素可以是多个字符可以链接存储ABCD提交单选题10分串的长度是指（）串中所含不同字母的个数串中所含字符的个数串中所含不同字符的个数串中所含非空格字符的个数ABCD提交单选题10分设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数为（）。【烟台大学】2n-1n2(n2/2)+(n/2)(n2/2)+(n/2)-1ABCD提交(n2/2)-(n/2)-1E其他情况F单选题10分设有两个串S1和S2，求S2在S1中首次出现的位置的运算称作（）【中南大学】求子串判断是否相等模型匹配连接ABCD提交单选题10分串运算举例串运算的例子：例，有下列四个串a，b，c，d：a=“DataStructure”b=“Data”c=“Structure”d=“Structure”它们的长度分别为14、4、9、9；且a、b、c、d都是a的子串；b在a中的位置（下标）是0，c在a中的位置是5；c和d两串相等。4.1串的基本概念4.2串的表示和实现串的顺序存储表示和实现串的链式存储结构4.3串的模式匹配*4.4算法拓展*4.5STL应用*4.6你怎么看？目录CONTENTS顺序存储结构的串的类型定义classString{public:String(constchar*str=NULL); //构造函数

String(constString&str); //拷贝构造函数

~String(){delete[]data;} //析构函数

intcapacity()const{returnmaxSize;} //最大存储容量

intsize()const{returncurLength;} //求字符串长度

boolempty()const{returncurLength==0;} //判空

intcompare(constString&s)const; //比较当前字符串和s的大小

StringsubStr(intpos,intnum)const; //从pos位置取长num的子串

intbfFind(constString&s,intpos=0)const; //朴素模式匹配(BF)String&insert(intpos,constString&s); //在pos位置插入串sString&erase(intpos,intnum); //删除从pos开始的num个字符

constchar*toCharStr()const{returndata;} //获取字符数组dataintkmpFind(constString&t,intpos=0); //改进的模式匹配(KMP)顺序存储结构的串的类型定义voidgetNext(constString&t,int*next); //获取next数组voidgetNextVal(constString&t,int*nextVal); //求nextVal数组booloperator==(constString&str)const; //重载==，判断两个串相等String&operator+(constString&str); //重载+，字符串的连接String&operator=(constString&str); //重载=，串间赋值char&operator[](intn)const; //重载[]，通过下标运算取存串中字符friendistream&operator>>(istream&cin,String&str);//重载>>friendostream&operator<<(ostream&cout,String&str);//重载<<private:char*data; //存储字符串

intmaxSize; //最大存储容量

intcurLength; //串的长度

voidresize(intlen); //扩大数组空间};*串的基本操作的实现[代码4.3]比较当前串与串s的大小：若两串相等，返回0；若当前串大，返回1；若当前串小，返回-1。intString::compare(constString&s)const{inti=0;while(s.data[i]!='\0'&&this->data[i]!='\0'){if(this->data[i]>s.data[i]) //this大于sreturn1;elseif(this->data[i]<s.data[i]) //this小于sreturn-1;i++;}if(this->data[i]=='\0'&&s.data[i]!='\0')//s有剩余return-1;if(s.data[i]=='\0'&&this->data[i]!='\0')return1; //this有剩余元素return0; //均无剩余元素，相等}*串的基本操作的实现[代码4.4]取子串：从主串中下标为pos的位置开始取长度为num的子串。当pos==curLength或num==0时，取到的子串为空串，当num>curLength–pos时，修改num=curLength-pos。StringString::subStr(intpos,intnum)const{ inti;Stringtmp(""); if(pos>curLength||pos<0) //pos的合法范围是[0..curLength]throwoutOfRange(); //抛出异常if(num<0)throwbadSize(); //num<0抛出异常if(num>curLength-pos) //num大于从pos开始到串尾元素个数num=curLength-pos; //修改num的值delete[]tmp.data; //释放tmp原来的存储空间tmp.maxSize=tmp.curLength=num; tmp.data=newchar[num+1]; //申请大小为num+1的存储空间for(i=0;i<num;i++) //长度为num的子串赋值给tmptmp.data[i]=data[pos+i];tmp.data[i]='\0'; returntmp;}4.1串的基本概念4.2串的表示和实现串的顺序存储表示和实现串的链式存储结构4.3串的模式匹配*4.4算法拓展*4.5STL应用*4.6你怎么看？目录CONTENTS串的链式存储结构最简单的链式存储结构是在一个结点的数据域中存放一个字符，这种存储结构优点是操作方便，不足之处是存储密度较低另一种链式存储结构称为块链式存储结构，即在一个结点的数据域中存放多个字符，这样做提高了存储密度，但是插入和删除操作可能会在结点间大量的移动字符，因此串一般采用顺序存储结构表示和实现。块链运算：插入Hesi

sdenuta##.t٨Heisastudent.Heisabrightstudent.Hesi

bgdeira.#tn٨httus

4.1串的基本概念4.2串的表示和实现4.3串的模式匹配

4.3.1BF朴素的模式匹配算法4.3.2KMP算法

*4.4算法拓展*4.5STL应用*4.6你怎么看？目录CONTENTS串的模式匹配子串的定位操作通常称做模式匹配（或模型匹配）主串又称为目标串，子串又称为模式串设有主串S和子串T，如果在主串S中找到一个与子串T相等的子串，则返回子串T第一次在主串S中出现的位置，即子串T的第一个字符在主串S中的位置。朴素的模式匹配算法朴素的模式匹配算法朴素的模式匹配算法

朴素的模式匹配算法[代码4.14]朴素模式匹配算法：当匹配成功时，返回子串在主串中第一次出现的位置；当匹配失败时，返回-1；当子串是空串时返回0。intString::bfFind(constString&s)const{inti=0,j=0; //主串和子串的指针if(curLength<s.curLength)return-1;//主串比子串短，匹配失败while(i<curLength&&j<s.curLength){ if(data[i]==s.data[j]) //对应字符相等指针后移i++,j++;else{ //对应字符不相等时i=i-j+1; //主串指针回溯j=0; } //子串从头开始}if(j>=s.curLength)return(i-s.curLength);elsereturn-1;}朴素的模式匹配算法朴素的模式匹配算法——分析

4.1串的基本概念4.2串的表示和实现4.3串的模式匹配

4.3.1BF朴素的模式匹配算法4.3.2KMP算法

*4.4算法拓展*4.5STL应用*4.6你怎么看？目录CONTENTSKMP—Knuth,Morris,Pratt三人发明特点主串无需回溯，主串指针一直往后移动，只有子串指针回溯在O(n＋m)的时间量级上完成串的模式匹配操作KMP算法

Si-1SiSi-kSi-jSi-j+k-1S0………i主串ST0Tk-1TkTj-kTj-1Tj……jk子串TKMP算法

KMP算法

KMP算法

KMP算法

KMP算法模式串T="Good“模式串T的next数组如下：模式串T=“abc123abcd“模式串T的next数组如下：KMP算法例4.3主串S="abc123abc123abcd"，

模式串T="abc123abcd"KMP算法KMP算法-101200120

-10001234-1

j012345678模式串aaabcaa1aj012345678模式串abcabcacb求模式串的next举例如何求next

如何求next[代码4.16]求next数组的算法实现voidString::getNext(constString&t,int*next){intj=0,k=-1;next[0]=-1;while(j<t.curLength-1){if((k==-1)||(t[j]==t[k])){++j,++k;next[j]=k;}elsek=next[k];}}算法时间复杂度为O(m)next的改进

例子i=3、j=3时失配。nextVal[3]=-1,i++，j=0。移动i到4，j到0i=7、j=3时失配。nextVal[3]=-1,i++，j=0。

移动i到8，j到0求nextval的算法[代码4.17]求nextVal数组的算法。voidString::getNextVal(constString&t,int*nextVal){intj=0,k=-1;nextVal[0]=-1;while(j<t.curLength-1){if((k==-1)||(t[j]==t[k])){++j,++k;if(t[j]!=t[k])nextVal[j]=k; elsenextVal[j]=nextVal[k]; }elsek=nextVal[k];}}-100012340-100-100-140

j012345678模式串abcabcacb求模式串的next、nextval值举例j01234567模式串babbabab-10011232-10-110-130已知字符串S为"abaabaabacacaabaabcc"，模式串t为"abaabc"，采用KMP算法进行匹配，第一次出现“失配”(s[i]!=t[i])时，i=j=5，则下次开始匹配时，i和j的值分别是（）。【2015年全国统考408】i=1，j=0 i=5，j=0i=5，j=2 i=6，j=2ABCD提交单选题10分设主串T=“abaabaabcabaabc”，模式串S=“abaabc”，采用KMP算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是（）。【2019年全国统考408】9101215ABCD提交单选题10分总结虽然朴素模式匹配算法的时间复杂度是O(n*m)，但在一般情况下，其实际的执行时间近似于O(n+m)，因此至今仍被采用。KMP算法是一种高效的模式匹配算法，它的核心思想是寻找模式串自身的特征，设计next数组，在此基础上达到目标串不回溯，模式串有规律回溯的目的，以减少回溯和比较的次数，但是这是建立在牺牲一定的存储空间的基础上的，KMP算法的时间复杂度为O(m+n)，空间复杂度为O(m)。4.1串的基本概念4.2串的表示和实现4.3串的模式匹配

*4.4算法拓展*4.5STL应用*4.6你怎么看？目录CONTENTS算法举例1S=“S1S2…Sn”是一个长为N的字符串，存放在一个数组中，编程序将S改造之后输出：（1）将S的所有第偶数个字符按照其原来的下标从大到小的次序放在S的后半部分；（2）将S的所有第奇数个字符按照其原来的下标从小到大的次序放在S的前半部分；例如：S=‘ABCDEFGHIJKL’则改造后的S为：

‘ACEGIKLJHFDB’【中科院计算所】算法举例1voidReArrangeString(){∥字符串改造,将第偶数个字符放在串的后半部分,第奇数个字符前半部分charch,s[],stk[]; ∥s和stk是字符数组（表示字符串）和字符栈

inti=1,j; ∥i和j字符串和字符栈指针

while((ch=getchar())!=’#’)∥读入字符串,’#’是字符串结束标志s[i++]=ch;s[i]=’\0’; ∥字符数组中字符串结束标志

i=1;j=1;

while(s[i]) ∥改造字符串

{if(i%2==0)stk[i/2]=s[i];elses[j++]=s[i];i++;}i--;i=i/2; ∥i先从’\0’后退，然后其含义是第偶数字符的个数

while(i>0)s[j++]=stk[i--]; ∥将第偶数个字符逆序填入原字符数组}4.1串的基本概念4.2串的表示和实现4.3串的模式匹配

*4.4算法拓展*4.5STL应用*4.6你怎么看？目录CONTENTS1.string对象的定义和初始化string的几个常用构造函数strings1;缺省构造函数，生成一个空字符串s1strings2(s1);拷贝构造函数，将s2初始化为s1的副本strings3("value");将s3初始化为一个字符串字面值的副本strings4(n,'c');将s4初始化为包含n个'c'字符的字符串2.string对象的输入输出#include<iostream>#include<string>usingnamespacestd;//usingstd::string;intmain(){strings1,s2;//定义s1、s2，并初始化s1、s2为空字符串//依次读取字符串一赋给s1，字符串二赋给s2cin>>s1>>s2; cout<<s1<<s2<<endl; //输出s1和s2return0;}

3.常用操作常用操作s.size()、s.length()返回s中字符的个数s.empty()如果s为空串，则返回true，否则返回falses.max_size()返回字符的可能最大个数s.capacity()返回重新分配之前的字符容量s.reserve()保留一定量内存以容纳一定数量的字符==、!=、<、<=、>、>=、pare()按字典序比较字符串=、s.assign()字符串赋值s.erase()清空字符串s1+s2把s1和s2连接成一个新字符串，返回新生成的字符串+=、s.append()在尾部添加字符s[n]、s.at(n)存取s中位置为n的字符，位置从0开始计数find()、rfind()、substr()、find_first_of、find_first_not_of、find_last_of和find_last_not_of子串查找常用操作s.insert()插入字符s.replace()字符串替换s.swap()交换两个字符串的内容>>、getline()从stream读取某值s.c_str()将内容以c_string返回s.data()将内容以字符数组形式返回s.begin()、s.end()提供类似STL的迭代器支持s.rbegin()、s.rend()逆向迭代器s.get_allocator()返回配置器…………

3.常用操作string的大小和容量函数一个C++字符串存在3种大小，相应的函数分别是：函数size()和length()等价，都返回string对象中字符个数。函数empty()判断字符串是否为空，判断字符串是否空也可以利用函数size()或者length()，将长度与0比较；函数max_size()，所获取的大小是当前字符串最多能容纳的字符数，和机器本身的限制或者字符串所在位置连续内存的大小有关系，例如，在某台PC上：cout<<s.max_size()<<endl;输出：4294967293；string的大小和容量函数的使用#include<iostream>#include<string>usingnamespacestd;intmain(){ strings("HelloWorld!"); //s初始化为"HelloWorld!" cout<<s.length()<<endl; cout<<s.size()<<endl; cout<<s.capacity()<<endl; cout<<s.max_size()<<endl; if(s.empty()) cout<<"s是空串"<<endl; else cout<<"s长度是"<<s.size()<<endl; return0;}string关系运算str1、str2比较，不失一般性，假设str1.length()<str2.length()，str2比str1长，如果str1与str2前面部分相同，则str1小于str2。如果str1和str2的字符不同，则比较第一个不匹配的字符。string类定义了常见的关系运算符（==、!=、<、<=、>、>=），关系运算符比较两个string对象时采用大小写敏感的字典序策略。例如：stringsubStr="Hello"; stringphrase="HelloWorld";stringstr="Hi";如果两两比较，则subStr小于phrase，str大于subStr，str大于phrase。

string关系运算string对象的比较string类还支持比较成员函数compare()，compare()支持用索引值和长度定位子串来进行比较，返回一个整数，如：strings("abcd");strings2("ab");pare("abcd"); //将s("abcd")和"abcd"比较，相等，返回0pare("dcba"); //将s("abcd")和"dcba"比较，返回一个小于0的值pare(s2);

//将s("abcd")和s2("ab")比较，返回大于0的值pare(s);

//相等，返回0//将s(“abcd”)中“ab”和s(“abcd”)中“cd”比较，返回值小于0S.compare(0,2,s,2,2);//将s(“abcd”)中的“bc”和“bcx”中的”bc”比较，返回0S.compare(1,2,”bcx”,2);string对象的赋值string对象的赋值有两种方式，一是使用操作符运算符=，如：stringstrTo,strFrom;strTo=strFrom;strings;stringstr("Hello");s.assign(str); s.assign("feeling");s.assign(str,0,3); //把"Hel"赋给s，索引从0开始//把str从索引2到结尾赋给s，即把"llo"赋给ss.assign(str,2,string::npos); s.assign(5,'t');二是使用成员函数assign()，assign()支持灵活的字符串赋值。string对象的赋值string对象相加相加指字符串连接，支持string对象和string对象、string对象与constchar*对象、string对象与char对象，可以通过使用加运算符（+）或复合赋值运算符（+=）连接，结果生成一个新的string对象，例如strings1("Hello");strings2("World\n");下面通过加法生成新的string对象：strings3=s1+s2; //s3是：HelloWorld\n s4=s1+"Kitty"; //s4是：HelloKittystring如果要把s2直接追加到s1末尾，可以使用+=运算符：s1+=s2; //相当于s1=s1+s2string加法返回的是string对象，和流输入输出（>>、<<）返回流对象类似，可以串接使用，如下：strings1,s2;cin>>s1>>s2;s1=s1+","+s2;cout<<s1<<","<<s2<<endl;string对象相加string对象的字符元素存取string类型支持通过下标运算符[]或者通过at()函数访问其中的字符元素，下标运算符[]需要一个size_type类型的值，作为“下标”或“索引”，以标明要访问字符的位置，string对象的下标从0开始，如果s是一个string对象且s不空，则s[0]就是字符串的第一个字符，s[1]就表示第二个字符，而s[s.size()-1]则表示s的最后一个字符。string对象的字符元素存取操作#include<iostream>#include<string>usingnamespacestd;intmain(){strings("somestring");for(string::size_typeix=0;ix!=s.size();++ix){ cout<<s[ix]<<endl;}

for(string::size_typeindex=0;index!=s.size();++index){ cout<<s.at(index)<<endl;}return0;}string对象的子串操作stringsubstr(size_typeindex,size_typenum=npos);substr(pos,len),返回一个从pos开始长度为len的字串 stringstr1="Howareyou"; cout<<str1.substr(0,3)<<endl; cout<<str1.substr(4,3)<<endl; cout<<str1.substr(8,3)<<endl; 结果显示Howareyoustring对象的查找子串操作str.find(str2)当str2是str1的字串时，返回str1中第一次出现的位置，如果没有则返回string::npos说明：string::npos是一个常数，其本身的值为-1，但由于是unsigned_int类型，因此实际上也可以认为是unsigned_int类型的最大值。string::npos用来作为find()函数失配时的返回值。

str1.find(str2,pos)从第pos位开始匹配返回值一样#include<iostream>#include<string>usingnamespacestd;intmain(){ stringstr="Thankyouforyoursmile."; stringstr2="you"; stringstr3="me"; if(str.find(str2)!=string::npos) cout<<str.find(str2)<<endl; if(str.find(str2,7)!=string::npos) cout<<str.find(str2,7)<<endl; if(str.find(str3)!=string::npos) cout<<str.find(str3)<<endl; else cout<<"Iknowthereisnopositionforme."<<endl;

return0;}string对象的查找子串操作insert(pos,string)在pos号位置插入字符串string#include<iostream>#include<string>usingnamespacestd;intmain(){ stringstr1="hhhhh",str2="www"; str1.insert(3,str2);

//往str[3]插入www。这里str2的位置直接写www也可以

cout<<str1<<endl; return0;}string对象的插入操作insert(it,it2,it3)，it为原字符串的欲插入位置，it2和it3为待插字符串的首尾迭代器，用来表示串[it2,it3)将被插在it的位置上#include<iostream>#include<string>usingnamespacestd;intmain(){stringstr1="hhhhh",str2="www";str1.insert(str1.begin()+3,str2.begin(),str2.end());

//往str[3]插入www。这里str2的位置直接写www也可以

cout<<str1<<endl;return0;}string对象的插入操作string对象的删除操作erase有两种用法：删除单个元素、删除一个区间内的所有元素。删除单个元素str.erase(it)用于删除单个元素，it为需要删除的元素的迭代器。#include<iostream>#include<string>usingnamespacestd;intmain(){ stringstr="ayvay"; str.erase(str.begin()+2); cout<<str<<endl; return0;}删除一个区间内的所有元素string.erase(first,last)，其中first为需要删除的区间的起始迭代器，而last则为需要删除的区间的末尾迭代器的下一个地址，也即为删除[first,last)。#include<iostream>#include<string>usingnamespacestd;intmain(){ stringstr="abcdefg"; str.erase(str.begin(),str.end()-1); cout<<str<<endl; return0;}string对象的删除操作str.erase(pos,length)，其中pos为需要删除的起始位置，length为删除的字符个数。#include<iostream>#include<string>usingnamespacestd;intmain(){ stringstr="abcdefg"; str.erase(3,2); cout<<str<<endl; return0;}string对象的删除操作string对象的清空clear()用以清空string中的数据#include<iostream>#include<string>usingnamespacestd;intmain(){ stringstr