第4章 字符串 习题参考答案
-
第
4
章
串
习题参考答案
一、基础知识题
4.1
简述下列每对术语的区别：
空串和空格串；
串常量与串变量；<
/p>
主串和子串；串变量的名字和串变量的值；静态分
配的顺序串与动
态分配的顺序串。
【解答】
不含任何字符的串称为空串，其长度为
0
。仅
含有空格字符的串称为空格串，其
长度为串中空格字符的个数。
空格符可用来分割一般的字符，
便于人们识别和阅读，
但计算<
/p>
串长时应包括这些空格符。空串在串处理中可作为任意串的子串。
用引号（数据结构教学中通常用单引号，而
C
语言中用双引号）括起来的字符序列称
为串常量，串值可以变化的量称为串变量。
串中任意个连续的字符组成的子序列被称为该串的子串。
包含子串的串又被称为该子串的主
串。子串在主串中第一次出现的第一个
字符的位置称子串在主串中的位置。
串变量的与其它变量一样
，
要用名字引用其值，
串变量的名字也是标识符，
串变量的值可以
修改。
串
的存储也有静态存储和动态存储两种。
静态存储指用一维数组，
通常一个字符占用一个字
节，需要静态定义串的长度，具有顺序存储结构的优缺点。若需
要在程序执行过程中，
动态
地改变串的长度，则可以利用标准函
数
malloc()
和
free()<
/p>
动态地分配或释放存储单元，提高
存储资源的利用率。在
C
语言中，动态分配和回收的存储单元都来自于一个被称之为“堆”
的自由存储区，故该方法可称为堆分配存储。类型定义如下所示：
typedef struct
{ char *str;
int
length;
}HString;
4.2
设有串
S=
’
good
’
，
T=
’
I
︼
am
︼
a
︼
student
’<
/p>
，
R=
’
！
’
，求：
（
1
）
StringConcat(T
，
R)
（
2
）
SubString(T
，
8
，
7
）
< br>
（
3
）
StringLength(T)
（
4
）
Index
(T
，
’
a
’
)
（
5
）
StringInsert(T
，
8
，
S)
（
6
）
Replac
e(T
，
SubString(T<
/p>
，
8
，
7)
，
’
teach
er
’
)
【解答】
(1) StringCo
ncat(T
，
R)=
’
I
︼
am
︼
a
︼
student
！
’
(2) SubString(T
，
8
，
7
）
=
’
student<
/p>
’
(3)
StringLength(T)=14
(4)
Index(T
，
’
a
’
)=3
(5) StringInsert(T
，
8
，
S)=
’
I
︼
am
︼
a
︼
goodstudent
’
(6)
Replace(T
，
SubStr
ing(T
，
8
，
7)
，
’
teacher
’
)=
’
I
︼
am
︼
a
︼
teacher
’
<
/p>
4.3
若串
S1=
‘
ABCDEFG
’
，
S2=
‘
9898
’
，
S3=
‘
###
’
，
S4=
‘
012345
’
，执行
concat(repl
ace(S1
，
substr(S1
，
length(S2)
，
length
(S3))
，
S3)
，
substr(S4
，
index(S2
，
‘
8
’
< br>)
，
length(S2)))
操作的结果是什么？
【解答】
concat(repla
ce(S1,substr(S1,length(S2),length(S3)),S3),substr(
S4
，
index(S2,
‘
8
’
),length(S2)))
= concat(replace(S1,substr(S1,4,3),S3),
substr(S4,2,4))
= concat(replace(S1,
’
DEF
’
,S3)
,
’
1234
’
)
= concat(
‘
ABC#
##G
’
,
’
1234
’
)
=
< br>‘
ABC###G1234
’
4.4
设
S
为一个长度为
n
的字符串，其中的字符各不相同，则
S
中的互异的非平凡子串（非
空且不同于
S
本身）的个数是多少？
【解答】长度为
n
的字符串中互异的非平凡子串（非空且不
同于
S
本身）的个数计算如下：
长度为
1
的子串有
n
个，长度为
2
的子串有
n-1
个，长度为
3
的子串
有
n-2
个，„„，长度
为
n-1
的子串有
2
个，<
/p>
长度为
n
的子串有
1
个
（按题意要求这个子串就是
S<
/p>
本身，
不能计算
在总数内）
。故子串个数为
:(2+n)*(n-1)/2
4.5 KMP
算法
(
字符串匹配算法
)
较
Brut
e(
朴素的字符串匹配
)
算法有哪些改
进
?
【解答】
KMP
算法的最大特点是主串指针不回溯，在整个匹配过程中，对主串从头到尾扫
描一
遍，对于处理存储在外存上的大文件是非常有效的。
虽然
Brute(
朴素的字符串匹配
)
算法的时间复杂度是
O(n*m)
，但在一般情
况下，其实际的执
行时间近似于
O(n+m)
< br>，因此至今仍被采用。
KMP
算法仅当主串与模式间存在
许多
“部分匹
配”的情况下才显得比
B
rute(
朴素的字符串匹配
)
算法快
得多。
4.6
求串’
ababaaababaa
’
的
next
函数值。
解答：
a b a b a a a b
a b a
next[j]
：
0 1 1 2 3 4 2 2 3 456
4.7
模式串
t=
< br>’
abcaabbcaabdab
’
，求模式串的
next
和
next
val
函数的值。
a
b
c
a
a
b
b
c
a
a
b
d
a
b
next[j]
：
0
1
1
1
2
2
3
1
1
2
2
3
1
2
nextval[j]
：
0
1
1
0
2
1
3
1
0
2
1
3
0
1
4.8
对
S=
’
aabcbabcaabca
aba
’
，
T=
’
bca
’
，画出以
T
为模式串，
S
为目标串的匹
配过程。
解答：
↓
i=1
第一趟匹配：
a a b c b a b c a a b c a a
b a
b
↑
j=1
↓
i=2
第二趟匹配：
a b a b c a b c a c b a b
b c
↑
j=2
↓
i=3
第三趟匹配：
a b a b c a b c a c b a b
b
↑
j=1
↓
i=7
第四趟匹配：
a b a b c a b c a c b a b
b c a
(
匹配成功
)
↑
j=4
二、算法设计题
4.11
试写出用单链表表示的字符串结点类型的定义，并依次实现它的计算串长度、串赋值、
判断两串相等、
求子串、
两串连接、
求子串在串中位置的
6
个函数。要求每个字符串结点中
只存放一个字符。
【解答】单链表结点的类型定义如下：
typedef struct Node
{ char
data;
struct Node *next;
}LN
ode
，
*LinkedString
；
(1)
计算串长度
int
StringLength(LinkedString
L)
{
∥求带头结点的用单链表表示的字符串的长度
p=L->next;
∥
p
指向串中第一个字符结点
j=0;
∥计数器初始化
while(p)
{j++; p=p->next;}
∥计数
器加
1
，指针后移
return
j;
}
(2)
串赋值
LinkedString StringAssign(LinkedString
L)
{//
字符串赋值
LNode *s,*p,*r;
s=(char *)malloc(sizeof(char));
s->next=null;
//
头结点
r=s;
//r
记住尾结点
L=L->next;
//
串中第一字符
while(L!=null)
{p=(char
*)malloc(sizeof(char));
p->data=L->data;
//
赋值
p->next=r->next;
//
插入链表中
r->next=p;
r=p;
//
指向新的尾结点
L=L->next;
}
return s;
}
(3)
判断两串相等
int
StringEqual(LinkedString s, LinkedString q)
{//
判断字符串的相等
LNode
*p=s->next,*r=q->next;
while(p && r)
if(p->data==r->data)
{p=p->next; r=r->next;}
else return 0;
if(!p && !r)
return 1;
else
return 0;
}
while(*q!= '0')
{q++; x++; }
∥查找字符串
t
的长度
x
，循环结束时
q
指向
'0'
for(j=i;j>=pos
;j--)
{*(p+x)=*p; p--;}
∥串
s
的
pos
后的子
串右移，空出串
t
的位置
q--;
∥指针
q
回退到串
t
的最后一个字符
for(j=1;j<=x;j++) *p--=*q--;
∥将
t
串插
入到
s
的
pos
位置上
【算法讨论】
串
s
的结束标记
('0')
也后移了
，而串
t
的结尾标记不应插入到
s
中。
4.16
设
S=
“
S1S2
„
Sn
”是一个长为
N
的字符串，存放在一个数组中，编写算法将
S
改造
之后输出：
（
1
）将
S
的所有第偶数个字符按照其
原来的下标从大到小的次序放在
S
的后半部分；
（
2
）将
< br>S
的所有第奇数个字符按照其原来的下标从小到大的次序放在
S
的前半部分；
例如：
S=
‘
ABCDEFGHIJKL
’
，则改造后的
S
为‘
ACEGIKLJHFDB
’
。
【题目分析】对读入的字符串的第奇数个字符
，直接放在数组前面，对第偶数个字符，先
入栈，到读字符串结束，再将栈中字符出栈，
送入数组中。
void
ReArrangeString()
∥改造字符串，将第
偶数个字符放在串的后半部分，第奇数个字符前半部分。
{char ch,s[],stk[];
∥
s
和
stk
是字符
数组（表示字符串）和字符栈
int i=1,j;
∥
i
和
j
字符串和字符栈指针
< br>
while((ch=getchar())!=<
/p>
’
#
’
)
s[i++]=ch;
∥读入
字符串
,
’
#
’是字符串结束标志
s[i]=
’<
/p>
0
’
;
∥字符数组中字符串结束标志
i=1;j=1;
while(s[i])
∥改造字符串
{if(i%2==0)
stk[i/2]=s[i];
else
s[j++]=s[i];
i++;
}
∥
while
i--; i=i/2;
∥
i
先从’
0
’后退
，然后其含义是第偶数字符的个数
while(i>0)
s[j++]=stk[i--]
∥将第偶数个字符逆序填入原字符数组
(4)
求子串
LinkedString Substring(LinkedString S,
int start, int i)
{//
求串
S
从
start
开始的<
/p>
i
个字符所组成的子串
LNode *sub,*p,*r,*s=S->next;
int
j=1;
if(start<1 || i<0) {printf(
“参数错误
n
”
); exit(0);}
sub=(char *)malloc(sizeof(char));
sub->next=null;
//
头结点
r=sub;
while
（
s!=null &&
j
）
{s=s->next; j++;}
if
（
s==null
）
{pri
ntf(
“起始位置太大
n
”
); exit(0);}
else
{j=0;
while
（
s!=null &&
j
）
//
若
i
太大，则截取到串尾
{p=(char *)malloc(sizeof(char));
p->data=s->data;
p->next=r->next;
r->next=p; -
-