4￥-four(天津科技大学)

第四章串4.1串类型的定义4.2串的表示和实现

4.2.1定长顺序存储表示

4.2.2堆分配存储表示

4.2.3串的块链存储表示4.3串的模式匹配算法4.4串操作应用举例—文本编辑1/22/20251第四章串4.1串类型的定义基本概念

串(String)是由零个或多个字符组成的有限序列。一般记作S=‘a1a2a3…an’，其中S是串名，单引号括起来的字符序列是串值；ai(1≦i≦n)可以是字母、数字或其它字符；串中所包含的字符个数称为该串的长度。

空串(EmptyString)：长度为零的串。它不包含任何字符。

空格串(BlankString)：由一个或多个空格组成的串。注意：空串和空格串的不同。1/22/20252第四章串基本概念（续）子串：串中任意个连续字符组成的子序列。主串：包含子串的串。通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的序号（或位置）。例如，设A和B分别为

A=“Thisisastring”B=“is”

则B是A的子串，A为主串。B在A中出现了两次，其中首次出现所对应的主串位置是3。因此，称B在A中的序号（或位置）为3。特别地，空串是任意串的子串，任意串是其自身的子串。1/22/20253第四章串基本概念（续）通常在程序中使用的串可分为两种：串变量和串常量。串常量和整常数、实常数一样，在程序中只能被引用但不能不能改变其值，即只能读不能写。通常串常量是由直接量来表示的，例如语句Error(“overflow”)中“overflow”是直接量。但有的语言允许对串常量命名，以使程序易读、易写。如C++中，可定义

constcharpath[]=“dir/bin/appl”;

这里path是一个串常量，对它只能读不能写。串变量和其它类型的变量一样，其取值是可以改变的。1/22/20254第四章串串的抽象数据类型定义串的抽象数据类型定义见教材P71

串的基本操作(13个)：StrAssign,Strcopy,StrEmpty,StrCompare,StrLength,ClearString,Concat,SubString,Index,Replace,StrInsert,StrDelete,DestroyString

许多高级语言均提供了串基本操作相应的运算或标准库函数来实现。下面仅介绍几种在C语言中常用的串运算，其它的串操作见教材及参考书。1/22/20255第四章串串变量及基本操作：

chars1[20]=“dirtreeformat”,s2[20]=“file.mem”;chars3[30],*p;

intresult;求串长(length)

int

strlen(chars);//求串的长度例如：cout<<strlen(s1);输出131/22/20256第四章串基本操作（续）（2）串复制(copy)char*strcopy(charto,charfrom);

该函数将串from复制到串to中，并且返回一个指向串to的开始处的指针。例如：strcopy(s3,s1);//s3=“dirtreeformat”(3)联接(concatenation)charconcat(charto,charfrom)

该函数将串from复制到串to的末尾，并且返回一个指向串to的开始处的指针。1/22/20257第四章串基本操作（续）例如：concat(s3,”/”)concat(s3,s2);//s3=“dirtreeformat/file.mem”(4)串比较（compare)

intstrcompare(chars1,chars2);

该函数比较串s1和串s2的大小，当返回值小于0，等于0或大于0时分别表示s1<s2、s1=s2或s1>s2

例如：

result=strcompare(“baker”,”Baker”)result>0result=strcompare(“12”,”12”);result=0result=strcompare(“Joe”,”Joseph”);result<01/22/20258第四章串基本操作（续）（5）字符定位(index)charstrchr(chars,charc);

该函数是找c在字符串中第一次出现的位置，若找到则返回该位置，否则返回NULL。

例如：p=strchr(s2,”.”);p指向“file”之后的位置

if(p)strcpy(p,”.cpp”);s2=“file.cpp”最小操作子集：串赋值StrAssign、串比较Strcompare、求串长StrLength、串联接concat和求子串SubString。串的其余操作可由这些基本操作组合而成。1/22/20259第四章串4.2串的表示和实现因为串是特殊的线性表，故其存储结构与线性表的存储结构类似。只不过由于组成串的结点是单个字符。串有三种机内表示方法，下面分别介绍。1定长顺序存储表示定长顺序存储表示,也称为静态存储分配的顺序表。它是用一组连续的存储单元来存放串中的字符序列。所谓定长顺序存储结构，是直接使用定长的字符数组来定义，数组的上界预先给出：

#definemaxstrlen255

typedefcharsstring[maxstrlen+1];

sstrings;//s是一个可容纳255个字符的顺序串。1/22/202510第四章串串的结束标记

一般可使用一个不会出现在串中的特殊字符在串值的尾部来表示串的结束。例如，C语言中以字符‵\0′表示串值的终结，这就是为什么在上述定义中，串空间最大值maxstrlen为256，但最多只能存放255个字符的原因，因为必须留一个字节来存放‵\0′字符。若不设终结符，可用一个整数来表示串的长度，那么该长度减1的位置就是串值的最后一个字符的位置。1/22/202511第四章串顺序串的类型定义顺序串的类型定义和顺序表类似：

typedef

struct{charch[maxstrlen];

intlength;}sstring;//其优点是涉及到串长操作时速度快。1/22/202512第四章串顺序存储时串操作的实现

串联接Concat(T,S1,S2)

求子串SubString(sub,s,pos,len)

注：串联接操作可能出现“截断”现象1/22/202513第四章串2堆分配存储表示

这种存储表示的特点是，仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得。所以也称为动态存储分配的顺序表。在C语言中，利用动态存储管理函数，来根据实际需要动态分配和释放字符数组空间。

typedef

struct{char*ch;//若是非空串，则按串长分配存储区，否则ch为null

intlength;//串长度

}hsring;1/22/202514第四章串3串的链式存储结构顺序串上的插入和删除操作不方便，需要移动大量的字符。因此，我们可用单链表方式来存储串值，串的这种链式存储结构简称为链串。

typedef

structnode{chardata;

structnode*next;}lstring;

一个链串由头指针唯一确定。这种结构便于进行插入和删除运算，但存储空间利用率太低。1/22/202515第四章串结点的大小由于串结构的特殊性，可使每个结点存放多个字符。通常将结点数据域存放的字符个数定义为结点的大小，显然，当结点大小大于1时，串的长度不一定正好是结点的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。…^headABCIBCDEFGHI###^headA1/22/202516第四章串块链结构（设头、尾指针）对于结点大小不为1的链串，其类型定义只需对上述的结点类型做简单的修改即可。

#definenodesize80

typedef

structnode{chardata[nodesize];

structnode*next;}node;

typedef

struct

lstring{node*head,*tail;

int

curlen;}lstring;1/22/202517第四章串存储密度的概念

存储密度小，运算处理方便，存储占用量大；存储密度大，情况则相反。串的链式存储结构队某些串操作（如联接等）有一定的方便，但总的说来不如另外两种存储结构灵活。存储密度=串值所占的存储位实际分配的存储位1/22/202518第四章串4.3串的模式匹配算法子串定位运算又称为模式匹配(PatternMatching)或串匹配(StringMatching)，此运算的应用非常广泛。在文本编辑程序中，我们经常要查找某一特定单词在文本中出现的位置。显然，解此问题的有效算法能极大地提高文本编辑程序的响应性能。在串匹配中，一般将主串称为目标串，子串称之为模式串。1/22/202519第四章串模式匹配（续）设S为目标串，T为模式串，且不妨设：

S=“s0s1s2…sn-1”T=“t0t1…tm-1”

串的匹配实际上是对于合法的位置0≦i≦n-m依次将目标串中的子串s[i..i+m-1]和模式串t[0..m-1]进行比较，若s[i..i+m-1]=t[0..m-1]，则称从位置i开始的匹配成功，亦称模式t在目标s中出现.1/22/202520第四章串模式匹配（续）若s[i..i+m-1]≠t[0..m-1]，则称从位置i开始的匹配失败。上述的位置i又称为位移，当s[i..i+m-1]=t[0..m-1]时，i称为有效位移；当s[i..i+m-1]≠t[0..m-1]时，i称为无效位移。这样，串匹配问题可简化为是找出某给定模式T在一给定目标T中首次出现的有效位移。

1/22/202521第四章串模式匹配算法串匹配的算法很多，这里我们只讨论一种最简单的称为朴素的串匹配算法。其基本思想是用一个循环来依次检查n-m+1个合法的位移i(0≦I≦n-m)是否为有效位移，其算法段为：

for(i=0;i<=n-m;i++){if(S[i..i+m-1]=T[0..m-1])returni;}1/22/202522第四章串模式匹配算法匹配过程设目标串为ababcabcacbab，模式串为abcac第一趟ababcabcacbababc第二趟ababcabcacbaba第三趟ababcabcacbababcac第四趟ababcabcacbaba第五趟ababcabcacbaba第六趟ababcabcacbababcac1/22/202523第四章串KMP算法—模式匹配的改进算法算法是由D.E.Knuth、V.R.Pratt和J.H.Morris同时发现，因而得名。改进在于：利用已经得到的部分匹配结果将模式向右“滑动”尽可能远的一段距离。算法可以在O(n+m)的时间数量级上完成。第一趟ababcabcacbababc第二趟ababcabcacbababcac第三趟ababcabcacbab