串的定义及其基本运算课件

《串的定义及其基本运算课件》由会员分享，可在线阅读，更多相关《串的定义及其基本运算课件（27页珍藏版）》请在装配图网上搜索。

1、,,,,,单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,4.1 串的定义及其基本运算,,4.2 串的定长顺序存储,及,基本运算,,4.3 串的堆存储结构,第四章 串,作业6：P235（1，2）,4.1.1串,的定义,,定义：,串(,string),是由零个或多个任意字符组成的字符序列，又称为字符串(,character string)，,一般记为:,4.1 串的定义及其基本运算,s=〝a,1,a,2,a,3,…a,n,〞,说明:,,1)其中s是串名，用双引号括起来的字符序列是串的值。,,2)a,i,(1<=i<=n)可以是字母、数字或

2、其他字符；n为串中字符的个数，称为串的长度,i是序号。,,3)一个长度为零的串称为空串，表示为s =“”或,,。,,4)空格也是合法字符，空格串是字符,为空格的串。,几个术语,空串,：长度为0的字符串；,,空格串,：由空格字符组成的字符串，长度>1.,,子串,:字符串中任意个连续的字符构成的序列;,,母串,:包含该子串的字符串;,,两串相等,:两个字符串的长度相等且各对应位置上的字符都相同.,,字符的位置,：从1开始,,子串的位置,：该子串第一个字符的位置,4.1.2,串的基本运算,1. 求串的长度StrLength(s)；,,2.串赋值StrAssign(s1,s2);,,3. 两个串的连

3、接StrConcat(s1,s2,s)或StrConcat(s1,s2),,4. 求某串的子串SubStr(s,i,len)；,,5.串比较StrCmp(s1,s2)；,,6.子串定位StrIndex(s,t);,,7.插入子串StrInsert(s,i,t)；,,8. 删除子串StrDelete(s,i,len)；,,9. 置换StrRep(s,t,r)。,4.2.1存储结构的实现,#define MAXSIZE,256,,typedef struct,,{,char,data[MAXSIZE];,,,int curlen,;,,}SeqString;,4.2,串的定长顺序存储及基本运算,第

4、一种：,第二种：,#define MAXSIZE 256,,char s[MAXSIZE];,a,b,e,f,i,0,2,5,6,s.curlen,c,d,g,h,1,3,4,7,8,s.data,MAXSIZE-1,a,b,e,f,i,0,2,5,6,c,d,g,h,1,3,4,7,8,\0,9,MAXSIZE-1,第三种：,#define MAXSIZE 256,,char s[MAXSIZE+1];,a,b,e,f,i,0,2,5,6,c,d,g,h,1,3,4,7,8,9,9,MAXSIZE,4.2.2运算实现（采用第二种表示串长的方式）,1. 求串的长度StrLength(s)；,i

5、nt StrLength(char s[]),,{int len=0;,,while(s[len]!=‘\0’)len++;,,return len;,,},2.串赋值,,StrAssign(s1,s2);,void Str,Assign,(s1,s2),,char,s1[ ], s2[ ],;,,{int j=0;,,while(s2[j]!=‘\0’),,{s1[j]=s2[j];,,j++;},,s1[j]=‘\0’;,,},3. 两个串的连接StrConcat1(s1,s2,s),4. 求某串的子串SubStr(s,i,len)；,,5.串比较StrCmp(s1,s2)；,4.2.

6、3模式匹配,设,s,和,t,是给定的两个串，在主串,s,中查找子串,t,的过程称为~。其中,t,也称为,模式,。,为运算方便，字符串采用定长存储，且用第三种方式表示串长：,#define MAXSIZE 256,,char s[MAXSIZE+1];,a,b,e,f,i,0,2,5,6,c,d,g,h,1,3,4,7,8,9,9,MAXSIZE,1.简单的模式匹配算法（BF算法）,（1）算法思想：,例：,,主串S: “acabaabaabcacaabc”,,模式串t:“abaabcac”,s： a c a b a a b a a b c a c a a

7、 b c,,t： a b a a b c a c,i=1,j=1,s： a c a b a a b a a b c a c a a b c,,t： a b a a b c a c,i=2,j=2,if（s[i]==t[j]）{i++；j++；},if（s[i]！=t[j]）,,{i回溯到本趟开始的下一个；,,j回溯到1；},s： a c a b a a b a a b c a c a a b c,,t： a b a a b c a c,

8、i=2,j=1,s： a c a b a a b a a b c a c a a b c,,t： a b a a b c a c,i=3,j=1,i=4,j=2,i=5,j=3,i=6,j=4,i=7,j=5,i=8,j=6,s： a c a b a a b a a b c a c a a b c,,t： a b a a b c a c,i=4,j=1,s： a c a b a a b a a b c

9、a c a a b c,,t： a b a a b c a c,i=5,j=1,i=6,j=2,s： a c a b a a b a a b c a c a a b c,,t： a b a a b c a c,i=6,j=1,i=7,j=2,i=8,j=3,i=9,j=4,i=10,j=5,i=11,j=6,i=12,j=7,i=13,j=8,i=14,j=9,（2）算法实现,,循环条件？,,什么时候回溯？,,回溯时,i、j,如何

10、计算？,,如何判断匹配是否成功？,,匹配成功时，返回的起始位置如何计算？,见P59的算法4-4,2.改进后的模式匹配算法（KMP算法）,s： a c a b a a b a a b c a c a a b c,,t：,a b,a,a b,c a c,i=8,j=6,s： a c a b a a b a a b c a c a a b c,,t：,a b,a,a b,c a c,i=8,k=3,（1）KMP算法思想：,i不回溯，j也不是回溯到1，而是回溯到k，也就是模式t向右滑动到某个位置k。,（2）

11、k位置的确定——next函数,用next函数来确定k的值，即k=next（j）；,j,,1 2 3 4 5 6 7 8,,模式串,,a b a a b c a c,,next（j）,,,,[例4-1]求模式串“abaabcac”的next函数值,next(j)=,max{k|1<=k

12、例：主串S: “aabcbabcaabcaababc”,,模式串t:“abcaababc”,j,,1 2 3 4 5 6 7 8 9,,模式串,,a b c a a b a b c,next[j],,,0,1,1,1,2,2,3,2,3,s： a a b c b a b c a a b c a a b a b c,,t： a b c a a b a b c,i=1,j=1,i=2,j=2,s： a a b c b a b c a a b c a a b a b c,,t： a b c a a b a b c,i=2,j=1,i=3,j=

13、2,i=4,j=3,i=5,j=4,j,,1 2 3 4 5 6 7 8 9,,模式串,,a b c a a b a b c,next[j],,,0,1,1,1,2,2,3,2,3,s： a a b c b a b c a a b c a a b a b c,,t： a b c a a b a b c,i=5,j=1,s： a a b c b a b c a a b c a a b a b c,,t： a b c a a b a b c,i=6,j=1,i=7,j=2,i=8,j=3,i=9,j

14、=4,i=10,j=5,i=11,j=6,i=12,j=7,s： a a b c b a b c a a b c a a b a b c,,t： a b c a a b a b c,i=12,j=3,i=13,j=4,i=14,j=5,i=15,j=6,i=16,j=7,i=17,j=8,i=18,j=9,i=19,j=10,（3）KMP算法实现,循环条件？,,什么时候回溯？,,回溯时,i、j,如何计算？,,如何判断匹配是否成功？,,匹配成功时，返回的起始位置如何计算？,见P61的算法4-5,（4）如何求next函数,next[1]=0;,,

15、设next[i-1]=k，如何求next[i]？（令j=i）,j,,1 2 3 4 5 6 7 8 9,,模式串,,a b c a b c d b c,next[j],0,i=2,j=1,k=next[j]=0,1,next(j)=,max{k|1<=k

16、 c a b c d b c,next[j],0 1 1 1 2,3,i=6,j=5,next[i]=k+1；,,k=2,第三种情况： t[k] ≠ t[j],,j,1 2 3 4 5 6 7 8 9,模式串,a b a a b a b b a,next[j],0 1 1 2 2 3 4,i=8,j=7,3,（1）回溯k=next[k]直至t[j]==t[k],j,1 2 3 4 5 6 7 8 9,模式串,a b c a b c d b c,nex

17、t[j],0 1 1 1 2 3 4,i=8,j=7,1,（2）回溯k=next[k]直至k==0,k=4,k=2,k=4,k=1,k=0,next[i]=k+1,；,next[i]=k+1；,j,,1 2 3 4 5 6 7 8 9,,模式串,,a b c a a b a b c,next[j],,,0,i=2：,j=1，k=next [1]=0,next [i]=k+1=1,i=3：,j=2，k=next [2]=1，t[k] ≠t[j]，k回溯,,1,1,1,k=next [1]=0,,next [i]= k+1= 1,i=4：

18、,j=3，k=next [3]=1，t[k] ≠t[j]，k回溯,,k=next [1]=0,,next [4]= k+1= 1,求next[i]：,i=1,next [i]=0,i=5：,j=4，k=next [4]=1 ，t[k] =t[j],,next [i]= k+1=2,,2,i=6 ：,j=5，k=next [5]=2，t[k] ≠t[j]，k回溯,,2,3,k=next [2]=1 ，t[k] =t[j],,next [i]= k+1=2,,i=7 ：,j=6，k=next [6]=2，t[k] =t[j],,next [i]= k+1=3,,j,,1 2 3 4 5 6

19、 7 8 9,,模式串,,a b c a a b a b c,next[j],,,0,1,1,1,2,i=8：,j=7，k=next [7]=3，t[k] ≠t[j]，k回溯,,k=next [3]=1 ，t[k] =t[j],,next [i]=k+1=2,,2,i=9 ：,j=8，k=next [8]=2，t[k] =t[j],,next [i]= k+1=3,,3,算法实现：,,void GetNext(char t[],int next[]),,{int i=2,j,k;,,next[1]=0; j=i-1；k=next[j]；,,while(i

20、<=t[0]),,{if(k==0|| t[k]==t[j]),,{next[i]=k+1;i++; j=i-1；k=next[j];},,else k=next[k];,/*k回溯*/,,},理解P63算法4-6,作业：根据NEXT算法求下列模式串的next函数值（写出过程）,,AAAB,,ABRACADABRA,,ASSTACASTRA,练习：根据NEXT算法求下列模式串的next函数值（写出过程）,,AABAACAABABA,4.3 串的堆存储结构,4.3.1 串名的存储映像,,1.带串长度的索引表,typedef struct,,{char name[MAXNAME];,,i

21、nt length;,,char *stradr;,,}LNode;,2.带末尾指针的索引表,typedef struct,,{char name[MAXNAME];,,char *stradr，*enadr;,,}ENode;,3.带特征位的索引表,typedef struct,,{char name[MAXNAME];,,int tag;,,union,,{char *stradr，,,char value[4];,,}uval;,,}TNode;,4.3.2 堆存储结构,基本思想：,,在内存中开辟能存储足够多的串、地址连续的存储空间作为应用程序只所有串的可利用存储空间，称为堆空间。,,（未分配区域）,,,（已分配区域）,,char store[SMAX+1];,,int free;,,typedef struct,,{int length;,,int stradr;,,}Hstring;,,