第4章 串-29-1

null第4章 串张成文 北京邮电大学计算机学院第4章 串4.1 串类型的概念数据结构---第4章 串*4.1 串类型的概念 串（字符串）：是由零个或多个字符组成的有限序列。 记作：s = ‘a1a2…an’ (n0) 串长：串中字符的个数n。 子串和主串：串中任意个连续的字符组成的子序列称 为该串的子串。包含子串的串称为主串。 串相等：两个串长度相等，且对应位置的字符都相等。 空串和空白串：空串不包含任何字符,表示为 ； 空白串由一个或多个空格组成，如‘ ’。串的常用基本操作串的常用基本操作 (1)用串常量赋值 StrAssign(&T, chars) 用串变量赋值 StrCopy(&T, S) (2)判定空串 StrEmpty(S) (3)两串比较 StrCompare(S, T) (4)求串长 StrLength(S) (5)串清空 ClearString(&S) (6)两串连接 Concat(&T, S1, S2) (7)求子串 SubString(&Sub, S, pos, len) (8)子串定位 Index(S, T, pos) (9)置换 Replace(&S, T, V) (10)插入 StrInsert(&S, pos, T) (11)删除 StrDelete(&S, pos, len) (12)串销毁 DestroyString(&S)串类型的最小操作子集null数据结构---第4章 串*4.2 串的存储结构（1）定长顺序存储表示7 s t u d e n t0 1 2 3 4 5 6 7 8MAXSTRLEN#define MAXSTRLEN 255 //予定义最大串长 typedef unsigned char SString[MAXSTRLEN+1];存放串的长度[存储定义]null数据结构---第4章 串*[基本操作实现示例]约定：串值长度上溢时，用“截尾法”处理， 即 “截断”超过予定义长度的部分。int StrCompare(SString S, SString T) //S>T,返回值>0；S=T，返回0；SS[0] || len<0 || len > S[0]-pos+1 ) return ERROR; Sub[1..len]= S[pos..pos+len-1]; Sub[0]= len return OK; } // SubStringnull数据结构---第4章 串*（2）堆分配存储表示动态分配串值存储空间，避免定长结构的截断现象。typedef struct { char *ch; //串空间基址，按串长申请 int length; //串长度 }HString;[存储定义]null数据结构---第4章 串*[基本操作实现示例]int StrCompare(HString S, HString T) //S>T,返回值>0；S=T，返回0；SS.length || len<0 || len > S.length-pos+1 ) return ERROR; if (Sub.ch) free(Sub.ch); if ( !len ) { Sub.ch=NULL; Sub.length=0; } else { if ( !(Sub.ch=(char *)malloc(len* sizeof(char)))) exit(OVERFLOW); Sub.ch[0..len-1]=S.ch[pos-1..pos+len-2]; Sub.length=len; } return OK; } // SubString4.3 串的模式匹配算法4.3 串的模式匹配算法定义 在主串中寻找子串（第一个字符）在主串中的位置 词汇 在模式匹配中，子串称为模式，主串称为目标。 示例 目标 S : “Beijing” 模式 P : “jin” 匹配结果 = 4 操作结果：若主串S中存在和串P值相同的子 串,返回它在主串S中第一次出现的位置;否则函数值为0。 以定长顺序存储结构讨论算法实现。串的模式匹配算法串的模式匹配算法1). 穷举模式匹配 2). 模式匹配的一种改进算法(KMP算法)1).穷举模式匹配算法思想 主串S，子串P; 将S中的第一个字符与P中的第一个字符进行比较； 若不同，就将S中的第二个字符与P中的第一个字符进行比较...，直到S的某一个字符和P的第一个字符相同，将它们之后的字符进行比较 若相同，将它们之后的字符进行比较 当S的某一个字符Si与P的字符Pj不同时，则S,P回退，即:将S中的第i-j+2个和P的第一个字进行比较，重复上述过程1).穷举模式匹配null数据结构---第4章 串*主串S子串P1 posn(S[0])m(P[0])i=pos; j=1;1失配null缺点 重复回溯太多 时间复杂度 最坏：为 O(m*n)，其中m和 n 分别为 S 串和 P 串的长度 最好：O(n)nullD.E.Knuth, J.H.Morris, V.R.Pratt 同时发现。 无回溯的模式匹配算法（克努特－莫里斯－普拉特算法） KMP算法的基本思想： 每当一趟匹配过程中出现字符比较不等时，指向主串的指针i不回溯，而是利用已经得到的“部分匹配”结果将模式串向右滑动一段距离后继续进行比较。该算法可以在O(m+n)的数量级上完成串的模式匹配。2) 模式匹配的一种改进算法(KMP算法)null数据结构---第4章 串*[改进之处] 在比较过程中，主串的下标i只增不减，不回溯，可使算法复杂度提高到O(m+n) 。 [分析] 1 2 3 4 5 6 7 8 9 10 11 12 13 主串S a b c d a b c d a b e g h s1s2…sn 子串P a b c d a b e g p1p2…pm m