第4篇 串-20060402-3-HB.pptVIP

第四章 串 4.1 串类型定义 4.2 串的表示和实现 4.3 串的模式匹配算法 串的基本概念 字符串（简称串） 是由零个或多个字符组成的有限序列记为： s=”a1a2…a3” (n≥0) 其中ai可以是字符,数字或其它字符 最外边的双引号本身不是串的内容,它们是串的标志,以便将串与标识符(如变量名等)加以区别 长度 串中字符个数。长度为零的串称为空串 空串与空格串 长度不同,一般用符号φ来表示空串””, ” ” 串的基本概念 子串 串s1中任意个连续字符组成的序列s2称为s1的子串，也称s1是s2的主串串s2 如: 空串, “a”、“ab”、“abc”和“abcd”等都是“abcde”的子串 如: a =“BEI” , b=“JING” c=“BEIJING” , d=“BEI JING” 子串在主串中的位置 即子串的第一个字符在主串中的序号 严格说，是某个子串的某个出现在主串里的位置 串的基本概念 相等 当且仅当两个串的长度相等并且各个对应位置上的字符都相同时,这两个串才是相等的 比较 字符串是特殊线性表 表中元素是字符 主要特征是支持一组以串为对象的操作 作业 试写一算法，实现堆存储结构的串的删除操作。 HString strDelete(HString S,int pos,intlen) 选做题。《题集》p28. 4.8 4.2.3 串的块链存储表示 串的块链存储表示 采用链表方式存储串值 结点大小（块大小）:每个链结点的数据域中存放的字符的个数 S D A T E ^ … … ABCD EFGH I # # # … … S ^ 4.2.3 串的块链存储表示 串的块链存储表示 ＃define CHUNKSIZE 80 //可由用户定义的块大小 Typedef struct Chunk{ char ch[CHUNKSIZE]; struct Chunk *next; } Typedef struct { Chunk *head, *tail; //串的头和尾指针 int curlen; //串的当前长度 }LString 4.2.3 串的块链存储表示 串的块链存储表示的特点 存储密度＝串值所占的存储位/实际分配的存储位 结点大小为1,存储密度小，运算处理方便，存储占用大 结点大小为4,存储密度大，运算处理复杂 串的链式存储与顺序存储的比较 除了联接操作（删除、插入）方便外，总体来说不如顺序存储结构灵活 占用存储量大且操作复杂 许多语言提供了标准的字符串库， C++ 语言标准库里的字符串库string Java 语言 脚本语言 许多实际的字符串库采用动态顺序表结构(堆分配存储)作为字符串的表示方式。这样可以支持任意长的字符串，又能比较有效地实现各种重要的字符串操作 4.3 串的模式匹配算法 模式匹配 设有主串s和子串t,子串t的定位就是要在主串s中找到一个与子串t相等的子串。通常把主串s称为目标串,把子串t称为模式串,因此定位也称作模式匹配。 模式匹配成功是指在目标串s中找到一个模式串t；不成功则指目标串s中不存在模式串t。 算法 简单模式匹配 KPM算法 4.3 串的模式匹配算法 简单匹配算法,其基本思路是: 从目标串s=“s0s1…sn-1”的第一个字符开始和模式串t=“t0t1…tm-1”中的第一个字符比较,若相等,则继续逐个比较后续字符； 否则从目标串s的第二个字符开始重新与模式串t的第一个字符进行比较。 依次类推,若从模式串s的第i个字符开始,每个字符依次和目标串t中的对应字符相等,则匹配成功,该算法返回i；否则,匹配失败,函数返回-1。 简单匹配算法 采用定长顺序存储结构，不依赖于其他串操作的匹配算法 int index( SString s, SString t, int pos) { //返回子串t在主串s中第pos个字符之后的位置若不存在，则函数值为0 //其中，t非空，1=pos=StrLength(s) int i=pos, j=1; while (i=s[0] j=t[0]) { if (s[i] == t[j]) { i++; j++; } else { i=i-j+2; j=1; } } if (jt[0]) return i-t[0];