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

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

ID:46584709

大小:181.65 KB

页数:6页

时间:2019-11-25

数据结构教程李春葆课后答案第4章串_第1页
数据结构教程李春葆课后答案第4章串_第2页
数据结构教程李春葆课后答案第4章串_第3页
数据结构教程李春葆课后答案第4章串_第4页
数据结构教程李春葆课后答案第4章串_第5页
资源描述:

《数据结构教程李春葆课后答案第4章串》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

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

2、会回退,所以BF算法是有回溯算法。在KMP算法的匹配过程中,当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算法是

3、简单模式匹配算法的改进,以目标串s="aabaaabc"、模式串t="aaabc"为例说明的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]

4、=t[1],所以有s[0]=t[1],这说明下次不必从i=1,j=0开始比较,而只需保持i=2不变,让i=2和j=next[j]=1的字符进行比较。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、效函数或失配函数。5.给出以下模式串的next值和nextval值:(1)ababaa(2)abaabaab答:(1)求其next和nextval值如表4.2所示。表4.2模式串"ababaa"对应的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.设目标

6、为s="abcaabbabcabaacbacba",模式串t="abcabaa"。(1)计算模式串t的nextval数组。(2)不写算法,给出利用改进的KMP算法进行模式匹配的过程。(3)问总共进行了多少次字符比较?解:(1)先计算next数组,在此基础上求nextval数组,如表4.4所示。表4.4计算next数组和nextval数组j0123456t[j]abcabaanext[j]-1000121nextval[j]-100-1021(2)改进的KMP算法进行模式匹配的过程如图4.2所示。第4章串3第1趟匹配s:abcaabbab

7、cabaacbacbai=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:abcaabbabcabaacbacbai=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.

8、2改进的KMP算法模式匹配的过程(3)从上述匹配过程看出:第1趟到第4趟的字符比较次数分别是5、3、1、7,所以总共进行了16次字符比较。7.有两个顺序串s1和s2,设计一个算法求一个顺序串s3,该串中的字

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。