4数据结构——串.ppt

第4章 串 4.1 串类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.1 串类型的定义 串是由零个或多个字符组成的有限序列 ，记作 S = ‘a1a2a3…an’ (n≥0) 其中，S是串名字，‘a1a2a3…an’是串值 ai是串中字符，n是串的长度，表示串中字符 的数目。 空串：零个字符的串称为空串 记作 “?” 子串：串中任意个连续的字符组成的子序列 主串：包含子串的串 字符在串中的位置：字符在序列中的序号 子串在串中的位置：子串的第一个字符在主串中的位置 两个串相等：两个串的长度相等，并且各个对应的字符也都相同。 例如，有下列四个串a，b，c，d： a= ‘program’ b= ‘Program’ c= ‘pro’ d= ‘program ’ 空格串： 由一个或多个空格组成的串 串的表示：用一对单引号括起来 串的操作：以“串的整体”为操作对象 Status StrAssign(HString T, char *chars){//生成一个值等于chars的串T if (T.ch) free (T.ch) ; //释放T原有空间 for (i=0,c=chars; c ; ++i, ++c);//求chars长度i if (! i ) {T.ch=NULL; T.length=0;} else { if (!(T.ch=(char *)malloc(i * sizeof(char)))) exit (OVERFLOW); T.ch[0..i-1]=chars[0..i-1]; T.length=i; } return OK; } //StrAssign int StrLength ( HString S )  { //求S串的长度 return S.length; } // StrLength int StrCompare (HString S, HString T ) { //比较两个串，若ST,则返回值0； //若S=T,则返回值=0； // 若S＜T,则返回值＜0； for (i=0;iS.length iT.length; ++i) if (S.ch[i] != T.ch[i]) return S.ch[i]-T.ch[i]; return S.length-T.length ; } // StrCompare Status ClearString ( HString S ){// 将S清为空串 if ( S.ch ) { free ( S.ch ) ; S.ch=NULL; } S.length=0; return OK; } // ClearString Status SubString(HString Sub,HString S,int pos,int len) { //用Sub返回串S的第pos个字符开始长度为len的子串 if (pos1 || posS.length || len0 ||lenS.length-pos+1) return ERROR; if (Sub.ch) free(Sub.ch); if (!len) { Sub.ch=NULL; Sub.length=0;} else { Sub.ch=(char *)malloc(len*sizeof(char)); Sub.ch[0..len-1]=S.ch[pos-1..pos+len-2]; Sub.length=len; } return OK; } // SubString 由于串结构中每个数据元素为一个字符，所以最直接的链式存储结构是每个结点的数据域存放一个字符。举例： 由于串中的字符个数不一定是每个结点存放字符个数的整倍数，所以，需要在最后一个结点的空缺位置上填充特殊的字符。 这种存储形式优点是存储密度高于结点大小为1 的存储形式；不足之处是做插入、删除字符的操作时，可能会引起结点之间字符的移动，算法实现起来比较复杂。 4.3 串的模式匹配算法 定义 在串中寻找子串（第一个字 符）在串中的位置 词汇 在模式匹配中，子串称为模 式，串称为目标。 示例 目标 S : “Beijing” 模式 P : “jin” 匹配结果 = 4 4.3.1