《第三章 数组和字符串（数据结构word版课件）.doc》由会员分享，可在线阅读，更多相关《第三章 数组和字符串（数据结构word版课件）.doc（21页珍藏版）》请在三一文库上搜索。
1、第三章 数组和字符串3.1 数 组3.1.1 数组的存储和寻址 一个一维数组就是若干元素的一个有限序列，而其每个元素都通过一个下标来指定，且元素本身就是一个数据结构（或是整型、逻辑型、字符型等简单数据类型，或是数组、记录等复杂数据类型）。对一维数组唯一的限制是所有的元素都具有相同的类型，并占据相同大小的存储空间。因数组元素要通过数组名及紧跟其后的方括号中的下标来确定，故一个一维数组就对应一个下标函数。下面我们讨论数组在计算机存储器中的存储方式。因为通常不进行数组的插入或者删除操作，所以在内存储器中我们选择顺序存储方式实现数组的存储。在内存中以“线性式”的方式组织数组很方便。设一维数组An存放在
2、n个连续的存储单元中，每个数组元素占一个存储单元（不妨设为C个连续字节）。如果数组元素A0的首地址是L，则A1的首地址是L+C，A2的首地址是L+2C， ，依次类推，对于有：Loc (Ai)=Loc (A0)+iC对于高维数组（多维的数据结构）之存储，可将其转化为一维来实现。因此必须对高维数组元素的存放次序进行约定。高维数组通常有两种存放次序约定按行优先顺序和按列优先顺序.首先介绍按行优先顺序。所谓按行优先顺序，就是将高维数组元素按行向量的顺序存储，第个行向量存储在第个行向量之后。换句话说，就是用一维数组的存储结构来解决高维数组的存储问题。设A为n维数组，其每个元素占C个字节，且第一个元素的地
3、址为，若要算出该数组的任一个元素的地址，可将n维数组可考虑为如下一维数组( ， )设该数组的每个元素占C1个字节。显然，包含的数组元素实际与一个n-1维数组(包含个的数组元素)相同，于是我们有： .又可将（）看作如下一维数组(, , ,)设它的每个元素占C2个字节，显然C2 = m3m4 mnC ；如此类推，设一维数组(， )设它的每个元素占个字节，则Cn-1=mn C . 故的存储地址为： 所谓按列优先顺序，就是将数组元素按列向量的顺序存储，第i+1个列向量存储在第i个列向量之后。换句话说，就是将数组转化为一维数组来考虑。请读者计算以按列优先顺序存储的多维数组中任一个元素的存储地址。3.2
4、矩 阵3.2.1 矩阵类矩阵的乘法运算略为复杂，对于矩阵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 ( . FOR k=1 TO p DO . ) 前面提到过，可直接以按行优先次序用一维数组存放矩阵元素，下面给出的算法Multi-2是对用一维数组所存放矩阵的乘法运算实现。该算法中用一维数组s存放Amp，用一维数组t存放Bpn，求存放A与B的乘积Cmn 的一维数组w.由矩阵乘法公式知，其中aik是矩阵A中第
5、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)/ Amp用一维数组s存放，Bpn用一维数组t存放，求A与B的乘积Cmn并用一维数组w存放M1. 初始化cw0 . / 初始时cw是c11在一维数组w中的下标M2. 循环FOR i=1 TO m DO / 第一层循环cs(i-1)p. / 令cs为a
6、i1在一维数组s中的下标ct0. / 令ct为b11在一维数组t中的下标FOR j=1 TO n DO / 第二层循环( ctj-1. / 令ct为b1j在t中的下标 wcw0 . FOR k=1 TO p DO / 第三层循环，叠加aikbkj 并存于wcw中 ( wcwwcw+scstct. cscs+1. / cs为A中本行下一列元素在s中的下标 ctct+n. ) / ct为B中本列下一行元素在t中的下标 cwcw+1. ) ) 3.2.2 特殊矩阵前一小节所介绍的矩阵类，是以按行优先次序将所有矩阵元素存放在一个一维数组中。但是对于特殊矩阵，如对称矩阵、三角矩阵、对角矩阵和稀疏矩阵等,
7、 如果用矩阵类Matrix来实现，那么大量的存储空间中存放的是重复信息或者是零元素，这样造成很大的空间浪费。为节约存储空间和算法（程序）运行时间，通常会采用压缩存储的方法。对角矩阵的压缩存储nn维方阵M是对角矩阵，则对 i j (1 i , j n)，都有M(i, j)=0，即非对角线上的元素均为0 . 对于一个nn维对角矩阵，至多只有n个非零元素，因此只需存储其n个对角元素的信息。很容易想到，采用一维数组dn来压缩存储对角矩阵，其中di存储Mi,i的值。三角矩阵的压缩存储三角矩阵分为上三角矩阵和下三角矩阵。方阵M是上三角矩阵，当且仅当i j时有M(i, j)=0 . 方阵M是下三角矩阵，当且
8、仅当i 0 THEN ( FOR k=0 TO n-1 DO FOR i=0 TO count-1 DO IF (col( ai )=k THEN ( row( bj )k. col( bj )row( ai ). value( bj )value( ai ). jj+1. ) / 考察三元组表b中的下一个结点 对于用三元组表存储的稀疏矩阵，若矩阵非零元素个数为t，求其转置矩阵的时间复杂性是多少？观察Transpose算法不难发现，函数中包含两重循环，第一重循环是对转置矩阵按行优先依次确认非零元素，故循环次数为A的行数n；第二重循环是扫描原矩阵的三元组表，执行次数是矩阵A的非零元素个数t，显然
9、，求转置矩阵的时间复杂性为O(nt) .用三元组表存储稀疏矩阵，无论是添加或删除矩阵非零元素，还是对矩阵实施某些操作（例如AA+B），都可能引起矩阵中非零元素的个数和位置的变化，这些变化将引起与矩阵对应的三元组表中大量结点的移动，效率较低。用链接存储方式实现稀疏矩阵则会避免这些问题。下面介绍稀疏矩阵的一种链接存储方式十字链表。3.2.4 十字链表在稀疏矩阵的十字链表中，矩阵的每一行都设置为由一个表头结点引导的循环链表（简称为行链表），矩阵的每一列也都设置为由一个表头结点引导的循环链表（简称为列链表）。矩阵的元素结构如下：LEFTUPROWCOLVAL其中LEFT和UP是指针变量，分别存放该元素
10、的左邻非零元素和上邻非零元素的地址信息，ROW和COL存放该元素在矩阵中的行号和列号，VAL存放元素值。下图给出一个稀疏矩阵和它的十字链表： （3-3）图 3.2 十字链表-1-1-1-1-1-1-1136214448-1329347这里，每一行和每一列都有一个表头结点：BASEROWi，i=1，2，m（m行）BASECOLj， j=1，2，n（n列）且-1 = COL（Loc（BASEROWi） 0-1 = ROW（Loc（BASECOLj） 0因为行或列都是一个循环链表，所以行表头BASEROWi中的LEFT指针循环地链接到该行最右边的非零元素，列表头BASECOLj中的UP指针循环地链接
11、到该列最下边的非零元素。3.3 字符串3.3.1 字符串的定义与字符串类字符串(String)是由零个或多个字符(char)顺序排列组成的有限序列，简称为串。例如 “good morning”就是由12个字符构成的一个字符串。一般把字符串记作：其中S是串名，引号中的字符序列是串值。字符个数是串的长度，长度为0的串被称为空串，因为它不包含任何字符。注意“”并非空串，因为它包含一个字符空格，被称为空白传。若把某个串称为主串，则主串中任意个连续的字符组成的子序列被称为子串。子串在主串中第一次出现时，其首字符在主串中的序号被称为该子串在主串中的位置。字符串是许多非数值计算问题处理的主要对象，在模式匹配
12、、程序编译及数据处理等领域中均有应用。在C+语言中, 可直接用字符串指针（例如char *p =“good”）或者字符数组（例如char a =“good”）创建顺序存储的字符串，前者声明创建指针变量p，指向在存储空间某处的字符串“good”（以 n结尾）中的字母g，后者声明创建一个具有5个元素的数组a，它包含字符g、 o、 o、 d、 n . 利用标准头文件（早期的C+使用 ）所提供的处理字符串的库函数，可以对字符串进行操作。人们把C+语言中的函数库作为字符串数据类型的一种方案，并将其称之为“标准字符串”。3.3.2 模式匹配算法文本编辑器中常用的“查找”、“替换”和“全部替换”等基本的编辑
13、操作就是最普通的模式匹配问题，即：在文本文件中查找串。它的查找过程可简单描述如下：给定两个字符串变量和，其中目标串有个字符，模式串有个字符， . 从的给定位置（通常为的第一个字符）开始，搜索模式，如果找到，返回模式的第一个字符在中的位置；如果没找到（即中没有），则返回-1 . 朴素的模式匹配算法关于模式匹配，最简单的方法是：从的第一个字符开始，将（长度为）中字符依次与中的字符进行比较，若，则匹配成功，返回与相匹配的字符在中的位置（下标0） ；若某一步，说明此次匹配不成功，以下比较无需进行。于是再从的第二个字符开始进行第二次匹配，重复刚才的步骤，看是否有，若匹配成功，返回与相匹配的字符在中的下标
14、1. 否则从的第三个字符开始进行第三次匹配. 若第次匹配（即最后一次匹配）仍得不到，说明匹配失败，返回 -1 .这种模式匹配算法被称为朴素的模式匹配算法，该算法的ADL描述如下：算法StringMatchingINT StringMatching ( S, P )/ S为目标串，P为模式串，返回S中首个P子串的位置SM1. 初始化i0 . / i是目标串开始匹配的位置SM2. 逐字符匹配WHILE i | S |-| P | DO /从目标串的字符Si开始，与模式串P逐字符匹配( j0 . / j是模式串开始匹配的位置 WHILE Si = Pj AND j | P | DO( ii+1 .
15、jj+1 ) IF j = | P | THEN RETURN i | P | . / 匹配成功 ii j + 1 )SM 3 匹配失败RETURN 1 .朴素模式匹配算法的优点是过程简单，缺点是效率低。在最坏情况下，该算法要匹配次，每次匹配要做次比较，因此最坏情况下的比较次数是，时间复杂性为，通常情况下，的值远小于的值，于是最坏情况下的时间复杂性可粗略地记为 .模式匹配的改进算法朴素模式匹配算法效率不高的主要原因是进行了重复的字符比较，我们考虑如下例子：对于模式串P = abab ，目标串S = abaaabab ，其朴素的模式匹配过程为 第一次 S a b a a a b a b | |
16、| 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），因此第三次比较必然失败。于是我们只须进行第四次、第五次比较，就可以匹配成功，显然对模式进行分析可以减少比较次数，从而降低算法的时间复杂性，提高运行效率。
17、我们就一般情形进行讨论。设目标串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指向，由上述说明可知，指针
18、s无须回溯到，指针p也无须回溯到，需要做的只是将指针p回溯至，就可继续进行匹配。问题是：如何确定式（3.4）中的k值 . D.E.Knuth等人发现，对于不同的j，应取不同的k值，也就是说，k的取值只与模式P的前j个字符构成有关，而与目标S无关。因此，可以给出一个失败函数f ( j )，用它来确定k .设模式 ，P的失败函数可定义成：， k为满足，且的最大整数-1，其他情况f( j)=下面给出利用失败函数的KMP算法 (KnuthMorrisPratt算法) 实现FastFind ./ 整型数组f 表示失败函数，它应该在类定义中说明为私有数据成员int String : FastFind（St
19、ring pat）constint p = 0，s = 0 ;/ 给出模式和目标的扫描指针的初始位置int m = pat.size，n = size ;/ 模式和目标的长度while（p m & s n ）if（pat.strp = = strs ） 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算法的关键是计算，即在中找出最大的前后相等的子串，使得：我
20、们设，用归纳法来计算失败函数。设已知，欲求得 .（1）如果，显然 .如果，则必有 . 寻找h，使它满足h 0 DOi 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前进的（不返回），因此该算法的时间复杂性为，综上所述，采用失败函数的模式匹配算法的时间复杂性为 .