第4章串 要求:逻辑结构和顺序存储表示算法(顺序串) 1、简述空串和空格串(或称空格字符串)的区别 2、已知下列字符串 a=THIS’,f= A SAMPLE’,c='600D’,d='NE,b=’‘, S=Concat(a, Concat(SubString(f, 2, 7), Concat(b, SubString(a, 3, 2)))) t=Replace(f, SubString(f, 3, 6), c), u=Concat(SubString(c, 3, 1), d) g='IS, v=Concat(s, Concat(b, Concat(t, Concat(b, u)))) 其中 Concat(a,b)为将串b联接到串a之后,其他操作与教材P71页串的抽象数据类型中定义的操作 致,试问:s,t,v, Strength(s), Index(v,g), Index(u,g)各是什么? 3、已知:s=(XYZ)+*,t=(X+Z)*Y。试用联接、求子串和置换等操作,将s转化为t 4、编写算法,求串s所含不同字符的总数和每种字符的个数 5、两个字符串相等的充要条件是 和 设字符串S1= ABCDEF,S2=PQRS°’,则运算S= CONCAT(SUB(S1,2,LEN(S2),SUB(S1,LEN(S2),2)) 后的串值为 参考解答: 1、空串是指长度为零的串,而空格串是指串中字符是空格的字符串 2、s=‘ THIS SAMPLE IS’t= A GOODU='ONE’v= THIS SAMPLE IS A GOOD ONE’14,3,0 Replace(s, Substring(s, 3, 5), Concat(Substring(3, 6, 1), Concat(Substring(s, 4, 2) Concat(Substring(s, 7, 1), Substring(s, 3, 1))))) 4、算法1 void count(String T) i StrCopy (s, T) mFStrlength(S for(i=l: i<=m: i++) Substring(Sub1, S, i, 1) if(! StrCompare(Subl, #'))continue I Substring (Sub2, S, j, 1) if(!StrCompare(Sub1, Sub2)) Replace(S,sub1,"#”) nutt printf(Sub1, n) printf(num) 5、长度相等每一对应位置字符相等 第5章数组和广义表 要点 77 第 4 章 串 要求：逻辑结构和顺序存储表示算法（顺序串） 1、简述空串和空格串（或称空格字符串）的区别。 2、已知下列字符串 a=’THIS’, f=’A SAMPLE’, c=’GOOD’, d=’NE’, b=’ ‘, s=Concat(a,Concat(SubString(f,2,7),Concat(b,SubString(a,3,2)))), t=Replace(f,SubString(f,3,6),c), u=Concat(SubString(c,3,1),d), g=’IS’, v=Concat(s,Concat(b,Concat(t,Concat(b,u)))) 其中 Concat(a,b)为将串 b 联接到串 a 之后，其他操作与教材 P71 页串的抽象数据类型中定义的操作 一致，试问：s,t,v,StrLength(s),Index(v,g),Index(u,g)各是什么？ 3、已知：s=’(XYZ)+*’, t=’(X+Z)*Y’。试用联接、求子串和置换等操作，将 s 转化为 t。 4、编写算法，求串 s 所含不同字符的总数和每种字符的个数。 5、两个字符串相等的充要条件是 和 。 6、设字符串 S1=’ABCDEF’, S2=’PQRS’, 则运算 S=CONCAT(SUB(S1,2,LEN(S2)),SUB(S1,LEN(S2),2)) 后的串值为 。 参考解答： 1、空串是指长度为零的串，而空格串是指串中字符是空格的字符串。 2、s= ‘THIS SAMPLE IS’ t=’A GOOD’ u=’ONE’ v=’THIS SAMPLE IS A GOOD ONE’ 14, 3, 0 3 、 Replace(s,Substring(s,3,5) ,Concat(Substring(3,6,1) ,Concat(Substring(s,4,2), Concat(Substring(s,7,1),Substring(s,3,1))))) 4、算法 1： void count(String T) { StrCopy(S,T); m=Strlength(S); num=0; for(i=1;i<=m;i++) { n=1; Substring(Sub1,S,i,1); if(!StrCompare(Sub1,’#’))continue; for(j=i+1;j<=m;j++) { Substring(Sub2,S,j,1); if(!StrCompare(Sub1,Sub2)) n++; } Replace(S,sub1,’#’); num++; printf(Sub1,n); } printf(num); } 5、长度相等 每一对应位置字符相等 6、BCDEDE 第 5 章 数组和广义表 要点：