PPT《第4章串》

第4章串4.

1 串的定义4.2 抽象数据类型串的实现4.3 串的应用举例:文本编辑 4.1 串的定义 串(String)是零个或多个字符组成的有限序列. 一般记为: S=′a1a2...an′ (n≥0)其中S是串的名字, 用单引号括起来的字符序列是串的值,ai(1≤i≤n)可以是字母、数字或其它字符.n是串中字符的个数, 称为串的长度,n=0时的串称为空串 (Null String). 串中任意个连续的字符组成的子序列称为该串的子串. 包含子串的串相应地称为主串.通常将字符在串中的序号称为该字符在串中的位置.子串在主串中的位置则以子串的第一个字符在主串中的位置来表示. 假如有串A=′China Beijing′, B=′Beijing′, C=′China′, 则它们的长度分别为

13、7和5.B和C是A的子串, B在A中的位置是7, C在A中的位置是1. 当且仅当两个串的值相等时,称这两个串是相等的,即只有当两个串的长度相等, 并且每个对应位置的字符都相等时才相等. 串的抽象数据类型定义如下: ADT String { 数据对象: D={ai| ai ∈CharacterSet, i=1, 2, …, n;

n≥0} 数据关系: R={| ai-1, ai ∈D, i=2, …, n;

n≥0} 基本操作:(1) StrAsign(S, chars)初始条件: chars是字符串常量.操作结果: 生成一个值等于chars的串S. (2) StrInsert(S, pos, T)初始条件: 串S存在, 1≤pos≤StrLength(S)-len+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存在.操作结果: 若S>T, 则返回值>0;

如S=T, 则返回值=0;

若SMAXLEN,则B的全部字符被舍弃(不需后移),并且C在插入时也有部分字符被舍弃. 与上述类似, 在进行串的连接时(假设原来串为A, 长度为LA, 待连接串为B, 长度为LB), 也可能有三种情况: (1)连接后串长≤MAXLEN, 则直接将B加在A的后面. (2)连接后串长>MAXLEN且LAMAXLEN且LA=MAXLEN, 则B的全部字符被舍弃(不需连接). 置换时的情况较为复杂,假设原串为A、长度为LA,被置换串为B、长度为LB, 置换串为C、 长度为LC,每次置换位置为pos,则每次置换有三种可能: (1) LB=LC: 将C复制到A中pos起共LC个字符处. (2) LB>LC: 将A中B后的所有字符前移LB-LC个字符位置,然后将C复制到A中pos起共LC个字符. (3) LBlen) return(0);

/* 插入位置不合法 */if (s->len + t.lenlen + t.len-1;

i>=t.len + pos;

i--) s->ch[i]=s->ch[i-t.len];

for (i=0;

ich[i+pos]=t.ch[i];

s->len=s->len+t.len;

} else if (pos+t.lenMAXLEN, 但串t的字符序列可以全部插入 */ for (i=MAXLEN-1;

i>t.len+pos-1;

i--) s->ch[i]=s->ch[i-t.len];

for (i=0;

ich[i+pos]=t.ch[i];

s->len=MAXLEN;

}else { /* 串t的部分字符序列要舍弃 */ for (i=0;

ich[i+pos]=t.ch[i];

s->len=MAXLEN;

}return(1);

} 【算法4.1 串插入函数】 (2) 串删除函数.StrDelete(s, pos, len) /* 在串s中删除从序号pos起len个字符 */SString *s;

int pos, len;

{int i;

if (pos(s->len-len)) return(0);

for (i=pos+len;

ilen;

i++) s->ch[i-len]=s->ch[i];

s->len=s->len - len;

return(1);

} 【算法4.2 串删除函数】 (3) 串复制函数.StrCopy(s, t) /* 将串t的值复制到串s中*/SString *s, t;

{int i;

for (i=0;