C_char_4串.pptVIP

* 4.1 串类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 第四章 串 4.1串类型的定义 1.串的逻辑结构定义 串 : 是由零个或多个字符组成的有限序列. 例： S=“a1a2a3......an-1an” NOTE: 串是数据对象为字符集的特殊的线性表 串的长度:串中字符的个数 空串:串中包含零个字符的串 主串和子串 :串中任意个连续的字符组成的子序列称为该串的子串,包含子串的串相应地称为主串 例：S=“DATA STRUCTURE”??? “DATA”? 是 S 的子串， S 称为主串 4.1串类型的定义 字符在串中的位置:字符在序列中的序号称为该字符在串中的位置 子串在主串中的位置:以子串在主串中的第一次出现时,子串的第一个字符在主串中的位置来表示 ? 例：S=“ABCDEFGCDEHIE”;??“CDE” 在 S 中的位置是？ 4.1 串类型的定义 ADT String { 数据对象： D＝{ ai |ai∈CharacterSet, i=1,2,...,n, n≥0 } 数据关系： R1＝{ ai-1, ai | ai-1, ai ∈D, i=2,...,n } 串是有限长的字符序列，由一对双引号相括，如: ? a string ? 基本操作： StrAssign (T, chars) StrCopy (T, S) DestroyString(S) StrEmpty (S) StrCompare (S, T) StrLength(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) ClearString (S) } ADT String 2.串的常见操作 NOTE: 下面的基本操作,都只是一种形式定义，其实现依赖于串所采用的存储结构。 1) StrAssign(T, chars)初始条件：chars 是字符串常量。操作结果：把 chars 值赋给 T。 2) StrCopy(T, S)初始条件：串S存在。操作结果：由串S复制得串T。 3) DestroyString(S) 初始条件：串S存在。操作结果：串S被销毁。 4) StrEmpty(S) 初始条件：串S存在。操作结果：若S 为空串，则返回true，否则返回false。 ? ?表示空串，空串的长度为零。 2.串的常见操作 5) StrCompare(S, T)初始条件：串S和T存在。操作结果：若S ? T, 则返回值 ? 0; 若S ? T，则返回值 ? 0；若S ? T，则返回值 ?0 例如：StrCompare(“data”, “state”) 0 StrCompare(“cat”, “case”) 0 6) StrLength (S) 初始条件：串 S 存在。操作结果：返回 S 的元素个数，称为串的长度。 7) Concat(T,S1,S2)初始条件：串S1和S2存在。操作结果：用 T 返回由 S1 和 S2 联接而成的新串。 例如： Concat( T, ?man?, ?kind?) 求得 T = ?mankind? 8) SubString(Sub,S,pos,len)初始条件：串S存在， 1≤pos≤StrLength(S) 且 0≤len≤StrLength(S)-pos+1。 操作结果：用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串.子串为“串”中的一个字符子序列 例如：SubString( sub, ?commander?, 4, 3) 求得 sub = ?man? ; SubString( sub, ?commander? , 1, 9) 求得 sub = ?commander? SubString( sub, ?commander?, 9, 1) 求得 sub = ?r? 9) Index (S, T, pos) 初始条件：串S和T存在，T是非空串，1≤pos≤StrLength(S)。操作结果： 若主串 S 中存在和串 T 值相同的子串, 则返回它在主串 S 中第pos个字符之后第一次出现的位置; 否则函数值为0。 “子串在主串中的位置”意指子串中的第一个字符在主串中的位序。假