第四章串 4.1串类型的定义 4.2串的表示和实现 4.2.1定长顺序存储表示 4.2.2堆分配存储表示 4.3串的模式匹配算法 讨论基本的串处理操作和两种存储结构
第四章 串 4.1 串类型的定义 4.2 串的表示和实现 4.2.1 定长顺序存储表示 4.2.2 堆分配存储表示 4.3 串的模式匹配算法 讨论基本的串处理操作和两种存储结构
4.1串类型的定义 非数值处理的对象基本上是字符串数据 串( string)(或称字符串) 由零个或多个字符组成的有限序列 己为 (n>=0) a1(1<=i<=n)是字母,数字或其它字符 n称为串的长度,n=0的串称为空串( Null string) 子串一串中任意个连续字符组成的子序列 包含子串的串叫主串 子串在主串中的位置 子串的第一个字符在主串中的序号
4.1 串类型的定义 非数值处理的对象基本上是字符串数据 串(string)(或称字符串)---- • 由零个或多个字符组成的有限序列 • 记为: s = ‘ a1a2...an ’ (n>=0) • ai(1<=i<=n)是字母,数字或其它字符 • n称为串的长度,n=0的串称为空串(Null string) 子串----串中任意个连续字符组成的子序列 • 包含子串的串叫主串 • 子串在主串中的位置 ---- • 子串的第一个字符在主串中的序号
串的例子 例如:a,b,C,d四个字符串为 a=BEI b=JING C=BEIJING, d=BEI JING 它们的长度分别为3,4,7,8 a和b都是c和d的子串 a在c和d中的位置都是1 b在c中的位置是4,而b在d中的位置是5 注意:单引号是为字符串区别于变量名而设,它不是字符串的内容 称两个串是相等的 当且仅当这两个串每个字符对应相等
串的例子 例如:a,b,c,d 四个字符串为 • a= ‘BEI’ , b=‘JING’ • c= ‘BEIJING’ , d=‘BEI JING’ • 它们的长度分别为 3,4,7,8 • a和b都是c和d的子串 • a在c和d中的位置都是1 • b在c中的位置是4,而b在d中的位置是5 • 注意:单引号是为字符串区别于变量名而设,它不是字符串的内容 称两个串是相等的 --- • 当且仅当这两个串每个字符对应相等
串的抽象数据类型 数据对象为字符集的线性表 ADT String i 数据对象:D={a1|a1 Characteset,i=1,2 数据关系:R={<a1,a1>1a1D,i=2,…n} 基本操作: StrAssign(&T, chars); StrCopy(&T, s); StrEmpty(S); StrCompare(s, T) StrEngth(s) ClearString(&s); Concat(&T, S1, S2); Substring(&Sub, S, pos,len); Index(s,T, pos); Replace(&s,T, v) StrInsert(&S, pos,T); StrDelete(&S, pos, len) DestroyString(&s) JADT String
串 的 抽 象 数 据 类 型 --- 数据对象为字符集的线性表 ADT String { 数据对象：D = {ai | ai CharacteSet,i=1,2,...n, n>=0} 数据关系： R1 = {＜ ai-1. , aj＞| ai D, i=2,...n}。 基本操作： • StrAssign(&T,chars); StrCopy(&T,S); • StrEmpty (S); StrCompare(S,T); • StrLength(S); ClearString(&S); • Concat(&T,S1,S2); Substring(&Sub,S,pos,len); • Index(S,T,pos); Replace(&S,T,V); • StrInsert(&S,pos,T); StrDelete(&S,pos,len); • DestroyString(&S) }ADT String
基本操作的功能说明1 StrAssign(&t, chars) 初始条件: chars是字符串常量 操作结果:生成一个其值等于 chars的串T StrCopy(&t,s) 初始条件:字符串S已经存在 操作结果:由串S复制得串T。 StrEmpty (s) 初始条件:字符串S已经存在。 操作结果:若S为空串,则返回TRUE,否则返回 FALSE StrCompare(s,T) 初始条件:字符串S和T存在。 作结果:若ST,则返回值>0;若S=T,则返回值=0;否则返回
基本操作的功能说明1 StrAssign(&T,chars) • 初始条件: chars是字符串常量。 • 操作结果: 生成一个其值等于chars的串T。 StrCopy(&T,S) • 初始条件: 字符串S已经存在。 • 操作结果: 由串S复制得串T。 StrEmpty (S) • 初始条件: 字符串S已经存在。 • 操作结果: 若S为空串，则返回TRUE,否则返回FALSE。 StrCompare(S,T) • 初始条件: 字符串S和T存在。 • 操作结果: 若S>T,则返回值>0;若S=T,则返回值=0;否则返回 值<0