二、串的抽象数据定义 · ADT String{ 数据对象:D={a1|an∈ Character Set. jE=1,2,,n,20} 数据关系:R={<an1a1>|a1,a1∈D,i=2,,ny 基本操作:· StrAssign(&T, chars∥串赋值 初始条件: chars是字符串常量。 ●操作结果:把 chars赋为T的值。 StrCopy(&T,S川∥串复制 初始条件:串S存在。 ●操作结果:由串S复制到串T。 北京邮电大学自动化学院
北京邮电大学自动化学院 6 ⚫ ADT String { D＝{ ai |ai∈CharacterSet,i=1,2,...,n, ≥0 } ⚫ 数据关系： R1＝{ < ai-1 , ai > | ai-1 , ai ∈D, i=2,...,n } 二、串的抽象数据定义 ⚫ 基本操作: ⚫ StrAssign (&T, chars)//串赋值 ⚫ 初始条件：chars 是字符串常量。 ⚫ 操作结果：把 chars 赋为 T 的值。 ⚫ StrCopy (&T, S)//串复制 ⚫ 初始条件：串 S 存在。 ⚫ 操作结果：由串S复制到串T。 ⚫ 数据对象：
、串的抽象数据定义 StrCompare(s,T)∥串比较 ●初始条件:串S和T存在。 操作结果:若S>T,则返回值>0; ●若S=T,则返回值=0; 若S<T,则返回值<0。 StrEngth(S)∥求串长 初始条件:串S存在 ●操作结果:返回S的元素个数,称为串的长度。 北京邮电大学自动化学院
北京邮电大学自动化学院 7 ⚫ StrCompare (S, T)//串比较 ⚫初始条件：串 S 和 T 存在。 ⚫ 操作结果：若S T，则返回值 0； ⚫ 若S = T，则返回值 = 0； ⚫ 若S T，则返回值 0。 二、串的抽象数据定义 ⚫ StrLength (S) //求串长 ⚫ 初始条件：串 S 存在。 ⚫ 操作结果：返回 S 的元素个数， 称为串的长度
、串的抽象数据定义 Concat(&T,S1S2)∥串连接 ●初始条件:串S1和S2存在 操作结果:用T返回由S1和S2联接而成的新串。 SubString(&Sub, S, pos, len) 初始条件:串S存在,1pos≤ StrEngth(S),且 0sen≤ StrEngth(S)-pos+1。 ●操作结果:用Sub返回串S的第pos个字符起长度 为len的子串。 北京邮电大学自动化学院
北京邮电大学自动化学院 8 ⚫ Concat (&T, S1 , S2 )//串连接 ⚫ 初始条件：串 S1 和 S2 存在。 ⚫ 操作结果：用 T 返回由 S1 和 S2 联接而成的新串。 二、串的抽象数据定义 ⚫ SubString (&Sub, S, pos, len) ⚫ 初始条件：串 S 存在，1≤pos≤StrLength(S) ，且 0≤len≤StrLength(S)-pos+1。 ⚫ 操作结果：用 Sub 返回串 S 的第 pos 个字符起长度 为 len 的子串
、串的抽象数据定义 ● Destroy String(8S) StrEmpty(s) ●初始条件:串S存在。 初始条件:串S存在。 ●操作结果:串S被销毁。 操作结果:若S为空串,则返 回true,否则返回fase e Clear String(&S) ●初始条件:串S存在。 ●操作结果:将S清为空串。 .3ADT String 北京邮电大学自动化学院
北京邮电大学自动化学院 9 ⚫ DestroyString (&S) ⚫ 初始条件：串 S 存在。 ⚫ 操作结果：串 S 被销毁。 二、串的抽象数据定义 ⚫ StrEmpty (S) ⚫ 初始条件：串S存在。 ⚫ 操作结果：若 S 为空串,则返 回 true,否则返回 false。 ⚫ ClearString (&S) ⚫ 初始条件：串S存在。 ⚫ 操作结果：将S清为空串。 ⚫ } ADT String
三、串的基本操作 ●在上述抽象数据类型定义的13种操作中, 求串长 StrEngth 串赋值 StrAssign、 °串联接 Concat ●串比较 StrCompare、 求子串 SubString 等五种操作构成串类型的最小操作子集。即:这些操作不可 能利用其他串操作来实现,反之,其他串操作(除串清除 ClearString和串销毁 Destroy String外)可在这个最小操作 子集上实现。 北京邮电大学自动化学院 10
北京邮电大学自动化学院 10 ⚫ 在上述抽象数据类型定义的13种操作中， 三、串的基本操作 ⚫ 串赋值StrAssign、 ⚫ 串比较StrCompare、 ⚫ 求串长StrLength、 ⚫ 串联接Concat ⚫ 求子串SubString ⚫ 等五种操作构成串类型的最小操作子集。即：这些操作不可 能利用其他串操作来实现，反之，其他串操作（除串清除 ClearString和串销毁DestroyString外）可在这个最小操作 子集上实现