华北水利学院数据结构第四章(陈波.ppt

《华北水利学院数据结构第四章(陈波.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章特殊的线性表——串问题的提出查毒程序搜索引擎1.串的逻辑结构串：由零个或多个任意字符组成的有限序列。串长度：串中所包含的字符个数。空串：长度为0的串，记为：""。非空串通常记为：S=“a1a2…an”其中：S是串名，双引号是定界符，双引号引起来的部分是串值，ai（1≤i≤n）是一个任意字符。1.串的逻辑结构两个串相等：如果两个串的长度相等且对应字符都相等。子串：串中任意连续的字符组成的子序列称为该串。主串：包含子串的串。子串的第一个字符在主串中的序号称为子串的位置。顺序串：用数组来存储串中的字符序列。（1）用一个变量来表示串的长度。2.串的存储结构——顺序

2、串如何表示串的长度？顺序串：用数组来存储串中的字符序列。（2）在串尾存储一个不会在串中出现的特殊字符作为串的终结符。2.串的存储结构——顺序串如何表示串的长度？顺序串：用数组来存储串中的字符序列。（3）用数组的0号单元存放串的长度，串值从1号单元开始存放。2.串的存储结构——顺序串如何表示串的长度？链接串：用链接存储结构来存储串。p552.串的存储结构——链接串3.串的基本操作串的链接串的比较串的复制习题4.4、4.5、4.6习题4.7。编写一个函数来颠倒单词在字符串里的出现顺序。【《程序员面试攻略(第2版)》p81】例如，把字符串“Doordonot,there

3、isnotry.”转换为“try.noistherenot,doorDo”。假设所有单词都以空格为分隔符，标点符号也当做字母来对待。请对你的设计思路做出解释，并对你的解决方案的执行效率进行评估。3.串的基本操作删除特定字符。【《程序员面试攻略(第2版)》p78】用C语言编写一个高效率的函数来删除字符串里的给定字符。这个函数的调用模型如下所示：voidRemoveChars(charstr[],charremove[]);注意，remove中的所有字符都必须从str中删除干净。比如说，如果str是“BattleoftheVowels:HawaiiVS.Grozny”

4、，remove是“aeiou”，这个函数将把str转换为“BttlfthVwls:Hwvs.Grzny”。请对你的设计思路做出解释，并对你解决方案的执行效率进行评估。4.串的应用——模式匹配模式匹配：给定主串S="s1s2…sn"和模式T="t1t2…tm"，在S中寻找T的过程称为模式匹配。如果匹配成功，返回T在S中的位置，如果匹配失败，返回0。4.串的应用——BF模式匹配算法基本思想：从主串S的第一个字符开始和模式T的第一个字符进行比较，若相等，则继续比较两者的后续字符；否则，从主串S的第二个字符开始和模式T的第一个字符进行比较，重复上述过程，直到T中的字符全部

5、比较完毕，则说明本趟匹配成功；或S中字符全部比较完，则说明匹配失败。例：主串S="ababcabcacbab"，模式T="abcac"ababcabcacbabi=3，j=3失败；i回溯到2，j回溯到1ijijij第1趟abcac4.串的应用——BF模式匹配算法ababcabcacbabi=3，j=3失败；i回溯到2，j回溯到1ji第1趟abcac例：主串S="ababcabcacbab"，模式T="abcac"4.串的应用——BF模式匹配算法ababcabcacbabi=2，j=1失败i回溯到3，j回溯到1第2趟ijabcac例：主串S="ababcabcacb

6、ab"，模式T="abcac"4.串的应用——BF模式匹配算法ababcabcacbabi=2，j=1失败i回溯到3，j回溯到1第2趟ijabcac例：主串S="ababcabcacbab"，模式T="abcac"4.串的应用——BF模式匹配算法ababcabcacbababcaci=7，j=5失败i回溯到4，j回溯到1第3趟ijijijijij例：主串S="ababcabcacbab"，模式T="abcac"4.串的应用——BF模式匹配算法ababcabcacbababcaci=7，j=5失败i回溯到4，j回溯到1第3趟ij例：主串S="ababcabcacba

7、b"，模式T="abcac"4.串的应用——BF模式匹配算法ababcabcacbababcaci=4，j=1失败i回溯到5，j回溯到1第4趟ij例：主串S="ababcabcacbab"，模式T="abcac"4.串的应用——BF模式匹配算法ababcabcacbababcaci=4，j=1失败i回溯到5，j回溯到1第4趟ij例：主串S="ababcabcacbab"，模式T="abcac"4.串的应用——BF模式匹配算法ababcabcacbababcaci=5，j=1失败i回溯到6，j回溯到1第5趟ij例：主串S="ababcabcacbab"，模式T="a

8、bcac"