第三章数组和字符串

1、12022-3-3第三章第三章 数组和字符串数组和字符串l第一节第一节 数组数组l第二节第二节 矩阵矩阵l第三节第三节 字符串字符串22022-3-3一、数组的存储和寻址一、数组的存储和寻址一维数组是若干个元素的一维数组是若干个元素的有限序列有限序列。元。元素本身就是一个数据结构。素本身就是一个数据结构。一维数组的元素必须具有一维数组的元素必须具有相同的类型相同的类型，每个数组元素都占据每个数组元素都占据相同大小的存储空相同大小的存储空间间。数组采用顺序存储。数组采用顺序存储。3.1 数数 组组 32022-3-3n 每个元素都通过一个下标来指定，故一每个元素都通过一个下标来指定，故一个一维数

2、组对应一个下标函数。个一维数组对应一个下标函数。n 一维数组一维数组An ，每个数组元素占一个存，每个数组元素占一个存储单元（不妨设为储单元（不妨设为C个连续字节）个连续字节）. 数组数组元素元素A0的首地址的首地址Loc(A0)，则对于，则对于0i n-1，有：，有：Loc(Ai)=Loc(A0)+i*C 42022-3-3n可以将高维数组转化为一维数组计算可以将高维数组转化为一维数组计算元素的地址。元素的地址。n高维数组有两种存放次序：按行优先高维数组有两种存放次序：按行优先顺序和按列优先顺序存储。顺序和按列优先顺序存储。52022-3-3l按行优先顺序按行优先顺序，就是将数组元素按行向量

3、的，就是将数组元素按行向量的顺序存储，第顺序存储，第i+1个行向量存储在第个行向量存储在第i个行向个行向量之后。量之后。BASIC、PASCAL、C/C+等程序等程序设计语言中，数组按行优先顺序存放；设计语言中，数组按行优先顺序存放；l按列优先顺序按列优先顺序，就是将数组元素按列向量的，就是将数组元素按列向量的顺序存储，第顺序存储，第i+1个列向量存储在个列向量存储在i第个列向第个列向量之后。量之后。FORTRAN语言、语言、Matlab中，数组中，数组按列优先顺序存放。按列优先顺序存放。 62022-3-3 例例 int x23 /*有有23个数组元素个数组元素*/ x00 x01 x02

4、x10 x11 x12二维数组二维数组72022-3-3按行优先顺序存放按行优先顺序存放存储分配顺序为：存储分配顺序为： x00-x01- x02-x10- x11-x1282022-3-3二维数组可以看作是一种特殊的一维数组。二维数组可以看作是一种特殊的一维数组。例例 float a34; b0 a00 a01 a02 a03 b- b1 a10 a11 a12 a13 b2 a20 a21 a22 a23 92022-3-3二维数组二维数组(m n)中元素中元素aij的地址：的地址：Loc(a ij) = Loc(bi) +j*CLoc(bi)=Loc(b0)+i*C / C=n*CLoc

5、(aij)=Loc(a00)+i*n*C+j*C= Loc(a00) + (i*n+j)*C 102022-3-3例例 float a34Loc(a12) = a+(i*n+j)*C = a+(1*4+2)*4 = a+24112022-3-3多维数组元素在内存中的排列顺序为：第一多维数组元素在内存中的排列顺序为：第一维的下标变化最慢，最右边的维下标变化最维的下标变化最慢，最右边的维下标变化最快。快。 例例float a234三维数组三维数组122022-3-3a000a001a002a003a010a011a012a013a020a021a022a023a100a101a102a103 a1

6、10a111a112a113 a120a121a122a123 132022-3-3三维数组三维数组Amnp中数组元素中数组元素aijk的地址的地址计算公式为：计算公式为： Loc(aijk)=Loc(a000)+i*n*p*C+j*p*C+k*C142022-3-3例例 float D334Loc(D122) = d+ i*n*p*C+j*p*C+k*C = d+(1*3*4+2*4+2)*4 = d+88152022-3-3ai1i2in的存储地址的存储地址（行优先）（行优先） 112210CiiiLociiiLocnn),(),(1122300CiCiiiLocn),(.111100Ci

7、CiCiLocnnn ),(11200 ( , , )nnnnLociC iC miC mmCimiLocnnknkppk)(),(111 00 162022-3-3ai1i2in的存储地址的存储地址（列优先）（列优先） 1121(0,0) ( *)*knkpkpLocimiC172022-3-3 A0:2,0:4,0:10,0:2 分别给出按行优先、列优先存储下的分别给出按行优先、列优先存储下的 AIJKL地址计算公式。地址计算公式。 Loc(A)+(165I+33J+3K+L)*C 行优先行优先 Loc(A)+ (165L+15K+3J+I)*C 列优先列优先182022-3-3l如何计算

8、按列优先顺序存储的数组元素地如何计算按列优先顺序存储的数组元素地址？址？ 将数组元素按列向量的顺序存储，第将数组元素按列向量的顺序存储，第i+1个个列向量存储在第列向量存储在第i个列向量之后。请大家自个列向量之后。请大家自己推导。己推导。192022-3-3二、自定义数组类二、自定义数组类 数组类型是高级程序设计语言所提供的基本数据类数组类型是高级程序设计语言所提供的基本数据类型之一，可定义一组相同类型的元素。但是直接创型之一，可定义一组相同类型的元素。但是直接创建的数组存在着一些问题，诸如：建的数组存在着一些问题，诸如：l无法对数组执行一些简单运算，如数组加法和数组无法对数组执行一些简单运算

9、，如数组加法和数组减法等操作；减法等操作；l没有越界索引保护，不检查数组的下标索引值是否没有越界索引保护，不检查数组的下标索引值是否在在0到到arraysize-1范围内。例如一些高级程序设计语范围内。例如一些高级程序设计语言对越界索引访问并不一定会产生异常。没有越界言对越界索引访问并不一定会产生异常。没有越界索引保护会直接给程序调试带来难以预料的困难。索引保护会直接给程序调试带来难以预料的困难。为了弥补这些缺陷，可以自定义一个数组类。为了弥补这些缺陷，可以自定义一个数组类。202022-3-3 在自定义的数组类中，不但需要重载一些在自定义的数组类中，不但需要重载一些必要的运算符，还需要对下标

10、符号必要的运算符，还需要对下标符号“ ”进进行重载，以确保可提供越界索引保护。行重载，以确保可提供越界索引保护。 212022-3-33.2 矩矩 阵阵 矩阵是许多物理问题中出现的数学对象，是一种常矩阵是许多物理问题中出现的数学对象，是一种常用的数据组织方式。计算机工作者关心的是矩阵在计用的数据组织方式。计算机工作者关心的是矩阵在计算机中如何存储，以及如何实现矩阵的基本操作。算机中如何存储，以及如何实现矩阵的基本操作。 二维数组与矩阵相比：二维数组与矩阵相比： 数组的基本操作是数组加减，而矩阵的基本操作数组的基本操作是数组加减，而矩阵的基本操作还有矩阵相乘、矩阵转置等；还有矩阵相乘、矩阵转置等

11、； 数组的下标从数组的下标从0开始开始, 而矩阵的下标一般从而矩阵的下标一般从1开始；开始； 数组元素用数组元素用aij表示表示, 而矩阵元素通常用而矩阵元素通常用a(i, j)表表示。示。222022-3-3矩阵的乘法运算矩阵的乘法运算对于矩阵对于矩阵Amp和和Bpn的乘积的乘积Cmn ，其第，其第i行第行第j列元素列元素cij的计算公式为的计算公式为 ，乘法运算的算法，乘法运算的算法可描述如下：可描述如下：算法算法Multi-1(A, B, C, m, p, n)FOR i=1 TO m DO FOR j=1 TO n DO ( Cij 0 . FOR k=1 TO p DO Cij Ci

12、j + AikBkj . ) 1ikkjkpab232022-3-3 算法算法Multi-2是对用一维数组所存放矩阵的是对用一维数组所存放矩阵的乘法运算实现。该算法中，乘法运算实现。该算法中，按行优先，按行优先，用一维用一维数组数组s存放存放Amp，用一维数组，用一维数组t存放存放Bpn，求存，求存放放A与与B的乘积的乘积Cmn 的一维数组的一维数组w. cs为为A中中i行行k列元素的下标，那么列元素的下标，那么A中中i行行k+1列元素的下标是什么？列元素的下标是什么？ cscs 1. ct为为B中中k行行j列元素的下标，那么列元素的下标，那么B中中k+1行行j列元素的下标是什么？列元素的下标

13、是什么？ ctct n. 242022-3-3算法算法Multi-2(s, t, m, p, n. w)M1. 初始化初始化 cw0 . / 初始时初始时cw是是c11在一维数组在一维数组w中的下标中的下标M2. 循环循环 FOR i=1 TO m DO / 第一层循环第一层循环 FOR j 1 TO n DO / 第二层循环第二层循环 ( cs(i 1)p . / 确定确定A矩阵第矩阵第i行的第一个元素行的第一个元素 ctj 1. / 确定确定B矩阵第矩阵第j列的第一个元素列的第一个元素wcw0 . /计算计算Cij FOR k 1 TO p DO / 第三层循环第三层循环 / 叠加叠加ai

14、kbkj 并存于并存于wcw中中 ( wcwwcw scs tct. cscs 1. / cs为为A中本行下一列元素在中本行下一列元素在s中的下标中的下标 ctct n. ) / ct为为B中本列下一行元素在中本列下一行元素在t中的下标中的下标 cwcw 1. ) 252022-3-3l分析：分析：矩阵乘法算法中包含了三层矩阵乘法算法中包含了三层for循环，所以循环，所以其时间复杂性为其时间复杂性为O (mnp) . 262022-3-3前面所介绍的矩阵类，是以按行优先次序将所前面所介绍的矩阵类，是以按行优先次序将所有矩阵元素存放在一个一维数组中。但是对于有矩阵元素存放在一个一维数组中。但是对

15、于特殊矩阵，如特殊矩阵，如对称对称矩阵、矩阵、三角三角矩阵、矩阵、对角对角矩阵矩阵和和稀疏稀疏矩阵等矩阵等, 如果用矩阵类如果用矩阵类Matrix来实现，来实现，那么大量的存储空间中存放的是重复信息或者那么大量的存储空间中存放的是重复信息或者是零元素，这将造成很大的空间浪费。为节省是零元素，这将造成很大的空间浪费。为节省存储空间，提高算法运行效率，通常会采用压存储空间，提高算法运行效率，通常会采用压缩存储的方法。缩存储的方法。二、特殊矩阵二、特殊矩阵272022-3-3二、特殊矩阵二、特殊矩阵 1、对角矩阵的压缩存储、对角矩阵的压缩存储若若n*n的方阵的方阵M是对角矩阵，则对所有的是对角矩阵，

16、则对所有的ij (0in, 0jj时有时有M(i, j)=0 . 方阵方阵M是下对角矩阵，当且仅当是下对角矩阵，当且仅当ij时有时有M(i, j)=0 . 292022-3-3 以以下三角矩阵下三角矩阵M为例，讨论其压缩存储方法：为例，讨论其压缩存储方法：l将下三角矩阵映射为一个一维数组将下三角矩阵映射为一个一维数组dld需要多少个元素？需要多少个元素？ n(n+1)/2l按行优先方式，按行优先方式， M(i, j)的寻址方式是什么？的寻址方式是什么？302022-3-3l设元素设元素M(i, j)前面有前面有k个元素，可以计算出个元素，可以计算出 k =1+2+ (i 1) + (j 1)=

17、 i(i 1)/2 + (j 1)l设一维数组设一维数组d的下标是从的下标是从0开始，则开始，则M(i, j)映映射到射到d中所对应的元素是中所对应的元素是dk . 有了有了k的计算的计算公式，可以很容易实现下三角矩阵的压缩公式，可以很容易实现下三角矩阵的压缩存储。存储。 312022-3-3 3. 对称矩阵对称矩阵M的压缩存储的压缩存储u 将对称矩阵映射为一个一维数组将对称矩阵映射为一个一维数组du d需要多少个元素？需要多少个元素？ n(n+1)/2u 按行优先方式，按行优先方式， M(i, j)的寻址方式是什么？的寻址方式是什么？322022-3-3li j，映射到，映射到dk，k =

18、i(i 1)/2 + (j 1) li j，映射到映射到dq， q= j(j 1)/2 + (i 1)332022-3-34、稀疏矩阵的压缩存储、稀疏矩阵的压缩存储 定义：设矩阵定义：设矩阵 中非零元素的个数远远中非零元素的个数远远小于零元素的个数，则称小于零元素的个数，则称 A 为稀疏矩阵。为稀疏矩阵。u 特点：零元素的分布一般没有规律，无法特点：零元素的分布一般没有规律，无法简单地利用一维数组和映射公式来实现其压简单地利用一维数组和映射公式来实现其压缩存储。缩存储。u 作用：仅存储非零元素，节省空间。作用：仅存储非零元素，节省空间。Amn342022-3-3l对于矩阵对于矩阵 的每个元素的

19、每个元素aij，知道其行号，知道其行号i和列号和列号j，就可以确定该元素在矩阵中的位，就可以确定该元素在矩阵中的位置。因此，如果用一个结点来存储一个非置。因此，如果用一个结点来存储一个非零元素的话，那么该结点可以设计如下：零元素的话，那么该结点可以设计如下： Am nrowVal(aij)col352022-3-3l由三个域（行号、列号和元素值）构成的结点由三个域（行号、列号和元素值）构成的结点被称为三元组结点：矩阵的每个非零元素可由被称为三元组结点：矩阵的每个非零元素可由一个三元组结点（一个三元组结点（i，j，aij）唯一确定。）唯一确定。l如何在三元组结点的基础上实现对整个稀疏矩如何在三元

20、组结点的基础上实现对整个稀疏矩阵的存储？阵的存储？ 顺序存储顺序存储方式实现的三元组表方式实现的三元组表; 链接存储链接存储方式实现的十字链表。方式实现的十字链表。 362022-3-3三元组表三元组表 将表示稀疏矩阵的非零元素的三元组将表示稀疏矩阵的非零元素的三元组结点结点按行优先按行优先的顺序排列，得到一个线的顺序排列，得到一个线性表，将此线性表用顺序存储结构存储性表，将此线性表用顺序存储结构存储起来，称之为三元组表。起来，称之为三元组表。 372022-3-3 50 0 0 0 10 0 20 0 0 0 0 0 30 0 60 5AB0B1B2B3B4B51132512444-6020

21、-301045031例例 稀疏矩阵稀疏矩阵三元组表三元组表382022-3-3 50 10 0 -30 0 0 0 0 0 20 0 -60 0 0 0 5A例例 稀疏矩阵稀疏矩阵 50 0 0 0 10 0 20 0 0 0 0 0 30 0 60 5A转置矩阵转置矩阵392022-3-3 50 10 0 -30 0 0 0 0 0 20 0 -60 0 0 0 5A例例 稀疏矩阵的三元组表示稀疏矩阵的三元组表示 50 0 0 0 10 0 20 0 0 0 0 0 30 0 60 5Aa0a1a2a3a4a511503220121044534-6014-30b0b1b2b3b4b51150

22、41-30211044543-602320402022-3-3算法算法Transpose(a. b) / 矩阵矩阵A存放在三元组表存放在三元组表a中，求中，求A的转置矩阵并将其的转置矩阵并将其 保存在三元组表保存在三元组表b中中 T1. 初始化初始化 j 0. / 首先赋值三元组表首先赋值三元组表b的第一个结点的第一个结点b0T2. a为空？为空？ IF count = 0 RETURN; / a为空为空 FOR k 1 TO n DO / 对矩阵对矩阵b按行优先依次确认非零元素按行优先依次确认非零元素 FOR i 0 TO t-1 DO / 对每个对每个k扫描所有非零元扫描所有非零元 IF

23、(col( ai ) k THEN / 处理列号为处理列号为k的非零元素的非零元素( row( bj )k. / 行号应为行号应为k col( bj )row( ai ). / 列号应为其在列号应为其在a中的行号中的行号 value( bj )value( ai ). jj 1. ) / 赋值三元组表赋值三元组表b中的下一个结点中的下一个结点412022-3-3l对于一个用三元组表存储的稀疏矩阵对于一个用三元组表存储的稀疏矩阵 ，若矩，若矩阵非零元素个数为阵非零元素个数为t，求，求 的转置矩阵的时间的转置矩阵的时间复杂性是多少呢？复杂性是多少呢？l观察观察Transpose函数不难发现，函数中

24、包含双重函数不难发现，函数中包含双重循环，第一重循环是对转置矩阵循环，第一重循环是对转置矩阵 按行优先依按行优先依次确认非零元素，故循环次数为次确认非零元素，故循环次数为A的行数的行数n；第；第二重循环是扫描原矩阵的三元组表，执行次数是二重循环是扫描原矩阵的三元组表，执行次数是矩阵非零元素个数矩阵非零元素个数t，显然，求转置矩阵的时间复，显然，求转置矩阵的时间复杂性为杂性为O(nt) .nmAnmAmnA422022-3-3稀疏矩阵的三元组表存储方式分析稀疏矩阵的三元组表存储方式分析相应的算法描述较为简单，但对于非零元的相应的算法描述较为简单，但对于非零元的位置位置或或个个数数经常发生变化的矩

25、阵运算就显得不太适合。经常发生变化的矩阵运算就显得不太适合。例例 执行将矩阵执行将矩阵 B 相加到矩阵相加到矩阵 A 上的运算时，某位置上的运算时，某位置上的结果可能会由上的结果可能会由非零元变为零元非零元变为零元，但也可能，但也可能由零元由零元变为非零元变为非零元，这就会引起在，这就会引起在A的三元组表中进行删除的三元组表中进行删除和插入操作，从而导致和插入操作，从而导致大量结点的移动大量结点的移动。432022-3-3a0a1a2a3a4216239124448437b0b1b2b3b411523322134443-7a0115a1126a2214a3221a43212a5434a6448

26、矩阵相加矩阵相加对此类运算采用链式存储结构为宜。对此类运算采用链式存储结构为宜。442022-3-3LEFTUPROWCOL VAL十字链表十字链表矩阵的元素结构如下：分别矩阵的元素结构如下：分别表示该元素的左邻非零元素、表示该元素的左邻非零元素、上邻非零元素、所在的行、上邻非零元素、所在的行、所在的列和它的值。所在的列和它的值。例：稀疏矩阵例：稀疏矩阵800070900004060043214321452022-3-3矩阵的每一行、每一列都设置为由一个表头结矩阵的每一行、每一列都设置为由一个表头结点引导的循环链表，并且各行和各列的表头结点引导的循环链表，并且各行和各列的表头结点有如下特点：点

27、有如下特点： -1 = COL（Loc（BASEROWi） 0 -1 = ROW（Loc（BASECOLj）col(pb) ，则只要将，则只要将pa指针往左推进一步指针往左推进一步，并重新加以比较即可。，并重新加以比较即可。4）col(pa)col(pb) ，则需在，则需在A矩阵的链表中插入矩阵的链表中插入pb所所指结点。指结点。512022-3-3 对矩阵的运算实质上就是在十字链表中对矩阵的运算实质上就是在十字链表中插入结点、删除结点以及改变某些结点插入结点、删除结点以及改变某些结点的的 VAL 域的值。域的值。522022-3-3在十字链表中，因为行或列都是一个循环链表，在十字链表中，因为

28、行或列都是一个循环链表，所以行表头所以行表头BASEROWi中的中的LEFT指针循环地指针循环地链 接 到 该 行 最 右 边 的 非 零 元 素 ， 列 表 头链 接 到 该 行 最 右 边 的 非 零 元 素 ， 列 表 头BASECOLj中的中的UP指针循环地链接到该列最指针循环地链接到该列最下边的非零元素。下边的非零元素。在解线性方程组、求矩阵的逆以及求解线性规在解线性方程组、求矩阵的逆以及求解线性规划等实际问题中划等实际问题中, 都需要施行一种都需要施行一种主步骤主步骤操作，操作，即如下的矩阵变换：即如下的矩阵变换： 532022-3-3 abcd变换前主列别列主行别行 1/ab a

29、c adbc a变换后主列别列主行别行变换前，若某主行别列元素为变换前，若某主行别列元素为0或某别行主列元素为或某别行主列元素为0，则变换后它们仍然为零。则变换后它们仍然为零。对某别行别列元素对某别行别列元素Aij，仅当其对应的主行，仅当其对应的主行j列和主列列和主列i行元素皆非零，它才需要被处理。行元素皆非零，它才需要被处理。 542022-3-3 50 0 0 0 10 0 20 0 0 0 0 0 30 0 60 5A 处于处于主行主列主行主列的非零元素的非零元素 a 被称为被称为主元素主元素.下面下面选矩阵选矩阵A 的的A21 10为主元素，执行主步骤为主元素，执行主步骤操作。操作。5

30、52022-3-30001010100001010505050501010000010303010060510020010200101010020002010130300010562022-3-3经主步骤操作后矩阵经主步骤操作后矩阵A变成变成A*；A*之第之第3列第列第1行的行的元素变成非零，第元素变成非零，第3列第列第4行的非零元素变为零；行的非零元素变为零；A*仍然是稀疏矩阵。仍然是稀疏矩阵。5000.1 02000005100030 A* A 500000200000030010065572022-3-3算法算法 SP（BASE，PIVOT）/ 稀疏矩阵的主步骤操作，稀疏矩阵的表示方式为

31、正交链表，指针稀疏矩阵的主步骤操作，稀疏矩阵的表示方式为正交链表，指针/变量变量PIVOT指向主元素，一维数组指向主元素，一维数组PTR1:n是指针型是指针型SP1 初始化，确定主行初始化，确定主行I0，主列，主列J0 I0ROW(PIVOT) . J0COL(PIVOT) . 1.0 / VAL(PIVOT) . VAL(PIVOT) 1.0 . P0Loc(BASEROWI0) . Q0Loc (BASECOLJ0) .SP2 处理主行处理主行I0 P0LEFT(P0) . JCOL(P0) . IF J0 THEN GOTO SP3. ELSE (PTRJ Loc(BASECOLJ) .

32、 VAL(P0) * VAL(P0) . GOTO SP2. ) .SP3 找新行找新行I，并指定，并指定P1 Q0UP(Q0) . IROW (Q0) . IF I0 THEN RETURN . IF I=I0 THEN GOTO SP3 . PLoc(BASEROWI) . P1LEFT(P) .582022-3-3SP4 确定新列确定新列J P0LEFT(P0) . JCOL(P0) . IF J J DO (PP1 . P1LEFT(P) . IF COL(P1) =J THEN GOTO SP7 .SP6 插入新元素插入新元素 WHILE ROW(UP(PTRJ) I DO PTRJ

33、UP(PTRJ) . X=AVAIL . VAL(X) VAL(Q0) VAL(P0) . ROW(X) I . COL(X) J . LEFT(X) P1 . UP(X) UP(PTRJ) . LEFT(P) X . P X. UP(PTRJ) X . PTRJ X . GOTO SP4.592022-3-3SP7 主步骤操作主步骤操作 VAL(P1) VAL(P1) - VAL(Q0)* VAL(P0) . IF VAL(P1)=0 THEN GOTO SP8 . ELSE (PTRJP1 . PP1 . P1LEFT(P) . GOTO SP4 . ) . SP8 删除零元素删除零元素

34、WHILE UP(PTRJ) P1 DO PTRJUP(PTRJ) . UP(PTRJ)UP(P1) . LEFT(P)LEFT(P1) . AVAIL = P1 . P1 LEFT(P) . GOTO SP4. 602022-3-3第三章第三章 数组和字符串数组和字符串l第一节第一节 数组数组l第二节第二节 矩阵矩阵l第三节第三节 字符串字符串612022-3-3一、字符串的定义和实现一、字符串的定义和实现l串的定义：串是由串的定义：串是由零个或多个字符顺序排列零个或多个字符顺序排列组成的组成的有限序列。有限序列。 如字符串如字符串 S 可记作：可记作： S “a0a1 an-1” S是是串

35、名串名，引号中的字符序列是，引号中的字符序列是串值串值， 字符个数字符个数n是是串长度串长度。l空串：长度为空串：长度为零零的串称为空串。的串称为空串。l空白串：由一个或多个空白串：由一个或多个空格空格组成的串称为空白串。组成的串称为空白串。3.3 字符串字符串 622022-3-3l子串子串：某某串中任意个串中任意个连续连续字符组成的序列称为该字符组成的序列称为该串的子串，相对于子串它又被称作主串。串的子串，相对于子串它又被称作主串。l子串在主串中子串在主串中第一次第一次出现时，出现时，其首字符在主串中其首字符在主串中的序号被称为的序号被称为该子串在主串中的位置该子串在主串中的位置。l例例

36、A = “This is a string” B = “is” 子串子串B = “is”在主串中的位置是在主串中的位置是3632022-3-31、串的顺序存储：把一个串所包含的字符序列相继存、串的顺序存储：把一个串所包含的字符序列相继存入连续的字节中入连续的字节中 (1) 非紧缩格式非紧缩格式 : 一个存储单元存放一个字符一个存储单元存放一个字符 例例 S “a0a1 an-1” a0a1an-1Word0Word1Wordn-1二、字符串的存储方式二、字符串的存储方式642022-3-3(2) 紧缩格式紧缩格式 : 一个存储单元存放一个存储单元存放多个多个字符字符 例例 S=“a0a1 an

37、-1” / 一个存储单元存放一个存储单元存放4个字符个字符 a1a4an-1Word0Word1a0a2a3a5a6a7an-2Word n/4 -1652022-3-32、串的链式存储：串的链式存储：串的链接存储是把可用的存储空间串的链接存储是把可用的存储空间分成一系列大小相同的结点，其中每个结点的结构分成一系列大小相同的结点，其中每个结点的结构为为（str, link）5china p 结点大小为结点大小为4的链串的链串Sc5hian 结点大小为结点大小为1的链串的链串662022-3-3例：有两个链接方式存储的串例：有两个链接方式存储的串S和和T，将，将T所所 指串插入到指串插入到S所指

38、串第所指串第i个字符之后。个字符之后。672022-3-3算法算法STRI（S , T, i . S)/*S和和T是两个链式串，算法是两个链式串，算法STRI将串将串T插到串插到串S的第的第 i 个字符之后；串个字符之后；串S和和T的元素有两个域的元素有两个域str和和link，str域的值为字符，域的值为字符，link域存放指向下一结点的指针，串域存放指向下一结点的指针，串S和和T的首结点的的首结点的str域的值为串长域的值为串长 */STRI1 初始化初始化 L1STR(S). L2 STR(T). IF (iL1) THEN (PRINT ” String Length error”.

39、RETURN )IF L2=0 THEN RETURN. IF L1=0 THEN ( S T. RETURN )682022-3-3STRI2寻找插入位置寻找插入位置 P S. j 0.WHILE ( j i ) DO ( P LINK(P). j j+1 )STRI3插入插入 T1 LINK(T). SAVE LINK(P).LINK(P) T1.WHILE LINK(T1) DO T1 LINK(T1). /*T1指向串指向串T的尾部结点的尾部结点*/LINK(T1) SAVE.STR(S) L1+L2. 692022-3-3模式匹配问题定义模式匹配问题定义朴素模式匹配算法及时间复杂性分

40、析朴素模式匹配算法及时间复杂性分析快速模式匹配算法（快速模式匹配算法（KMP算法）算法）三、三、 模式匹配算法模式匹配算法702022-3-3在在目标串目标串中寻找中寻找模式串模式串出现的出现的首位置首位置； 给定两个字符串给定两个字符串S和和P，其中目标，其中目标S有有n个字符，模式个字符，模式P有有m个个字符，字符，m=n。从。从S的第一个字符开始，搜索模式的第一个字符开始，搜索模式P，如果找，如果找到，返回模式到，返回模式P的第一个字符在的第一个字符在S中的位置；如果没找到（中的位置；如果没找到（即即S中不包含中不包含P），则返回），则返回-1 。 例：例：S= “abaaabab”,

41、P = “abab” 模式匹配的应用模式匹配的应用 - 文本编辑器中常用的文本编辑器中常用的“查找查找”、“替换替换” - 搜索引擎中的关键字检索搜索引擎中的关键字检索 - 生物信息学的基因序列生物信息学的基因序列(DNA)匹配匹配 CATTGGTATATTGGAGGTT ATTGGCTA 1、模式匹配问题定义、模式匹配问题定义712022-3-3722022-3-3第一次匹配第一次匹配:从从S 的第一个字符开始的第一个字符开始, 将将 P (长度为长度为m)中字符依中字符依次与次与 S 中的字符做比较中的字符做比较, 若若s0 p0, s1 p1, , sm 1 pm 1, 则匹配则匹配成功

42、成功, 返回与返回与p0相匹配的字符相匹配的字符s0在在S中的位置中的位置(下标下标0)；若某一；若某一步步si pi , 说明此次匹配不成功，以下比较无需进行说明此次匹配不成功，以下比较无需进行. 于是进行于是进行第二次匹配第二次匹配:从从S的第二个字符开始的第二个字符开始, 重复刚才的步骤重复刚才的步骤, 看是否看是否有有s1 p0, s2 p1, , sm pm 1, 若有则匹配成功，返回与若有则匹配成功，返回与p0相匹配相匹配的字符的字符s1在在S中的位置中的位置(下标下标1). 否则进行否则进行第三次匹配第三次匹配:从从S的第的第三个字符开始三个字符开始 若若第第n m 1次次(最后

43、一次最后一次)匹配匹配仍得不到仍得不到sn m p0, sn m 1 p1, , sn 1 pm 1 ，说明匹配完全失败，返回，说明匹配完全失败，返回 1 .2. 朴素模式匹配算法的主要思想朴素模式匹配算法的主要思想732022-3-3算法算法StringMatching( S, P ) 朴素模式匹配算法朴素模式匹配算法/ S为目标串，为目标串，P为模式串，返回为模式串，返回S中首个中首个P子串的位置子串的位置SM1. 初始化初始化i0 .SM2. 逐字符匹配逐字符匹配WHILE i | S |-| P | DO /*从目标串的字符从目标串的字符Si开始，开始，与模式串与模式串P逐字符匹配逐字

44、符匹配*/( j0 . WHILE Si = Pj AND j | P | DO( ii+1 . jj+1 ) IF j = | P | THEN RETURN i | P | . / 匹配成功匹配成功 ii j + 1 )SM 3 匹配失败匹配失败RETURN 1. 742022-3-3S :abaaababP:abab abababababababab 朴素模式匹配算法朴素模式匹配算法752022-3-3l基本运算：基本运算：字符比较字符比较l最好时间复杂性：最好时间复杂性： B(n, m) = ml最坏时间复杂性：最坏时间复杂性： W(n, m) =m*(n-m+1) = O(n*m)l

45、平均时间复杂性：平均时间复杂性： E(n, m) = O(n*m)l朴素模式匹配算法的优点是过程简单，缺点朴素模式匹配算法的优点是过程简单，缺点是效率比较低。是效率比较低。 朴素模式匹配算法时间复杂性朴素模式匹配算法时间复杂性762022-3-3朴素模式匹配算法平均时间复杂性朴素模式匹配算法平均时间复杂性,( , )( )( )11()1221(1)(1)2111(1)(1)( (1)()(1)(1)242()m nI DE m nP IT IqmmmmnmmnmmqnmnmmqmnmmnmmO mn 772022-3-3 基本思想基本思想朴素模式匹配算法朴素模式匹配算法中，中，S S中的字符

46、参与了中的字符参与了多多次次比较比较（最坏情况下是（最坏情况下是m m次比较）次比较）原因是：匹配失败后，下次的匹配位置原因是：匹配失败后，下次的匹配位置仅向仅向右移动一位字符右移动一位字符能否移动多个字符，从而加速匹配过程，并能否移动多个字符，从而加速匹配过程，并且使且使S S中的字符尽可能只被比较中的字符尽可能只被比较1 1次？次？3. 快速模式匹配算法快速模式匹配算法(KMP)D.E.Knuth, V.R.Pratt, J.H.Morris, 1977 782022-3-3l朴素模式匹配算法效率不高的主要原因是朴素模式匹配算法效率不高的主要原因是进行了重复的字符比较进行了重复的字符比较l

47、对于模式串对于模式串P = abab ，目标串，目标串S = abaaabab ，其朴素的模式匹配过程为，其朴素的模式匹配过程为792022-3-3我们发现我们发现 P0 P2, P1 P3, P0 P1S1=P1 ，P1 P0第二次比较必然失败第二次比较必然失败第一次第一次比较次数比较次数4S :abaaabab=P:abab802022-3-3S1=P1 ，P1 P0第二次比较必然失败第二次比较必然失败S3P3 ， P3=P1第第三三次比较必然失败次比较必然失败第一次第一次比较次数比较次数4S :abaaabab=P:abab812022-3-3第二次匹配第二次匹配比较次数比较次数 1S

48、:abaaababP:abab第三次匹配第三次匹配比较次数比较次数 2S :abaaabab=P:ababS1 P0S3 P1可见可见, 第一次匹配后，接着只需进行第四、第第一次匹配后，接着只需进行第四、第五次匹配五次匹配822022-3-3一般情况一般情况:设目标串设目标串S “s0 , s1, sn 1”,模式串模式串P “p0, p1, pm 1”假设当前正进行假设当前正进行 t 1次匹配次匹配, 有有st st 1st j p0 p1pj , 但但 st j 1 pj 1于是于是 t 1次匹配失败。次匹配失败。Ss0stst 1st 2st jst j 1sn 1 Pt 1次匹配次匹配

49、p0p1p2pjpj 1Pt 2次匹配次匹配p0p1pj 1t 2次匹配次匹配（t 2 t 1 1）应从应从 st 1 开始，比较是否有开始，比较是否有 st 1 st 2st m p0 p1 pm 1但由但由 t 1次匹配次匹配，知，知 st 1 st 2st j p1 p2 pj 如果如果 p0 p1 pj 1 p1 p2 pj ，则可断定，则可断定 t 2次匹配次匹配必然失败必然失败 832022-3-3ss0stst 1st 2st jst j 1sn 1 p(t 1次匹配次匹配)p0p1p2pjpj 1p(t 2次匹配次匹配)p0p1pj 1p(t 3次匹配次匹配)p0pj 2t 3

50、次匹配（次匹配（t 3 t 1 2）同理由同理由 t 1次匹配知次匹配知 st 2st 3st j p2 p3pj ,若若p0 p1 pj 2 p2 p3 pj ，则可断定，则可断定t 3次匹配必然失败次匹配必然失败.第第 t x 次匹配次匹配 (t x t 1 x 1): 判断判断 p0 p1 pj (x 1) px 1 px px 1 pj 令令k j (x 1) , 则则x 1 j k , x j k 1 , t x t j k 1 p0 p1 pk pj k pj k 1 pj k 2 pj842022-3-3以此类推以此类推, 直至存在一个直至存在一个k, 使得使得 p0 p1pk

51、pj k pj k 1pj 且且 p0 p1 pk pk 1 pj k 1 pj k pj k 1pj (3-4)则可直接进行则可直接进行t 1 j k次次比较，因为已知比较，因为已知 st j k st j k 1 st j pj k pj k 1 pj p0 p1 pk 故只须从故只须从 t +1次匹配时次匹配时 S 的失配字符的失配字符st j 1开始开始, 考察是否有考察是否有 st j 1 st j 2 st j m 1 k pk 1 pk 2 pm 1 继续进行以后继续进行以后m 1 k个个字符的匹配。字符的匹配。 总之，当总之，当 t +1次匹配失败时，指针次匹配失败时，指针 s

52、 指向指向 st j 1，指针，指针 s 无须无须回溯到回溯到 st 1，计算出指针，计算出指针p 指向指向 pk 1，指针指针p也无须回溯到也无须回溯到 p0，就，就可继续进行匹配。可继续进行匹配。即进行即进行 st j 1 与与 pk 1 之匹配。之匹配。 852022-3-3p0p1pkpk+1pj k 1pj kpj问题是如何确定式问题是如何确定式(3-4)中的中的 k 值值. 克努斯等发现克努斯等发现, 对不同的对不同的 j, 应取不同的应取不同的 k 值值, 就是说就是说 k 的取值只与模式的取值只与模式 P 的前的前 j 个字符构个字符构成有关成有关。因此，可因此，可给出一个失败

53、函数给出一个失败函数 f ( j )，用它来确定，用它来确定 k即即 f ( j ) k p0 p1pk pj k pj k 1pj p0 p1 pk pk 1 pj k 1pj k pj k 1pj从从 p0 p1pj 中找出中找出两个最大的相等子串两个最大的相等子串, 一个从前向后一个从前向后, 一一个个从后向前。从后向前。 862022-3-3失败函数失败函数当匹配失败时，如何确定新的匹配位置，即，当匹配失败时，如何确定新的匹配位置，即，确定确定P中的哪个字符和中的哪个字符和S中的失败点字符重新匹配中的失败点字符重新匹配。设模式设模式 P p0 p1pm 1 ，P的失败函数定义为：的失败函数定义为：f( j ) k，k 是满足是满足 0 k j 且且 p0 p1pk pj k pj k 1pj 的的最大整数最大整数 1，其它情况其它情况1、注意上式中，有、注意上式中，有 j 02、f( j )是最大子串长度减一是最大子串长度减一872022-3-3在在 p0 p1pj 中找出中找出最大的前后相等子串最大的前后相等子串，使得：，使得： p0 p1pk pj k pj k 1pj 用用归纳法归纳法计算失败函数计算失败函数, 设设f (0) 1, 已知已知 f( j ) k, 求求 f ( j