《数据结构》课件1第4章 串

第4章串串的定义串的存储结构串的模式匹配4.1串的定义2描述各种信息的文字符号序列通常称为字符串，简称串。在计算机上的非数值处理一般都是字符串数据。串是一种内容受限的线性表。串是由零个或多个字符构成的有限序列，记为：s="a1a2…an"例如："thisisastring"，"is"

，"

"

串长：串值中字符个数（n）空串：长度为0的串空格串：仅含有空格字符的串(n不为0)子串：串中若干相邻字符组成的子序列主串：包含子串的串子串中第0个字符在主串中出现的位置称为此子串在该主串中的位置。

串名串值串之间的大小关系：设s1="a0a1…am-1"，s2="b0b1…an-1"若m=n且ai=bi，i=0，1，…m-1，则s1=s2(2)满足下面条件之一，则s1<s2m<n，且ai=bi，i=0，1，…m-1 例如："abc"与"abcd"存在某个0<k≤min(m，n)，使得ai=bi，i=0，1，…k-1，ak<bk

例如："abc"与"adc"(3)不满足以上条件，则s1>s24.1串的定义3串的抽象数据类型定义4.2串的存储结构1.串的顺序存储4串的顺序存储结构简称为顺序串。类似于顺序表，顺序串也是用一组地址连续的存储单元存储串中的字符序列。为了表示串的结尾，一般在串尾存储一个不会在串中出现的特殊字符作为串的终结符。例如，C++语言中用’\0’表示串的结束。4.2串的存储结构2.串的链式存储5串采用链式存储结构存储时称为链串，可采用带头结点的单链表来表示。链串的组织形式与一般的单链表类似，主要区别在于链串中的一个结点可以存储多个字符。通常将链串中每个结点所存储的字符个数称为结点大小。在链式存储方式中，结点大小的选择直接影响着串处理的效率。存储密度小（如结点大小为1）时，运算处理方便，但存储占用量大。存储密度大时，一些基本操作（如插入、删除）的实现有所不便，而且可能引起大量字符移动结点大小为4的链表：结点大小为1的链表：结点大小大于1时，链表的最后一个结点不一定全被串值占满，未占用的数据域里应补上不属于串的字符集的特殊符号4.3串的模式匹配6设T="t0t1…tn-1"，P="p0p1…pm-1"，其中0<m≤n。如要在字符串T中查找是否有与字符串P相同的子串，则称字符串T为目标串或主串，称字符串P为模式串或子串，在T中从位置pos开始查找与P相同的子串第一次出现的位置的过程称为字符串模式匹配。4.3串的模式匹配1.BF算法7Brute-Force算法简称为BF算法，也称简单模式匹配算法。BF算法的基本思想是蛮力匹配，即从主串s的第一个字符开始和模式串t的第一个字符进行比较，若相等，则继续逐个比较后续字符；否则，从主串s的第二个字符开始重新与模式串t的第一个字符进行比较，以此类推。若从主串s的第i个字符开始，每个字符依次和模式串t中的对应字符相等，则匹配成功，返回位置i；否则，匹配失败，返回-1。第1趟TabaababP

abab第2趟TabaababPabab第3趟TabaababPabab第4趟TabaababPabab4.3串的模式匹配1.BF算法8(1)用start保存主串比较的开始位置，初值为0。(2)用i和j指示主串s和模式串t中当前正待比较的字符下标，i和j的初值均为0。(3)重复下述操作，直到s或t的所有字符比较完毕：①若s[i]和t[j]相等，则继续比较s和t的下一对字符；②否则，下标i和j分别回溯，开始下一趟匹配。(4)若t中所有字符全部比较完毕，则匹配成功，返回本趟匹配的起始位置；否则匹配失败，返回0。【算法步骤】intBF(strings,stringt){ inti=0,j=0,start=0; while(i<s.length()&&j<t.length()) { if(s[i]==t[j]) { j++;i++; } else { start++; i=start; j=0; } } if(j==t.length()) returnstart+1;

else return0;}4.3串的模式匹配1.BF算法9最好情况每趟不成功的匹配都发生在模式串t的第一个字符与主串s中相应字符的比较。假设从主串的第i个位置开始与模式串匹配成功，则前在i－1趟不成功的匹配中共比较了i－1次，第i趟成功的匹配中共比较了m次，总比较次数为i－1＋m。对于成功匹配的主串，其起始位置由1到n－m＋1，假设这n－m＋1个位置上的匹配成功概率相等，则最好情况下匹配成功的平均比较次数为：【算法分析】设主串s长度为n，模式串t长度为m。时间复杂度为n+m

时间复杂度为n×m4.3串的模式匹配2.KMP算法10BF算法简单但效率低。造成BF算法效率低的主要原因是回溯，即在某趟匹配失败后，主串s要回溯到本趟匹配开始字符的下一个字符，模式串t要回溯到第一个字符，而这些回溯往往是不必要的。改进算法——KMP消除回溯

本章小结(1)串是一种内容受限的线性表，它限定了表中的元素为字符。(2)串有两种基本存