第四章串4.1串的定义及基本运算4.1串的定义及基本运算2.串的基本运算:串赋值StrAssign(&T,chars)初始条件:chars是字符串常量。操作结果:生成一个值等于chars的串T。串比较StrCompare(S,T)初始条件:串S和T存在。操作结果:若S>T,则返回值>0;如S=T,则返回值=0;若S<T,则返回值<0。求串长StrLength(S)初始条件:串S存在。操作结果:返回串S的长度,即串S中的元素个数。串联接Concat(&T,S1,S2)初始条件:串S1和S2存在。操作结果:将T返回由S1和S2联接而成的新串。求子串SubString(&Sub,S,pos,len)初始条件:串S存在,1≤pos≤StrLength(S)且1≤len≤StrLength(S)-pos+1。操作结果:用Sub返回串S的第pos个字符起长度为len的子串。定位函数intIndex(StringS,StringT,intpos)//T为非空串。若主串S中第pos个字符之后存在与T相等的子//串，则返回第一个这样的子串在S中的位置，否则返回0。{if(pos>0){n=StrLength(S);m=StrLength(T);i=pos;while(i<=n-m+1){SubString(sub,S,i,m);if(StrCompare(sub,T)!=0)++i;elsereturni;}}return0;}4.2串的表示和实现4.2串的表示和实现4.2串的表示和实现4.2串的表示和实现4.2串的表示和实现4.2串的表示和实现4.2串的表示和实现4.2串的表示和实现＃defineCHUNKSIZE<大小>typedefstructChunk{charch[CHUNKSIZE];structChunk*next;}Chunk;存储密度大，一些操作（如插入，删除）有所不便，引起大量字符移动，适合于在串基本保持静态使用方式时采用；存储密度小，运算处理方便，但存储空间量大，若处理过程中，需大量内外存交换，回影响总效率；串的字符集的大小，也会影响串值存储方式的选取。总结（1）空串与空格串是不相同的，空串的长度为0，空格串的长度为包含的空格个数。（2）串是有限个字符的序列，是一种取值范围受限的特殊的线性表。练习：以串的堆分配存储表示作为串的类型描述。设计一个非递归算法求一个串的逆串。0~S.length/2-1;(S.length+1)/2~S.length-1voidReverse(HString&S){for(i=0;i<S.length/2;i++){temp=S.ch[i];S.ch[i]=S.ch[S.length-i-1];S.ch[S.length-i-1]=temp;}}2.用递归算法实现串的逆串，要求不另设串存储空间。voidReverse(HString&S,inti){if(i>=S.length/2)return;else{temp=S.ch[i];S.ch[i]=S.ch[S.length-i-1];S.ch[S.length-i-1]=temp;Reverse(S,i+1);}}4.3串的模式匹配4.3串的模式匹配4.3串的模式匹配4.3串的模式匹配4.3串的模式匹配4.3串的模式匹配4.3串的模式匹配4.3串的模式匹配4.3串的模式匹配4.3串的模式匹配4.3串的模式匹配4.3串的模式匹配4.3串的模式匹配4.3串的模式匹配4.3串的模式匹配4.3串的模式匹配4.3串的模式匹配4.3串的模式匹配4.3串的模式匹配4.3串的模式匹配4.3串的模式匹配4.3串的模式匹配4.3串的模式匹配4.3串的模式匹配p1p2…pj-k+1…pj-1pjpj+1next[j]=k‖‖≠p1…pk-1pkpk+1next[k]=k’p1……pk’pk’+1next[k’]=k”p1…pk’’pk’’+1next[k’’’]=k’’’4.3串的模式匹配KMP算法的时间复杂度设主串s的长度为n,模式串t长度为m,在KMP算法中求next数组的时间复杂度为O(m),在后面的匹配中因主串s的下标不减即不回溯,比较次数可记为n,所以KMP算法总的时间复杂度为O(n+m)。4.3串的模式匹配4.3串的模式匹配next函数的改进4.3串的模式匹配j1234567891011121314151617模式串abcaabbcabcaabdabnext[j]01112231123456712本章小结