第4章串4.1串的基本概念4.2串的存储结构本章小结4.3串的模式匹配串（或字符串），是由零个或多个字符组成的有穷序列。含零个字符的串称为空串，用Ф表示。串中所含字符的个数称为该串的长度（或串长）。通常将一个串表示成“a1a2…an”的形式。其中最外边的双引号本身不是串的内容，它们是串的标志，以便将串与标识符（如变量名等）加以区别。每个ai（1≤i≤n）代表一个字符。4.1串的基本概念当且仅当两个串的长度相等并且各个对应位置上的字符都相同时，这两个串才是相等的。一个串中任意个连续字符组成的子序列（含空串）称为该串的子串。例如，“a”、“ab”、“abc”和“abcd”等都是“abcde”的子串（真子串是指不包含自身的所有子串）。思考题：串和线性表有什么异同？例4.1问题:“abcde”有多少个真子串?解:空串数:1含1个字符的子串数:5含2个字符的子串数:4含3个字符的子串数:3含4个字符的子串数:2共有1+2+3+4+5=15个子串。推广：含有n个相互相同字符的串有n(n+1)/2个真子串。串的基本运算如下:StrAssign(&s,cstr)：将字符串常量cstr赋给串s，即生成其值等于cstr的串s。StrCopy(&s,t)：串复制。将串t赋给串s。StrEqual(s,t)：判串相等。若两个串s与t相等则返回真；否则返回假。StrLength(s)：求串长。返回串s中字符个数。Concat(s,t)：串连接:返回由两个串s和t连接在一起形成的新串。SubStr(s,i,j)：求子串。返回串s中从第i（1≤i≤n）个字符开始的、由连续j个字符组成的子串。InsStr(s1,i,s2)：插入。将串s2插入到串s1的第i（1≤i≤n+1）个字符中，即将s2的第一个字符作为s1的第i个字符，并返回产生的新串。DelStr(s,i,j)：删除。从串s中删去从第i（1≤i≤n）个字符开始的长度为j的子串，并返回产生的新串。RepStr(s,i,j,t)：替换。在串s中，将第i（1≤i≤n）个字符开始的j个字符构成的子串用串t替换，并返回产生的新串。DispStr(s)：串输出。输出串s的所有元素值。4.2.1串的顺序存储及其基本操作实现4.2串的存储结构在顺序串中，串中的字符被依次存放在一组连续的存储单元里。一般来说，一个字节（8位）可以表示一个字符（即该字符的ASCII码）。因此，一个内存单元可以存储多个字符。例如，一个32位的内存单元可以存储4个字符（即4个字符的ASCII码）。串的顺序存储有两种方法：一种是每个单元只存一个字符，这称为非紧缩格式（其存储密度小）；另一种是每个单元存放多个字符，这称为紧缩格式（其存储密度大）。ABCDEFGHIJKLMN100110021003...