1、第四章习题1. 设 s=I AM A STUDENT, t=GOOD, q=WORKER。给出下列操作的结果：StrLength(s); SubString(sub1,s,1,7); SubString(sub2,s,7,1);StrIndex(s,A,4); StrReplace(s,STUDENT,q); StrCat(StrCat(sub1,t), StrCat(sub2,q);2. 编写算法，实现串的基本操作 StrReplace(S,T,V)。3. 假设以块链结构表示串，块的大小为 1，且附设头结点。试编写算法，实现串的下列基本操作：StrAsign(S,chars)； StrCop
2、y(S,T)； StrCompare(S,T)； StrLength(S)；StrCat(S,T)； SubString(Sub,S,pos,len)。 4 叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值。5 已知：S=”(xyz)*”,T=”(x+z)*y”。试利用联接、求子串和置换等操作，将 S 转换为 T.6 S 和 T 是用结点大小为 1 的单链表存储的两个串，设计一个算法将串 S 中首次与 T 匹配的子串逆置。7 S 是用结点大小为 4 的单链表存储的串,分别编写算法在第 k 个字符后插入串 T，及从第 k 个字符删除 len 个字符。以下
3、算法用定长顺序串：8 编写下列算法：（1）将顺序串 r 中所有值为 ch1 的字符换成 ch2 的字符。（2）将顺序串 r 中所有字符按照相反的次序仍存放在 r 中。（3）从顺序串 r 中删除其值等于 ch 的所有字符。（4）从顺序串 r1 中第 index 个字符起求出首次与串 r2 相同的子串的起始位置。（5）从顺序串 r 中删除所有与串 r1 相同的子串。9 写一个函数将顺序串 s1 中的第 i 个字符到第 j 个字符之间的字符用 s2 串替换。10 写算法，实现顺序串的基本操作 StrCompare(s,t)。11 写算法，实现顺序串的基本操作 StrReplace(SubString
4、(sub1,s,1,7) sub1=I AM A ;SubString(sub2,s,7,1) sub2= ;StrIndex(s,4,A)=6;StrReplace(s,STUDENT,q); s=I AM A WORKER;StrCat(StrCat(sub1,t),StrCat(sub2,q) sub1=I AM A GOOD WORKER。4.2 编写算法，实现串的基本操作 StrReplace(S,T,V)。【解答】算法如下：int strReplace(SString S,SString T, SString V)/*用串 V 替换 S 中的所有子串 T */int pos,i;
5、pos=strIndex(S,1,T); /*求 S 中子串 T 第一次出现的位置*/if(pos = = 0) return(0);while(pos!=0) /*用串 V 替换 S 中的所有子串 T */switch(T.len-V.len)case 0: /*串 T 的长度等于串 V 的长度*/for(i=0;ichpos+i=V.chi;case 0: /*串 T 的长度大于串 V 的长度*/for(i=pos+t.ien;ilen;i-) /*将 S 中子串 T 后的所有字符S-chi-t.len+v.len=S-chi; 前移 T.len-V.len 个位置*/for(i=0;ic
6、hpos+i=V.chi;S-len=S-len-T.len+V.len;case len-T.len+V.len)len-T.len+V.len;i=pos+T.len;i-) S-chi=S-chi-T.len+V.len; for(i=0;ichpos+i=V.chi;S-len=S-len-T.len+V.len; else /*替换后串长MAXLEN, 但串 V 可以全部替换*/ if(pos+V.len=pos+T.len; i-)S-chi=s-chi-T.len+V.len for(i=0;ichpos+i=V.chi;S-len=MAXLEN;else /*串 V 的部分字符
7、要舍弃*/ for(i=0;ichi+pos=V.chi;S-len=MAXLEN;/*switch()*/pos=StrIndex(S,pos+V.len,T); /*求 S 中下一个子串 T 的位置*/*while()*/ return(1);/*StrReplace()*/附加题：用链式结构实现定位函数。【解答】typedef struct Node char data;struct Node *next;Node,*Lstring;int strIndex(Lstring S, int pos, Lstring T) /*从串 S 的 pos 序号起，串 T 第一次出现的位置 */ N
8、ode *p, *q, *Ppos; int i=0，,j=0;if(T-next= =NULL | S-next = =NULL) return(0); p=S-next;q=T-next;while(p!=NULL j+;if(j!=pos) return(0); while(p!=NULL /*Ppos 指向当前匹配的起始字符*/if(p-data = = q-data) p=p-next; q=q-next;else /*从 Ppos 指向字符的下一个字符起从新匹配*/p=Ppos-next; q=T-head-next;i+;if(q= =NULL) return(pos+i); /
9、*匹配成功*/else return(0); /*失败*/第 4 章 串习题1. 设 s=I AM A STUDENT, t=GOOD, q=WORKER。给出下列操作的结果：StrLength(s); SubString(sub1,s,1,7); SubString(sub2,s,7,1);StrIndex(s,A,4); StrReplace(s,STUDENT,q); StrCat(StrCat(sub1,t), StrCat(sub2,q);参考答案StrLength(s)=14; sub1= I AM A_; sub2= _; StrIndex(s,A,4)=6; StrReplac
10、e(s,STUDENT,q)= I AM A WORKER; StrCat(StrCat(sub1,t), StrCat(sub2,q)= I AM A GOOD WORKER;2. 编写算法，实现串的基本操作 StrReplace(S,T,V)。3. 假设以块链结构表示串，块的大小为 1，且附设头结点。试编写算法，实现串的下列基本操作：StrAsign(S,chars)； StrCopy(S,T)； StrCompare(S,T)； StrLength(S)； StrCat(S,T)； SubString(Sub,S,pos,len)。说明 ：用单链表实现。4 叙述以下每对术语的区别：空串和
11、空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值。5 已知：S=”(xyz)*”,T=”(x+z)*y”。试利用联接、求子串和置换等操作，将 S转换为 T.6 S 和 T 是用结点大小为 1 的单链表存储的两个串，设计一个算法将串 S 中首次与 T 匹配的子串逆置。7 S 是用结点大小为 4 的单链表存储的串, 分别编写算法在第 k 个字符后插入串 T，及从第 k 个字符删除 len 个字符。以下算法用定长顺序串：8 写下列算法：（1） 将顺序串 r 中所有值为 ch1 的字符换成 ch2 的字符。（2） 将顺序串 r 中所有字符按照相反的次序仍存放在 r 中。（3） 从顺序串 r
12、 中删除其值等于 ch 的所有字符。（4） 从顺序串 r1 中第 index 个字符起求出首次与串 r2 相同的子串的起始位置。（5） 从顺序串 r 中删除所有与串 r1 相同的子串。9 写一个函数将顺序串 s1 中的第 i 个字符到第 j 个字符之间的字符用 s2 串替换。提示 ：（ 1）用静态顺序串 （2）先移位，后复制10 写算法，实现顺序串的基本操作 StrCompare(s,t)。11 写算法，实现顺序串的基本操作 StrReplace(&s,t,v)。提示 ：（1） 被替换子串 定位（相当于第 9 题中 i）（2） 被替换子串 后面的字符 左移或右移（为替换子串准备房间）（3） 替换子串 入住（复制）（4） 重复上述，直到
