数据结构课件 chapter04串.ppt

《数据结构课件 chapter04串.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章串、数组和广义表本章目录4.1串的定义和操作4.2串的存储结构4.3串的模式匹配算法4.4串操作应用举例4.5数组4.6矩阵的压缩存储4.7广义表4.8小结串的定义定义：串（string），或称字符串，是由零个或多个字符组成的有限序列。一般记为：s=“a0a1a2…an-1”(n>=0)s是串名。字符序列”a0a1a2…an-1”是串的值，必须用双引号作为定界符。‘ai’是串中的某个字符，引用时用单引号作为定界符。串中字符的数目n称为串长。串长为0（n=0）的串称为空串（nullstring）。串的定义子串：串中任意个连续的字符组成的子序列。主串：包含子串的串。子

2、串在主串中的位置：子串的第一个字符在主串中的位置（字符在串中的位置：字符在串中的序号）。例如：串A=“ChinaBeijing”，B=“Beijing”，C=“China”，D=“inaB”，E=“iij”其中，B、C、D、E中哪些是A的子串，哪些不是。如果是A的子串，则在A中的位置分别是多少。串的定义两个串相等两个串的长度相等对应位置的字符相同注意空串：n=0的串。空格串：由一个或多个空格组成的串。空串的长度一定为0，空格串的长度一定大于0，但具体值由空格的个数决定。串的顺序存储串的顺序存储是用一组地址连续的存储单元存储串中的字符序列。Q：串是若干个字符组成的一个字符

3、序列，那么对于一个串，如何判断串的结束呢？A1：字符串结束标志“”。A2：用数组下标为0的元素存放串的实际长度。0123456789abcdefg01234567897abcdefg串赋值：assign(s,t)将一个值t赋给串svoidassign(chars[],chart){inti;printf(“Pleaseinputtheposition:”);scanf(“%d”,&i);s[i]=t;}求串长：strlen(s)求出给定串s的长度（实际长度）intstrlen(chars[]){intlen=0,i=0;while(s[i]!=‘’){len

4、++;i++;}returnlen;}串复制：strcopy(s,t)将串t复制给串svoidstrcopy(chars[],chart[]){inttlen,i;tlen=strlen(t);/*调用函数strlen求出串t的实际长度*/for(i=0;i

5、len(s),tlen=strlen(t),i;if(stlen!=tlen)return0;else{for(i=0;i

6、‘’;}s1abcds2mnmn串连接：strcat(s,s1,s2)将s1和s2连接，结果放在s中。voidstrcat(chars[],chars1[],chars2[]){intlen1=strlen(s1),len2=strlen(s2),i=0,j;j=0;while(s1[j]!=‘’){s[i]=s1[j];i++;j++;}j=0;while(s2[j]!=‘’){s[i]=s2[j];i++;j++;}s[i]=‘’;}s1abcds2mnsabcdmn求子串：substr(s,i,k)返回串s的第i个位置开始的

7、k个字符组成的串char*substr(chars[],inti,intk){char*t;intj,n;for(j=0,n=i;n