《数据结构幻灯片(部分6)》由会员分享，可在线阅读，更多相关《数据结构幻灯片(部分6)（35页珍藏版）》请在金锄头文库上搜索。
1、1,4.1 串类型的定义 一、串和基本概念 串是零个或多个字符组成的有限序列。一般记作S=a1a2a3an，S 是串名，单引号括起来的字符序列是串值；ai(1in)可以是字母、数字或其它字符；串中所包含的字符个数称为该串的长度。长度为零的串称为空串，它不包含任何字符。 通常将仅由一个或多个空格组成的串称为空白串。注意：空串和空白串的不同，例如“ ”和“”分别表示长度为1的空白串和长度为0的空串。,第四章 串,2,串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的序号（或位置）。例如:a,
2、b,c,d 四个字符串为 a=BEI , b=JING c=BEIJING , d=BEI JING 它们的长度分别为 3,4,7,8；a和b都是c和d的子串。a在c和d中的位置都是1，b在c中的位置是4,而b在d中的位置是5。 注意:单引号是为字符串区别于变量名而设,它不是字符串的内容 称两个串是相等的 当且仅当这两个串每个字符对应相等,3,二、串的抽象数据定义 串的抽象数据类型定义见书P71 ADT String 数据对象：D = ai | aiCharacteSet,i=1,2,.n, n=0 数据关系： R1= ai-1., ai| aiD, i=2,.n。 基本操作： StrAssi
3、gn( DestroyString(&S) ADT String,4,基本操作的功能说明,StrAssign(否则返回值0。,5,StrLength(S) 初始条件: 字符串S已经存在。 操作结果: 返回串S元素个数，称为串的长度。 ClearString(&S) 初始条件: 字符串S已经存在。 操作结果: 将串S清为空串。 Concat(&T,S1,S2) 初始条件: 字符串S1,S2已经存在。 操作结果: 用T返回由串S1和S2联结而成的新串。 Substring(&Sub,S,pos,len) 初始条件: 串S存在,1=pos=S的长度,0=len=S的长度-pos+1。 操作结果: 用
4、Sub返回串S的第pos个字符起长度为len的子串。,6,Index(S,T,pos) 初始条件: 串S和T存在,T是非空串，1=pos=S的长度。 操作结果: 若主串S中存在和串T相同的子串，则返回它在主串 S中第pos个字符之后第一次出现的位置；否则返回。 Replace(&S,T,V) 初始条件: 字符串S,T,V已经存在，T是非空串。 操作结果: 用V替换主串S中出现的所有与T相等的不重叠的子串。 StrInsert(&S,pos,T) 初始条件: 字符串S,T存在，1=pos=S的长度+1。 操作结果: 在串S的第pos个字符之前插入串T。 StrDelete(&S,pos,len)
5、 初始条件: 串S存在，1=pos=S的长度-len+1。 操作结果: 从串S中删除第pos个字符起长度为len的子串。 DestroyString(&S): 把存在的串S销毁。,7,上述13种基本操作中,下面5种操作构成最小操作子集: 串赋值 StrAssign; 串比较 StrCompare; 求串长 StrLength; 串联结 Concat; 求子串 Substring; 其它操作可以用其实现 例如定位函数 Index(S,T,pos) 的算法如右:,int Index(String S, String T, int pos) int i,n,m; String sub; if(pos
6、 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; / Index,8,4.2 串的表示和实现,4.2.1 定长顺序存储表示 用一组连续的存储单元存储串值的字符序列. 在C语言中,用字符“0”表示串的终结,“0”不计入串长. 另一种方法是定长数组表示一个串:,#define MAXSTRLEN 255 / 串的长度最大为255 typedef un
7、signed char SStringMAXSTRLEN+1; / 0号单元存放串的长度, 其最大值刚好是255.,当超出255个字符时,串的多余内容被舍去,叫做“截断” 以下用串联结和求子串为例介绍这种存储,9,S1,S2,T,0 maxstrlen,0 maxstrlen,S10+S20 = MAXSTRLEN 时,S1,S2,T,0 maxstrlen,0 maxstrlen,S10+S20 MAXSTRLEN 时 截断部分,10,1.串联结 Concat(&T,S1,S2)的算法,status Concat(SString / Concat,11,2.求子串SubString(&Sub
8、,S,pos,len)的算法,status SubString(SString / SubString,12,4.2.2 堆分配存储表示 也是用一组连续的存储单元存储串值的字符序列. 但存储空间是在程序执行过程中动态分配得到的. 在C语言中,用字符“0”表示串的终结,“0”不计入串长.,typedef struct char *ch; / 若是非空串,则按实际长度分配,否则为NULL; int length; / 串长度 HString;,以下用串插入操作 StrInsert(&S,pos,T)为例介绍这种存储,13,串插入StrInsert(&S,pos,T)的算法,status StrIn
9、sert(HString / StrInsert,14,Hstring串类基本操作的算法描述 Status StrAssign(HString ,15,int StrLength(HString S) / 返回S的元素个数,称为串的长度 return S.length; ,int StrCompare(HString S,HString T) / 若ST,则返回值0;若S=T,则返回值=0;若ST,则返回值0 int i; for(i=0;iS.length ,16,Status ClearString(HString ,17,Status Concat(HString ,18,Status
10、SubString(HString ,19,4.2.3 串的块链存储结构,为了提高存储密度，可使每个结点存放多个字符。通常将结点数据域存放的字符个数定义为结点的大小(比如说划分成大小为4的结点)，每一个结点有两个域：data域放4个字符，next域放下一个结点的指针。例如, s=abcdefghk,显然，当结点大小大于 1时，串的长度不一定正好是结点的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。,20,#define chunksize 80 typedef struct chunk char chchunksize; struct chunk *next; chunk,typ
11、edef struct / 串的链表结构 Chunk *head, *tail; / 串的头和尾指针 int curlen; / 串的当前长度 LString;,21,4.3 串的模式匹配算法,4.3.1求子串位置的定位函数 Index(S, T, pos) 采用定长顺序存储结构,不依赖其他串操作的匹配算法:,int Index(SString S, SString T, int pos) / T是非空串,也称为模式，1 T0) return i-T0; / 匹配成功 else return 0; / 匹配不成功 ,22,简单匹配算法（BF算法）的匹配过程示例,例：主串S=“ababcabca
12、cbab“，模式T=“abcac“,i=3，j=3失败； i回溯到2，j回溯到1,第 1 趟,a b c a c,23,例：主串S=“ababcabcacbab“，模式T=“abcac“,i=3，j=3失败； i回溯到2，j回溯到1,j,i,第 1 趟,a b c a c,简单匹配算法（BF算法）的匹配过程示例,24,例：主串S=“ababcabcacbab“，模式T=“abcac“,i=2，j=1失败 i回溯到3，j回溯到1,第 2 趟,a b c a c,简单匹配算法（BF算法）的匹配过程示例,25,例：主串S=“ababcabcacbab“，模式T=“abcac“,i=2，j=1失败 i
13、回溯到3，j回溯到1,第 2 趟,i,j,a b c a c,简单匹配算法（BF算法）的匹配过程示例,26,例：主串S=“ababcabcacbab“，模式T=“abcac“,a b c a c,i=7，j=5失败 i回溯到4，j回溯到1,第 3 趟,简单匹配算法（BF算法）的匹配过程示例,27,例：主串S=“ababcabcacbab“，模式T=“abcac“,a b c a c,i=7，j=5失败 i回溯到4，j回溯到1,第 3 趟,i,j,简单匹配算法（BF算法）的匹配过程示例,28,例：主串S=“ababcabcacbab“，模式T=“abcac“,a b c a c,i=4，j=1失
14、败 i回溯到5，j回溯到1,第 4 趟,简单匹配算法（BF算法）的匹配过程示例,29,例：主串S=“ababcabcacbab“，模式T=“abcac“,a b c a c,i=4，j=1失败 i回溯到5，j回溯到1,第 4 趟,i,j,简单匹配算法（BF算法）的匹配过程示例,30,例：主串S=“ababcabcacbab“，模式T=“abcac“,a b c a c,i=5，j=1失败 i回溯到6，j回溯到1,第 5 趟,简单匹配算法（BF算法）的匹配过程示例,31,例：主串S=“ababcabcacbab“，模式T=“abcac“,a b a b c a b c a c b a b,a b
15、 c a c,i=5，j=1失败 i回溯到6，j回溯到1,第 5 趟,i,j,简单匹配算法（BF算法）的匹配过程示例,32,例：主串S=“ababcabcacbab“，模式T=“abcac“,a b a b c a b c a c b a b,a b c a c,i=11，j=6，T中全部字符都比较完毕，匹配成功。,第 6 趟,简单匹配算法（BF算法）的匹配过程示例,33,int Index(SString S, SString T, int pos) / T是非空串,也称为模式，1 T0) return i-T0; / 匹配成功 else return 0; / 匹配不成功 ,start+; i=start; j =1;,34,BF算法的复杂度分析,设n = StrLength(S);m = StrLength(T); 设匹配成功发生在si处，则字符比较次数在前面i-1趟匹配中共比较了i-1次，第i趟成功的匹配共比较了m次，所以总共比较了i-1+m次，所有匹配成功的可能共有n-m+1种，
