数据结构课件：第4章 串

教学内容第1章绪论第2章线性表第3章栈和队列第4章串第5章数组和广义表第6章树和二叉树第7章图第8章查找第9章排序第4章串4.1串的定义4.2串的表示和实现4.3串的模式匹配算法4.4串操作应用举例第4章串

在非数值处理、事务处理等问题常涉及到一系列的字符操作。比如汇编和语言编译、信息检索系统、文字编辑系统、问答系统、自然语言翻译系统等，都是以字符串作为处理对象的。

计算机的硬件结构主要是反映数值计算的要求，因此，字符串的处理比具体数值处理复杂。本章讨论串的存储结构及几种基本的处理。4.1串类型的定义4.1.1

串的基本概念串(字符串string)：由零个或多个字符组成的有限序列。记作S=‘a1a2…an’

（n≥0）串名：S；串值：用单引号括起来的字符序列。ai可以是字母、数字或其他字符。长度：串中字符的数目n。空串：含零个字符的串，表示。空格串：由一个或多个空格组成的串。例如：x=‘123’表明x是一个串变量名，赋予它的值是字符序列123，

x=123表明x是一个整型变量，赋予它的值为整数123。注意：串值一定要用单引号括起来。单引号本身不属于串，只是为了避免混淆。注意：空串和空格串的区别。子串：串中任意个连续的字符组成的子序列。字符在串的位置：字符在序列中的序号。子串在串的位置：子串的第一个字符在串中的位置。相等：当且仅当两个串的值相等。长度相等且对应位置的字符都相等。

例子：a=‘BEI’

b=‘JING’

c=‘BEIJING’

d=‘BEIJING’长度分别为3、4、7、8；a和b都是c和d的子串；a在c和d中的位置都是1；b在c和d中的位置是4和5；a、b、c、d彼此不相等。串的比较：串的比较：通过组成串的字符之间的比较来进行的。

给定两个串：X=‘x1x2…xn’和Y=‘y1y2…ym’，则：1.当n=m且x1=y1，…，xn=ym时，称X=Y；2.当下列条件之一成立时，称X＜Y：⑴n＜m且xi=yi（1≤i≤n）；⑵存在k≤min(m,n)，使得xi=yi(1≤i≤k-1)且xk＜yk。

例：S1=‘ab12cd’，S2=‘ab12’，S3=‘ab13’串与线性表的区别：串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。然而，串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以“单个元素”作为操作对象，如：在线性表中查找某个元素、求取某个元素、在某个位置上插入一个元素和删除一个元素等；而在串的基本操作中，通常以“串的整体”作为操作对象，如：在串中查找某个子串、求取一个子串、在串的某个位置上插入一个子串以及删除一个子串等。4.1.2

串的抽象数据类型定义

ADTString{数据对象：D={ai|ai∈CharacterSet,i=1,2,…,n,n≥0}数据关系：R={<ai-1,ai>|ai-1,ai∈D,i=2,3,…,n}基本操作：StrAssign(&T,chars)

初始条件：chars是串常量。

操作结果：赋于串T的值为chars。

StrCopy(&T,S)

初始条件：串S存在。

操作结果：由串S复制得串T。DestroyString(&S)

初始条件：串S存在。

操作结果：串S被销毁。StrEmpty(S)

初始条件：串S存在。

操作结果：若S为空串，则返回TRUE，否则返回FALSE。

StrCompare(S,T)

初始条件：串S和T存在。

操作结果：若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0。StrLength(S)

初始条件：串S存在。

操作结果：返回串S序列中的字符个数，即串的长度。ClearString(&S)

初始条件：串S存在。

操作结果：将S清为空串。Concat(&T,S1,S2)

初始条件：串S1和S2存在。

操作结果：用T返回由S1和S2联接而成的新串。Replace(&S,T,V)

初始条件：串S，T和V存在，T是非空串。

操作结果：用V替换主串S中出现的所有与T相等的不重叠的子串。SubString(&Sub,S,pos,len)

初始条件：串S存在，1≤pos≤StrLength(S)且

0≤len≤StrLength(S)-pos+1。

操作结果：用Sub返回串S的第pos个字符起长度为len的子串。Index(S,T,pos)

初始条件：串S和T存在，T是非空串，

1≤pos≤StrLength(S)。

操作结果：若主串S中存在和串T值相同的子串，则返回它

在主串S中第pos个字符之后第一次出现的位置；

否则函数值为0。StrInsert(&S,pos,T)

初始条件：串S和T存在，1≤pos≤StrLength(S)＋1。操作结果：在串S的第pos个字符之前插入串T。StrDelete(&S,pos,len)

初始条件：串S存在，1≤pos≤StrLength(S)-len+1。操作结果：从串S中删除第pos个字符起长度为len的子串。}ADTString定位函数（算法4.1）基本思想：从主串S中取“第i个字符起、长度和串T相等的子串”和串T比较，若相等，则求得函数值为i，否则i值增1直至找到相等的子串或者不存在和T相等的子串为止。

intIndex(StringS,StringT,intpos){

//T为非空串。若主串S中第pos个字符之后存在与T相等的子串，

//则返回第一个这样的子串在S中的位置，否则返回0。

if(pos>0){ n=StrLength(S);m=StrLength(T);i=pos; while(i<=n-m+1){

SubString(sub,S,i,m);//取从第i个起长度为m的子串

if(StrCompare(sub,T)!=0)++i;

elsereturni;

//找到和T相等的子串

}//while }//if return0;

//S中不存在满足条件的子串}//Index

4.2串的表示和实现

串是一种特殊的线性表，其存储表示和线性表类似，但又不完全相同。串的存储方式取决于将要对串所进行的操作。串在计算机中有3种表示方式：◆定长顺序存储表示：将串定义成字符数组，利用串名可以直接访问串值。用这种表示方式，串的存储空间在编译时确定，其大小不能改变。◆堆分配存储方式：仍然用一组地址连续的存储单元来依次存储串中的字符序列，但串的存储空间是在程序运行时根据串的实际长度动态分配的。◆块链存储方式：是一种链式存储结构表示。4.2.1

串的定长顺序存储表示

这种存储结构又称为串的顺序存储结构。是用一组连续的存储单元来存放串中的字符序列。所谓定长顺序存储结构，是直接使用定长的字符数组来定义，数组的上界预先确定。定长顺序存储结构定义为：#defineMAXSTRLEN255；//用户可在255以内定义最大串长

typedefunsignedcharSString[MAXSTRLEN+1]；//0号单元存放串的长度如何表示串的长度？方案1：用一个变量来表示串的实际长度。

0123456……Max-1

abcdefg9空闲如何表示串的长度？方案1：用一个变量来表示串的实际长度。方案2：在串尾存储一个不会在串中出现的特殊字符作为串的终结符，表示串的结尾。

01234567……Max-1

abcdefg\0空闲如何表示串的长度？方案1：用一个变量来表示串的实际长度。方案2：在串尾存储一个不会在串中出现的特殊字符作为串的终结符，表示串的结尾。

方案3：用数组的0号单元存放串的长度，从1号单元开始存放串值。

01234567……Max-1

9

abcdefg空闲1.字符串的连接设串的最大长度为10，

S1=‘ABCDEF’

S2=‘GHIJ’

S3=‘KLMNOP’

S4=‘QRSTUVWXYZ’S1连接S2，结果‘ABCDEFGHIJ’。S1连接S3，结果‘ABCDEFKLMN’，S3的‘OP’部分被截断。S4连接S1，结果‘QRSTUVWXYZ’，S1全部被截断。算法说明：StatusConcat(SString&T,SStringS1,SStringS2){//算法4.2

//以T返回由S1和S2联接而成的新串，若未截断，返回TRUE，否则FALSE If(S1[0]+S2[0]<=MAXSTRLEN){ //未截断

T[1..S1[0]]=S1[1..S1[0]];

T[S1[0]+1..S1[0]+S2[0]]=S2[1..S2[0]];

T[0]=S1[0]+S2[0];

uncut=TRUE;

} elseif(S1[0]<MAXSTRSIZE){ //截断

T[1..S1[0]]=S1[1..S1[0]];

T[S1[0]+1..MAXSTRLEN]=S2[1..MAXSTRLEN-S1[0]];

T[0]=MAXSTRLEN;

uncut=FALSE;

} else { //截断 (仅取S1)

T[0..MAXSTRLEN]=S1[0..MAXSTRLEN];

uncut=FALSE;

} returnuncut;}//Concat

求子串操作SubStr(s,pos,len)示例2.求子串abcdefgepos=3,len=3pos=7,len=4cdeabcdefgege空串算法说明：StatusSubString(SString&Sub,SStringS,intpos,intlen){

//以Sub带回串S中第pos个字符起长度为len的子串（算法4.3）

//其中，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1 if(pos<1||pos>s[0]||len<0||len>s[0]-pos+1)

returnERROR; Sub[1..len]=S[pos..pos+len-1]；

Sub[0]=len；

returnOK;}//SubString

在串的顺序存储结构中，如果操作中出现串值序列的长度超过上界MAXSTRLEN时，约定用截尾法处理，这种情况不仅在求联接串时可能发生，在串的其他操作中，如插入、置换等也可能发生。克服这个弊病只有不限定串长的最大长度，即动态分配串值的存储空间。4.2.2串的堆分配存储表示系统开辟一个串值存储空间（串值可利用空间），同时建立一个符号表；建立一个新串时，在可利用空间分配，并在符号表中记录下串变量名、串值在可利用空间的位置、串长度等信息。长度位置串名符号表串值存储空间31a长度位置串名符号表IEB串值存储空间44b31a长度位置串名符号表GNIJIEB串值存储空间88c44b31a长度位置串名符号表IAHGNAHSGNIJIEB串值存储空间616d88c44b31a长度位置串名符号表NIBRAHIAHGNAHSGNIJIEB串值存储空间4.2.3串的链式存储表示

串的链式存储结构和线性表的串的链式存储结构类似，采用单链表来存储串，结点的构成是：◆data域：存放字符，data域可存放的字符个数称为结点的大小；◆next域：存放指向下一结点的指针。若每个结点仅存放一个字符，则结点的指针域就非常多，造成系统空间浪费，为节省存储空间，考虑串结构的特殊性，使每个结点存放若干个字符，这种结构称为块链结构。结点大小为1的链表（非压缩形式）ABCDEFhead结点大小为4的链表（压缩形式）headDCBA##FE串的块链式存储的类型定义包括：⑴块结点的类型定义#defineCHUNKSIZE80//可由用户定义的块大小typedefstructchunk

{

//结点结构

charch[CHUNKSIZE]; structChunk*next;

}Chunk;(2)块链串的类型定义typedefstruct

{//串的链表结构

Chunk*head,*tail;//串的头和尾指针

intcurlen;//串的当前长度

}LString;在链式存储方式中，结点大小的选择和顺序存储方式的格式选择一样都很重要，它直接影响着串处理的效率。在各种串的处理系统中，所处理的串往往很长或很多，比如一本书的几百万个字符，情报资料的成千上万个条目等等。这就要求我们考虑串值的存储密度。存储密度可以定义为：存储密度=串值所占的存储位/实际分配的存储位显然，存储密度小，运算处理方便，但是存储占用量大。

串值的链式存储结构对某些串操作，比如联接操作等有一定方便之处，但总的来说不如另外两种存储结构灵活，它占用存储量大且操作复杂。4.3串的模式匹配算法（了解）模式匹配：子串在主串中的定位称为模式匹配或串匹配(字符串匹配)。模式匹配成功是指在主串S中能够找到模式串T，否则，称模式串T在主串S中不存在。

模式匹配的应用在非常广泛。例如，在文本编辑程序中，我们经常要查找某一特定单词在文本中出现的位置。显然，解此问题的有效算法能极大地提高文本编辑程序的响应性能。模式匹配是一个较为复杂的串操作过程。迄今为止，人们对串的模式匹配提出了许多思想和效率各不相同的计算机算法。介绍两种主要的模式匹配算法。4.3.1

模式匹配——BF算法朴素的模式匹配算法(BF(BruteForce)算法)

基本思想：从主串S的第一个字符开始和模式T的第一个字符进行比较，若相等，则继续比较两者的后续字符；否则，从主串S的第二个字符开始和模式T的第一个字符进行比较，重复上述过程，直到T中的字符全部比较完毕，则说明本趟匹配成功；或S中字符全部比较完，则说明匹配失败。例：主串S=‘ababcabcacbab’，模式T=‘abcac’ababcabcacbabi=3，j=3失败；i回溯到2，j回溯到1ijijij第

1趟abcac

例：主串S=‘ababcabcacbab’，模式T=‘abcac’ababcabcacbabi=3，j=3失败；i回溯到2，j回溯到1ji第

1趟abcac

例：主串S=‘ababcabcacbab’，模式T=‘abcac’ababcabcacbabi=2，j=1失败i回溯到3，j回溯到1第

2趟ijabcac

例：主串S=‘ababcabcacbab’，模式T=‘abcac’ababcabcacbabi=2，j=1失败i回溯到3，j回溯到1第

2趟ijabcac

例：主串S=‘ababcabcacbab’，模式T=‘abcac’ababcabcacbababcac

i=7，j=5失败i回溯到4，j回溯到1第

3趟ijijijijij例：主串S=‘ababcabcacbab’，模式T=‘abcac’ababcabcacbababcac

i=7，j=5失败i回溯到4，j回溯到1第

3趟ij例：主串S=‘ababcabcacbab’，模式T=‘abcac’ababcabcacbababcac

i=4，j=1失败i回溯到5，j回溯到1第

4趟ij例：主串S=‘ababcabcacbab’，模式T=‘abcac’ababcabcacbababcac

i=4，j=1失败i回溯到5，j回溯到1第

4趟ij例：主串S=‘ababcabcacbab’，模式T=‘abcac’ababcabcacbababcac

i=5，j=1失败i回溯到6，j回溯到1第

5趟ij例：主串S=‘ababcabcacbab’，模式T=‘abcac’ababcabcacbababcac

i=5，j=1失败i回溯到6，j回溯到1第

5趟ij例：主串S=‘ababcabcacbab’，模式T=‘abcac’ababcabcacbababcac

i=11，j=6，T中全部字符都比较完毕，匹配成功。第

6趟ijijijijijij4.3.1

模式匹配——BF算法1.在串S和串T中设比较的起始下标i和j；2.循环直到S或T的所有字符均比较完；

2.1如果S[i]=T[j]，继续比较S和T的下一个字符；

2.2否则，将i和j回溯，准备下一趟比较；3.如果T中所有字符均比较完，则匹配成功，返回匹配的起始比较下标；否则，匹配失败，返回0；BF算法：intBF(charS[],charT[]){i=1;j=1;start=1;while(i<=S[0]&&j<=T[0]){if(S[i]==T[j]){i++;j++;}else{

start++;i=start;j=1;}}if(j>T[0])returnstart;elsereturn0;}设串S长度为n，串T长度为m，在匹配成功的情况下，考虑两种极端情况：

⑴最好情况：不成功的匹配都发生在串T的第一个字符。例如：S=‘aaaaaaaaaabcdccccc’T=‘bcd’设匹配成功发生在si处，则在i-1趟不成功的匹配中共比较了i-1次，第i趟成功的匹配共比较了m次，所以总共比较了i-1+m次，所有匹配成功的可能情况共有n-m+1种，则：)(2)()1(11mnOmnmipmnii+=+=å+-´+-=设串S长度为n，串T长度为m，在匹配成功的情况下，考虑两种极端情况：

(2)最坏情况：不成功匹配都发生在串T的最后一个字符。例如：S=‘aaaaaaaaaaabccccc’T=‘aaab’设匹配成功发生在si处，则在i-1趟不成功的匹配中共比较了(i-1)×m次，第i趟成功的匹配共比较了m次，所以总共比较了i×m次，因此为什么BF算法时间性能低？在每趟匹配不成功时存在大量回溯，没有利用已经部分匹配的结果。如何在匹配不成功时主串不回溯？主串不回溯，模式就需要向右滑动一段距离。如何确定模式的滑动距离？4.3.2模式匹配——KMP算法该改进算法是由D.E.Knuth，J.H.Morris和V.R.Pratt提出来的，简称为KMP算法。此算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。其改进在于：

每当一趟匹配过程出现字符不相等时，不需要回溯i指针，而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较。i=3，j=3失败；

s2=t2;t1≠t2∴t1≠s2ababcabcacbabij第

1趟abcac

ababcabcacbab第

2趟abcac

i=3，j=3失败；

s2=t2;t1≠t2∴t1≠s2ababcabcacbabij第

1趟abcac

ababcabcacbababcac

第

3趟ababcabcacbababcac

第

3趟iji=7，j=5失败s4=t2;t1≠t2∴t1≠s4ababcabcacbababcac

第

4趟ababcabcacbababcac

第

3趟iji=7，j=5失败s5=t3;t1≠t3∴t1≠s5ababcabcacbababcac

第

5趟ababcabcacbababcac

第

3趟iji=7，j=5失败s5=t3;t1≠t3∴t1≠s5ababcabcacbababcac

第

6趟匹配成功结论：i可以不回溯，模式向右滑动到的新比较起点k，并且k仅与模式串T有关！需要讨论两个问题：①如何由当前部分匹配结果确定模式向右滑动的新比较起点k？②模式应该向右滑多远才是最高效率的?希望某趟在si和tj匹配失败后，指针i不回溯，模式t向右“滑动”至某个位置上，使得tk对准si继续向右进行。显然，现在问题的关键是串t“滑动”到哪个位置上？不妨设位置为k，即si和tj匹配失败后，指针i不动，模式t向右“滑动”，使tk和si对准继续向右进行比较，要满足这一假设，就要有如下关系成立：‘t1t2…tk-1’

=‘si-k+1si-k+2…si-1’(4.1)(4.1)式左边是tk前面的k-1个字符，右边是si

前面的k-1个字符。而本趟匹配失败是在si和tj之处，已经得到的部分匹配结果是：‘t1t2…tj-1’

=‘si-j+1si-j+2…si-1’(4.2)因为k<j，所以有：‘tj-k+1tj-k+2…tj-1’

=‘si-k+1si-k+2…si-1’(4.3)(4.3)式左边是tj前面的k-1个字符，右边是si

前面的k-1个字符，通过(4.1)和(4.3)得到关系：‘t1t2…tk-1’

=‘tj-k+1tj-k+2…tj-1’(4.4)结论：某趟在si和tj匹配失败后，如果模式串中有满足关系(4)的子串存在，即：模式中的前k-1个字符与模式中tj字符前面的k-1个字符相等时，模式t就可以向右“滑动”至使tk和si对准，继续向右进行比较即可。next函数模式中的每一个tj都对应一个k值，由(4.4)式可知，这个k值仅依赖与模式t本身字符序列的构成，而与主串s无关。我们用next[j]表示tj对应的k值，根据以上分析，next函数有如下性质：①next[j]是一个整数，且0≤next[j]<j②为了使t的右移不丢失任何匹配成功的可能，当存在多个满足(4.4)式的k值时，应取最大的，这样向右“滑动”的距离最短，“滑动”的字符为j-next[j]个。③如果在tj前不存在满足(4.4)式的子串，此时若t1≠tj，则k=1;若t1=tj，则k=0;这时“滑动”的最远，为j-1个字符即用t1和sj+1继续比较。next[j]＝0当j＝1时//不比较max{k|1<k<j且T1…Tk-1=Tj-(k-1)…Tj-1}1其他情况令k=next[j]，则：当j=1时，next[j]=0；//next[j]=0表示根本不进行字符比较当j>1时，next[j]的值为：模式串的位置从1到j-1构成的串中所出现的首尾相同的子串的最大长度加1。当无首尾相同的子串时next[j]的值为1。//next[j]=1表示从模式串头部开始进行字符比较可见，模式中相似部分越多，则next[j]函数越大，它既表示模式T字符之间的相关度越高，模式串向右滑动得越远，与主串进行比较的次数越少，时间复杂度就越低。

模式串T：abaabcacj：12345678新匹配位k=next[j]:01122312j=1时,next[j]＝0；j=2时,next[j]＝1；j=3时,T1≠T2，因此，k=1；j=4时,T1＝T3，因此，k=2；j=5时,T1＝T4，因此，k=2；j=6时，T1T2=T4T5，因此，k=2+1=3；以此类推。KMP算法：在求得模式的next函数之后，匹配可如下进行：假设以指针i和j分别指示主串和模式中的比较字符，令i的初值为pos，j的初值为1。若在匹配过程中si==tj，则i和j分别增１；若si≠tj匹配失败后，则i不变，j退到next[j]位置再比较，若相等，则指针各自增１，否则j再退到下一个next值的位置，依此类推。直至下列两种情况：一种是j退到某个next值时字符比较相等，则i和j分别增１继续进行匹配;另一种是j退到值为零（即模式的第一个字符失配），则此时i和j也要分别增１，表明从主串的下一个字符起和模式重新开始匹配。4.4串操作应用举例——文本编辑

文本编辑是串的一个很典型的应用。它被广泛用于各种源程序的输入和修改，也被应用于信函、报刊、公文、书籍