《串的定义及其基本运算.ppt》由会员分享，可在线阅读，更多相关《串的定义及其基本运算.ppt（27页珍藏版）》请在三一办公上搜索。
1、4.1 串的定义及其基本运算4.2 串的定长顺序存储及基本运算4.3 串的堆存储结构,第四章 串,作业6：P235（1，2）,4.1.1串的定义定义：串(string)是由零个或多个任意字符组成的字符序列，又称为字符串(character string)，一般记为:,4.1 串的定义及其基本运算,s=a1 a2 a3an,说明:1)其中s是串名，用双引号括起来的字符序列是串的值。2)ai(1=i=n)可以是字母、数字或其他字符；n为串中字符的个数，称为串的长度,i是序号。3)一个长度为零的串称为空串，表示为s=“”或。4)空格也是合法字符，空格串是字符,为空格的串。,几个术语,空串：长度为0的
2、字符串；空格串：由空格字符组成的字符串，长度1.子串:字符串中任意个连续的字符构成的序列;母串:包含该子串的字符串;两串相等:两个字符串的长度相等且各对应位置上的字符都相同.字符的位置：从1开始子串的位置：该子串第一个字符的位置,串的基本运算,1.求串的长度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.删除子串S
3、trDelete(s,i,len)；9.置换StrRep(s,t,r)。,4.2.1存储结构的实现,#define MAXSIZE 256typedef struct char dataMAXSIZE;int curlen;SeqString;,4.2串的定长顺序存储及基本运算,第一种：,第二种：,#define MAXSIZE 256char sMAXSIZE;,第三种：,#define MAXSIZE 256char sMAXSIZE+1;,4.2.2运算实现（采用第二种表示串长的方式）,1.求串的长度StrLength(s)；,int StrLength(char s)int len=0
4、;while(slen!=0)len+;return 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 s
5、MAXSIZE+1;,1.简单的模式匹配算法（BF算法）,（1）算法思想：,例：主串S:“acabaabaabcacaabc”模式串t:“abaabcac”,if（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 c,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,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,（2）算法实现循环条件？什
6、么时候回溯？回溯时i、j如何计算？如何判断匹配是否成功？匹配成功时，返回的起始位置如何计算？,见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,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,（1）KMP算法思想：,i不回溯，j也不是回溯到1，而是回溯到k，也就是模式t向右滑动到某个位置k。,（2）k位置的确定next函数,用next函数来确定k的值，即k=next（j）；,例4-1求模式串“abaabcac”的ne
7、xt函数值,0,1,1,2,2,3,1,2,练习：求下列模式串的next函数值 AAAB AABAACAABABA ABRACADABRA ASSTACASTRA,例：主串S:“aabcbabcaabcaababc”模式串t:“abcaababc”,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,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,s：a a b c b a b c a a b c a a b a b c t：a
8、 b c a a b a b c,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,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,（3）KMP算法实现,循环条件？什么时候回溯？回溯时i、j如何计算？如何判断匹配是否成功？匹配成功时，返回的起始位置如何计算？,见P61的算法4-5,（4）如何求next函数,next1=0;设nexti-1=k，如何求nexti？（令j=i）,k=nextj=0,1,第一种情况：k=0,nexti=k+1；,第二种情况:tk=tj
9、,3,nexti=k+1；,第三种情况：tk tj,3,（1）回溯k=nextk直至tj=tk,1,（2）回溯k=nextk直至k=0,nexti=k+1；,nexti=k+1；,0,i=2：,j=1，k=next 1=0,next i=k+1=1,i=3：,j=2，k=next 2=1，tk tj，k回溯,1,1,1,k=next 1=0,next i=k+1=1,i=4：,j=3，k=next 3=1，tk tj，k回溯,k=next 1=0,next 4=k+1=1,求nexti：,i=1,next i=0,i=5：,j=4，k=next 4=1，tk=tj,next i=k+1=2,2
10、,i=6：,j=5，k=next 5=2，tk tj，k回溯,2,3,k=next 2=1，tk=tj,next i=k+1=2,i=7：,j=6，k=next 6=2，tk=tj,next i=k+1=3,i=8：,j=7，k=next 7=3，tk tj，k回溯,k=next 3=1，tk=tj,next i=k+1=2,2,i=9：,j=8，k=next 8=2，tk=tj,next 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)n
11、exti=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.带串长度的索引表,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 堆存储结构,基本思想：在内存中开辟能存储足够多的串、地址连续的存储空间作为应用程序只所有串的可利用存储空间，称为堆空间。,char storeSMAX+1;int free;typedef structint length;int stradr;Hstring;,
