c语言-第4章字符串、数组和特殊矩阵.ppt

《c语言-第4章字符串、数组和特殊矩阵.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、字符串相等，当且仅当两个串的长度相等，并且各个对应位置的字符都相等。例如：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：由零个或多个字符型的数据元素构成的有限集合；数据关系R：{

3、其中ai,ai+1D,i

4、=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）Replace(S,T1,T2)（13）Strdestroy(S)}ADTstring4.1.3字符串的存储及其实

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

6、

7、i>S->length+1

8、

9、S->length+T.length>MAXSIZE)printf("connotinsert“);else{for(k=

10、S->length-1;k>=i-1;k--)S->str[T.length+k]=S->str[k];for(k=0;kstr[i-1+k]=T.str[k];S->length=S->length+T.length;S->str[S->length]=‘’;}}（2）删除运算strdelete(S,i,len)voidstrdelete(seqstring*S,inti,intlen){intk;if(i<1

11、

12、i>S->length

13、

14、i+len-1>S->length)print

15、f(“cannotdelete”);else{for(k=i-1+len;klength;k++)S->str[k-len]=S->str[k];S->length=S->length-len;S->str[S->length]=‘’;}}（3）连接运算strconcat(S1,S2)seqstring*strconcat(seqstringS1,seqstringS2){inti;seqstring*r;if(S1.length+S2.length>MAXSIZE){printf("cannotcon

16、cate");return(NULL);}else{r=(seqstring*)malloc(sizeof(seqstring));for(i=0;istr[i]=S1.str[i];for(i=0;istr[S1.length+i]=S2.str[i];r->length=S1.length+S2.length;r->str[r->length]='';}return(r);}（4）求子串运算substring(S,i,len)seqstring*

17、substring(seqstringS,inti,intlen){intk;seqstring*r;if(i<1

18、

19、i>S.length

20、

21、i+len-1>S.length