第 4 章数据结构习题题目及答案 串
-
一、基础知识题
4.1
简述下列每对术语的区别：
空串和空格串；
串常量与串变量；主
串和子串；串变量的名字和串变量的值；静态分配的顺序串
与动态分配的顺序串。
【解答】
不含任
何字符的串称为空串，其长度为
0
。仅含有空格字符的串称为空
格串，其长度为串
中空格字符的个数。空格符可用来分割一般的字符，便于人们识别和阅
读，但计算串长时应包括这些空格
符。空串在串处理中可作为任意串的子串。
用引号（数据结构教学中通常用单引号
，而
C
语言中用双引号）括起来的字符序列称为串常量，其
串值是常量。串值可以变化的量称为串变量。
串中任意个连续的字符组成的子序列被称为该串的
子串
。包
含子串的串又被称为该子串的
主串
。子串
在主串中第一次出现时的第一个字符的位置称子串在主串中的
位置
。
串变量与其它变量一样，要用名字引用其值，串变量的
名字也是标识符，串变量的值可以修改。
串的存储也有静态存
储和动态存储两种。静态存储指用一维数组，通常一个字符占用一个字节，需要
静态定义
串的长度，具有顺序存储结构的优缺点。若需要在程序执行过程中，动态地改变串的长度，则可
< br>以利用标准函数
malloc()
和
free()
动态地分配或释放存储单元，提高存储资源的利用率。在
C
语言中，
动态分配和回收的存储单元都来自于一个
被称之为
“
堆
”
的自由存储区，故该方法可称为
堆分配存储
。类型
定义如下所示：
typedef
struct
{
char
*str;
int
length;
}HString;
4.2
设有串
S=’good’
，
T=’I
︼
am
︼
a
︼
student’
，
R=’
！
’
，
求：
（
1
）
StringConcat(T
，<
/p>
R)
（
2
）
SubString(T
，
8
，
7
）
（
3
< br>）
StringLength(T)
（
4
）
Index(
T
，
’a’)
（
5
）
StringInsert(T
，
8
，
S)
（
6
）
Rep
lace(T
，
SubString
(T
，
8
，
7
)
，
’teacher’)
【解答】
(1) StringCo
ncat(T
，
R)=’I
︼
am
︼
a
︼
student
！
’
(2) SubString(T
，
8
，
7
）
=’s
tudent’
(3)
StringLength(T)=14
(4)
Index(T
，
’a’)=3
(5) String
Insert(T
，
8
，
S)=’I
︼
am
︼
a
︼
goodstudent’
(6)
Replace(T
，
SubString(T
，
8
，
7)
，
’teacher’)= ’I
︼
< br>am
︼
a
︼
teacher’
4.3<
/p>
若串
S
1
=‘A
BCDEFG’
，
S
2
=‘9898’
，
S
3
=‘###’
，
S
4
=‘’
，执行
concat(replace(S<
/p>
1
，
substr(S
< br>1
，
length(S
2
)
，
length(S
3
))
，
S
3
)
，
substr(S
4
，
index(S
2
，
‘8’)
，
le
ngth(S
2
)))
操作的结果是什么？
【解答】
concat(repla
ce(S
1
,substr(S
1
,length(S
2
),length(
S
3
)),S
3
),substr(S
4
，
inde
x(S
2
,‘8’),length(S
2
)))
= concat(replace(S
1
,substr(S
1
,4,3),S
3
),substr(S
4
,2,4))
= concat(replace(S
1
,’DEF’,S
3
),’1234’)
=
concat(‘ABC###G’,’1234’)
=
‘ABC###G1234’
4.4
设
S
为一个长度为
n
的字符串，
其中的字符
各不相同，
则
S
中的互异的非平凡子串
（非空且不同
于
S
本身）的个数是多少？
【解答】长度为
< br>n
的字符串中互异的非平凡子串（非空且不同于
S
本身）的个数计算如下：
长度为
1
的子串有
n
个，长度为
2
的子串有
n-1
个，长度为
3
的子串有
n-2
个，
……
，长度为
n-1
的子串有
2
个，长度为
n
的子串有
1
个（按题
意要求这个子串就是
S
本身，不能计算在总数内）。故子串
个数为
:(2+n)*(n-1)/2
4.5 KMP
算法
(
字符串匹配算法
)
较
Brut
e(
朴素的字符串匹配
)
算法有哪些改
进
?
【解答】
KMP
算法的最大特点是主串指针不回溯，在整个匹配过程中，对主串从头到尾扫描一遍，对
< br>于处理存储在外存上的大文件是非常有效的。
虽然
Brute(
朴素的字符串匹配
)
算法的时间复杂度是
O(n*m)
，但在一般情
况下，其实际的执行时间
近似于
O(n+m)
< br>，因此至今仍被采用。
KMP
算法仅当主串与模式间存在
许多
“
部分匹配
”
的情况下才显得
比
Brute(
朴
素的字符串匹配
)
算法快得多。
4.6
求串
’ababaaababaa’
的
next
函数值。
【解答】
j
t
串
next[j]
4.7
模式串
t=’abcaabbcaabdab’
，求模式串的
next
和
nextv
al
函数的值。
【解答】
j
t
串
next[j]
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
0 1 1 1 2 2 3 1 1 2 2 3 1 2
0 1 1 0 2 1 3 1 0 2 1 3 0 1
4.8
对
S=’aabcbabca
abcaaba’
，
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
1 2 3 4 5
6
7 8 9 10
11
12
a b a b a a a b a b
a
a
0 1
1 2 3 4
2 2 3 4 5 6
↑
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.9
选择题：下面关于串的的叙述中，哪一个是不正确的？
A
．串是字符的有限序列
B
．空串是由空格构成的串
C
．模式匹配是串的一种重要运算
D
．串既可以采用顺序存储，也可以采用链式存储
【解答】
B
4.10
选择题：串是一种特殊的线性表，下面哪个叙述体现了这种
特殊性？
A
．数据元素是一个字符
B.
可以顺序存储
C.
数据元素可以是多个字符
D.
可以链接存储
【解答】
A
二、算法设计题
4.11
试写出用单链表表示的字符串结点类型的定义，
并依次实现它的计算串长度
、
串赋值、
判断两串
相等、求子串、两
串连接、求子串在串中位置的
6
个函数。要求每个字符串结点中
只存放一个字符。
【算法
4.11<
/p>
】
单链表结点的类型定义如下：
typedef
struct
Node
{char
data;
struct
Node *next;
}LNode
，
*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)
{//
将字符串
L
的值赋给串
s
LNode *s,*p,*r;
s=(char *)malloc(sizeof(char));
s->next=null;
//
头结点
r=s;
//r
记住尾结点
L=L->next;
//
串中第一字符
while
(L)
{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;
}
(4)
求子串