第4章串 4.1串的基本概念 42串的存储结构 4.3串的模式匹配
1 4.1 串的基本概念 4.2 串的存储结构 4.3 串的模式匹配 第4章 串
41串的基本概念 字符串: ·简称为串,是由零个或多个字符组成的有穷序列 空串: 含零个字符的串,用Φ表示 串的长度: 串中所含字符的个数 串的表示: a1a。。a 1“2 其中,最外边的双引号本身不是串的内容,它们是串的 标志,以便将串与标识符(如变量名等加以区别 a(1≤im)代表一个字符 空格串: 只包含空格的串,空格用□表示 2
2 • 字符串: • 简称为串，是由零个或多个字符组成的有穷序列 • 空串: • 含零个字符的串，用Ф表示 • 串的长度: • 串中所含字符的个数 • 串的表示： • “a1 a2…an ” • 其中，最外边的双引号本身不是串的内容,它们是串的 标志，以便将串与标识符(如变量名等)加以区别 • ai (1≤i≤n)代表一个字符 • 空格串： • 只包含空格的串，空格用□表示 4.1 串的基本概念
两个串相等: 当且仅当两个串的长度相等并且各个对应位置上 的字符都相同 子串: 个串中任意个连续字符组成的子序列 含空串,但不含串本身 例如,“a”、“ab”、“abc”和“abcd”等都是 “ abcde”的子串(有的教材将本身作为子串)
3 • 两个串相等： •当且仅当两个串的长度相等并且各个对应位置上 的字符都相同 • 子串： •一个串中任意个连续字符组成的子序列 •含空串，但不含串本身 •例如， “a”、 “ab”、 “abc”和“abcd”等都是 “abcde”的子串（有的教材将本身作为子串）
讨论:“ abcde有多少个子串? 解:空串数1 含1个字符的子串数5 含2个字符的子串数4 含3个字符的子串数3 含4个字符的子串数2 共有1+2+3+4+5=15个子串
4 讨论: “abcde”有多少个子串? 解: 空串数:1 含1个字符的子串数:5 含2个字符的子串数:4 含3个字符的子串数:3 含4个字符的子串数:2 共有1+2+3+4+5=15个子串
串的基本运算 (1) Strassign(& S, cstr):将一个字符串常量赋给串s, 即生成一个其值等于cstr的串s (2) StrCopy(&s,t:串复制,将串赋给串s (3) Strequal(s,+:判串相等,若两个串s与相等则返 回真;否则返回假。 (4) StrEngth(s):求串长,返回串s中字符个数
5 (1) StrAssign(&s,cstr):将一个字符串常量赋给串s， 即生成一个其值等于cstr的串s。 (2) StrCopy(&s,t):串复制，将串t赋给串s。 (3) StrEqual(s,t):判串相等，若两个串s与t相等则返 回真；否则返回假。 (4) StrLength(s):求串长，返回串s中字符个数。 串的基本运算
(5) Concat(s,t:串连接,返回由两个串s和连接在 一起形成的新串 (6 Substr(s,ij):求子串,返回串s中从第i(1s≤n) 个字符开始的、由连续j个字符组成的子串。 (7) InsTr(s1,i2:将串s2插入到串s的第(l<n+) 个字符中,即将s2的第一个字符作为s的第i个字符, 并返回产生的新串
6 (5)Concat(s,t):串连接，返回由两个串s和t连接在 一起形成的新串。 (6)SubStr(s,i,j):求子串，返回串s中从第i(1≤i≤n) 个字符开始的、由连续j个字符组成的子串。 (7)InsStr(s1,i,s2):将串s2插入到串s1的第i(1≤i≤n+1) 个字符中，即将s2的第一个字符作为s1的第i个字符， 并返回产生的新串
(8) Destr(s,i):从串s中删去从第i(≤i≤n)个字符开 始的长度为的子串,并返回产生的新串。 (9) Repstr(sit):替换,在串s中,将第i(1≤i≤n)个 字符开始的j个字符构成的子串用串t替换,并返回产 生的新串。 (10) Dispstr(s:串输出,输出串s的所有元素值
7 (8)DelStr(s,i,j):从串s中删去从第i(1≤i≤n)个字符开 始的长度为j的子串，并返回产生的新串。 (9)RepStr(s,i,j,t):替换，在串s中，将第i(1≤i≤n)个 字符开始的j个字符构成的子串用串t替换，并返回产 生的新串。 (10) DispStr(s):串输出，输出串s的所有元素值
子串定位: Index(S,T 初始条件:串S和T存在,且T是非空串 操作结果:若主串S中存在和串T相等的子串,则返回 它在主串S中第一次出现的位置;否则返回0 子串在主串中的位置:子串中的第一个字符在主串中 的“位序”。 【例】a= Welcome to Beijing b=” Welcome c= Bel d= Bei 长度分别为18、7、3、3; b、c、d都是a的子串;b在a中的位置是1, c在中的位置是12;c和d两串相等 8
8 子串定位：Index(S,T) • 初始条件：串 S 和 T 存在，且T 是非空串 • 操作结果：若主串 S 中存在和串 T相等的子串，则返回 它在主串 S 中第一次出现的位置;否则返回0。 • 子串在主串中的位置：子串中的第一个字符在主串中 的“位序” 。 • 【例】a= ’Welcome to Beijing’ b= ’Welcome’ c= ’Bei’ d= ’Bei’ • 长度分别为18、7、3、3； • b、c、d都是a的子串；b在a中的位置是1， c在a中的位置是12；c和d两串相等
子串定位: Index(S,T 【算法思想】 在主串S中取从第个字符起,长度和串T相等的子串与串T比较, 若相等,则求得函数值为i,否则i值增1,直至串S中不存在和串 T相等的子串为止。 【算法设计】 int Index( String S, String T)i n=StringLength(S); m= String Length(T); i=1; while(i<= n-m+1)t StrCopy( sub, SubStr(s, i, m)) if( StrEqual(sub, T)l=0)++i; else return i 3/ while return0;/S中不存在与T相等的子串 ∥算法结束
9 子串定位：Index(S,T) • 【算法思想】 • 在主串S中取从第i个字符起，长度和串T相等的子串与串T比较， 若相等，则求得函数值为i，否则i值增1，直至串S中不存在和串 T相等的子串为止。 • 【算法设计】 int Index (String S, String T) { return 0; // S中不存在与T相等的子串 } // 算法结束 n = StringLength(S); m = StringLength(T); i = 1; while ( i <= n-m+1) { } // while StrCopy( sub,SubStr(S,i,m) ); if ( StrEqual(sub,T) != 0 ) ++i ; else return i ;
总结 ◆串的逻辑结构和线性表极为相似,区别仅在于串 的数据对象约束为字符集。 ◆串的基本操作和线性表有很大差别: ◆在线性表的基本操作中,大多以“单个元素” 作为操作对象; ◆而在串的基本操作中,通常以“串的整体”作 为操作对象
10 ◆ 串的逻辑结构和线性表极为相似，区别仅在于串 的数据对象约束为字符集。 ◆ 串的基本操作和线性表有很大差别： ◆ 在线性表的基本操作中，大多以“单个元素” 作为操作对象； ◆ 而在串的基本操作中，通常以“串的整体”作 为操作对象。 总 结