数据结构第四章2009.ppt

第四章 串; 4.1 串类型的定义;串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的序号（或位置）。例如，设A和B分别为 A=“This is a string” B=“is” 则B是A的子串，A为主串。B在A中出现了两次，其中首次出现所对应的主串位置是2。因此，称B在A中的序号（或位置）为2 特别地，空串是任意串的子串，任意串是其自身的子串。 串比较：相等、大小;若串S=’computer’，其不含空串的子串数目是______。 ;串的抽象数据定义P71 ADT String { 数据对象： D＝{ ai |ai∈CharacterSet, i=0,1,,...,n-1, n≥0 } 数据关系： R1＝{ ai-1, ai | ai-1, ai ∈D, i=1,...,n-1 } 基本操作： 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 的值。 ;; DestroyString (S) 初始条件：串 S 存在。 操作结果：串 S 被销毁。 ; StrEmpty(S)初始条件：串S存在。操作结果：若 S 为空串，则返回TRUE， 否则返回 FALSE。; StrCompare(S,T)初始条件：串S和T存在。操作结果：若S ? T，则返回值 ? 0；  若S ? T，则返回值 ? 0；  若S ? T，则返回值 ? 0。; StrLength(S) 初始条件：串S存在。 操作结果：返回 S 的元素个数， 称为串的长度。; Concat(T,S1,S2) 初始条件：串 S1 和 S2 存在。 操作结果：用 T 返回由 S1 和 S2 联接而成的新串。;;例如： SubString( sub, “commander”,3, 3) 求得 sub = “man” ； SubString( sub, “commander”, 0, 9) 求得 sub = “commander”； SubString( sub, “commander”, 8, 1) 求得 sub = “r”；;SubString(sub, “commander”,3, 7) sub = ? ; Index(S,T,pos)初始条件：串S和T存在，T是非空串， 0≤pos≤StrLength(S)-1。操作结果： 若主串 S 中存在和串 T 值相同 的子串, 则返回它在主串 S 中第pos个 字符之后第一次出现的位置； 否则函数值为-1。 ;假设 S = ?abcaabcaaabc?, T = ?bca? ; Replace(S,T,V) 初始条件：串S, T和 V 均已存在，  且T是非空串。 操作结果：用V替换主串S中出现 的所有与（模式串）T  相等的不重叠的子串。;例如：; StrInsert (S, pos, T)初始条件：串S和T存在，