第四章 串.ppt

第四章串
串的基本概念
串的存储结构
串的操作算法
连接、比较、拷贝
模式匹配(查找子串)
查找并替换
串的应用
串的基本概念
定义:
串是由零个或多个任意字符组成的有限序列。一般记作 S="a1 a2…an"
例如:
S1="data structure",长度为14的串
S2=“struct”, 长度为6的串
S3=“”, 空串,长度为0
S4=“”, 空格串,长度为1
子串, 主串
串的存储结构
顺序存储结构
用固定长度的数组来存储串中的字符序列
链式存储结构
用链表存储串中的字符序列
1 串的顺序存储结构
有三种方法表示串的长度
2 串的链式存储结构
(1)非压缩形式
(2)压缩形式
串的操作算法

void StrCat (char *s1, char *s2) //连接
{
len1=strlen(s1);
len2=strlen(s2);
if (len1+len2>MaxSize-1) {cerr<<"超长"; exit(1);}
i=0;
while(s2[i]!='\0')
{
s1[i+len1]=s2[i];
i++;
}
s1[i+len1]='\0';
}
2. 串的比较
int StrCmp(char *s1, char *s2) //比较
{
i=0;
while (s1[i]==s2[i] && s1[i]!='\0')
i++;
return (s1[i]-s2[i]);
}

void StrCpy(char *s1, char *s2) //复制
{
int len=strlen(s2);
if (len>MaxSize-1) {cerr<<"超长"; exit(1);}
while (*s1++ = *s2++);
}
4. 串的模式匹配
给定两个串s和t,在主串s中寻找子串t的过程称为模式匹配,t称为模式。
模式匹配算法
简单的模式匹配算法,简称BF算法;
KMP模式匹配算法
为了操作方便,串采用第(3)种顺序存储方式,即串的长度存放在0号单元,串值从1号单元存放.