数据结构 C语言版 教学课件 作者 李云清 第04章_字符串.ppt

《数据结构 C语言版 教学课件 作者 李云清 第04章_字符串.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第4章　字符串、数组和特殊矩阵字符串字符串的模式匹配稀疏矩阵数组特殊矩阵4.1字符串4.1.1字符串的基本概念字符串是由零个或多个字符构成的有限序列，一般可表示成如下形式：“c1c2c3….cn”(n≥0)串中所含字符的个数n称为字符串的长度；当n=0时，称字符串为空串。串中任意个连续的字符构成的子序列称为该串的子串，包含子串的串称为主串。通常称字符在字符串序列中的序号为该字符在串中的位置。子串在主串中的位置以子串的第一个字符在主串中的位置来表示。例如：T=“STUDENT”，S=“UDEN”,则S是T

2、的子串，S在T中出现的位置为3。两个字符串相等，当且仅当两个串的长度相等，并且各个对应位置的字符都相等。例如：T1=“REDROSE”T2=“REDROSE”由于T1和T2的长度不相等，因此T1≠T2。若T3=“STUDENT”T4=“STUDENS”虽然T3和T4的长度相等，但两者有些对应的字符不同，因而T3≠T4。值得一提的是，若S=“”，此时S由一个空格字符组成，其长度为1，它不等价于空串，因为空串的长度为0。4.1.2字符串类的定义ADTstring{数据对象D：由零个或多个字符型的数据元素构成

3、的有限集合；数据关系R：{

4、其中ai,ai+1D,i=1,2,……n-1}字符串的基本操作如下：（1）Strcreate(S)（2）Strassign(S,T)（3）Strlength(S)（4）Strempty(S)（5）Strclear(S)（6）Strcompare(S1，S2)（7）Strconcat(S1，S2)（8）Substring(S,i,len)（9）Index(P,T)（10）Strinsert(S,i,T)（11）Strdelete(S,i,len)（12）Re

5、place(S,T1,T2)（13）Strdestroy(S)}ADTstring4.1.3字符串的存储及其实现1、串的顺序存储及其部分运算的实现串的顺序存储使用数组存放，具体类型定义如下：#defineMAXSIZE100typedefstruct{charstr[MAXSIZE];intlength;}seqstring;（1）插入运算strinsert(S,i,T)voidstrinsert(seqstring*S,inti,seqstringT){intk;if(i<1

6、

7、i>S->l

8、ength+1

9、

10、S->length+T.length>MAXSIZE)printf("connotinsert“);else{for(k=S->length-1;k>=i-1;k--)S->str[T.length+k]=S->str[k];for(k=0;kstr[i+k-1]=T.str[k];S->length=S->length+T.length;S->str[S->length]=‘’;}}（2）删除运算strdelete(S,i,len)

11、voidstrdelete(seqstring*S,inti,intlen){intk;if(i<1

12、

13、i>S->length

14、

15、i+len-1>S->length)printf(“cannotdelete”);else{for(k=i+len-1;klength;k++)S->str[k-len]=S->str[k];S->length=S->length-len;S->str[S->length]=‘’;}}（3）连接运算strconcat(S1,S2)seqs

16、tring*strconcat(seqstringS1,seqstringS2){inti;seqstring*r;if(S1.length+S2.length>MAXSIZE){printf("cannotconcate");return(NULL);}else{r=(seqstring*)malloc(sizeof(seqstring));for(i=0;istr[i]=S1.str[i];for(i=0;istr[S

17、1.length+i]=S2.str[i];r->length=S1.length+S2.length;r->str[r->length]='';}return(r);}（4）求子串运算substring(S,i,len)seqstring*substring(seqstringS,inti,intlen){intk;seqstring*r;if(i<1

18、

19、i>S.length

20、

21、i+len-1>S.leng