(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 ◆ 串的逻辑结构和线性表极为相似，区别仅在于串 的数据对象约束为字符集。 ◆ 串的基本操作和线性表有很大差别： ◆ 在线性表的基本操作中，大多以“单个元素” 作为操作对象； ◆ 而在串的基本操作中，通常以“串的整体”作 为操作对象。 总 结