串类型的定义串的表示与实现的模式匹配算法串操作应用举例课件

1、串类型的定义串的表示和实现串的模式匹配算法串操作应用举例第四章 串第1页，共55页。1、了解串的概念；学习要点2、熟悉串的基本运算的定义 及实现方法；3、掌握基本串匹配算法。第2页，共55页。 在较早的程序设计语言中，字符串（简称串）是作为输入或输出的常量（是直接量，不参加运算）出现，而非数值处理的对象基本上是字符串数据。这就要求字符串也能以变量的形式出现，能进行一系列字符串操作（运算） 。目前大多数程序设计语言都支持串这种数据类型。第3页，共55页。 1、串 2、串长：串中所包含的字符个数。 3、空串 ：长度为零的串，它不包含任何字符。 记作“” 4、子串：串中任意个连续的字符组成的子序列。

2、 5、主串：包含子串的串。 4.1 串类型的定义 基本概念 ：零个或多个字符组成的有限序列，即数 据元素为字符的线性表。一般记为 S=a1a2. an ，其中，S是串名， 单引号括起的字符序列是串值。 第4页，共55页。7、子串在主串中的位置 ：子串在主串中第一次出现时，子串的第一个字符在主串中的位置。6、字符在串中的位置：字符在序列中的序号。 8、两个串相等 ：两个串的长度相等，并且各 个对应位置的字符都相等时才相等。9、空格串 ： 由一个或多个空格组成的串，其长度为串中空格字符的个数。它与空串是不同的概念。 第5页，共55页。 串的逻辑结构和线性表极为相似，区别仅在于串的数据对象为字符集。

3、 串的基本操作和线性表有很大差别： 在线性表的基本操作中，大多以“单个元素”作为操作对象； 在串的基本操作中，通常以“串的整体”作为操作对象 。第6页，共55页。 ADT String 数据对象：D ai |aiCharacterSet, i=1,2,.,n, n0 数据关系：R1 | ai-1, ai D, i=2,.,n 基本操作： ADT StringADT串的定义第7页，共55页。StrAssign (&T, chars) /串赋值 初始条件：chars 是字符串常量。 操作结果：把 chars 赋为 T 的值。 StrCopy (&T, S) /串复制 初始条件：串 S 存在。 操作

4、结果：由串 S 复制得串 T。DestroyString (&S) /串销毁 初始条件：串 S 存在。 操作结果：串 S 被销毁。第8页，共55页。 StrEmpty(S) /串判空初始条件：串S存在。操作结果：若 S 为空串，则返TRUE， 否则返回 FALSE。StrCompare(S,T) /串比较例如：StrCompare(data, state) 0初始条件：串 S 和 T 存在。操作结果：若S T，则返回值 0； 若S T，则返回值 0； 若S T，则返回值 0第9页，共55页。StrLength (S) /求串长初始条件：串 S 存在。操作结果：返回 S 的元素个数， 称为串的长

5、度。Concat (&T, S1, S2) /串联接例如： Concate( T, man, kind) 求得 T = mankind初始条件：串 S1 和 S2 存在。操作结果：用 T 返回由 S1 和 S2 联接而成的新串。第10页，共55页。 SubString (&Sub, S, pos, len) /求子串 初始条件： 串 S 存在，1posStrLength(S) 且0lenStrLength(S)-pos+1。 操作结果：用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串。子串为“串”中的一个字符子序列。第11页，共55页。 SubString( sub, co

6、mmander, 1, 9) 求得 sub = commander SubString( sub, commander, 9, 1) 求得 sub = r 例如： SubString( sub, commander, 4, 3) 求得 sub = man;第12页，共55页。SubString(sub , student, 5, 0) 得sub= 关于参数len（子串长度）的说明：长度为 0 的子串为“合法”串空串。事实上对任何串S和位置pos 都有：SubString(sub, commander, 4, 7) 得sub = manderSubString(sub , S, pos, 0)得

7、sub= ；有时对len放宽到lenStrLength(S)-pos+1，此时规定 SubString(sub ,S, pos, len) 的值取S的第pos个字符到S的最后一个字符作为子串（长为StrLength(S)-pos+1）。第13页，共55页。Index (S, T, pos) /(子)串(位置)定位 初始条件：串S和T存在，T是非空串， 1posStrLength(S)。 操作结果：若主串 S 中存在和串T值相同 的子串, 则返回它在主串S中第 pos个字符之后第一次出现的位 置;否则函数值为0。第14页，共55页。假设 S = abcaabcaaabc, T = bca Ind

8、ex(S, T, 1) =Index(S, T, 3) = Index(S, T, 8) = “子串在主串中的位置”意指子串中的第一个字符在主串中的位序。2;6;0;第15页，共55页。Replace (&S, T, V) /串替换初始条件：串S, T和 V 均已存在， 且 T 是非空串。操作结果：用V替换主串S中出现的所有与 （模式串） T相等的不重叠的子串。 例如：假设S=abcaabcaaabca, T = bca若V=x,则经置换后得到S=axaxaax若V=bc,则经置换后得到S=abcabcaabc 第16页，共55页。 StrInsert (&S, pos, T) /串插入例如：

9、S = chater，T = rac， 则执行 StrInsert(S, 4, T)之后得到 S = character初始条件：串S和T存在， 1posStrLength(S)1。操作结果：在串S的第pos个字符之前插入 串T。 第17页，共55页。StrDelete (&S, pos, len) /串删除 初始条件：串S存在 ， 1posStrLength(S)-len+1。 操作结果：从串S中删除第pos个字符 起长度为len的子串。 ClearString(&S) /串清除初始条件：串S存在。操作结果：将S清为空串。第18页，共55页。在上述抽象数据类型定义的13种操作中， 串赋值St

10、rAssign、串复制Strcopy、 串比较StrCompare、求串长StrLength、 串联接Concat以及求子串SubString 等六种操作构成串类型的最小操作子集。 这些操作不可能利用其他串操作来实现， 反之，其他串操作（除串清除ClearString和串 销毁DestroyString外）可在这个最小操作子 集上实现。第19页，共55页。 例如，可利用串比较、求串长和求子串等操作实现定位函数Index(S,T,pos)。 StrCompare(SubString(S, i, StrLength(T),T ) T 串 T 串iposStrLength(S) StrLength(

11、T) +1算法的基本思想：? = 0S 串 在pos到StrLength(S) StrLength(T) +1范围内寻求使下式成立的i值 T 串ipos+1第20页，共55页。int Index (String S, String T, int pos) / 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); if (StrCompa

12、re(sub,T) != 0) +i ; else return i ; return 0; / S中不存在与T相等的子串 / Index第21页，共55页。 利用最小操作子集中的操作也可实现 串判空 StrEmpty(S) 、 串替换 Replace (&S, T, V) 、 串删除 StrDelete (&S, pos, len) 、 串插入 StrInsert (&S, pos, T) 等操作。留作习题第22页，共55页。 若在程序设计语言中，串只是作为输入或输出的常量出现，则只需存储此串的串值，即字符序列即可。但在多数非数值处理的程序中，串也以变量的形式出现。4.2 串的表示和实现 串

13、有三种机内表示方法: 一、串的定长顺序存储表示二、串的堆分配存储表示三、串的块链存储表示第23页，共55页。 用一组地址连续的存储单元存储串值的字符序列。该结构可用定长数组描述如下： #define MAXSTRLEN 255 /可在255以内定义最大串长 typedef unsigned char Sstring MAXSTRLEN + 1; / 0号单元存放串的长度一、串的定长顺序存储表示第24页，共55页。 对串的长度有两种表示方法: 1.以下标为0的数组分量存放串的实际长度 (如 PASCAL语言) ,特点是便于进行某些操作； 2.在串值后面加不计入串长的结束标记字符(如C 语言采用“

14、0” ) ,此时的串长为隐含值,特点是 访问容易,但删除或插入麻烦。说明： 串的实际长度可在预定义长度的范围内随意设定， 超过预定义长度的串值则被 “截断” 。 对超长部分实施截断操作正是串的定长顺序存储 表示的弊端。为克服此弊端，惟有不限定最大串 长，即动态分配串值的存储空间。第25页，共55页。 以下以串联接为例进行讨论在这种存储结构表示下如何实现串的操作： 假设T, S1, S2都是 Sstring型变量, T为S1联结S2后所得之串,则联接运算Concat (&T, S1, S2) 是将S1和S2的值分别传送到T的相应位置上,超过MAXSTRLEN的部分截断之。 其运算结果可能有三种情

15、况： 1) S10+ S20 MAXSTRLEN 2) S10+ S20 MAXSTRLEN 3) S10 MAXSTRLEN第26页，共55页。1) S10+ S20 MAXSTRLEN串S1串S2串 TS10S20S10+ S20MAXSTRLENMAXSTRLENMAXSTRLEN第27页，共55页。2) S10+ S20 MAXSTRLEN串 S1串 S2串 TS10S20MAXSTRLENMAXSTRLENMAXSTRLEN截去第28页，共55页。 串S2被全部截去。3) S10 MAXSTRLEN串 S1串 S2串 TS10S20S10MAXSTRLENMAXSTRLENMAXST

16、RLEN第29页，共55页。Status Concat(SString &T, SString S1, SString S2) if (S10+S20 = MAXSTRLEN) / 不截断 T1.S10 = S11.S10; TS10+1.S10+S20 = S21.S20; T0 = S10+S20; uncut = TRUE; else / 截断 if ( S10 MAXSTRSIZE ) T1.S10 = S11.S10;TS10+1.MAXSTRLEN = S21.MAXSTRLENS10;T0 = MAXSTRLEN; uncut = FALSE; 第30页，共55页。 else T

17、0.MAXSTRLEN = S10.MAXSTRLEN; / T0 = S10 = MAXSTRLEN uncut = FALSE; return uncut; / Concat 在串的顺序存储结构中，实现串操作的原操作为“字符序列的复制”，操作的时间复杂度基于字符序列的长度。第31页，共55页。二、串的堆分配存储表示 堆分配存储类似于线性表的顺序存储结构，仍以一组地址连续的存储单元存储串值的字符序列，但它们的存储空间是在程序执行过程中动态分配而得的。在C语言中是由动态分配函数malloc()和free()来管理一个称之为“堆（heap）”的自由存储区的。该存储结构类型描述如下：typedef

18、 struct char *ch ; / 若是非空串，则按串长分配存储区， /否则ch为NULL int length; / 串长度 一个串值的确定是通过串在堆中的起始位置和串的长度实现的。HString;第32页，共55页。 这类串操作实现的算法为: 先为新生成的串（若该串已存在,则先释放其所占空间）分配一个长度适当的存储空间，然后进行串值的复制。这种存储结构表示时的串操作仍基于 “字符序列的复制” 进行的。为此，串名与串值之间要建立一个对照表。 0 1 2 3 4 5 6 7 8 9 HString a,b ;串名 基址 ch 长度 length a 2000 4 b 2012 4 D a

19、 t a S t r u c t u r e B o o k 16 2000第33页，共55页。 串插入算法Status StrInsert (Hstring &S, int pos, Hstring T) /在串S的第pos个字符之前插入串T S.ch0 1 pos-1T.lengthif (pos S.length+1) return ERROR； if ( T.length ) /T非空，则重新分配空间，插入Tif(!(S.ch=(char *) ralloc(S.ch , (S.length +T.length) *sizeof(char) exit(OVERELOW) ； for(

20、i=S.length-1;i pos - 1;-i ) /插入T而腾出位置 S.chi +T.length= S.chi ；第34页，共55页。 S.chpos - 1. pos +T.length - 2= T.ch0. T.length - 1; /插入T S.length = T.length; return OK ; 第35页，共55页。堆分配存储结构表示时的（只含最小操作子集）基本操作的算法描述Status StrAssign(HString &T,char *chars) /生成一个其值等于串常量chars的串Tif(T.ch) free(T.ch); /若串T已存在,释放其所占空

21、间for ( i=0, c=chars ; c ; +i, +c );if ( ! i ) T.ch=null; T.length=0; else if( ! ( T.ch = ( char * )malloc(i*sizeof(char) exit(OVERFLOW); T.ch0.i-1=chars0.i-1; T.length=i; return OK ; 第36页，共55页。int StrLength(HString s) return s.length; int StrCmpare(HString S , HString T) for(i=0; iS.length & iT.leng

22、th; +i) if(S.chi!=T.chi ) return(S.chi T.chi); return S.lengthT.length; Status ClearString(HString &S) if(S.ch) free(S.ch); s.ch=null; S.length=0; return OK; 第37页，共55页。Status Concat(HString &T, HString S1, HString S2) / 用T返回由S1和S2联接而成的新串 if (T.ch) free(T.ch); / 释放旧空间 if (!(T.ch = (char *) malloc ( (

23、S1.length+S2.length)*sizeof(char) exit (OVERFLOW); T.ch0.S1.length-1 = S1.ch0.S1.length-1; T.length = S1.length + S2.length; T.chS1.length.T.length-1 = S2.ch0.S2.length-1; return OK; / Concat第38页，共55页。 Status SubString(HString &Sub, HString S, int pos, int len) if (pos S.length | len S.length-pos+1)

24、 return ERROR;if ( Sub.ch ) free ( Sub.ch ); / 释放旧空间 if ( ! len ) Sub.ch = NULL; Sub.length = 0; / 空子串 else / 完整子串 Sub.ch = (char *)malloc(len*sizeof(char); Sub.ch0.len-1 = Spos-1.pos+len-2; Sub.length = len; return OK; / SubString第39页，共55页。三、串的块链存储表示 可采用链表方式存储串值，每个结点可以存放一个字符，也可以存放多个字符 （如图所示）。 为便于进行

25、串的操作，当以链表存储串值时，还需增设尾指针指示链表中的最后一个结点，并给出当前串的长度，如此定义的结构就称为块链结构.描述如下：A B C DE F G HI # # #head head A B C I 第40页，共55页。#define CHUNKSIZE 80 / 可由用户定义的块大小typedef struct Chunk / 结点结构 char chCHUNKSIZE; struct Chunk *next; Chunk;typedef struct / 串的链表结构 Chunk *head, *tail; / 串的头和尾指针 int curlen; / 串的当前长度 LStrin

26、g;第41页，共55页。 在链式存储结构中，结点大小的选择直接影响着串处理的效率。在各种串的处理系统中，所要处理的串往往很长或很多。因此需考虑串的存储密度。存储密度 = 数据元素所占存储位实际分配的存储位 链式存储结构类似线性链表，由于串结构的特殊性, 要考虑每个结点是存放一个字符还是多个字符。一个字符的，插入、删除、求长度非常方便，但存储效率低。 多个字符的，改善了效率，在处理不定长的大字符串时很有效，但插入、删除不方便，可用特殊符号来填满未充分利用的结点。 第42页，共55页。 例如: 在编辑系统中，整个文本编辑区可以看成是一个串，每一行是一个子串，构成一个结点。即: 同一行的串用定长结构

27、(80个字符), 行和行之间用指针相联接。 实际应用时，可以根据问题所需来设置结点的大小。第43页，共55页。4.3串的模式匹配算法 子串位置定位操作Index( S , T , pos )通常称作串的模式匹配（其中T被称为模式串）,是各种串处理系统中最重要的操作之一。很多软件若有“编辑”菜单项的话，则其中必有“查找”子菜单项。查找即为模式匹配。第44页，共55页。INDEX (S, T, pos)初始条件：串S和T存在，T是非空串， 1posStrLength(S)。操作结果：若主串S中存在和串T值相同的 子串返回它在主串S中第pos个字符之后 第一次出现的位置; 否则函数值为0 。 回忆一

28、下串定位操作的定义:第45页，共55页。模式匹配的算法的基本思想: 从主串S的第 pos个字符起和模式串T的第一个字符比较，若相等，则逐个比较后续字符;否则从S的下一个字符起再重新和T的字符比较。依此类推,直至T中的每个字符依次和S 中一个连续的字符序列相等为止,则称匹配成功,返回与T中第一个字符相等的字符在S中的序号;否则称匹配不成功,返回零。 为此,设置主串指针i和模式串指针j指示当前两串对应位置上的 (待比较的)字符。 以下展示模式T=abcac和主串S=ababcabcacbab的匹配过程:第46页，共55页。a b a b c a b c a c b a b第一趟匹配 i=1.a b

29、 c a ca b a b c a b c a c b a b第三趟匹配 i=3.第四趟匹配 i=4.第五趟匹配 i=5.第六趟匹配 i=6.匹配成功第二趟匹配 i=2.a b a b c a b c a c b a ba b a b c a b c a c b a ba b a b c a b c a c b a ba b a b c a b c a c b a ba b c a ca b c a ca b c a ca b c a ca b c a c327411j=1.j=1.j=1.j=1.j=1.j=1.3111655T0第47页，共55页。以定长顺序结构表示串时的简单算法（不依赖于

30、其它串操作）int Index(SString S, SString T, int pos) i = pos; j = 1; while ( i S0 & j T0) /匹配成功( T0 个对应位置上的字符相同） return i-T0; /返回子串在主串中的位置 else return 0; / Index 本算法思路简单，匹配过程易于理解，通常称作朴素的匹配算法。在某些应用场合，如文本编辑，效率也较高。但当主串中存在多个与模式串“部分匹配”的子串时，就引起主串指针i的多次回溯，从而降低匹配效率。以下介绍的KMP算法就是一种改进算法，其改进在于：不需回溯i指针，而是利用已得“部分匹配”的结果将模式串尽可能远地向右“滑动”。第49页，共55页。 以模式T=abcac和主串S=ababcabcacbab的匹配过程为例简但介绍KMP算法：a b a b c a b c a c b a b第一趟匹配 i=1.a b c a c第三趟匹配 i=3.第四趟匹配 i=4.第五趟匹配 i=5.第六趟匹配 i=6.匹配成功a b a b c a b c a c b a ba b a b c a b c a c b a ba b a b c a b c a c b a ba b a b c a b c a c b a ba b c a ca b c a ca