《串的定义及其基本运算》由会员分享，可在线阅读，更多相关《串的定义及其基本运算（27页珍藏版）》请在金锄头文库上搜索。
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; SeqStr
3、ing;4.2串的定长顺序存储及基本运算第一种：第二种：#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+; retu
4、rn len; 2.串赋值StrAssign(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; abefi0256
5、cdgh1347899MAXSIZE1.简单的模式匹配算法（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
6、b a a b c a ci=2j=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=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=6
7、j=1i=7j=2i=8j=3i=9j=4i=10j=5i=11j=6i=12j=7i=13j=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，
8、也就是模式t向右滑动到某个位置k。（2）k位置的确定next函数用next函数来确定k的值，即k=next（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
9、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=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
10、 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 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如何计算？如何判断匹配是否成功？匹配
11、成功时，返回的起始位置如何计算？见P61的算法4-5（4）如何求next函数next1=0;设nexti-1=k，如何求nexti？（令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第三
12、种情况： 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=8j=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=n
13、ext 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=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 cn
14、extj 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，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函数值（写出过
15、程） AAAB ABRACADABRA ASSTACASTRA 练习：根据NEXT算法求下列模式串的next函数值（写出过程） AABAACAABABA 4.3 串的堆存储结构4.3.1 串名的存储映像 1.带串长度的索引表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;
