文档介绍：串类型的定义
串的表示和实现
串的模式匹配算法
本章小结
习题四
基本概念及串类型的定义串类型的定义
串、串名、串值、串的长度、空串、子串、主串、序号(位置)、串相等、空格串。
串(String)是由零个或多个字符组成的有限序列。一般记为:S=‘a1a2a3…an’,其中S 是串名,双引号括起来的字符序列是串值;ai(1≦i≦n)可以是字母、数字或其它字符;串中所包含的字符个数称为该串的长度。长度为零的串称为空串(Empty String),它不包含任何字符。串中任意个连续字符组成的子序列称为该串的子串,包含子串的串相应地称为主串。特别地,空串是任意串的子串,任意串是其自身的子串。通常称字符在序列中的序号为该字符在串中的位置。子串在主串中的位置,则以子串的第一个字符在主串中的
位置来表示。
例如:a,b,c,d为如下的4个串:
a=‘BEI’, b=‘JING ’
c=‘BEIJING’, d=‘BEI JING’
它们的长度分别为:3,4,7和8;并且a和b都是c和d的子串,a在c和d中的位置都是1,而在b在c中的位置是4,在d中的位置是5。
称两个字符串是相等的,当且仅当这两个串的值相等。也就是说,只有当两个串的长度相等,且对应位置上的字符也都相等时才相等。例如,上面的串a,b,c,d彼此都不相等。由一个或多个空格组成的串被称为空格串。空格串不是空串,例;‘’和‘’不同。
串的逻辑结构和线性表极为相似,区别仅在于串的数据对象的类型限制为字符。
串的抽象数据类型的定义如下:
ADT String {
数据对象:D={ ai |ai∈CharacterSet,
i=1,2,...,n, n≥0 }
数据关系: R1={ < ai-1, ai > | ai-1, ai ∈D,
i=2,...,n }
基本操作: StrAssign (&T, chars)
初始条件:chars 是字符串常量。
操作结果:把 chars 赋为 T 的值。
DestroyString(&S)
初始条件:串 S 存在。
操作结果:串 S 被销毁。
StrCopy (&T, S)
初始条件:串 S 存在。
操作结果:由串 S 复制得串 T。
StrLength(S)
初始条件:串 S 存在。 操作结果:返回 S 的元素个数,称为串的长度。
StrEmpty (S) 初始条件:串S存在。 操作结果:若 S 为空串,则返回 true, 否则返回 false。
pare (S, T)
初始条件:串 S 和 T 存在。 操作结果:若S T,则返回值 0;
若S T,则返回值 0; 若S T,则返回值 0。
例如:pare(data, state) < 0
pare(cat, case) > 0
pare(cat , cat )=0
StrEmpty (S) 初始条件:串S存在。 操作结果:若 S 为空串,则返回 true, 否则返回 false。
表示空串,空串的长度为零。
Concat (&T, S1, S2)
初始条件:串 S1 和 S2 存在。 操作结果:用 T 返回由 S1 和 S2首尾相接而成的新串。
例如:Concate( T, man, kind)
求得 T = mankind
SubString (&Sub, S, pos, len)
初始条件:串 S 存在,1≤pos≤StrLength(S)
且 0≤len≤StrLength(S)-pos+1。
操作结果:用 Sub 返回串 S 的从第 pos 个字符起长度为 len 的子串。
例如: SubString( sub, commander , 4, 3)
求得 sub = man ;
ClearString (&S)
初始条件:串S存在。
操作结果:将S清为空串。 Index (S, T, pos) 初始条件:串S和T存在,T是非空串, 1≤pos≤StrLength(S)。 操作结果: 若主串 S 中存在和串 T 值相同的子串, 则返回它在主串 S 中第pos个字符之后第一次出现的位置; 否则函数值为0。
StrDelete (&S, pos, len)
初始条件:串S存在, 1≤pos≤StrLength(S)-len+1。 操作结果:从串S中删除第pos个字符起长度为len的子串。
Replace (&S, T, V)
初始条件:串S, T和 V 均已存在,且 T 是非空串。 操作结果:用 V 替换主串 S 中出现的所有与(模式串)T相等的不重叠的子串。
StrInsert (&S, po