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

1、4.1 串的定义及其基本运算4.2 串的定长顺序存储及基本运算4.3 串的堆存储结构第四章 串作业6：P235（1，2）4.1.1串的定义v定义：串(string)是由零个或多个任意字符组成的字符序列，又称为字符串(character string)，一般记为:4.1 串的定义及其基本运算s=a1 a2 a3an说明:1)其中s是串名，用双引号括起来的字符序列是串的值。2)ai(1=i1.子串:字符串中任意个连续的字符构成的序列;母串:包含该子串的字符串;两串相等:两个字符串的长度相等且各对应位置上的字符都相同.字符的位置：从1开始子串的位置：该子串第一个字符的位置4.1.2 串的基本运算1.

2、求串的长度StrLength(s)；2.串赋值StrAssign(s1,s2);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 256typedef struct char dataMAXSIZE;int curlen;SeqString;4.2串

3、的定长顺序存储及基本运算第一种：第二种：#define MAXSIZE 256char sMAXSIZE;abefi0256s.curlencdgh13478s.dataMAXSIZE-1abefi0256cdgh1347809MAXSIZE-1第三种：#define MAXSIZE 256char sMAXSIZE+1;abefi0256cdgh1347899MAXSIZE4.2.2运算实现（采用第二种表示串长的方式）1.求串的长度StrLength(s)；int StrLength(char s)int len=0;while(slen!=0)len+;return len;2.串赋值St

4、rAssign(s1,s2);void StrAssign(s1,s2)char s1,s2 ;int j=0;while(s2j!=0)s1j=s2j;j+;s1j=0;3.两个串的连接StrConcat1(s1,s2,s)4.求某串的子串SubStr(s,i,len)；5.串比较StrCmp(s1,s2)；4.2.3模式匹配设s和t是给定的两个串，在主串s中查找子串t的过程称为。其中t也称为模式。为运算方便，字符串采用定长存储，且用第三种方式表示串长：#define MAXSIZE 256char sMAXSIZE+1;abefi0256cdgh1347899MAXSIZE1.简单的模式匹

5、配算法（BF算法）（1）算法思想：例：主串S:“acabaabaabcacaabc”模式串t:“abaabcac”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=1j=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 ci=2j=2if（si=tj）i+；j+；if（si！=tj）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 ci=2j=1 s：a c a b a a b a a

6、 b c a c a a b c t：a b a a b c a ci=3j=1i=4j=2i=5j=3i=6j=4i=7j=5i=8j=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 ci=4j=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 ci=5j=1i=6j=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 ci=6j=1i=7j=2i=8j=3i=9j=4i=10j=5i=11j=6i=12j=7i=13j

7、=8i=14j=9（2）算法实现循环条件？什么时候回溯？回溯时i、j如何计算？如何判断匹配是否成功？匹配成功时，返回的起始位置如何计算？见P59的算法4-42.改进后的模式匹配算法（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 ci=8j=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 ci=8k=3（1）KMP算法思想：i不回溯，j也不是回溯到1，而是回溯到k，也就是模式t向右滑动到某个位置k。（2）k位置的确定next函数用next函数来确定k的值，即k=nex

8、t（j）；j1 2 3 4 5 6 7 8模式串a b a a b c a cnext（j）例4-1求模式串“abaabcac”的next函数值 next(j)=maxk|1=kj且”t1t2tk-1”=”tj-k+1tj-k+2tj-1”1 其他情况0 j=101122312 练习：求下列模式串的next函数值 AAAB AABAACAABABA ABRACADABRA ASSTACASTRA 例：主串S:“aabcbabcaabcaababc”模式串t:“abcaababc”j1 2 3 4 5 6 7 8 9模式串a b c a a b a b cnextj 0 11122323 s：a

9、 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=1j=1i=2j=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=2j=1i=3j=2i=4j=3i=5j=4j1 2 3 4 5 6 7 8 9模式串a b c a a b a b cnextj 0 11122323 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=5j=1 s：a a b c b a b c a a b c a a

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

11、？（令j=i）j1 2 3 4 5 6 7 8 9模式串a b c a b c d b cnextj0 i=2j=1k=nextj=01next(j)=maxk|1=kj且”t1t2tk-1”=”tj-k+1tj-k+2tj-1”1 其他情况0 j=1第一种情况：k=0nexti=k+1；第二种情况:tk=tjj1 2 3 4 5 6 7 8 9模式串a b c a b c d b cnextj0 1 1 1 23i=6j=5nexti=k+1；k=2第三种情况：tk tj j1 2 3 4 5 6 7 8 9模式串a b a a b a b b a nextj0 1 1 2 2 3 4i=8

12、j=73（1）回溯k=nextk直至tj=tkj1 2 3 4 5 6 7 8 9模式串a b c a b c d b cnextj0 1 1 1 2 3 4i=8j=71（2）回溯k=nextk直至k=0 k=4k=2k=4k=1k=0 nexti=k+1；nexti=k+1；j1 2 3 4 5 6 7 8 9模式串a b c a a b a b cnextj 0 i=2：j=1，k=next 1=0next i=k+1=1 i=3：j=2，k=next 2=1，tk tj，k回溯111k=next 1=0next i=k+1=1 i=4：j=3，k=next 3=1，tk tj，k回溯k

13、=next 1=0next 4=k+1=1求nexti：i=1next i=0i=5：j=4，k=next 4=1，tk=tjnext i=k+1=2 2 i=6：j=5，k=next 5=2，tk tj，k回溯23k=next 2=1，tk=tjnext i=k+1=2 i=7：j=6，k=next 6=2，tk=tjnext i=k+1=3 j1 2 3 4 5 6 7 8 9模式串a b c a a b a b cnextj 01112i=8：j=7，k=next 7=3，tk tj，k回溯k=next 3=1，tk=tjnext i=k+1=2 2i=9：j=8，k=next 8=2，

14、tk=tjnext i=k+1=3 3算法实现：void GetNext(char t,int next)int i=2,j,k;next1=0;j=i-1；k=nextj；while(i=t0)if(k=0|tk=tj)nexti=k+1;i+;j=i-1；k=nextj;else k=nextk;/*k回溯*/理解P63算法4-6 作业：根据NEXT算法求下列模式串的next函数值（写出过程）AAAB ABRACADABRA ASSTACASTRA 练习：根据NEXT算法求下列模式串的next函数值（写出过程）AABAACAABABA 4.3 串的堆存储结构4.3.1 串名的存储映像 1.

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