第4章 综合练习
1.
设有串S=’good’，T=’I︼am︼a︼student’，R=’！’，求：
（1）StringConcat(T,R) ==’I
am a student!’
（2）SubString(T,8,7） ==’student’
（3）StringLength(T) ==14
（4）Index(T, ’a’) ==3
（5）StringInsert(T,S,8) ==’I am a goodstudent!’
（6）replace(T, SubString(T,8,7),
’teacher’) =’I am a
teacher’
2.
若串S1=’ABCDEFG’， S2=’9898’，S3=’###’，S4=’012345’，试计算执行
concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,’8’),length(S2)))
操作的结果。
【解答】 结果为: ‘ABC###G1234’
3.
求串’ababaaababaa’ 的next函数值。
【解答】
|
j |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
串 |
a |
b |
a |
b |
a |
a |
a |
b |
a |
b |
a |
a |
|
nxt[j] |
0 |
1 |
1 |
2 |
3 |
4 |
2 |
2 |
3 |
4 |
5 |
6 |
4. 模式串t=’abcaabbcaabdab’，求模式串的next和nextval函数的值。
【解答】
|
j |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
|
串 |
a |
b |
c |
a |
a |
b |
b |
c |
a |
a |
b |
d |
a |
b |
|
nxt[j] |
0 |
1 |
1 |
1 |
2 |
2 |
3 |
1 |
1 |
2 |
2 |
3 |
1 |
2 |
|
nxtval[j] |
0 |
1 |
1 |
0 |
2 |
1 |
3 |
1 |
0 |
2 |
1 |
3 |
0 |
1 |
5.。给出字符串‘abacabaaad’在KMP算法中的next和nextval数组。
【解答】
|
j |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
串 |
a |
b |
a |
c |
a |
b |
a |
a |
a |
d |
|
nxt[j] |
0 |
1 |
1 |
2 |
1 |
2 |
3 |
4 |
2 |
2 |
|
nxtval[j] |
0 |
1 |
0 |
2 |
0 |
1 |
0 |
4 |
2 |
2 |
6. 对S=’aabcbabcaabcaaba’，T=’bca’，画出以T为模式串，S为目标串的匹配过程。
【解答】
bca的next值数为: 011
a a b c b a b c a a b c a a b a
b c
b
b c a
b c
b
b c a
7. 若S=’software’,则其子串的数目是多少？
【解答】(1+8)*8/2+1=37 (包括空串和自身)
8. 试写出用单链表表示的字符串结点类型的定义，并依次实现它的计算串长度、串赋值、判断两串相等、求子串、两串连接、求子串在串中位置的6个函数。要求每个字符串结点中只存放一个字符。
9. 编写一个算法frequency，统计在一个输入字符串中各个不同字符出现的频度。
void count()
//本算法统计在输入字符串中各个不同字符出现的频度
{int i,arr[255]={0}; //用数组存放各字符出现的频度,
数组初始化
char ch;
while ((ch=getchar())!=end) arr[ch]++; //设end代表结束输入的字符
for (i=33;i<=255; i++)
//ASCII 0—32是控制字符
{if (i%10==0) printf(“\n”);
//10个字符一行
printf(“%c出现的频度为%d”,i,arr[i]);
}
}
10. 顺序串上实现串比较运算strcmp（s,t）的算法。
void strcmp(SSTRING s,t)
//在顺序串上实现串s和串t的比较运算,若s>t返回1,若s=t返回0,若s<t返回-1
{int i=1;
while (i<=s[0] && i<=t[0])
if (s[i]==t[i]) i++;
else if (s[i]>t[i]) return 1;
else return -1
if (i<t[0]) return 1;
//t串长度小于s串长度
else if (i<s[0]) return -1; //s串长度小于t串长度
else return 0;
}//算法结束
11. 试写一算法，在串的顺序存储结构上实现串基本操作StringConcat(S,T) 。
12. 输入的一段正文中，删除以下两种形式作为标志的注释部分：{ }，并将删除注释后的正文输出。
假设正文采用顺序结构存储
void output(sstring
s)
{//删除正文中的注释部分
int i cou=0;
for (i=1;i<=s[0];i++)
{if s[i]=’{’ cou++;
if(s[i]=’}’ )
{cou--;
if cou<0 printf(“｛与｝的个数不相等”)
}
if cou=0 printf(“%c”,s[i]);
}
}
13. 输入一文本行（最多50个字符），找出某一个不包含空格的子串在文本行中出现的次数。
int strcount(String
str, String substr)
{//找出不包含空格的子串在文本行中出现的次数
int i=0,j,k,count=0;
for(i=0;i<=str[0];i++) //str[0]为串str的长度
for(j=i,k=0;str[i]==substr[k];j++,k++)
if(k==substr[0]-1)
count++;
//找到一个子串
return(count);
}
14. 用顺序结构存储的串S，编写算法删除S中第i个字符开始的j个字符。