山东理工大学：《数据结构》课程教学课件（数学）CH4 串

第四章串 41串的类型定义 42$的表和实观 43串的模式匹配算法 作业

4.1串类型的定义 、 串的基本概念 串(String)是零个或多个字符组成的有限序列。 一 般记作S=‘a1a2agan’,其中S是串名， 单引号括起来的字符序列是串值；a:(1≤i≤n) 可以是字母、数字或其它字符；串中所包含的字 符个数称为该串的长度。长度为零的串称为空 串(Empty String),不包含任何字符。 注意：空串和空格串不同，如‘’和”分 别表示长度为1的空格串和长度为0的宠串(O)

(String)是零个或多个字符组成的有限序列。 一般记作 S= ‘a1a2a3.an ’ ，其中 S 是串名， 单引号括起来的字符序列是串值；ai(1≤i≤n) 可以是字母、数字或其它字符；串中所包含的字 符个数称为该串的 。长度为零的串称为 (Empty String)，不包含任何字符。 4.1 串类型的定义 一、串的基本概念 空串和空格串不同，如‘ ’和‘’分 别表示长度为1的空格串和长度为0的空串（○）

串中任意个连续字符组成的子序列称为该串的子串， 包含子串的串相应地称为主串。通常将子串在主串中首次 出现时，该子串的首字符在主串中对应的序号，定义为 子串在主串中的位置（或序号）。 例如：A=‘This is a string’，B= ‘3’ 则B是A的子串，A为主串。B在A 中出现了两次，其中首次出现所对应的主串位 释易地， 因此，B在A中的位置为3。 空串是任意串的子串，任意串是其自身的子串

空串是任意串的子串，任意串是其自身的子串。 串中任意个连续字符组成的子序列称为该串的 ， 包含子串的串相应地称为 。通常将子串在主串中首次 出现时，该子串的首字符在主串中对应的序号，定义为 （或序号）。 A = ‘ ’ ，B = ‘ ’ 则 B 是 A 的子串，A 为主串。B 在 A 中出现了两次，其中首次出现所对应的主串位 置是 3 。因此，B 在 A 中的位置为 3

二、串的抽象数据类型定义如下： ADT String 数据对象： D={aa∈CharacterSet, i=1,2,.,n, n≥0} 数据关系： R={|a.,a∈D, i=2,.,n}

二、串的抽象数据类型定义如下： ADT String { 数据对象： D＝{ ai |ai∈CharacterSet, i=1,2,.,n, n≥0 } 数据关系： R1＝{ | ai-1 , ai ∈D, i=2,.,n }

基本操作： StrAssign (&T,chars) DestroyString(&S) StrCopy (&T,S) StrLength(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) 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) 初始条件：串$存在。 操作结果：串$被销毁

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

StrEmpty (S) 初始条件：串$存在。 操作结果：若$为空串，则返回 TRUE,否则返▣ FALSE

StrEmpty (S) 初始条件：串S存在。 操作结果：若 S 为空串，则返回 TRUE，否则返回 FALSE