成都信息工程学院：《数据结构》课程教学资源（讲稿）第四章 串

第四章串 串的定义 串的操作 41串的定义 据 串:由零个或多个字符组成的有限序列, 构 记为S=“a 主串、子串、串名、串长; S=“ How are you, everybody!” >空串、空格串; 字符在串中的位置、子串在串中的位置; 两个串相等当且仅当两个串值相等,即 长度,位置相等;

1 第四章 串 串的定义 串的操作 数 据 结 构 之 串 2 4.1 串的定义 ¾ 串：由零个或多个字符组成的有限序列， 记为S= “a1a2a3……an ”。 ¾ 主串、子串、串名、串长； S=“How are you,everybody!” ¾ 空串、空格串； ¾ 字符在串中的位置、子串在串中的位置； ¾ 两个串相等,当且仅当两个串值相等，即 长度，位置相等；

42串的基本操作 据结构 StrAssign(&t, chars StrCompare(S,T):S、T相等返回rue,否则返 回fa Strength(S):求串中字符的个数; Con Cat(S,T):将串T的值紧接着放在串S的末尾 组成一个新串; Substring(Sub,s,star, ,ength):求S从 start位置开 始,长度为 length的子串; 据 SetEmpty(&T):设置空串 构> StrCopy(s,T):把T值赋给S Index(S,T,pos):求子串在主串中位置的定位函数; Replace(S,T,v):以v替换所有在S中出现的和T相 等的串; Strlnsert(S,Pos,T):在串S的第Pos个字符之前插 入串T; StrDelete(S,Pos,len):从串S中删除Pos个字符起 长度为len的子串;

2 数 据 结 构 之 串 3 4.2 串的基本操作 ¾ StrAssign(&T,chars) ¾ StrCompare(S,T): S、T相等返回true，否则返 回faule； ¾ StrLength(S) : 求串中字符的个数； ¾ ConCat(S,T) : 将串T的值紧接着放在串S的末尾， 组成 一个新串； ¾ SubString(Sub,S,start,length): 求S从start位置开 始，长度为 length 的子串； 数 据 结 构 之 串 4 ¾ SetEmpty(&T) : 设置空串 ¾ StrCopy(S,T): 把T值赋给S； ¾ Index(S,T,pos): 求子串在主串中位置的定位函数； ¾ Replace(S,T,v): 以v替换所有在S中出现的和T相 等的串； ¾ StrInsert(S,Pos,T): 在串S的第Pos个字符之前插 入串T； ¾ StrDelete(S,Pos,len): 从串S中删除Pos个字符起 长度为len的子串；

43串的表示和实现 撒>定长顺序存储表示 结 紧缩格式:在一个存储单元中存放多个字符 非紧缩格式:一个存储单元中只存放一个字符, 所需存储单元个数即串的长度 例:如一个单元存放k个字符,长度为n,则此 串值占[n/k]个存储单元 DA|T|A一个存储单元 TR UCTU FES 据动态分配串值的存储空间 构 动态串的类型定义 typedef struct( char * ch int ength;∥/串的长度 JHS;

3 数 据 结 构 之 串 5 4.3 串的表示和实现 ¾ 定长顺序存储表示 ¾ 紧缩格式：在一个存储单元中存放多个字符 ¾ 非紧缩格式：一个存储单元中只存放一个字符， 所需存储单元个数即串的长度 例：如一个单元存放k个字符，长度为n，则此 串值占[n/k]个存储单元。 D T A : S A D TA A W TR S U TU C F S E 一个存储单元 数 据 结 构 之 串 6 ¾ 动态分配串值的存储空间； ¾ 动态串的类型定义： typedef struct{ char *ch ; int length; //串的长度 }HS;

>串的链式存储 #define CHUNKsIZe 80 /由用户定义的块长度 数据结构 typedef struct Chunk i har ch( CHUNKSIZE;/字符串块 struct chunk *next;/指向下一个字符串块 3 Chunk; /结构名称 typedef struct i Chunk“head,“tail;/指向头尾的指针 nt curlen /串的当前长度* 3 STring; /串名称 一 ABCDEFG1## FA叶c >串基本操作的实现 将串S1和串S2联接成新串 构 算法描述 给T分配存储空间,存储空间大小为S1和S2长度 之和。 将S1中的每一个字符拷贝到T中。 修改T的长度 将S2中的所有字符拷贝到T剩余的存储空间中。 返回。 程序如下:

4 数 据 结 构 之 串 7 ¾ 串的链式存储 #define CHUNKSIZE 80 /*由用户定义的块长度*/ typedef struct Chunk { char ch[CHUNKSIZE]; /*字符串块*/ struct Chunk *next; /*指向下一个字符串块*/ }Chunk; /*结构名称*/ typedef struct { Chunk *head, *tail; /*指向头尾的指针*/ int curlen; /*串的当前长度*/ } LString; /*串名称*/ F A B C 1 ^ A B C D E F G H 1 # # # ^ F 数 据 结 构 之 串 8 ¾ 串基本操作的实现 ¾ 将串S1和串S2联接成新串 ¾算法描述： ¾给T分配存储空间，存储空间大小为S1和S2长度 之和。 ¾将S1中的每一个字符拷贝到T中。 ¾修改T的长度。 ¾将S2中的所有字符拷贝到T剩余的存储空间中。 ¾返回。 ¾程序如下：

Status Concat(Hstring T, Hstring SI, Hstring S2)( 据ifT.ch)free.h;/如果T.ch非空,则释放其存储空间 I* if( (T ch=(char*)malloc(S1. length+S2. length+1)*sizeof(char)) 构分配空间 return OVErFlow;/若分配失败,则返回溢出信息* for(count=0; count<sl length; count++) Tch count=Slch| count];/将S中字符拷贝到T中* T. ength=SI length+S2. length; /修改长度 for(count-SI.length; count<Tlength; count++) Tch| count=S2 ch count- Sl length;/将S2中所有字符 拷贝到T中* TchIT.ength=“0; return OK;/返回*/} 求子串T在主串S中的位置 据 算法思想:从主丰S的第一个字符 构 起和模式串(子串)的第一个字符 比较,相等则继续,否则从主串的 第二个字符起重新和模式比较,直 至比较完毕为止。 图示 S=“ a babcabcac bab T=“ab

5 数 据 结 构 之 串 9 Status Concat(Hstring T, Hstring S1, Hstring S2){ int count; if(T.ch) free(T.ch); /*如果T.ch非空，则释放其存储空间*/ if(!(T.ch=(char *)malloc(S1.length+S2.length+1)*sizeof(char)))) /*分配空间*/ return OVERFLOW; /*若分配失败，则返回溢出信息*/ for(count=0;count<S1.length;count++) T.ch[count]=S1.ch[count]; /*将S1中字符拷贝到T中*/ T.length=S1.length+S2.length; /*修改长度*/ for(count=S1.length;count<T.length;count++) T.ch[count]=S2.ch[count- S1.length]; /*将S2中所有字符 拷贝到T中*/ T.ch[T.length] = ‘\0’; return OK; /*返回*/ } 数 据 结 构 之 串 10 ¾ 求子串T在主串S中的位置 ¾算法思想：从主串S的第一个字符 起和模式串（子串）的第一个字符 比较，相等则继续，否则从主串的 第二个字符起重新和模式比较，直 至比较完毕为止。 ¾图示 S = “a b a b c a b c a c b a b” T = “a b c a c

第一趟匹配 a babcabcac bab 结 第二趟匹配 ba bca bcac ba b 第三趟匹配 a babcabcac b 第四趟匹配 a ba bcabcac bab 据 构 第五趟匹配: a babcabcac bab 第六趟匹配:

6 数 据 结 构 之 串 11 第一趟匹配： a b a b c a b c a c b a b a b c j=3 i=3 第二趟匹配： a b a b c a b c a c b a b a j=1 i=2 第三趟匹配： a b a b c a b c a c b a b a b c a c j=5 i=7 数 据 结 构 之 串 12 第四趟匹配： a b a b c a b c a c b a b a j=1 i=4 第五趟匹配： a b a b c a b c a c b a b a j=1 i=5 第六趟匹配： a b a b c a b c a c b a b a b c a c j=6 i=11

数据结构 int Index(Hs S, Hs T, int pos)t k=i=pos-1; j=0; while(kTlength) return(i+1 ) else return(0); 13 >模式匹配的KMP算法 构 请同学们参照演示程序和教材 中的相关内容进行钻研 14

7 数 据 结 构 之 串 13 int Index(HS S , HS T , int pos) { k= i = pos-1 ; j=0; while(kT.length) return ( i+1 ); else return (0); } 数 据 结 构 之 串 14 ¾ 模式匹配的KMP算法 请同学们参照演示程序和教材 中的相关内容进行钻研

串的算法练习 银1完成动态串的基本操作,page71; A 2 Status StrInsert( HS &S, int pos, HS T)C 3. Status StrDelete(hs &s, int pos, int len, HS &T) 数据结构 本章重点 串的基本概念 串的基本操作 串的查找

8 数 据 结 构 之 串 15 串的 算法练习 1.完成动态串的基本操作，page 71; 2. Status StrInsert( HS &S , int pos , HS T){ ……. } 3. Status StrDelete(HS &S,int pos,int len,HS &T) { ……. } 数 据 结 构 之 串 16 ¾ 本章重点 ¾ 串的基本概念 ¾ 串的基本操作 ¾ 串的查找