数据结构--第四章串演示幻灯片.ppt

(8) 清空函数 StrClear(s) /*将串s置为空串 */ HString *s; { if (s-ch!=NULL) free(s-ch); s-ch=NULL; s-len=0; return(1); } (9) 连接函数 StrCat(s，t) /*将串t联接在串s的后面 */ HString *s，t; {int i;char *temp;? temp=(char *)malloc(s-len + t.len); if (temp==NULL) return(0); for (i=0;is-len;i++) temp[i]=s-ch[i]; for (i=s-len;is-len + t.len;i++) temp[i]=t.ch[i-s-len]; s-len+=t.len; free(s-ch);s-ch=temp; return(1); } (10) 求子串函数 SubString(sub，s，pos，len) /*将串s中序号pos起len个字符复制到sub中 */ HString *sub，s; int pos，len; {int i; if (sub-ch!=NULL) free(sub-ch); if (pos0 || poss.len || len1 || lens.len-pos) { sub-ch=NULL;sub-len=0;return(0);} else {sub-ch=(char *)malloc(len); if (sub-ch==NULL) return(0); for (i=0;ilen;i++) sub-ch[i]=s.ch[i+pos]; sub-len=len; return(1); }} 第4章 串 4.1 串的定义 4.2 抽象数据类型串的实现 4.2.1 定长顺序串 4.2.2 堆串 4.2.3 块链串 4.3 串的应用举例：文本编辑 4.1 串的定义 串(String)是零个或多个字符组成的有限序列。 一般记为： S=‘a1a2…an’ (n≥0) 子串：串中任意个连续的字符组成的子序列称为该串的子串。 主串：包含子串的串相应地称为主串。 其中S为串名，用单引号括起来的为串值， n为串的长度。 通常将字符在串中的序号称为该字符在串中的位置。 空格串：由一个或多个称为空格的特殊字符组成的串。 空串： n=0时的串为空串 4.1 串的定义 串(String)是零个或多个字符组成的有限序列。 一般记为： S=‘a1a2…an’ (n≥0) 子串：串中任意个连续的字符组成的子序列称为该串的子串。 主串：包含子串的串相应地称为主串。 其中S为串名，用单引号括起来的为串值， n为串的长度。 通常将字符在串中的序号称为该字符在串中的位置。 空格串：由一个或多个称为空格的特殊字符组成的串。 空串： n=0时的串为空串 串的抽象数据类型定义： ADT String { 数据对象:D={ai| ai ∈CharacterSet,i=1,2,…,n; n≥0} 数据关系:R={ai-1,ai| ai-1,ai ∈D,i=2,…,n; n≥0} 基本操作： （1） StrAsign(S,chars) 初始条件:chars是字符串常量 操作结果:生成一个值等于chars的串S （2） StrInsert(S,pos,T) 初始条件:串S和T存在,1≤pos≤StrLength(S) +1 操作结果:在串S的第pos个字符之前插入串T （3） StrDelete(S,pos,len) 初始条件: 串S存在,1≤pos≤StrLength(S) -len +1 操作结果: 从串S中删除第pos个字符起长度为len的子串 （4） StrCopy(S,T) 初始条件: 串S存在 操作结果:由串T复制得串S （5） StrEmpty(S) 初始条件: 串S存在 操作结果:若串S为空串,则返回TRUE,否则返回FALSE （6）StrCompare(S,T) 初始条件: 串S和T存在 操作结果:若ST,则返回值0;若S=T,则返回值=0;若ST, 则返回值0 （7）StrLength(S) 初始条件: 串S存在 操作结果:返回串S的长度,即串S中的元素个数 （8）StrClear(S) 初始条件: 串S存在 操作结果:将S清为空串 （9）StrCat(S,T) 初始条件: 串S和T存在 操作结果:将串T的值连接在串S的后面 （10）SubString(Sub,S,pos,len) 初始条件: 串S存在, 1≤pos≤StrLength(S)且