第三章-数组和字符串(数据结构word版课件).doc

第三章 数组和字符串
§3.1 数 组
3.1.1 数组的存储和寻址
一个一维数组就是若干元素的一个有限序列，而其每个元素都通过一个下标来指定，且元素本身就是一个数据结构（或是整型、逻辑型、字符型等简单数据类型，或是数组、记录等复杂数据类型）。对一维数组唯一的限制是所有的元素都具有相同的类型，并占据相同大小的存储空间。因数组元素要通过数组名及紧跟其后的方括号中的下标来确定，故一个一维数组就对应一个下标函数。
下面我们讨论数组在计算机存储器中的存储方式。因为通常不进行数组的插入或者删除操作，所以在内存储器中我们选择顺序存储方式实现数组的存储。
在内存中以“线性式”的方式组织数组很方便。设一维数组A[n]存放在n个连续的存储单元中，每个数组元素占一个存储单元（不妨设为C个连续字节）。如果数组元素A[0]的首地址是L，则A[1]的首地址是L+C，A[2]的首地址是L+2C，… …，依次类推，对于有：
Loc (A[i])=Loc (A[0])+i´C
对于高维数组（多维的数据结构）之存储，可将其转化为一维来实现。因此必须对高维数组元素的存放次序进行约定。高维数组通常有两种存放次序约定——按行优先顺序和按列优先顺序.
首先介绍按行优先顺序。所谓按行优先顺序，就是将高维数组元素按行向量的顺序存储，第个行向量存储在第个行向量之后。换句话说，就是用一维数组的存储结构来解决高维数组的存储问题。
设A为n维数组，其每个元素占C个字节，且第一个元素的地址为，若要算出该数组的任一个元素的地址，可将n维数组可考虑为如下一维数组
( ，，…， )
设该数组的每个元素占C1个字节。显然，包含的数组元素实际与一个n-1维数组(包含个的数组元素)相同，于是我们有： .
又可将（）看作如下一维数组
(, , …,)
设它的每个元素占C2个字节，显然C2 = m3´m4 ´¼´mn´C ；
如此类推，设一维数组
(，，…， )
设它的每个元素占个字节，则Cn-1=mn ´ C .
故的存储地址为：

所谓按列优先顺序，就是将数组元素按列向量的顺序存储，第i+1个列向量存储在第i个列向量之后。换句话说，就是将数组转化为一维数组来考虑。请读者计算以按列优先顺序存储的多维数组中任一个元素的存储地址。
§3.2 矩 阵
3.2.1 矩阵类
矩阵的乘法运算略为复杂，对于矩阵Am×p和Bp×n的乘积Cm×n ，其第i行第j列元素cij的计算公式为，显然乘法运算的算法可描述如下：
算法Multi-1(A, B, C, m, p, n) // 求矩阵与的乘积
FOR i=1 TO m DO
FOR j=1 TO n DO
( .
FOR k=1 TO p DO
. ) ▐
前面提到过，可直接以按行优先次序用一维数组存放矩阵元素，下面给出的算法Multi-2是对用一维数组所存放矩阵的乘法运算实现。该算法中用一维数组s存放Am×p，用一维数组t存放Bp×n，求存放A与B的乘积Cm×n 的一维数组w.
由矩阵乘法公式知，其中aik是矩阵A中第i行第k列的元素，bkj是矩阵B中第k行第j列的元素，因为矩阵A和B分别按行优先存放在一维数组s和t中，所以ai(k+1)在s中的下标比aik在s中的下标多1，b(k+1)j在t中的下标比bkj在t中的下标多n .这说明，随着一个矩阵元素行号或列号的变换，其在对应的一维数组的下标要进行相应变换。
算法Multi-2(s, t, w, m, p, n)
// Am×p用一维数组s存放，Bp×n用一维数组t存放，求A与B的乘积Cm×n并用一维数组w存放
M1. [初始化]
cw¬0 . // 初始时cw是c11在一维数组w中的下标
M2. [循环]
FOR i=1 TO m DO // 第一层循环
cs¬(i-1)×p. // 令cs为ai1在一维数组s中的下标
ct¬0. // 令ct为b11在一维数组t中的下标
FOR j=1 TO n DO // 第二层循环
( ct¬j-1. // 令ct为b1j在t中的下标
w[cw]¬0 .
FOR k=1 TO p DO // 第三层循环，叠加aik×bkj 并存于w[cw]中
( w[cw]¬w[cw]+s[cs]´t[ct].
cs¬cs+1. // cs为A中本行下一列元素在s中的下标
ct¬ct+n. ) // ct为B中本列下一行元素在t中的下标
cw¬cw+1. ) ) ▐

3.2.2 特殊矩阵
前一小节所介绍的矩阵类，是以按行优先次序将所有矩阵元素存放在一个一维数组中。但是对于特殊矩阵，如对称矩阵、三角矩阵、对角矩阵和稀疏矩阵等, 如果用矩阵类Matrix来实现，那么大量的存储空间中存放的是重复信息或者是零元素，这样造成很大的空间浪费。为节约存储空间和算法（程序）运行时间，通常会采用压缩存储的方法。
对角矩阵的压缩存储
n´n维方阵M是对角矩阵，则对 "i ¹ j (1£ i , j £ n)，都有M(i, j)=0，即非对角线上的元素均为0 .

对于一个n´n维对角矩阵，至多只有n个非零元素，因此只需存储其n个对角元素的信息。很容易想到，采用一维数组d[n]来压缩存储对角矩阵，其中d[i]存储M[i,i]的值。
三角矩阵的压缩存储
三角矩阵分为上三角矩阵和下三角矩阵。方阵M是上三角矩阵，当且仅当i > j时有M(i, j)=0 . 方阵M是下三角矩阵，当且仅当i < j时有M(i, j)=0 .

我们以下三角矩阵为例，讨论其压缩存储方法。
考虑一个n´n维下三角矩阵，其第一行至多有1个非零元素，第二行至多有2个非零元素，¼，第n行至多有n个非零元素，非零元素至多共有(1+2+¼+n) = n(n+1)/2个。可以用大小为n(n+1)/2的一维数组来存储下三角矩阵，换言之，就是要把下三角矩阵M的非零元素映射到一个一维数组d中。映射次序可采用按行优先或按列优先。假设映射采取按行优先，非零元素M(i, j)会映射到一维数组d中的哪个元素？
设元素M(i, j)前面有k个元素，则k可计算如下：
k =1+2+¼+(i -1)+( j-1)=i(i-1)/2+( j-1)
设一维数组d的下标是从0开始，则M(i, j)映射到d中所对应的元素是d[k] . 有了k的计算公式，可以很容易实现下三角矩阵的压缩存储。
对称矩阵的压缩存储
n´n方阵M是对称矩阵，当且仅当对"i , j (1£ i , j £ n)，均有M(i , j) = M( j , i) .

因为对称矩阵中M(i, j)与M(j, i)的信息相同，所以只需存储其上三角部分或下三角部分的元素信息。
稀疏矩阵的压缩存储
若m´n 矩阵 A 中的非零元素的个数远小于零元素的个数，且零元素的分布没有规律, 则矩阵 A 被称为稀疏矩阵。
与前面介绍的几种特殊矩阵不同，稀疏矩阵中的大多数元素为零元素，且零元素的分布没有明确规律，甚至根本没有规律，因此无法简单地利用一维数组和映射公式来实现其压缩存储。
对于m´n矩阵A的每个元素apq，知道其行号p和列号q，就可以确定该元素在矩阵中的位置。因此，如果用一个结点来存储矩阵A的一个非零元apq，那么该结点可设计如下：
row
col
value

如上所示，由三个域row, col, value构成的结点被称为三元组结点，其中row=p-1，col=q-1，val=apq的值，row，col，val分别是矩阵A之非零元素apq的行号减1，列号减1和apq的值。由此可见，矩阵A的任一非零元素apq可由一个三元组结点唯一确定。
如何在三元组结点的基础上实现对整个稀疏矩阵的存储？接下来的3.2.3和3.2.4两小节将分别介绍用顺序存储方式实现的三元组表和链接存储方式实现的十字链表。
3.2.3 三元组表
将表示稀疏矩阵A的所有非零元素的三元组结点按行优先的顺序排列，可得到一个线性表LL，用顺序存储方式存储的线性表LL，被称为三元组表。

例如：

B[0]

B[1]

B[2]

B[3]

B[4]

B[5]

0
0
50
1
0
10
1
2
20
3
0
-30
3
2
-60
3
3
5

图3.1 稀疏矩阵A对应三元组表

我们知道，若矩阵，则其转置矩阵. 仍以（3-1）给出的稀疏矩阵A为例，A的转置矩阵为：
（3-2）
（3-2）所示的转置矩阵A′所对应的三元组表示为：

C[0]

C[1]

C[2]

C[3]

C[4]

C[5]

0
0
50
0
1
10
0
3
-30
2
1
20
2
3
-60
3
3
5

下面给出求转置矩阵的ADL算法描述，其中假设稀疏矩阵存储在一个三元组表a中，且A的非零元素个数为count，算法Transpose求A的转置矩阵并将其保存在三元组表b中。本算法的主要思想是针对每个列号k（k=0, 1, ¼, n-1），对a进行扫描，考察a中是否有列号为k的结点 (注意列号为k的结点可能不止一个)，若有，记为a[u] (假定a[u]在a中的行号为i)，将a[u]依次保存在b的b[w] 中，则row(b[w])=k，col(b[w])=i，val(b[w])= val(a[u]).

算法Transpose(a, b)
// 已知矩阵A存放在三元组表a中，求A的转置矩阵并将其保存在三元组表b中
T1. [初始化]
j=0. // 首先考察三元组表b的第一个结点b[0]
T2. [a为空？]
IF count > 0 THEN
( FOR k=0 TO n-1 DO
FOR i=0 TO count-1 DO
IF (col( a[i] )=k THEN
( row( b[j] )¬k.
col( b[j] )¬row( a[i] ).
value( b[j] )¬value( a[i] )
).
j¬j+1. ) // 考察三元组表b中的下一个结点 ▐

对于用三元组表存储的稀疏矩阵，若矩阵非零元素个数为t，求其转置矩阵的时间复杂性是多少？观察Transpose算法不难发现，函数中包含两重循环，第一重循环是对转置矩阵按行优先依次确认非零元素，故循环次数为A′的行数n；第二重循环是扫描原矩阵的三元组表，执行次数是矩阵A的非零元素个数t，显然，求转置矩阵的时间复杂性为O(nt) .
用三元组表存储稀疏矩阵，无论是添加或删除矩阵非零元素，还是对矩阵实施某些操作（例如A¬A+B），都可能引起矩阵中非零元素的个数和位置的变化，这些变化将引起与矩阵对应的三元组表中大量结点的移动，效率较低。用链接存储方式实现稀疏矩阵则会避免这些问题。下面介绍稀疏矩阵的一种链接存储方式——十字链表。
3.2.4 十字链表
在稀疏矩阵的十字链表中，矩阵的每一行都设置为由一个表头结点引导的循环链表（简称为行链表），矩阵的每一列也都设置为由一个表头结点引导的循环链表（简称为列链表）。
矩阵的元素结构如下：
LEFT
UP
ROW
COL
VAL

其中LEFT和UP是指针变量，分别存放该元素的左邻非零元素和上邻非零元素的地址信息，ROW和COL存放该元素在矩阵中的行号和列号，VAL存放元素值。
下图给出一个稀疏矩阵和它的十字链表：
（3-3）

图 3.2 十字链表

-1

-1

-1

-1

-1

-1

-1

1
3
6

2
1
4

4
4
8

-1

3
2
9

3
4
7

这里，每一行和每一列都有一个表头结点：
BASEROW[i]，i=1，2，¼，m（m行）
BASECOL[j]， j=1，2，¼，n（n列）
且
-1 = COL（Loc（BASEROW[i]））< 0
-1 = ROW（Loc（BASECOL[j]））< 0
因为行或列都是一个循环链表，所以行表头BASEROW[i]中的LEFT指针循环地链接到该行最右边的非零元素，列表头BASECOL[j]中的UP指针循环地链接到该列最下边的非零元素。
§3.3 字符串
3.3.1 字符串的定义与字符串类
字符串(String)是由零个或多个字符(char)顺序排列组成的有限序列，简称为串。例如 “good morning”就是由12个字符构成的一个字符串。一般把字符串记作：

其中S是串名，引号中的字符序列是串值。字符个数是串的长度，长度为0的串被称为空串，因为它不包含任何字符。注意“⊔”并非空串，因为它包含一个字符——空格，被称为空白传。
若把某个串称为主串，则主串中任意个连续的字符组成的子序列被称为子串。子串在主串中第一次出现时，其首字符在主串中的序号被称为该子串在主串中的位置。
字符串是许多非数值计算问题处理的主要对象，在模式匹配、程序编译及数据处理等领域中均有应用。
在C++语言中, 可直接用字符串指针（例如char *p =“good”）或者字符数组（例如char a[] =“good”）创建顺序存储的字符串，前者声明创建指针变量p，指向在存储空间某处的字符串“good”（以 ‘\n’结尾）中的字母g，后者声明创建一个具有5个元素的数组a，它包含字符‘g’、 ‘o’、 ‘o’、 ‘d’、 ‘\n’ . 利用标准头文件<cString>（早期的C++使用 <String.h>）所提供的处理字符串的库函数，可以对字符串进行操作。人们把C++语言中的<cString>函数库作为字符串数据类型的一种方案，并将其称之为“标准字符串”。
3.3.2 模式匹配算法
文本编辑器中常用的“查找”、“替换”和“全部替换”等基本的编辑操作就是最普通的模式匹配问题，即：在文本文件中查找串。它的查找过程可简单描述如下：给定两个字符串变量和，其中目标串有个字符，模式串有个字符， . 从的给定位置（通常为的第一个字符）开始，搜索模式，如果找到，返回模式的第一个字符在中的位置；如果没找到（即中没有），则返回-1 .
朴素的模式匹配算法
关于模式匹配，最简单的方法是：从的第一个字符开始，将（长度为）中字符依次与中的字符进行比较，若，则匹配成功，返回与相匹配的字符在中的位置（下标0） ；若某一步，说明此次匹配不成功，以下比较无需进行。于是再从的第二个字符开始进行第二次匹配，重复刚才的步骤，看是否有，若匹配成功，返回与相匹配的字符在中的下标1. 否则从的第三个字符开始进行第三次匹配. … ¼ 若第次匹配（即最后一次匹配）仍得不到，说明匹配失败，返回 -1 .
这种模式匹配算法被称为朴素的模式匹配算法，该算法的ADL描述如下：
算法StringMatching
INT StringMatching ( S, P )
// S为目标串，P为模式串，返回S中首个P子串的位置
SM1. [初始化]
i←0 . // i是目标串开始匹配的位置
SM2. [逐字符匹配]
WHILE i ≤ | S |-| P | DO //从目标串的字符Si开始，与模式串P逐字符匹配
( j←0 . // j是模式串开始匹配的位置
WHILE Si = Pj AND j < | P | DO
( i←i+1 . j←j+1 )
IF j = | P | THEN RETURN i – | P | . // 匹配成功
i←i – j + 1 )
SM 3 [匹配失败]
RETURN –1 .▐

朴素模式匹配算法的优点是过程简单，缺点是效率低。在最坏情况下，该算法要匹配次，每次匹配要做次比较，因此最坏情况下的比较次数是，时间复杂性为，通常情况下，的值远小于的值，于是最坏情况下的时间复杂性可粗略地记为 .

模式匹配的改进算法
朴素模式匹配算法效率不高的主要原因是进行了重复的字符比较，我们考虑如下例子：
对于模式串P = " abab "，目标串S = " abaaabab "，其朴素的模式匹配过程为

第一次 S a b a a a b a b
|| || || \
P a b a b

第二次 S a b a a a b a b
\
P a b a b

第三次 S a b a a a b a b
|| \
P a b a b

第五次 S a b a a a b a b
|| || || ||
P a b a b

第四次 S a b a a a b a b
|| \
P a b a b

显然，用朴素模式匹配算法解决该例，需要进行5次匹配。但是通过对模式的结构进行研究，可以发现，，，，通过第一次比较知道：
（1），因此第二次比较必然失败；
（2），因此第三次比较必然失败。
于是我们只须进行第四次、第五次比较，就可以匹配成功，显然对模式进行分析可以减少比较次数，从而降低算法的时间复杂性，提高运行效率。
我们就一般情形进行讨论。

设目标串S= ，模式串P = ，假设当前正在进行第t+1次匹配，有，但是，于是此次匹配失败。
若按照朴素的模式匹配算法，第t+2次匹配应从开始，比较是否有

但是根据第t+1次匹配，已知，如果，则我们可以断定第t+2次匹配必然失败。
再考虑第t+3次匹配，同样的道理，根据第t+1次匹配，已知，如果，可以断定第t+3次匹配必然失败.
依次类推，直至存在一个k，使得
且 （3.4）
那么我们可以直接进行第t+j-k+1次比较，因为已知

故只须从第t+1次匹配时S的失配字符开始，考察是否有

继续进行以后字符的匹配。

总结来说，当第t+1次匹配失败时，指针s指向，指针p指向，由上述说明可知，指针s无须回溯到，指针p也无须回溯到，需要做的只是将指针p回溯至，就可继续进行匹配。
问题是：如何确定式（3.4）中的k值 . D.E.Knuth等人发现，对于不同的j，应取不同的k值，也就是说，k的取值只与模式P的前j个字符构成有关，而与目标S无关。因此，可以给出一个失败函数f ( j )，用它来确定k .
设模式 ，P的失败函数可定义成：
， k为满足，且的最大整数
-1，其他情况
f( j)=

下面给出利用失败函数的KMP算法 (Knuth–Morris–Pratt算法) 实现FastFind .

// 整型数组f [ ] 表示失败函数，它应该在类定义中说明为私有数据成员
int String :: FastFind（String pat）const
{
int p = 0，s = 0 ; // 给出模式和目标的扫描指针的初始位置
int m = pat.size，n = size ; // 模式和目标的长度
while（p < m && s < n ）
if（pat.str[p] = = str[s] ）
{ p++ ; s ++ ; }
else if（p = = 0） s++ ; // 若第一个字符就匹配失败，则从S的下一个字符开始
else p = pat.f [ p-1 ] + 1 ; // 用失败函数来确定p应回溯到的字符
if（p < m） // 整个匹配过程失败
return –1 ;
return s – m ;
}
显然，KMP算法的关键是计算，即在中找出最大的前后相等的子串，使得：

我们设，用归纳法来计算失败函数。设已知，欲求得 .
（1）如果，显然 .
如果，则必有 . 寻找h，使它满足h<k，且

这就是说， .
（2）如果不存在这样的h，说明中没有前后相等的子串，因此

如果存在这样的h，再检验是否成立。若成立，说明已找到中最大的前后相等的子串，即：

于是 .
若，再在中寻找最大的前后相等的子串，其中，检验是否有 . 如此类推，如果找到了某个t，使得

则 .
如果不存在这样的，那么 .
于是可以给出失败函数的递推公式（3.5）：

，若能找到最小的整数，使得
-1，若上述的不存在
（3.5）

下面分别给出计算的算法的ADL描述，其C++实现见附录3.3：
算法Fail ( P$ . f ) // 失败函数
F1. [赋初值]
m ¬ size（P$）. f (0)¬ – 1 .
F2. [循环计算]
FOR j = 1 TO m – 1 DO
( i ¬f (j – 1).
WHILE AND i > 0 DO
i ¬f (i).
IF THEN f (j)¬i +1
ELSE f (j)¬ – 1. ) ▐
由失败函数的定义，我们知道算法Fail中的WHILE循环每次重复时，i值是严格递减的。由递推公式(3.5)还可知道，FOR循环中i值的增量至多为m . 由上述分析知，整个计算过程中i值的减少不可能多于m次，WHILE循环的总比较次数至多为m次，故算法Fail的时间复杂性为 .
在KMP算法中，字符比较是沿着目标S前进的（不返回），因此该算法的时间复杂性为，综上所述，采用失败函数的模式匹配算法的时间复杂性为 .