文档介绍：第4章串
串的基本概念
串的存储结构
本章小结
串的模式匹配
串(或字符串),是由零个或多个字符组成的有穷序列。含零个字符的串称为空串,用Ф表示。
串中所含字符的个数称为该串的长度(或串长)。
通常将一个串表示成"a1a2…an"的形式。其中,最外边的双引号本身不是串的内容,它们是串的标志,以便将串与标识符(如变量名等)加以区别。每个ai(1≤i≤n)代表一个字符。
串的基本概念
当且仅当两个串的长度相等并且各个对应位置上的字符都相同时,这两个串才是相等的。
一个串中任意个连续字符组成的子序列(含空串,但不含串本身)称为该串的子串。例如,“a”、“ab”、“abc”和“abcd”等都是“abcde”的子串(平凡子串不包括自身)。
问题: “abcde”有多少个平凡子串?
解: 空串数:1
含1个字符的子串数:5
含2个字符的子串数:4
含3个字符的子串数:3
含4个字符的子串数:2
共有1+2+3+4+5=15个子串。
串的基本运算如下:
(1) StrAssign(&s,chars):将一个字符串常量赋给串s,即生成一个其值等于chars的串s。
(2) StrCopy(&s,t):串复制:将串t赋给串s。
(3) StrEqual(s,t):判串相等:若两个串s与t相等则返回真;否则返回假。
(4) StrLength(s):求串长:返回串s中字符个数。
(5) Concat(s,t):串连接:返回由两个串s和t连接在一起形成的新串。
(6)SubStr(s,i,j):求子串:返回串s中从第i(1≤i≤StrLength(s))个字符开始的、由连续j个字符组成的子串。
(7)InsStr(s1,i,s2):将串s2插入到串s1的第i(1≤i≤StrLength(s)+1)个字符中,即将s2的第一个字符作为s1的第i个字符,并返回产生的新串。
(8)DelStr(s,i,j):从串s中删去从第i(1≤i≤StrLength(s))个字符开始的长度为j的子串,并返回产生的新串。
(9)RepStr(s,i,j,t):替换:在串s中,将第i(1≤i≤StrLength(s))个字符开始的j个字符构成的子串用串t替换,并返回产生的新串。
(10) DispStr(s):串输出:输出串s的所有元素值。
串的顺序存储及其基本操作实现
串是一种特殊的线性表,在非紧缩格式中,它的每个结点仅由一个字符组成,因此存储串的方法也就是存储线性表的一般方法。存储串最常用的方式是采用顺序存储,即把串的字符顺序地存储在内存一片相邻的空间,这称为顺序串。
串的存储结构
顺序存储采用一般顺序表的存储结构,其类型定义如下:
#define MaxSize 100
typedef struct
{
char data[MaxSize];
int len;
} strtype;
其中,ch域用来存储字符串,len域用来存储字符串的当前长度,MaxSize常量表示允许所存储字符串的最大长度。在C语言中每个字符串以'\0'标志结束。
顺序串中实现串的基本运算如下:
(1) StrAssign(str,cstr)
将一个字符串常量赋给串str,即生成一个其值等于cstr的串s。
void StrAssign(SqString &str,char cstr[])
{ int i;
for (i=0;cstr[i]!='\0';i++)
[i]=cstr[i];
=i;
}