《数据结构与算法》第4章 串

第4章申 41串类型的定义 42串的表示和实现 43串的模式匹配算法

第4章 串 4.1 串类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法

4.1类型的定义 串是由多个或零个字符组成的有限序列,记作 S=‘c1C2C3 (n>=0) 其中,S是串名字,'c1c2c3…cn2是串值 c是串中字符,n是串的长度,表示串中字符 的数目。 空串:零个字符的串称为空串记作“O” 子串:串中任意个连续的字符组成的子序列 主串:包含子申的串 字符在串中的位置:字符在序列中的序号 子串在串中的位置:子串的第一个字符在主串中的位置

4.1 串类型的定义 串是由多个或零个字符组成的有限序列 ，记作 S = ‘c1c2c3…cn ’ (n>=0) 其中，S是串名字，‘ c1c2c3…cn ’是串值 ci是串中字符，n是串的长度，表示串中字符 的数目。 空串：零个字符的串称为空串 记作 “Ø” 子串：串中任意个连续的字符组成的子序列 主串：包含子串的串 字符在串中的位置：字符在序列中的序号 子串在串中的位置：子串的第一个字符在主串中的位置

串相等:p70 空格串:由一个或多个空格组成的串 串的表示:用一对单引号括起来 串的操作:以“串的整体”为操作对象

串相等：p70 空格串：由一个或多个空格组成的串 串的表示：用一对单引号括起来 串的操作：以“串的整体”为操作对象

4.2的表示和实现 1定长顺序存储表示 2堆分配存储表示 3串的块链存储表丞 4.串的基本操作

4.2 串的表示和实现 1.定长顺序存储表示 2.堆分配存储表示 3.串的块链存储表示 4.串的基本操作

1.定长版序存猪表 静态分配 每个串预先分配一个固定长度的存储区域。 实际串长可在所分配的固定长度区域内变动 以下标为0的数组分量存放串的实际长度; 在串值后加入”0”表示结束,此时串长为隐含值 用定长数组描述: # define maXstrlen255/最大串长 typedef unsigned char SString [ MAXsTRLen 11 0单元存放串的长度

1.定长顺序存储表示 静态分配 每个串预先分配一个固定长度的存储区域。 实际串长可在所分配的固定长度区域内变动 ▪ 以下标为0的数组分量存放串的实际长度； ▪ 在串值后加入”\0”表示结束，此时串长为隐含值 用定长数组描述： #define MAXSTRLEN 255 //最大串长 typedef unsigned char SString[MAXSTRLEN + 1] //0号单元存放串的长度

2.堆分配存信表示 以一组地址连续的存储单元存放串值字符 序列; 存储空间动态分配,用malc和fee)来 理 typedef struct ichar*ch int length; JHstring

2.堆分配存储表示 以一组地址连续的存储单元存放串值字符 序列； 存储空间动态分配，用malloc()和free()来 管理 typedef struct {char *ch; int length; }Hstring;

3.牛的块链存储表示 串的链式存储方式 结点大小:一个或多个字符 nP78图42(a)(b) 存储密度=串值所占的存储位(实际分配的存储位

3.串的块链存储表示 串的链式存储方式 结点大小：一个或多个字符 ▪ P78图4.2 (a) (b) ▪ 存储密度=串值所占的存储位/实际分配的存储位

4.的基本操作 串插入 Status strlnsert( HString&s, int pos, HString T 串赋值 Status StrAssign( HString&s, char*chars) 求串长 int StrEngth( HString S 串比较 int StrCompare( HString S, HString T 串联接 Status Concat(( HString&s, HString S1, HString S2) 求子串 Status SubString( HString&sub, HString S, int pos, int len) 串清空 Status Clear String( HString&S) 串定位 删除 置换

4.串的基本操作 串插入 Status StrInsert(HString &S,int pos,HString T) 串赋值 Status StrAssign(HString &S,char *chars) 求串长 int StrLength(HString S) 串比较 int StrCompare(HString S,HString T) 串联接 Status Concat(HString &S,HString S1,HString S2) 求子串 Status SubString(HString &Sub,HString S,int pos,int len) 串清空 Status ClearString(HString &S) 串定位 删除 置换

Status StrInsert(HString &s, int pos, HString T) ∥在串5的第pos个位置前插入T if (pos s length+1)return ERROR; if (T length)t if ((sch=(char ealloc(sch, (S length+T length)*sizeof(char))) exit(OVERFLOW) for(i=s length-1; i>=pos-1; -i) sch[i+T length]=S ch[] for (i=0; K<=Tlength-1; i ++ sch[pos-1+iT.ch[] Slength+=Tlength; s return OK

Status StrInsert(HString &S,int pos,HString T) //在串S的第pos个位置前插入串T { int i; if (posS.length+1) return ERROR; if (T.length){ if (!(S.ch=(char*) realloc(S.ch,(S.length+T.length)*sizeof(char)))) exit(OVERFLOW); for (i=S.length-1;i>=pos-1;--i){ S.ch[i+T.length]=S.ch[i]; } for (i=0; i<=T.length-1;i++) S.ch[pos-1+i]=T.ch[i]; S.length+=T.length; } return OK; }

Status StrAssign(HString &S, char chars) 生成一个值等 chars的5 int i,j; char *C, for(i=0, c=chars; C: ++i, ++c) if isch=NULL,s length=0; 1 else if ((sch=(char *)malloc(i * sizeof(char)) exit(OVERFLOW) for(=0j<=i-1+){ s.chjchars0; Slength=i return OK

Status StrAssign(HString &S,char *chars) 生成一个值等于chars的串S { int i,j; char *c; for (i=0,c=chars;*c;++i,++c); if (!i) {S.ch=NULL; S.length=0;} else { if (!(S.ch=(char *)malloc(i * sizeof(char)))) exit(OVERFLOW); for (j=0;j<=i-1;j++){ S.ch[j]=chars[j];} S.length=i; } return OK; }