数据结构-串结构.ppt

void get_next (SString T, int next[ ] ) { //next函数值存入数组next i=1; next[1]=0; j=0; while(iT[0] ) { if ( j= = 0||T[i]= = T[j] ) { ++i; ++j; next[i]=j; } else j=next[j]; } // while }// get_next i 1 2 3 4 5 6 7 8 模式 a b a a b c a c j=Next[i] 0 1 1 2 2 3 1 2 求解next[j] 算法的流程图: i=1; j=0 next[1]=0 iT[0] j==0 || T[i]==T[j] ++i; ++j; next[i]=j; j=next[j]; END Y Y N N 附：求解next[j] 算法流程图: 模式： a a a a b j：1 2 3 4 5 next[j]： 0 1 2 3 4 S: a a a b a a a a b T: a a a a b i: 1 2 3 4 5 6 7 8 9 a a a a b a a a a b a a a a b a a a a b ② next [ j ]是否完美无缺？ 答：未必，例如当 S=‘a b a a a a b’,T=‘a a a a b’时 ,仍有 多余动作（参见P84改进算法,称为nextval [ j ] ） 当Pj==Pnext[j]时，则 如果Si != Pj，==》 Si != Pnext[j] 因此，Si 没有必要继续与 Pnext[j]进行比较， 而应该直接和Pnext[j]的下一个字符Pnext[next[j]] 进行比较。 因此，在计算next函数时， 如果出现Pj=Pnext[j] = Pk 则next[j]=next[k]=next[next[j]] 修改算法见教材P84 算法4.8 此时效率不高的原因为： 模式串 P= ‘ abaabcac ’的 next 函数值序列为 ________ 。练习： 补充：C语言中常用的串运算 串比较，int strcmp(chars1,char s2); // StrCompare(S,T) 求串长， int strlen(char s); // StrLength(S) 串连接，char strcat(char to,char from) // Concat(T, S1, S2) 子串T定位，char strchr(char s,char c); // Index(S, T, pos) …… Concat ＝concatenation，在字符串处理中,把多个短字符串合成为长字符串的操作。 注：用C处理字符串时，要调用标准库函数 #includestring.h 数据结构课程的内容 第4章 串（String） 4.2 串的表示和实现 4.3 串的模式匹配算法 1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式 4.1 串类型的定义 记为： s =‘ a1 , a2 , …….. , an’ (n≥0 ) 串名 串值（用‘ ’ 括起来） 串中字符个数（n≥0）. n=0 时称为空串 ? 。 由一个或多个空格符组成的串。 串s中任意个连续的字符序列叫s的子串; S叫主串。 子串的第一个字符的序号。 字符在串中的序号。 串长度相等，且对应位置上字符相等。 串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。 4.1 串类型的定义 若干术语： 串长： 空白串： 子串： 子串位置： 字符位置： 串相等： 隐含结束符‘/0’ ，即ASCII码NULL 练1：串是由 字符组成的序列，一般记为 。 练2：现有以下4个字符串： a =‘BEI’ b =‘JING’ c = ‘BEIJING’ d = ‘BEI JING’ 问：① 他们各自的长度？ ② a是哪个串的子串？在主串中的位置是多少？ a =3，b =4，c