云大数据结构课程教学课件串.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 串定义 串（string，或称字符串）是 n 个字符的有限序列。通常记作　　　s = ‘a1 a2 … an ‘ (n≥0) 串的长度、空串（null string）、子串、主串 求子串在串中的位置 例如：a,b,c,d为如下的串： a = ‘BEI’; b = ‘JING’ ; c = ‘BEIJING’ ; d = ‘BEI JING’ 串相等，空格串，空串（Ф ） 串中任意个连续的字符组成的子序列 字符在序列中的序号为该字符在串中的位置 串的逻辑结构和线性表的差别仅在于串中的数据对象定为“字符集” 在串的基本操作中，以“串的整体”作为操作对象。 * 串的抽象数据类型 ADT String { 　 数据对象：D＝{ai| ai∈CharacterSet, i=1,2,...,n, n≥0 } 数据关系：R1＝{ ai, aj | ai,aj∈D, i=2,...,n } 基本操作： 　　1、StrAssign (T,chars) 　　　 初始条件：chars 是串常量。 　　　 操作结果：赋于串T的值为 chars。 2、StrCopy (T, S) 　　　 初始条件：串 S 存在。 　　　 操作结果：由串 S 复制得串 T。 3、DestroyString (S) 　　　 初始条件：串 S 存在。 　　　 操作结果：串 S 被销毁。 * 串的抽象数据类型 4、StrEmpty (S) 　　　初始条件：串 S 存在。 　　　操作结果：若 S 为空串，则返回 TRUE，否则返回 FALSE。 5、StrCompare (S, T) 　　　初始条件：串 S 和 T 存在。 　　　操作结果：若ST，则返回值=0；若S=T，则返回值0；若ST，则返回值0。 6、StrLength (S) 　　　初始条件：串 S 存在。 　　　操作结果：返回串 S 序列中的字符个数，即串的长度。 7、ClearString (S) 　　　初始条件：串 S 存在。 　　　操作结果：将 S 清为空串。 串值大小是按词典次序进行比较的，如： 　　　　StrCompare(data,Stru)0 　　　　StrCompare(cat, case)0 * 串的抽象数据类型 8、Concat (T, S1, S2) 　　初始条件：串 S1 和 S2 存在。 　　操作结果：用 T 返回由 S1 和 S2 联接而成的新串。 9、SubString (Sub, S, pos, len) 　　初始条件：串S存在，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。 　　操作结果：用 Sub 返回串S的第 pos 个字符起长度为 len 的子串。 10、Index (S, T, pos) 　　初始条件：串S和T存在，T 是非空串，1≤pos≤StrLength(S)。 　　操作结果：若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0。 11、Replace (S, T, V) 　　初始条件：串 S，T 和 V 存在，T 是非空串。 　　操作结果：用V替换主串S中出现的所有与T相等的不重叠的子串。 Concat(T,“class,“room)得到的结果是：T =“classroom。 SubString(Sub,commander,4,3)得到的结果是Sub=man Index(This is a pen,is,pos) 若S=abcacabcaca，T=abca和V=x，则置换之后的S=xcxca * 串的抽象数据类型 12、StrInsert (S, pos, T) 　　　初始条件：串 S 和 T 存在，1≤pos≤StrLength(S)＋1。 　　　操作结果：在串 S 的第 pos 个字符之前插入串 T。 13、StrDelete (S, pos, len) 　　　初始条件：串 S 存在，1≤pos≤StrLength(S)-len+1。 　　　操作结果：从串 S 中删除第 pos 个字符起长度为 len 的子串。 ? } ADT String * 串的定位 串的定位－Index(S,T,pos)算法的基本思想为：从主串S中取“第 i 个字符起、长度和串T相等的子串”和串T比较，若相等，则求得函数值为 i，否则 i 值增1直至找到和串T相等的子串或者串S中不存在和T相等的子串为止 。 SubString(sub,S,i,StrLength(T)) StrCompar