第四章:串
1.串是数据元素为字符的线性表,串的定义及操作。
串即字符串,是由零个或多个字符组成的有限序列,是数据元素为单个字符的特殊线性表。
串比较:int strcmp(char *s1,char *s2);
求串长:int strlen(char *s);
串连接:char strcat(char *to,char *from)
子串T定位:char strchr(char *s,char *c);
2.串的存储结构,因串是数据元素为字符的线性表,所以存在“结点大小”的问题。
模式匹配算法 。
串有三种机内表示方法:
3.模式匹配算法 :
算法目的:确定主串中所含子串第一次出现的位置(定位)
定位问题称为串的模式匹配,典型函数为Index(S,T,pos)
BF算法的实现—即编写Index(S, T, pos)函数
BF算法设计思想:
将主串S的第pos个字符和模式T的第1个字符比较,
若相等,继续逐个比较后续字符;
若不等,从主串S的下一字符(pos+1)起,重新与T第一个字符比较。
直到主串S的一个连续子串字符序列与模式T相等。返回值为S中与T匹配的子序列第一个字符的序号,即匹配成功。
否则,匹配失败,返回值 0。
Int Index_BP(SString S, SString T, int pos)
{ //返回子串T在主串S中第pos个字符之后的位置。若不存在,则函数值为0.
// 其中,T非空,1≤pos≤StrLength(S)
i=pos; j=1;
while ( i<=S[0] && j<=T[0] ) //如果i,j二指针在正常长度范围,
{
if (S[i] = = T[j] ) {++i, ++j; } //则继续比较后续字符
else {i=i-j+2; j=1;} //若不相等,指针后退重新开始匹配
}
if(j>T[0]) return i-T[0]; //T子串指针j正常到尾,说明匹配成功, else return 0; //否则属于i>S[0]情况,i先到尾就不正常
} //Index_BP
补充重点:
1.空串和空白串有无区别?
答:有区别。
空串(Null String)是指长度为零的串;
而空白串(Blank String),是指包含一个或多个空白字符‘ ’(空格键)的字符串.
2.“空串是任意串的子串;任意串S都是S本身的子串,除S本身外,S的其他子串称为S的真子串。”