《数据结构》课程教学资源（PPT课件讲稿）第四章 串

41串的抽象数据类型的定义 42串的表示和实现 43串的模式匹配算法

4.1 串的抽象数据类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法

41串的抽象数据举型的完Y如下 串是有限长的字符序 ADT String i 列,由一对单引号相 数据对象 括,如: a string D=&a; la; E CharacterSet 1=1.2 n>0} 数据关系 R1={|a1,a;∈D, 9·9

4.1 串的抽象数据类型的定义如下： ADT String { 数据对象： D＝{ ai |ai∈CharacterSet, i=1,2,...,n, n≥0 } 数据关系： R1＝{ | ai-1 , ai ∈D, i=2,...,n } 串是有限长的字符序 列，由一对单引号相 括，如: a string

基本操作 StrAssign(&T, chars) Destroy String(&s) StrCopy(&t, s) Strengh sth(s) StrCompare (S, T) Concat(&T, S1, S2) StrEmpty(S

基本操作： StrAssign (&T, chars) StrCopy (&T, S) DestroyString(&S) StrEmpty (S) StrCompare (S, T) StrLength(S) Concat (&T, S1, S2)

SubString(&Sub, S, pos, len) ClearString(&s) Index(s, T, pos Replace(&s, T, v) StrInsert(&s, pos, T) StrDelete(&s, pos, len) 3 ADT String

SubString (&Sub, S, pos, len) Index (S, T, pos) Replace (&S, T, V) StrInsert (&S, pos, T) StrDelete (&S, pos, len) ClearString (&S) } ADT String

StrAsSign(&t, chars 初始条件: chars是字符串常量。 操作结果:把 chars赋为T的值

StrAssign (&T, chars) 初始条件：chars 是字符串常量。 操作结果：把 chars 赋为 T 的值

StrCopy(&T,s) 初始条件:串S存在。 操作结果:由串S复制得串T

StrCopy (&T, S) 初始条件：串 S 存在。 操作结果：由串 S 复制得串 T

DestroyString( &s) 初始条件:串S存在。 操作结果:串S被销毁

DestroyString (&S) 初始条件：串 S 存在。 操作结果：串 S 被销毁

StrEmpty 初始条件:串S存在 操作结果:若S为空串,则返回TRUE 否则返回 FALSE。 表示空串,空串的长度为零

StrEmpty (S) 初始条件： 串 S 存 在 。 操作结果：若 S 为空串，则返回TRUE， 否则返回 FALSE。  表示空串，空串的长度为零

StrCompare (S, T) 初始条件:串S和T存在。 操作结果:若S>T,则返回值>0; 若S=T,则返回值=0; 若S0

StrCompare (S, T) 初始条件： 串 S 和 T 存 在 。 操作结果：若S  T，则返回值  0； 若S = T，则返回值 = 0； 若S  T，则返回值  0。 例如：StrCompare(data , state) 0

StrEngth 初始条件:串S存在。 操作结果:返回S的元素个数, 称为串的长度

StrLength (S) 初始条件： 串 S 存 在 。 操作结果：返回 S 的元素个数， 称为串的长度