Chapter04_串_数据结构(C语言版)_严蔚敏_配套课件.pdf

第四章 串 4.1 串类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.1 串类型的定义 一、串的定义 二、串的抽象数据类型的定义如下 一、串的定义 串(string)(或字符串），是由零个或多个字符组成的有限 序列。一般记为 s ‘a1a2a3…an’ (n≥0) 其中,s是 串名,单引号括起来的字符序列是串的值； ai可以是字母,数字或其他字符; 串中的字符个数称为串的长度; 零个字符的串称为空串 （Null string)，其长度为零; 串中任意个连续的字符组成的子序列称为该串的子串； 包含子串的串相应地称为主串； 字符在序列中的序号为该字符在串中的位置； 子串在主串中的位置则以子串的第一个字符在主串中的位 置来表示； 由一个或多个空格字符组成的串称为空格串； 例：串a,b,c,d,e五个串如下: a ‘very difficult’; b ‘ ’; c ‘’; d ‘very’; e ‘difficult’; 串a的长度为14; 串b是长度为3的空格串; 串c是空串,长度为0; 串d和e是串a的子串，串d在串a中的位置 是1，串e在串a中的位置是6。 • 串相等：当且仅当两个串的值相等，即只有当两个 串的长度相等，并且各个对应位置的字符都相等时 才相等； • 空串是任意串的子串； • 任意串又是自己的子串 注意： ⑴串值必须用一对单引号括起来，但单引号本身不属 于串； ⑵空串与空白串截然不同，空串不包含任何字符。 二、串的抽象数据类型的定义如下： ADT String { 数据对象： D ＝{ a |a ∈CharacterSet, i i i=1,2,...,n, n ≥0 } 数据关系： R ＝{ a , a | a , a ∈D, 1 i-1 i i-1 i i=2,...,n } 基本操作： StrAssign (T, chars) DestroyString(S) StrCopy (T, S) StrLength(S) StrCompare (S, T) Concat (T, S1, S2) StrEmpty (S) 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 StrAssign (T, chars) 初始条件：chars 是字符串常量。 操作结果：把 chars 赋为 T 的值。 StrCopy (T, S) 初始条件： 串S 存在。 操作结果：由串 S 复制得串 T。 DestroyString (S) 初始条件： 串S 存在。 操作结果： 串S 被销毁。 StrEmpty (S) 初始条件： 串S存在。 操作结果：若 S 为空串，则返回 TRUE; 否则返回 FALSE 。 ′′表示空串，空