第4章 串 习题参考答案
一、基础知识题
4.1 简述下列每对术语的区别：
    空串和空格串； 串常量与串变量；主串和子串；串变量的名字和串变量的值；静态分配的顺序串与动态分配的顺序串。
【解答】 不含任何字符的串称为空串，其长度为0。仅含有空格字符的串称为空格串，其长度为串中空格字符的个数。空格符可用来分割一般的字符，便于人们识别和阅读，但计算串长时应包括这些空格符。空串在串处理中可作为任意串的子串。
    用引号（数据结构教学中通常用单引号，而C语言中用双引号）括起来的字符序列称为串常量，串值可以变化的量称为串变量。
串中任意个连续的字符组成的子序列被称为该串的子串。包含子串的串又被称为该子串的主串。子串在主串中第一次出现的第一个字符的位置称子串在主串中的位置。
串变量的与其它变量一样，要用名字引用其值，串变量的名字也是标识符，串变量的值可以修改。
串的存储也有静态存储和动态存储两种。静态存储指用一维数组，通常一个字符占用一个字节，需要静态定义串的长度，具有顺序存储结构的优缺点。若需要在程序执行过程中，动态地改变串的长度，则可以利用标准函数malloc()和free()动态地分配或释放存储单元，提高存储资源的利用率。在C语言中，动态分配和回收的存储单元都来自于一个被称之为“堆”的自由存储区，故该方法可称为堆分配存储。类型定义如下所示：
typedef struct
{ char *str;
  int length;
}HString;
4.2设有串S=’good’，T=’I︼am︼a︼student’，R=’！’，求：
  （1）StringConcat(T，R)  （2）SubString(T，8，7）
  （3）StringLength(T)    （4）Index(T， ’a’)
  （5）StringInsert(T，8，S)
（6）Replace(T， SubString(T，8，7)， ’teacher’)
【解答】
(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，8，S)=’I︼am︼a︼goodstudent’
(6) Replace(T， SubString(T，8，7)，’teacher’)= ’I︼am︼a︼teacher’
4.3若串S1=‘ABCDEFG’， S2=‘9898’ ，S3=‘###’，S4=‘012345’，执行
concat(replace(S1，substr(S1，length(S2)，length(S3))，S3)，substr(S4，index(S2，‘8’)，length(S2)))
操作的结果是什么？
【解答】
concat(replace(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’)
= ‘ABC###G1234’
4.4 设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数是多少？
【解答】长度为n的字符串中互异的非平凡子串（非空且不同于S本身）的个数计算如下：
长度为1的子串有n个，长度为2的子串有n-1个，长度为3的子串有n-2个，……，长度为n-1的子串有2个，长度为n的子串有1个（按题意要求这个子串就是S本身，不能计算在总数内）。故子串个数为:(2+n)*(n-1)/2
4.5 KMP算法(字符串匹配算法)较Brute(朴素的字符串匹配)算法有哪些改进?
【解答】KMP算法的最大特点是主串指针不回溯，在整个匹配过程中，对主串从头到尾扫描一遍，对于处理存储在外存上的大文件是非常有效的。
虽然Brute(朴素的字符串匹配)算法的时间复杂度是O(n*m)，但在一般情况下，其实际的执行时间近似于O(n+m)，因此至今仍被采用。KMP算法仅当主串与模式间存在许多“部分匹配”的情况下才显得比Brute(朴素的字符串匹配)算法快得多。
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=’abcaabbcaabdab’，求模式串的next和nextval函数的值。
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=’aabcbabcaabcaaba’，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;
}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)
{//字符串赋值
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;
}
}
  (4) 求子串
LinkedString Substring(LinkedString S, int start, int i)
{//求串S从start开始的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;
printf函数的执行顺序while（s!=null && j<start）
  {s=s->next; j++;}
if（s==null）
{printf(“起始位置太大\n”); exit(0);}
else     
{j=0;
while（s!=null && j<i）//若i太大，则截取到串尾
  {p=(char *)malloc(sizeof(char));
    p->data=s->data;
    p->next=r->next;
    r->next=p;
    r=p;
    j++;
  }
}
return sub;
} ∥算法结束
  (5) 两串连接
LinkedString Concat(LinkedString S, LinkedString T)
{∥求串S和串T的连接，返回结果串
LNode *p=S;
while(p->next!=null)  //查串尾
  p=p->next;
p->next=T->next;
free(T);              //释放头结点
  return S;