CH4串11-03-28.ppt

1、第四章 串,4.1 串的类型定义,4.2 串的表示和实现,4.3 串的模式匹配算法,作业,串(String)是零个或多个字符组成的有限序列。一般记作 S= a1a2a3an，其中 S 是串名，单引号括起来的字符序列是串值；ai(1in) 可以是字母、数字或其它字符；串中所包含的字符个数称为该串的长度。长度为零的串称为 空串(Empty String)，不包含任何字符。,4.1 串类型的定义 一、串的基本概念,注意：空串和空格串不同，如 和分别表示长度为1的空格串和长度为0的空串（）。,特别地， 空串是任意串的子串，任意串是其自身的子串。,串中任意个连续字符组成的子序列称为该串的子串，包含子串的

2、串相应地称为主串。通常将子串在主串中首次 出现时，该子串的首字符在主串中对应的序号，定义为 子串在主串中的位置（或序号）。,例如：A = This is a string ，B = is 则 B 是 A 的子串，A 为主串。B 在 A 中出现了两次，其中首次出现所对应的主串位置是 3 。因此，B 在 A 中的位置为 3 。,二、串的抽象数据类型定义如下：,ADT String ,数据对象：,D ai |aiCharacterSet, i=1,2,.,n, n0 ,数据关系：,R1 | ai-1, ai D, i=2,.,n ,基本操作：,StrAssign (,SubString( sub,

3、commander , 1, 9),求得 sub = commander,SubString(sub, commander, 4, 7) sub = ?,SubString(sub, beijing, 7, 2) = ? sub = ?,SubString(student, 5, 0) = ,起始位置和子串长度之间存在约束关系,长度为 0 的子串为“合法”串,1posStrLength(S) ，0lenStrLength(S)-pos+1。,Index (S, T, pos)初始条件：串S和T存在，T是非空串， 1posStrLength(S)。操作结果： 若主串 S 中存在和串 T 值相同

4、的子串, 则返回它在主串 S 中 第pos个字符之后第一次出现 的位置;否则函数值为0。,假设 S = abcaabcaaabc , T = bca,Index(S, T, 1) = 2;,Index(S, T, 3) =？;,Index(S, T, 8) =？;,“子串在主串中的位置”意指子串 中的第一个字符在主串中的位序。,6,0,bca,bca,Replace ( / S中不存在与T相等的子串 / Index,n = StrLength(S); m = StrLength(T); i = pos;,while ( i = n-m+1) / while,SubString (sub, S,

5、 i, m); if (StrCompare(sub,T) != 0) +i ; else return i ;,又如串的置换函数Replace ( / 剩余串 Concat( S, news, sub );,n=StrLength(S); m=StrLength(T); pos = 1; StrAssign(news, NullStr); i=1;,作业,串的逻辑结构和线性表极为相似，区别 仅在于串的数据对象约束为字符集。,串的基本操作和线性表有很大差别。 在线性表的基本操作中，大多以“单个元素”作为操作对象； 在串的基本操作中，通常以“串的整体”作为操作对象。,在程序设计语言中，若串只是

6、作为输入或输出的常量出现，则只 需存储此串的串值，即字符序列即 可。但在多数非数值处理的程序中， 串也以变量的形式出现。,4.2 串的表示和实现,串有三种机内表示方法：,一、串的定长顺序存储表示,二、串的堆分配存储表示,三、串的块链存储表示,#define MAXSTRLEN 255 / 用户可在255以内定义最大串长 typedef unsigned char SString MAXSTRLEN + 1; / 0号单元存放串的长度,一、串的定长顺序存储表示,用一组地址连续的存储单元存储串值的字符序列。,按这种串的表示方法实现的串的运算时，其基本操作为 “字符序列的复制”。,串的实际长度可在这

7、个予定义长度的范围内随意设定，超过予定义长度的串值则被舍去，称之为“截断” 。,特点:,Status Concat(SString S1, SString S2, SString / Concat,例1.串的联接算法中需分三种情况处理：,T1.S10 = S11.S10; TS10+1.S10+S20 = S21.S20; T0 = S10+S20; uncut = TRUE; ,if (S10+S20 = MAXSTRLEN) / 未截断,else if (S10 MAXSTRLEN) / s2截断,s1未截断,else / s1截断(仅取S1),T1.S10 = S11.S10; TS10

8、+1.MAXSTRLEN = S21.MAXSTRLENS10; T0 = MAXSTRLEN; uncut = FALSE; ,T1.MAXSTRLEN = S11.MAXSTRLEN; T0 = MAXSTRLEN uncut = FALSE; ,Status SubString(SString / 若是非空串，则按串实际长度分配 /存储区，否则 ch 为NULL int length; / 串长，为操作方便约定串长 HString; 也是存储结构的一部分,这类串操作实现的算法为: 先为新生成的串分配一个存储空间，然后 进行串值的复制。,Status Concat(HString / Co

9、ncat,Status SubString(HString / SubString, ,Sub.ch =(char*)malloc(len*sizeof(char) Sub.ch0.len-1 = S.chpos-1.pos+len-2; Sub.length = len;,三、串的块链存储表示,可用链表来存储串值，由于串的每个数据元素是一个字符，因此用链表存储时，存在一个结点大小的问题。通常一个结点中存放的不是一个字符，而是一个子串。,为了提高存储密度，可使每个结点存放多个字符。通常将结点数据域存放的字符个数定义为结点的大小，显然，当结点大小大于 1时，串的长度不一定正好是结点的整数倍，因此

10、要用特殊字符(如#) ，来填充最后一个结点，以表示串的结束。,/串的块链存储表示 #define CHUNKSIZE 80 / 可由用户定义的块大小 typedef struct Chunk / 结点结构 char chCHUNKSIZE; struct Chunk *next; Chunk; typedef struct / 串的链表结构 Chunk *head, *tail; / 串的头和尾指针 int curlen; / 串的当前长度 LString;,例如: 在编辑系统中，整个文本编辑区可以看成是一个串，每一行是一个子串，构成一个结点。即: 同一行的串用定长结构(80个字符), 行和行

11、之间用指针相联接。,实际应用时，可以根据问题所需来设置结点的大小。,这是串的一种重要操作，很多 软件，若有“编辑”菜单项的话， 则其中必有“查找”子菜单项。,4.3串的模式匹配算法,初始条件：串 S 和 T 存在，T 是非空串， 1posStrLength(S)。,首先，回忆一下查找(串匹配)操作的定义:,INDEX (S, T, pos),操作结果：若主串 S 中存在和串 T 值 相同的子串,则返回它在主串 S 中 第 pos 个字符之后第一次出现 的位置; 否则函数值为0。,int Index (String S, String T, int pos) / T为非空串。若主串S中第pos个

12、字符之后存在与 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 (StrCompare(sub,T) != 0) +i ; else return i ; / while / if return 0; / S中不存在与T相等的子串 / Index,下面讨论以定长顺序结构 表示串时的几种算法。,一、简单算法（蛮力算法）,三、KMP算法（D.E

13、.Knuth, J.H.Morris , V.R.Pratt ）,二、首尾匹配算法,S 串,T 串,T 串,i,pos,S 串,T 串,T 串,i,j,jm (j=m+1),T 串,一、简单算法,j=1,i=i-j+2,返回？,匹配不成功！,:(i-m),T 串,int Index(SString S, SString T, int pos) / 返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0。 / 其中，T非空，1posStrLength(S)。 i = pos; j = 1; while (i T0) return i-T0; else return 0; / Ind

14、ex,先比较模式串的第一个字符， 再比较模式串的最后一个字符， 最后比较模式串中从第二个 到第 n-1 个字符。,二、首尾匹配算法,int Index_FL(SString S, SString T, int pos) sLength = S0; tLength = T0; i = pos; patStartChar = T1; patEndChar = TtLength; while (i = sLength tLength + 1) if (Si != patStartChar) +i; /重新查找匹配起始点 else if (Si+tLength-1 != patEndChar) +i;

15、 / 模式串的“尾字符”不匹配 else return 0; ,检查中间字符的匹配情况,k = 1; j = 2; while ( j tLength / 重新开始下一次的匹配检测,KMP算法的时间复杂度可以达到O(m+n),三、KMP(D.E.Knuth, J.H.Morris, V.R.Pratt) 算法,每当一趟匹配过程中出现字符比较不等时，不需回溯 i 指针，而是利用已经得到的“部分匹配”的结果将模式串向右“滑动”尽可能远的一段距离后，继续进行比较。,当 Si Tj 时， 已经得到的结果: Si-j+1.i-1 =T1.j-1 若已知 T1.k-1 =Tj-k+1.j-1 则有 Si-

16、k+1.i-1 =T1.k-1,k j,主串：S1 Sn,子串：P1 Pm,i,i,j,j,定义：模式串的next函数,0,1,1,2,2,3,1,2,int Index_KMP(SString S, SString T, int pos) / 已知next函数的KMP算法， 1posStrLength(S) i = pos; j = 1; while (i T0) return i-T0; / 匹配成功 else return 0; / Index_KMP,这实际上也是一个匹配的过程， 不同在于：主串和模式串是同一个串。,求 next 函数值的过程是一个递推过程， 分析如下:,已知：next

17、1 = 0；,(1)若： Tj = Tk ,则： nextj+1 = k+1,(2)若： Tj Tk , 则 需往前回溯,假设：nextj = k;,nextk,?,0,1,1,2,2,3,1,?,如何求next6?,当前j=5,next5=2, 考察 p5 与 p2 ：,如何求next7?,当前j=6,next6=3, 考察 p6 与 p3 ： 考察 p6 与 p1 ：,p5 = p2 ，所以next6=next5+1，,p6 p3 ，next3=1，继续,p6 p1 ，next1=0，则:,next7=1，从头开始比较。,void get_next(SString / get_next,还有一种特殊情况需要考虑： 例如： S = aaabaaabaaabaaabaaab T = aaaab nextj= 01234,nextvalj= 00004 (调整后的next值),若 pj = pnextj,则 Nextj= NextN