文档介绍：数据结构---第四章串1第四章串串是特殊的线性表,数据元素是单个字符。线性表的操作通常以“数据元素”为操作对象;串的操作主要以“子串”为操作对象。 串类型的定义 串的存储结构和操作的实现 串的模式匹配算法 串应用示例——文本编辑本章学习要点及习题数据结构---第四章串2 串类型的定义 串的概念串(字符串): 是由零个或多个字符组成的有限序列。记作: s = ‘a 1a 2…a n’ (n ?0) 串长:串中字符的个数 n。子串和主串:串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串称为主串。串相等:两个串长度相等,且对应位置的字符都相等。空串和空白串:空串不包含任何字符,表示为?; 空白串由一个或多个空格组成,如‘’。数据结构---第四章串3 串的常用基本操作(1) 用串常量赋值 StrAssign (&T, chars) 用串变量赋值 StrCopy (&T, S) (2) 判定空串 StrEmpty (S) (3 )两串比较 pare (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) 串类型的最小操作子集数据结构---第四章串4 [例]设 s=‘ I am a student. ’ t= ‘ OK! ’ p= ‘ student ’ q= ‘ nurse ’ r= ‘good ’ (1) Concat(newstr, s, t ) newstr= ‘ I am a student. OK! ’ (2) Replace(s, p , q); s= ‘ I am a nurse. ’ (3) StrInsert(s, 8, r) s= ‘ I am a good nurse. ’数据结构---第四章串5 串的存储结构和操作的实现 串的顺序存储结构(1)定长顺序存储表示 7 s t u d e n t 0 1 2 3 4 5 6 7 8 MAXSTRLEN #define MAXSTRLEN 255 // 予定义最大串长 typedef unsigned char SString [MAXSTRLEN+1]; 存放串的长度[存储定义] B O O K \0 C语言本身的串表示方式: 不便于求串长等操作数据结构---第四章串6 [基本操作实现示例]约定:串值长度上溢时,用“截尾法”处理, 即“截断”超过予定义长度的部分。 int pare (SString S, SString T) //S >T, 返回值>0;S=T ,返回 0;S<T ,返回值< 0 { for (i=1; i<=S[0] && i<=T[0]; i++) if (S[i] != T[i] ) return(S[i] - T[i] ); return S[0]-T[0] } // pare 操作基于“字符序列复制”i 数据结构---第四章串7 Status Concat (SString &T, SString S1, SString S2) //用T返回串 s1和s2联接而成的新串。//若未截断,返回 TRUE ,否则返回 FALSE { if ( S1[0]+S2[0] <= MAXSTRLEN ) { T[1..S1[0]] = S1[1..S1[0]]; T[s1[0]+1..S1[0]+S2[0]] = S2[1..S2[0]]; T[0]= S1[0]+S2[0]; uncut=TRUE; } else if (S1[0]<MAXSTR