4.3　串操作

由于字符串本质上是线性表,只不过其中的数据元素为字符类型,因此,线性表的所有运算对字符串也适用。

4.3.1　串的基本操作

在4.1.2小节中定义了串的13种操作,其中串赋值StrAssign、串比较StrCompare、求串长StrLength、串连接Concat与求子串SubString这5种操作构成串类型的最小操作子集,这些操作不可能利用其他操作实现。除串清除操作ClearString和串销毁操作DestroyString外,其他操作均可在这个最小操作子集上实现,即如果在最高程序设计语言中设有“串类型”的话,提供的操作不能没有这五项操作,它们不能通过其他的操作实现。

由于堆分配存储结构的串,既有顺序存储结构的特点,又能根据实际需要动态分配串操作所需要的存储空间,因此下面各字符串操作的实现均采用堆分配存储表示。

1.串赋值

字符串的赋值操作是指将一个字符串常量chars赋给字符串变量S,S原来的值被覆盖。例如:StrAssign（S,“Hello World！”）

执行之后,S＝“Hello World！”。

具体算法如下。

2.求串长

求串长即求串中字符的个数。例如:S＝“This is a Student”,字符串长度为StrLength（S）＝17。

具体算法如下。

3.求子串

求子串操作是指从当前串（串S）中的某个位置（pos）开始取出一定长度（len）的子串（sub）。如果len＝0,则得到空串。在求子串操作中,对于子串的起始位置和子串长度有一定要求,即1≤pos≤StrLength（S）,0≤len≤StrLength（S）－pos＋1）。

例如:S＝“This is a Student”,SubString（S,9,7）＝“Student”。

具体算法如下。

4.串比较

字符串比较是指有两个字符串S和T,若二者对应位置上的字符完全相同,则两串相等,返回0；若S＞T,则返回值＞0；若S＜T,则返回值＜0。例如:

具体算法如下。

5.串连接

串连接操作是指将一个字符串（S1）连接到另一个字符串（S2）的后面,形成一个新的字符串（T）。例如:S＝“Good Student”,Concat（S,S,"！"）,S＝“Good Student！”。

具体算法如下。

4.3.2　串的其他操作

在串的实际应用中,经常需要使用到串的插入、删除、查询和替换操作,这几种操作都可以利用上面的基本操作来实现。具体实现方法如下。

1.串插入

插入操作是指将一个指定的串（T）插入到当前串（S）的指定位置（pos）。插入操作中,串的插入位置1≤pos≤StrLength（S）＋1。例如:S＝“A Student”,T＝“Good”,StrInsert（S,2,T）,S＝“A Good Student”。

该操作可以通过SubString、StrLength、Concat等基本操作来实现,其算法基本思想为:由S和T生成一个新的串S,首先将它初始化为一个空串,并分配S.length＋L.length大小的存储空间,然后将位置pos之前S的子串、T串,以及pos之后的串连接,并将所得的新串赋给串S,如图4－2所示。

图4－2　串插入操作示意图

具体算法如下。

串的插入操作,其时间主要消耗在取子串操作和串连接操作上。由于取子串操作和串连接操作都需要对串S和串T字符逐个进行操作,因此该算法的时间复杂度为O（S.length＋L.length）。

2.串删除

串删除操作是指删除当前串（S）中从指定位置（pos）开始的一定长度（len）的子串。例如:S＝“I am a student”,StrDelete（S,1,5）,则S＝“a student”。

串的删除操作与串插入操作类似,可以通过SubString、StrLength、Concat等基本操作来实现。其算法基本思想为:取得串S中前pos—1个字符组成的子串及pos＋len—1之后的子串,进行连接,得到新的串S,修改串S长度,如图4－3所示。

图4－3　串删除操作示意图

具体算法如下。

串删除操作的时间复杂度为O（S.length）。

3.串查询

串查询操作用于实现对字符串的查找功能,如果当前串（串S）串中存在与给定串（串T）值相同的子串,则返回它在当前串S中某个指定位置（pos）之后第一次出现的位置。

例如:S＝“This is a Student！”,T＝“is”,Index（S,T,4）＝6。

该操作可以通过StrCompare、SubString、StrLength等基本操作来实现。其算法基本思想为:从主串S中取第i（＝pos）位起,其长度与串T相等的子串,与T相比较,若相等,则求得函数值为i（＝pos）,否则i值自增1；直到找到与串T相等的子串或串S中不存在与串T相等的子串为止。即求使等式StrCompare（SubString（S,I,StrLength（T））,T）＝＝0成立的i值。其中,i的初值应为pos,在找不到的情况下,i＝n－m＋1；n为串S长度；m为串T长度。基本操作过程如图4－4所示。

图4－4　串查询操作过程示意图

具体算法如下。

串查询操作的时间复杂度,在最好的情况下为O（S.length＋L.length）；在最差的情况下,每趟循环执行到最后才出现不等,故最多需要比较n－m＋1次,总比较次数为m×（nm＋1）,又由于m《n,因此时间复杂度为O（m×n）,即O（S.length×L.length）。

4.串替换

串替换操作用于实现用串V替换串S中出现的所有与串T相等的不重叠的子串。例如:S＝“XYXYXYXYXYXY”,T＝“XYX”,V＝“V”,则replace（S,T,V）＝“VYVYVY”。

该操作可以通过StrAssign、SubString、StrLength、Concat、Index等基本操作来实现。其算法基本思想为:由S和V生成一个新的串news,首先将它初始化为一个空串,然后重复以下步骤直至“查找不成功”为止。

（1）自pos位置起在串S中查找与串T相同的子串。

（2）将串S中不被置换的子串（即从pos起到与串T相同的子串在串S中的位置之前的字符序列）和串V相继连接到串news上。

（3）将S中不被置换的字符序列连接到串news中,并将所得的新串赋给串S。

基本操作过程如图4－5所示。

图4－5　串替换操作过程示意图

具体算法如下。

串替换操作的时间复杂度为O（L.length×S.length）。

本章小结

1.串是一种数据类型受到限制的特殊的线性表,并且规定表中每一个元素类型只能为字符型。

2.串虽然是线性表,但又有其特殊的地方。串不能作为单个字符进行讨论,而是作为一个整体（字符串）进行讨论。

3.串的存储结构主要分为顺序存储结构和链式存储结构两种。而顺序存储又分为定长顺序存储和堆分配存储。堆分配存储由于其能在串操作过程中动态分配存储空间,故其比定长顺序存储的适用性更强。串的链式存储把可利用的空间分成大小相同的若干连续的存储单元,每个结点有data和next两个域,其中data域用于存放指向下一个结点（首地址）的指针。该结构比较适用于待处理的串比较长的情况。

4.串的基本操作包括串赋值、求子串、求串长、串比较和串连接,以及利用基本操作所实现的串插入、串删除、串查询和串替换操作等。