数据结构教程李春葆课后答案第4章串.pdf

《数据结构教程李春葆课后答案第4章串.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第4章串教材中练习题及参考答案1.串是一种特殊的线性表，请从存储和运算两方面分析它的特殊之处。答：从存储方面看，串中每个元素是单个字符，在设计串存储结构时可以每个存储单元或者结点只存储一个字符。从运算方面看，串有连接、判串相等、求子串和子串替换等基本运算，这是线性表的基本运算中所没有的。2.为什么模式匹配中，BF算法是有回溯算法，而KMP算法是无回溯算法？答：设目标串为s，模式串为t。在BF算法的匹配过程中，当t[j]=s[i]时，置i++，j++；当t[j]≠s[i]时，置i=i-j+1，j=0。从中看到，一旦两字符不等，目标串指针i会回退，所以BF算法是有回溯算法。在KMP算法

2、的匹配过程中，当t[j]=s[i]时，置i++，j++；当t[j]≠s[i]时，i不变，置j=next[j]。从中看到，目标串指针i不会回退，只会保持位置不变或者向前推进，所以KMP算法是无回溯算法。3.在KMP算法中，计算模式串的next时，当j=0时，为什么要置next[0]=-1？答：当模式串中t0字符与目标串中某字符si比较不相等时，此时置next[0]=-1表示模式串中已没有字符可与目标串的si比较，目标串当前指针i应后移至下一个字符，再和模式串的t0字符进行比较。4.KMP算法是简单模式匹配算法的改进，以目标串s="aabaaabc"、模式串t="aaabc"为例说明的

3、next的作用。答：模式串t="aaabc"的next数组值如表4.1所示。表4.1模式串t对应的next数组j01234t[j]aaabcnext[j]-10120从i=0，j=0开始，当两者对应字符相等时，i++，j++，直到i=2，j=2时对应字符不相等。如果是简单模式匹配，下次从i=1，j=0开始比较。KMP算法已经获得了前面字符比较的部分匹配信息，即s[0..1]=t[0..1]，所以s[0]=t[0]，而next[2]=1表明t[0]=t[1]，所以有s[0]=t[1]，这说明下次不必从i=1，j=0开始比较，而只需保持i=2不变，让i=2和j=next[j]=1的字符

4、进行比较。i=2，j=1的字符比较不相等，保持i=2不变，取j=next[j]=0。i=2，j=0的字符比较不相等，保持i=2不变，取j=next[j]=-1。2数据结构教程学习指导当j=-1时i++、j++，则i=3，j=0，对应的字符均相等，一直比较到j超界，此时表示匹配成功，返回3。从中看到，next[j]保存了部分匹配的信息，用于提高匹配效率。由于是在模式串的j位置匹配失败的，next也称为失效函数或失配函数。5.给出以下模式串的next值和nextval值：（1）ababaa（2）abaabaab答：（1）求其next和nextval值如表4.2所示。表4.2模式串"ab

5、abaa"对应的next数组j012345t[j]ababaanext[j]-100123nextval[j]-10-10-13（2）求其next和nextval值如表4.3所示。表4.3模式串"abaabaab"对应的next数组j01234567t[j]abaabaabnext[j]-10011234nextval[j]-10-110-1106.设目标为s="abcaabbabcabaacbacba"，模式串t="abcabaa"。（1）计算模式串t的nextval数组。（2）不写算法，给出利用改进的KMP算法进行模式匹配的过程。（3）问总共进行了多少次字符比较？解：（1）先计

6、算next数组，在此基础上求nextval数组，如表4.4所示。表4.4计算next数组和nextval数组j0123456t[j]abcabaanext[j]-1000121nextval[j]-100-1021（2）改进的KMP算法进行模式匹配的过程如图4.2所示。第4章串3第1趟匹配s：abcaabbabcabaacbacbai=4i=4失败修改从i=0，j=0开始t：abcabaaj=4j=nextval[4]=0第2趟匹配s：abcaabbabcabaacbacbai=6i=6失败修改从i=4，j=0开始t：abcabaaj=2j=nextval[2]=0第3趟匹配s：a

7、bcaabbabcabaacbacbai=6i=6失败修改从i=6，j=0开始t：abcabaaj=0j=nextval[0]=-1s：abcaabbabcabaacbacba第4趟匹配成功i=14从i=6，j=-1开始返回14-7=7t：abcabaaj=7图4.2改进的KMP算法模式匹配的过程（3）从上述匹配过程看出：第1趟到第4趟的字符比较次数分别是5、3、1、7，所以总共进行了16次字符比较。7.有两个顺序串s1和s2，设计一个算法求一个顺序串s3，该串中的字