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

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,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=i1.,子串,:字符串中任意个连续的字符构成的序列;,母串,:包含该子串的字符串;,两串相等,:两个字符串的长度相等且各对应位置上的字符都相同.,字符的位置,：从1开始,子串的位置,：该子串第一个字符的位置,4.1.2,串的基本运算,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. 删除子串StrDelete(s,i,len)；,9. 置换StrRep(s,t,r)。,4.2.1存储结构的实现,#define MAXSIZE,256,typedef struct,char,dataMAXSIZE;,int curlen,;,SeqString;,4.2,串的定长顺序存储及基本运算,第一种：,第二种：,#define MAXSIZE 256,char sMAXSIZE;,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 sMAXSIZE+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)；,int StrLength(char s),int len=0;,while(slen!=0)len+;,return len;,2.串赋值,StrAssign(s1,s2);,void Str,Assign,(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 256,char sMAXSIZE+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 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（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,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 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,如何计算？,如何判断匹配是否成功？,匹配成功时，返回的起始位置如何计算？,见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）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)=,maxk|1=kj且”t,1,t,2,t,k-1,”=”t,j-k+1,t,j-k+2,t,j-1,”,1 其他情况,0 j=1,0,1,1,2,2,3,1,2,练习：求下列模式串的next函数值,AAAB,AABAACAABABA,ABRACADABRA,ASSTACASTRA,例：主串S: “aabcbabcaabcaababc”,模式串t:“abcaababc”,j,1 2 3 4 5 6 7 8 9,模式串,a b c a a b a b c,nextj,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=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,nextj,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=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函数,next1=0;,设nexti-1=k，如何求nexti？（令j=i）,j,1 2 3 4 5 6 7 8 9,模式串,a b c a b c d b c,nextj,0,i=2,j=1,k=nextj=0,1,next(j)=,maxk|1=kj且”t,1,t,2,t,k-1,”=”t,j-k+1,t,j-k+2,t,j-1,”,1 其他情况,0 j=1,第一种情况：k =0,nexti=k+1；,第二种情况: tk=tj,j,1 2 3 4 5 6 7 8 9,模式串,a b c a b c d b c,nextj,0 1 1 1 2,3,i=6,j=5,nexti=k+1；,k=2,第三种情况： tk tj,j,1 2 3 4 5 6 7 8 9,模式串,a b a a b a b b a,nextj,0 1 1 2 2 3 4,i=8,j=7,3,（1）回溯k=nextk直至tj=tk,j,1 2 3 4 5 6 7 8 9,模式串,a b c a b c d b c,nextj,0 1 1 1 2 3 4,i=8,j=7,1,（2）回溯k=nextk直至k=0,k=4,k=2,k=4,k=1,k=0,nexti=k+1,；,nexti=k+1；,j,1 2 3 4 5 6 7 8 9,模式串,a b c a a b a b c,nextj,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,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,j,1 2 3 4 5 6 7 8 9,模式串,a b c a a b a b c,nextj,0,1,1,1,2,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),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.带串长度的索引表,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 struct,int length;,int stradr;,Hstring;,