数据结构-基于C语言的描述第2版课件 第4章 串

DATASTRUCTUREDATASTRUCTUREDataStructureBYPENGBO

串是一种特殊的线性表，其元素是字符。计算机需要利用软件实现串类型。不同的应用中有效实现串的处理，必须根据具体情况使用合适的存储结构。第4章主要内容串第章4《数据结构–基于C语言的描述》（第2版）-清华大学出版社DATASTRUCTUREDATASTRUCTUREDataStructureBYPENGBO第4章主要内容4.1

串的类型定义4.2

串的存储表示及操作实现4.3

串的模式匹配串第章4《数据结构–基于C语言的描述》（第2版）-清华大学出版社4.1串的类型定义

串的特点在于以“串的整体”作为操作对象，而在线性表中则大多以“单个元素”作为操作对象。因此其基本操作和线性表的基本操作有很大差别。4.1串的类型定义4.1.1串的定义

串是由零个或多个字符组成的有限序列。一般记为：S="s1s2…sn" （n≥1）其中，S是串名，用双引号括起来的字符序列是串值；si（1≤i≤n）可以是字母、数字或其他字符。

例如：两个串：X="1234"，String="String"。

X是一个串变量名，赋给它的值是字符序列1234，而不是整数1234。

左边的String是一个串变量名，右边的字符序列String是赋给它的值。

4.1串的类型定义4.1.1串的定义

例如：求四个串""(空串)，""(1个空格)，""(4个空格)和""(8个空格)的长度。

●相关概念

（1）空串和空格串

●

由零个字符组成的串称为空串，其长度为0。

●

仅由一个或多个空格组成的串称为空格串，其长度为串中空格个数。

空串""的长度是0

空格串""的长度是1

空格串""的长度是4空格串""的长度是8

（2）字串、主串和位置

●

串中任意连续的字符组成的子序列称为该串的子串。

●

包含子串的串称为主串。

●

字符在序列中的序号称为该字符在串中的位置，子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。

例如：有四个串：A="china"、B="chi"、C="na"、D="china"。B在A和D中的位置都是1，C在A中的位置是4，在D中的位置是5A的长度为5，B的长度为3，C的长度为2，D的长度为64.1串的类型定义4.1.1串的定义●串的比较

给定两个串：X="x1x2…xn"，Y="y1y2…ym"。（1）当n=m且x1=y1，…，xn=ym

时，称X=Y；（2）当下列条件之一成立时，称X<Y：

●

n<m，且xi=yi（i=1,2,…,n）；

●存在某个k≤min(m,n)，使得xi=yi（i=1,2,…,k-1），xk<yk。（3）否则，X>Y。

例如：

"ab"="ab"，"abc"<"abcd"，"abac"<"abaec"，"abc">"abafg"4.1串的类型定义4.1.2串的抽象数据类型ADTString{Data：

D={ai|ai

ElemSet,i=1,2,…,n,n≥0}（具有字符类型的数据元素集合）

Relation：

R={<ai-1,ai>|ai-1,ai

D,i=2,…,n}（相邻数据元素具有前驱和后继的关系）

Operation：

StrAssign(&S,chars)

初始条件：串常量chars已经存在。 操作结果：将chars赋值给串S。

…… StrCompare(S,T)

初始条件：串S和串T已经存在。 操作结果：若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0。 ……}ADTString

串的其他操作，比如StrIndex、StrInser、StrDelete、StrReplace等操作均可以由这些基本操作组合完成。

可以利用基本操作：串比较StrCompare、求串长StrLength和求子串SubString。

（1）分别求出串S和串T的长度；

（2）设置指示器，令初值为pos；

（3）在串S中从第pos个字符开始，查找和串T相等的第一个子串，并返回其在串S中的位置：否则返回-1。（设T为非空串）4.1串的类型定义4.1.2串的抽象数据类型例4-1

利用基本操作实现串定位StrIndex(S,T,pos)操作。设计4.1串的类型定义4.1.2串的抽象数据类型例4-1

利用基本操作实现串定位StrIndex(S,T,pos)操作。算法4-1intStrIndex(StringS,StringT,intpos){//若在串S中第pos个字符后查找到第一个与T相等子串，则返回其在S中位置；否则返回–1if(pos>=1){s_len=StrLength(S);t_len=StrLength(T);i=pos;while(i<=(s_len-t_len+1)){

SubString(Sub,S,i,t_len);if(StrCompare(Sub,T)!=0)++i;elsereturni; //返回串T在主串S中的位置}}return–1; //主串S中不存在与串T相等子串}//StrIndex4.2串的存储表示及操作实现

在大多数非数值处理程序中，串以变量形式出现；而不同应用中有效实现串的处理，需要根据串操作特点，根据具体情况合理选择和设计串值的存储结构及维护方式。4.2串的存储表示及操作实现4.2.1定长顺序存储表示

在程序执行前，按预先定义大小，为串分配一个固定长度存储区，把串中字符按其逻辑次序依次存放在这组地址连续的存储单元，称为定长顺序串。●定长顺序串的定义4.2串的存储表示及操作实现4.2.1定长顺序存储表示●定长顺序串的定义

表示串的长度的方法

在串值后面添加一个不计串长的结束标记符（比如'\0'）。

以下标为0的数组分量存放串实际长度，串值（字符序列）从下标为1的数组分量开始存放。该方法能直接得到串长度，方便进行串操作。通常采用方法2表示串。4.2串的存储表示及操作实现4.2.1定长顺序存储表示●定长顺序串的类型定义#defineSTRING_SIZE255 //可在255内定义最大串长typedefunsignedcharSString[STRING_SIZE+1];//0号单元存放串的实际长度

进行串操作时，若其长度超过预定义大小则超过部分将被舍去，称为“截断”。因此定长顺序串难以适应诸如插入、连接、替换等操作。

赋值操作4.2.1定长顺序存储表示●定长顺序串的操作实现4.2串的存储表示及操作实现（1）计算串常量chars长度chars_len。

（2）如果chars_len=0，则置空串。

（3）如果chars_len≠0，则生成一个非空串。

●

若char_len>String_Size，则发生“截断”

●

若char_len<=String_Size，则赋值全部设计SString_Size+1String_Size+1数组charsSa1a2aString_Size-1aString_Size0String_Sizea1a2aian-1ana1a2aiachars_len-1achars_lenchars_lenchars_len基于定长顺序串赋值操作完成

4.2串的存储表示及操作实现4.2.1定长顺序存储表示●定长顺序串的操作实现

赋值操作voidStrAssign_SS(SString&S,charchars[]){//将串常量chars赋值给定长顺序串S；若chars长度大于给定空间则给出“截断赋值”信息i=0;chars_len=0;while(chars[i]!='\0'){ //求chars长度++chars_len;++i;}算法4-2if(!chars_len)S[0]=0; //chars长度为0，生成空串S4.2串的存储表示及操作实现4.2.1定长顺序存储表示●定长顺序串的操作实现

赋值操作算法4-2else{ //chars长度非0，生成非空串Sj=0;k=1;if(chars_len>STRING_SIZE){ //复制chars部分字符，发生截断while(k<=STRING_SIZE)S[k++]=chars[j++];S[0]=STRING_SIZE;cout<<"串常量长度大于给定空间，赋值发生截断！");}else{ //复制chars所有字符到Swhile(k<=chars_len)S[k++]=chars[j++];S[0]=chars_len;}}}//StrAssign_SS分析

①问题规模：串常量chars的长度（设值为n）；②基本操作：求chars的长度、字符复制；③时间分析：算法的时间复杂度为O(n)。4.2串的存储表示及操作实现4.2.1定长顺序存储表示●定长顺序串的操作实现

赋值操作算法4-2

清空操作voidClearString_SS(SString&S){ //重置定长顺序串S为空串S[0]=0;}//ClearString_SS算法4-34.2串的的存储表示及操作实现4.2.1定长顺序存储表示●定长顺序串的操作实现时间复杂度O(1)。

求串长操作intStrLength_SS(SStringS){//返回定长顺序串S的长度returnS[0];}//StrLength_SS算法4-44.2串的的存储表示及操作实现4.2.1定长顺序存储表示●定长顺序串的操作实现时间复杂度O(1)。4.2串的的存储表示及操作实现4.2.1定长顺序存储表示●定长顺序串的操作实现

比较操作设计依次比较串S和串T对应位置上的字符：

（1）如果S>T，则返回一个大于0的值；

（2）如果S<T，则返回一个小于0的值；

（3）如果S=T，则返回一个等于0值。intStrCompare_SS(SStringS,SStringT){//比较定长顺序串S和T：//若S>T，则返回值>0；若S<T，则返回值<0；若S=T，则返回值=0for(i=1;(i<=S[0])&&(i<=T[0]);++i)if(S[i]!=T[i])return(S[i]–T[i]);return(S[0]-T[0]);}//StrCompare_SS算法4-54.2串的的存储表示及操作实现4.2.1定长顺序存储表示●定长顺序串的操作实现

比较操作

①问题规模：串S和T长（设分别为n和m）最小值，即Min{n,m}；②基本操作：字符比较；③时间分析：算法的时间复杂度为O(Min{n,m})。分析4.2串的的存储表示及操作实现4.2.1定长顺序存储表示●定长顺序串的操作实现

连接操作设计情况1：如果S1[0]+S2[0]≤String_Size，则得到的T是正确的结果；

0S10S20TString_Size+1T[0]=S1[0]+S2[0]设计情况2：如果S1[0]<String_Size，且S1[0]+S2[0]>String_Size，则将截断S2，得到的T包含S1和S2的一个子串；

0S10S20TString_Size+1T[0]=String_Size4.2串的的存储表示及操作实现4.2.1定长顺序存储表示●定长顺序串的操作实现

连接操作设计0S10S20TString_Size+1情况3：如果S1[0]=String_Size，则得到的T只包含S1；

T[0]=String_Size4.2串的的存储表示及操作实现4.2.1定长顺序存储表示●定长顺序串的操作实现

连接操作设计情况4：如果S1[0]>String_Size，则将截断S1，得到的T只包含S1的一个子串。

0S10S20TString_Size+1T[0]=String_Size4.2串的的存储表示及操作实现4.2.1定长顺序存储表示●定长顺序串的操作实现

连接操作voidStrConcat_SS(Sstring&T,SStringS1,SStringS2){//用T返回由定长顺序串S1和S2连接而成的新串//若没有发生截断，则给出“正确连接”信息；若发生截断，则给出“发生截断”信息if((S1[0]+S2[0])<=STRING_SIZE)){ //没有截断j=1;k=1;while(j<=S1[0])T[k++]=S1[j++]; //复制S1到T中j=1;while(j<=S2[0])T[k++]=S2[j++]; //复制S2到T中T[0]=S1[0]+S2[0];cout<<"正确连接，没有发生截断！"}算法4-64.2串的的存储表示及操作实现4.2.1定长顺序存储表示●定长顺序串的操作实现

连接操作elseif(S1[0]<STRING_SIZE){ //截断S2j=1;k=1;while(j<=S1[0])T[k++]=S1[j++]; //复制S1到T中j=1;while(k<=STRING_SIZE)T[k++]=S2[j++]; //复制S2到T但S2截断T[0]=STRING_SIZE;cout<<"非正确连接，截断串S2！"

}算法4-64.2串的的存储表示及操作实现4.2.1定长顺序存储表示●定长顺序串的操作实现

连接操作

elseif(S1[0]==STRING_SIZE){ //截掉S2，仅取S1j=1;k=1;while(j<=S1[0])T[k++]=S1[j++]; //复制S1到T中T[0]=STRING_SIZE;cout<<"非正确连接，截掉串S2，仅取串S1！"}else{ //截断S1j=1;k=1;while(j<STRING_SIZE)T[k++]=S1[j++]; //复制S1到T但S1截断T[0]=STRING_SIZE;cout<<"非正确连接，截断串S1！"}}//StrConcat_SS算法4-64.2串的的存储表示及操作实现4.2.1定长顺序存储表示●定长顺序串的操作实现

连接操作

①问题规模：串S1和串S2的长度（设值分别为n和m）之和；②基本操作：字符复制；③时间分析：若没发生截断，则字符复制次数为n+m；否则小于n+m。因此算法的时间复杂度为O(n+m)。分析4.2串的的存储表示及操作实现4.2.1定长顺序存储表示●定长顺序串的操作实现

连接操作4.2串的的存储表示及操作实现4.2.1定长顺序存储表示●定长顺序串的操作实现

求子串操作设计求子串的过程即为复制字符序列的过程：

（1）判断待求子串参数是否合理，若不合理则给出相应信息并退出运行；

（2）求出主串S中第pos个字符起长度为len的子串。voidSubString_SS(SString&Sub,SStringS,intpos,intlen){//用Sub返回定长顺序串S的第pos个字符起长度为len的子串//若参数不合理，则给出错误信息//其中：1≤pos≤S的长度，0≤len≤S的长度–pos+1if((pos<1)||(pos>S[0])||(len<0)||(len>(S[0]-pos+1)))Error("PositionError!");for(i=1;i<=len;i++)Sub[i]=S[pos+i-1]; //复制字符到Sub中Sub[0]=len;}//SubString_SS算法4-7

①问题规模：待求子串的长度（设值为len）；②基本操作：字符复制；③时间分析：算法的时间复杂度为O(len)。4.2串的的存储表示及操作实现4.2.1定长顺序存储表示●定长顺序串的操作实现

求子串操作分析4.2串的存储表示及操作实现4.2.2堆分配存储表示

在程序执行过程中，按串实际长，在内存的自由存储空间“堆”中为其动态分配存储区，串中字符按其逻辑次序依次存放在这组地址连续的存储单元里，称为堆分配顺序串。●堆分配顺序串的定义动态分配存储空间基址释放存储空间堆

串存储空间在程序执行过程中按串实际大小分配。进行操作时不会发生“截断”。因此堆分配顺序串适应诸如插入、连接、替换等操作。4.2串的存储表示及操作实现4.2.2堆分配存储表示●堆分配顺序串的类型定义typedefstruct{char *ch; //存储空间基地址

int length; //串的实际长度}HString;

赋值操作4.2串的存储表示及操作实现4.2.2堆分配存储表示●堆分配顺序串的操作实现（2）如果chars_len=0，则置空串，S.ch=NULL且S.length=0。

（3）如果chars_len≠

0，则生成一个其值等于串常量chars值的新串。

基于堆分配顺序串赋值操作完成（1）计算串常量chars长度chars_len。

设计a1a2aian-1ana1a2ai数组charschars_lenan-1anS.chchars_lenS.length=chars_lenvoidStrAssign_HS(HString&S,charchars[]){//将串常量chars赋值给堆分配顺序串Si=0;chars_len=0;while(chars[i]!='\0'){ //求chars长度++chars_len;++i;}算法4-8if(!chars_len){ //chars长度为0，置S为空串S.ch=NULL;S.length=0;}if(S.ch)deleteS.ch; //若S已经存在，则释放其所占空间4.2串的存储表示及操作实现4.2.2堆分配存储表示●堆分配顺序串的操作实现

赋值操作else{ //chars长度非0，生成非空串SS.ch=newchar[chars_len]; //为S动态分配空间if(!S.ch)Error("Overflow!");j=0;k=0;while(k<chars_len)S.ch[k++]=chars[j++];S.length=chars_len;}}//StrAssign_HS4.2串的存储表示及操作实现4.2.2堆分配存储表示●堆分配顺序串的操作实现

赋值操作算法4-84.2串的存储表示及操作实现4.2.2堆分配存储表示●堆分配顺序串的操作实现

赋值操作分析

①问题规模：串常量chars长度（设值为n）；②基本操作：求chars的长度、字符复制；③时间分析：算法的时间复杂度为O(n)，不会发生截断现象。4.2串的存储表示及操作实现4.2.2堆分配存储表示●堆分配顺序串的操作实现

销毁操作设计

（1）释放串中字符所占用的存储空间；

（2）设置串的长度为0。voidDestroyString_HS(HString&S){//释放堆分配顺序串S中字符所占用的存储空间delete[]S.ch;S.length=0;}//DestroyString_HS算法4-9时间复杂度O(1)。4.2串的存储表示及操作实现4.2.2堆分配存储表示●堆分配顺序串的操作实现

清空操作设计重新设置串S为空串，即令堆分配顺序串S基地址为空，长度域值为0。voidClearString_HS(HString&S){ //重置堆分配顺序串S为空串if(S.ch){delete[]S.ch; //若S已存在，则释放其所占空间S.ch=NULL; }S.length=0;}//ClearString_HS算法4-10时间复杂度O(1)。4.2串的存储表示及操作实现4.2.2堆分配存储表示●堆分配顺序串的操作实现

求串长操作设计直接返回堆分配顺序串中的长度域值。intStrLength_HS(HStringS){//返回堆分配顺序串S的长度returnS.length;}//StrLength_HS算法4-11时间复杂度O(1)。4.2串的存储表示及操作实现4.2.2堆分配存储表示●堆分配顺序串的操作实现

比较操作设计依次比较串S和串T对应位置上的字符：

（1）如果S>T，则返回一个大于0的值；

（2）如果S<T，则返回一个小于0的值；

（3）如果S=T，则返回一个等于0值。intStrCompare_HS(HStringS,HStringT){//比较堆分配顺序串S和T：//若S>T，则返回值>0；若S<T，则返回值<0；若S=T，则返回值=0for(i=0;(i<S.length)&&(i<T.length);++i)if(S.ch[i]!=T.ch[i])return(S.ch[i]–T.ch[i]);return(S.length–T.length);}//StrCompare_HS算法4-12分析

①问题规模：串S和T长（设分别为n和m）最小值，即Min{n,m}；②基本操作：字符比较；③时间分析：算法的时间复杂度为O(Min{n,m})。4.2串的存储表示及操作实现4.2.2堆分配存储表示●堆分配顺序串的操作实现

比较操作

（1）根据动态顺序串S1和S2的长度之和，为T动态分配存储空间；

（2）如果空间分配失败，则给出相应信息并退出运行；

（3）如果空间分配成功，则依次将S1和S2中的字符复制到T中。

基于堆分配顺序串连接操作完成4.2串的存储表示及操作实现4.2.2堆分配存储表示●堆分配顺序串的操作实现

连接操作设计s21s2ms11s1nS2.chS1.chs11s1ns21s2mT.length=S1.length+S2.lengthT.chS1.Length+S2.length4.2串的存储表示及操作实现4.2.2堆分配存储表示●堆分配顺序串的操作实现

连接操作voidStrConcat_HS(Hstring&T,HStringS1,HStringS2){//用T返回由堆分配顺序串S1和串S2连接而成的新串if(T.ch)deleteT.ch; //释放T的旧空间T.ch=newchar[S1.length+S2.length];if(!T.ch)Error("Overflow!");算法4-13

i=0;k=0;while(i<S1.length)T.ch[k++]=S1.ch[i++]; //复制S1到T中

i=0;while(i<S2.length)T.ch[k++]=S2.ch[i++]; //复制S2到T中

T.length=S1.length+S2.length;}//StrConcat_HS4.2串的存储表示及操作实现4.2.2堆分配存储表示●堆分配顺序串的操作实现

连接操作分析

①问题规模：串S1和串S2长度（设值分别为n和m）之和；②基本操作：字符复制；③时间分析：字符复制次数为n+m，因此算法时间复杂度为O(n+m)，不会发生截断现象。4.2串的存储表示及操作实现4.2.2堆分配存储表示●堆分配顺序串的操作实现

求子串操作设计求子串的过程即为复制字符序列的过程：

（1）判断待求子串参数是否合理，若不合理则给出相应信息并退出运行；

（2）如果待求子串长度为0，则置子串为空串；

（3）如果待求子串长度非0，则为子串动态分配存储空间，并求出主串S中第pos个字符起长度为len的子串。4.2串的存储表示及操作实现4.2.2堆分配存储表示●堆分配顺序串的操作实现

求子串操作voidSubString_HS(HString&Sub,HStringS,intpos,intlen){//用Sub返回堆分配顺序串S的第pos个字符起长度为len的子串//若参数不合理，则给出错误信息；其中：1≤pos≤S长度，0≤len≤S长度–pos+1if((pos<1)||(pos>S.length)||(len<0)||(len>(S.length-pos+1)))Error("PositionError!");if(Sub.ch)deleteSub.ch; //释放Sub的旧空间算法4-14

if(!len){ Sub.ch=NULL;Sub.length=0;}//若len为0则置空串else{ //若len非0则求子串Sub.ch=newchar[len];if(!Sub.ch)Error("Overflow!");for(i=0;i<len;i++)Sub.ch[i]=S.ch[pos+i-1]; //复制字符到Sub中Sub.length=len;}}//SubString_HS4.2串的存储表示及操作实现4.2.2堆分配存储表示●堆分配顺序串的操作实现

求子串操作分析①问题规模：待求子串长度（设值为len）；②基本操作：字符复制；③时间分析：算法的时间复杂度为O(len)。

为提高存储空间利用率，一个结点存储多个字符。串长不一定是结点大小整数倍，最后一个结点不一定全被串值占满，补上'\0'或其他非串值字符。4.2串的存储表示及操作实现4.2.3串的块链存储表示●块链存储结构的定义串链式存储非压缩方式串链式存储压缩方式

非压缩方式：一个结点只存储一个字符，其优点是操作方便，但存储利用率低。

压缩方式：一个结点可以存储多个字符，其优点是存储密度高，但操作较复杂。

结点的存储方式4.2串的存储表示及操作实现4.2.3串的块链存储表示●块链存储结构的定义为了便于串操作，当以链表存储串值时，除了头指针外还可以附设一个尾指针，用来指示链表中最后一个结点，并给出当前串的有效长度。采用这种存储结构的串称为块链存储结构。

设尾指针的目的是为了便于进行串连接操作，但应该注意连接时需要处理第一个串尾的无效字符。4.2串的存储表示及操作实现4.2.3串的块链存储表示●块链存储结构的类型定义#defineChunk_Size80 //结点大小typedefstructChunk{char data[Chunk_Size]; //字符数组

structChunk *next; //指向下一块的指针}Chunk;typedefstruck{Chunk *head,*tail; //串的头指针和尾指针

int length; //串的当前长度}LinkString4.2串的存储表示及操作实现4.2.3串的块链存储表示●块链存储结构的存储密度

在块链式存储结构中，结点大小的选择直接影响着串处理的效率。这就要求我们考虑串值的存储密度。

当结点存储的字符个数少时，存储密度低，运算处理更加方便；当结点存储的字符个数多时，存储密度高，但运算处理不方便。4.2串的存储表示及操作实现4.2.3串的块链存储表示●块链存储结构的主要特点

块链存储压缩结构采用顺序与链式相结合的方式，即块内顺序，块间链式。对于连接等操作有一定方便性，但对于改变串长的操作，要涉及结点的增加与删除问题，增加了实现操作的复杂性。块链存储结构表示串"abcdefg"在第三个字符'c'之后插入子串"xyz"xyzdefg示例：4.2串的存储表示及操作实现4.2.3串的块链存储表示●块链存储结构的主要特点应用：正文编辑系统中，把整个“正文”看成一个串，把每一行看成一个子串，构成一个结点，即同一行串用定长顺序结构(80个字符)，而行和行之间用指针相联接。4.2串的存储表示及操作实现例4-2

假定串S采用定长顺序存储：

（1）将串S中所有其值为ch1的字符换成ch2的字符；

（2）将串S中所有字符按照相反的次序仍然存放在S中；

（3）从串S中删除其值等于ch的所有字符；第1小题：从头到尾扫描串S，遇到值为ch1的字符直接将ch2替换之。设计算法4-15voidTranslation_SS(SString&S,charch1,charch2){//将定长顺序串S中所有其值为ch1的字符换成ch2的字符for(i=1;i<=S[0];i++)if(S.[i]==ch1)S[i]=ch2;}//Translation_SS①问题规模：串S的长度（设值分为n）；②基本操作：字符替换；③时间分析：算法的时间复杂度为O(n)。4.2串的存储表示及操作实现例4-2

假定串S采用定长顺序存储：

（1）将串S中所有其值为ch1的字符换成ch2的字符；

（2）将串S中所有字符按照相反的次序仍然存放在S中；

（3）从串S中删除其值等于ch的所有字符；第1小题：分析第2小题：

（1）将串S中第一个字符与最后一个字符交换；

（2）将串S中第二个字符与倒数第二个字符交换；……如此下去，直至完成将串S的所有字符反序。4.2串的存储表示及操作实现例4-2

假定串S采用定长顺序存储：

（1）将串S中所有其值为ch1的字符换成ch2的字符；

（2）将串S中所有字符按照相反的次序仍然存放在S中；

（3）从串S中删除其值等于ch的所有字符；算法4-16voidInvert_SS(SString&S){//将定长顺序串S中所有字符反序，之后仍然存放在S中for(i=1;i<(S[0]/2);i++){

temp=S[i];S[i]=S[S[0]–i+1];S[S[0]–i+1]=temp;

}}//Invert_SS设计①问题规模：串S的长度（设值分为n）；②基本操作：字符交换；③时间分析：字符交换次数为

n/2

，因此算法时间复杂度为O(n)。第2小题：4.2串的存储表示及操作实现例4-2

假定串S采用定长顺序存储：

（1）将串S中所有其值为ch1的字符换成ch2的字符；

（2）将串S中所有字符按照相反的次序仍然存放在S中；

（3）从串S中删除其值等于ch的所有字符；分析第3小题：从头到尾扫描串S，对于值等于ch的字符：

（1）向前移动其后面所有字符，进行覆盖删除；

（2）修改串的当前长度。4.2串的存储表示及操作实现例4-2

假定串S采用定长顺序存储：

（1）将串S中所有其值为ch1的字符换成ch2的字符；

（2）将串S中所有字符按照相反的次序仍然存放在S中；

（3）从串S中删除其值等于ch的所有字符；设计算法4-17voidDeleteChar_SS(SString&S,charch){//从定长顺序串S中删除其值等于ch的所有字符for(i=1;i<=(S[0]);i++)if(S[i]==ch){for(j=i;j<(S[0];j++)S[j]=S[j+1];S[0]=S[0]-1；}}//Deletechar_SS①问题规模：串S的长度（设值为n）；②基本操作：字符前移；③时间分析：执行时间主要花费在两个嵌套的for循环中的字符前移操作上，循环次数最多为n

(n-1)/2，因此算法时间复杂度为O(n2)。第3小题：4.2串的存储表示及操作实现例4-2

假定串S采用定长顺序存储：

（1）将串S中所有其值为ch1的字符换成ch2的字符；

（2）将串S中所有字符按照相反的次序仍然存放在S中；

（3）从串S中删除其值等于ch的所有字符；分析4.2串的存储表示及操作实现判断串替换参数pos和len是否合理：如果不合理，则给出相应信息并退出运行；否则：

（1）为置换后的新串S1重新分配存储空间；

（2）在新串S1中保留原串中第pos个字符之前的字符；

（3）在新串S1中第pos个位置上插入替换子串S2；

（4）在新串S1中复制原串中第pos+len个字符及以后的所有字符；

（5）修改新串S1的当前长度。设计例4-3

假定串S1和S2采用堆分配顺序存储，用串S2替换串S1中第pos个字符开始len个字符构成的子串。比如，StrReplace("abcd",1,3,"xyz")，操作之后返回“xyzd”。voidStrReplace_HS(HString&S1,HStringS2,intpos,intlen){//若参数i和len不合理则给出相应信息//1≤pos≤S1.length，0≤len≤S1.length–pos+1//用串S2替换堆分配顺序S1中第pos个字符开始len个字符构成的子串if((pos<1)||(pos>S.length)||(len<0)||(len>(S.length-pos+1)))Errot("ParametersError!");else{for(i=0;i<S1.length;i++) //将S1暂存到数组a中a[i]=S1.ch[i];delete[]S1.ch; //释放S1的原始空间算法4-184.2串的存储表示及操作实现例4-3

假定串S1和S2采用堆分配顺序存储，用串S2替换串S1中第pos个字符开始len个字符构成的子串。比如，StrReplace("abcd",1,3,"xyz")，操作之后返回“xyzd”。4.2串的存储表示及操作实现例4-3

假定串S1和S2采用堆分配顺序存储，用串S2替换串S1中第pos个字符开始len个字符构成的子串。比如，StrReplace("abcd",1,3,"xyz")，操作之后返回“xyzd”。算法4-18S1.ch=newchar[S1.length-len+S2.length];if(!S1.ch)Error("Overflow!");

for(i=0;i<pos-1;i++) //保留原串中pos之前的字符S1.ch[i]=a[i];

for(j=0;j<S2.length;j++) //将S2插入S1中S1.ch[i++]=S2.ch[j];

for(k=pos+len-1;k<S1.length;k++) //复制原串pos+len及以后字符S1.ch[i++]=a[k];

S1.length=S1.length-len+S2.length;}}//StrReplace_HS分析①问题规模：主串S1和子串S2的长度（设值分别为n和m）；②基本操作：字符复制；③时间分析：算法的时间复杂度为O(n+m)。4.2串的存储表示及操作实现例4-3

假定串S1和S2采用堆分配顺序存储，用串S2替换串S1中第pos个字符开始len个字符构成的子串。比如，StrReplace("abcd",1,3,"xyz")，操作之后返回“xyzd”。4.2串的存储表示及操作实现例4-4

假定串S采用堆分配顺序存储，求串S中出现的第一个最长重复子串的下标和长度。

（1）设置最长重复子串的下标为index，最长重复子串的长度为length；初始时，index和length均赋值为0；

（2）扫描串S="a1

a2……an-1

an"：对于当前字符ai，判定其后面是否有相同字符，若有则记为aj；再判定ai+1是否等于aj+1，……；如此反复，找到一个不同字符为止，即找到了一个重复出现的子串，把其下标和长度记录在index1和length1中；将length1与length相比较，把较长子串的下标和长度存放在index和length中；

（3）按照（2）的方法从aj+length1之后继续查找重复子串；

（4）对于

ai+1之后字符采用上述（2）和（3）的方法，最后在index与length中存放的即为最长重复子串的下标与长度。设计4.2串的存储表示及操作实现例4-4

假定串S采用堆分配顺序存储，求串S中出现的第一个最长重复子串的下标和长度。voidMaxSubString_HS(HStringS,int&index,int&length){//求堆分配顺序串S中出现的第一个最长重复子串的下标index和长度lengthindex=0;length=0;i=0;while(i<(S.length-1)){j=i+1;while(j<S.length){if(S.ch[i]==S.ch[j]){ //寻找重复出现的子串length1=1;for(k=1;S.ch[i+k]==S.ch[j+k];k++)length1++;算法4-19

if(length1>length){index=i; //将较大串下标赋给indexlength=length1; //将较大串长度赋给length}

j+=length1; //继续查找后面的重复子串}elsej++;}i++; //继续扫描S第i个位置后字符}}//MaxSubString_HS4.2串的存储表示及操作实现例4-4

假定串S采用堆分配顺序存储，求串S中出现的第一个最长重复子串的下标和长度。算法4-194.2串的存储表示及操作实现例4-4

假定串S采用堆分配顺序存储，求串S中出现的第一个最长重复子串的下标和长度。分析①问题规模：串S的长度（设值为n）；②基本操作：字符比较；③时间分析：执行时间主要花费在三个嵌套的循环中的字符比较上，因此算法的时间复杂度为O(n2)。4.3串的模式匹配

对于子串的定位操作，即从主串S="s1s2…sn"的第pos个字符开始寻找子串T="t1t2…tm"的过程，通常称为模式匹配，其中T称为模式。如果匹配成功则返回T在S中的位置，否则返回0。4.3串的模式匹配4.3.1简单的模式匹配方法–BF算法

基本思想：从主串S的第pos个字符开始和模式T的第一个字符进行比较：如果相等，则继续比较两者的后续字符；否则，从主串S的下一个字符开始和模式T的第一个字符进行比较，重复上述过程。如果模式T中的字符全部比较完毕，则说明本趟匹配成功；否则说明匹配失败。

这是一种带回溯的匹配算法，简称BF(Brute-Force)算法4.3串的模式匹配4.3.1简单的模式匹配方法–BF算法●BF算法设计假设主串S="ababcabcacbab"，模式T="abcac"设i=1c第1趟匹配S串：ababcabcacbab匹配：abi=3j=3第2趟匹配S串：ababcabcacbab匹配：ai=2j=1第3趟匹配S串：ababcabcacbab匹配：abcaci=7j=5

在主串S和模式T中设置比较的起始下标i和j

(初始时，i=pos，j=1)；循环直到S中所剩字符个数小于T长度或T所有字符均比较完。设计

（1）如果S[i]=T[j]，则继续比较S和T的下一个字符；否则将i和j回溯，准备下一趟比较。4.3串的模式匹配4.3.1简单的模式匹配方法–BF算法●BF算法设计假设主串S="ababcabcacbab"，模式T="abcac"设i=1设计

（1）如果S[i]=T[j]，则继续比较S和T的下一个字符；否则将i和j回溯，准备下一趟比较。第4趟匹配S串：ababcabcacbab匹配：aj=1i=4第5趟匹配S串：ababcabcacbab匹配：ai=5j=1第6趟匹配S串：ababcabcacbab匹配：abcaci=11j=6

（2）如果T中所有字符均比较完，则说明匹配成功，返回匹配的起始比较下标；否则，说明匹配失败，返回0。模式T在主串S中的位置是11-5=64.3串的模式匹配4.3.1简单的模式匹配方法–BF算法●BF算法设计算法4-20intStrIndex_BF(SStringS,SStringT,intpos){//返回模式T在主串S中第pos个字符之后的位置；若不存在返回0i=pos;j=1; //设置S和T比较的起始下标if(j>T[0])return(i-T[0]); //匹配成功，返回T在S中位置elsereturn0; //匹配失败，返回0}//StrIndex_BF

while((i<=S[0])&&(j<=T[0])){if(S[i]==T[j]){ //字符相等，继续比较下个字符i++;j++;}

else{ //字符不等，i和j分别回溯i=i-j+2;j=1; //主串回溯到i-(j-1)+1=i-j+2}}●

最好情况下每趟不成功匹配都发生在T的第一个字符(S长为n，T长为m)。4.3串的模式匹配4.3.1简单的模式匹配方法–BF算法●BF算法分析●

最坏情况下每趟不成功匹配都发生在T最后一个字符(S长为n，T长为m)。

例如：

S="aaaaaaaaaaab"T="aaab"

例如：

S="aaaaaaaaaabc"T="bc"

等概率情况下，pi=1/(n-m+1))；

等概率情况下，pi=1/(n-m+1))；时间复杂度为O(n

m)

平均比较次数是：

平均比较次数是：

因此，该算法在最好情况下时间复杂度为O(n+m)。

因此，该算法在最坏情况下时间复杂度为O(n

m)。4.3串的模式匹配4.3.1简单的模式匹配方法–BF算法●BF算法分析BF算法特点：简单；缺点：效率较低，其原因是“回溯”，即在某趟匹配失败后对主串S要回溯到本趟匹配开始字符的下一个字符，模式T要回溯到第一个字符。模式匹配具有两个特征：●

算法一次执行时间不容忽视：问题规模很大，需要在大量信息中进行匹配；●

算法改进所取得的积累效益不容忽视：串匹配操作常被调用，执行频率高。4.3串的模式匹配4.3.2改进的模式匹配方法–KMP算法

基本思想：每当一趟匹配过程中出现字符比较不等时，不需要回溯主串的指针，即主串中的每个字符只参加一次比较，而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较。

对BF算法进行改进的模式匹配算法-KMP(D.E.Knuth-J.H.Morris-V.R.Pratt)算法，可以在O(n+m)的时间数量级上完成串的模式匹配操作。s2=t2；

t1≠t2；∴t1≠s2第5趟匹配，i=5，j=1失败BF：i前进到6，j保持1第6趟匹配，i=11，j=6成功T中所有字符都比较完毕第2趟匹配，i=2，j=1失败BF：i前进到3，j保持1第3趟匹配，i=7，j=5失败BF：i回溯到4，j回溯到14.3串的模式匹配4.3.2改进的模式匹配方法–KMP算法设主串s="ababcabcacbab"，模式t="abcac"第1趟匹配，i=3，j=3失败BF：i回溯到2，j回溯到1第4趟匹配，i=4，j=1失败BF：i前进到5，j保持1s4=t2；

t1≠t2；∴t1≠s4s5=t3；

t1≠t3；∴t1≠s5在这趟中s6=t4，且t1=t4；∴s6=t1因此，比较从s7和t2开始结论：（1）i可以不回溯；（2）模式向右滑动到的新的比较起点k！模式Ttjj本趟开始位置主串S

si

……i…BF算法的设计思想KMP算法的改进4.3串的模式匹配4.3.2改进的模式匹配方法–KMP算法●改进的模式匹配思想下一次开始位置j回溯回溯滑行kitk尽量利用已部分匹配的信息，让i不回溯，并加快模式的滑动速度。关键的问题是如何确定位置k。

4.3串的模式匹配4.3.2改进的模式匹配方法–KMP算法●需要解决的问题

假设应该与模式中的第k（k<j）个字符继续比较，则模式中第k个字符之前的k-1个字符必定与主串中第i个字符之前的k-1个字符相等。比较s1s2…si-j+1si-j…si-k+1si-k+2…si-1sit1t2…tk-1tk与模式中第k个字符继续比较t1t2…tj-k+1tj-k+2…tj-1tj

最后可以推得："t1t2…tk-1"="tj-k+1tj-k+2…tj-1"不等得到的模式和主串“部分匹配”的结果t1t2…tk-1tj-k+1tj-k+2…tj-1

模式中每一个字符tj

都对应一个k值，而这个k值仅依赖于模式本身字符序列的构成，与主串无关。4.3串的模式匹配4.3.2改进的模式匹配方法–KMP算法

模式的next[j]函数用来表示tj

对应的k值（1≤j≤m）。其定义如下：●next数组的定义next[j]=0 j=1max{k|1<k<j且t1t2…tk-1=tj-k+1tj-k+2…tj-1}1 其他next[j]表明当模式中第j个字符与主串中相应字符“失配”时，在模式中需要重新和主串中该字符进行比较的字符位置。

模式中相似部分越多，则next[j]函数越大，模式串向右滑动得越远，与主串进行比较的次数越少，时间复杂度就越低。4.3串的模式匹配4.3.2改进的模式匹配方法–KMP算法●next数组的定义

假设已求出next[1]，next[2]，…，next[j]，则用递推法求next[j+1]。令next[j]=k，那么next[j+1]可能有下面两种情况：

由next[j]函数的定义可知：当j=1时，next[1]=0；当j>1时，next[j]=k，表明在模式T中存在关系:其中k是满足1<k<j的某个值，且不可能存在k'>k。

"t1t2…tk-1"="tj-k+1tj-k+2…tj-1"

（2）如果tk

tj，则表明在模式T中：

"t1t2…tk"

≠

"tj-k+1tj-k+2…tj"4.3串的模式匹配4.3.2改进的模式匹配方法–KMP算法●next数组的定义

（1）如果tk=tj，则表明在模式T中：

且不可能存在k'>k，说明next[j+1]=k+1，即：next[j+1]=next[j]+1

"t1t2…tk"="tj-k+1tj-k+2…tj"

当tk

tj

时，应该将模式向右滑动至模式中的第next[k]个字符，和模式中的第j个字符tj

相比较。t1…tk'-1tk'…t