数据结构（七）数组和广义表

2019-04-09 本文已影响0人 hadoop_a9bb

数组

从本质上讲，数组与顺序表、链表、栈和队列一样，都用来存储具有 "一对一" 逻辑关系数据的线性存储结构。只因各编程语言都默认将数组作为基本数据类型，使初学者对数组有了 "只是基本数据类型，不是存储结构" 的误解。

数组结构的实现使用的是顺序存储结构。

根据数组中存储数据之间逻辑结构的不同，数组可细分为一维数组、二维数组、...、n 维数组：

一维数组，指的是存储不可再分数据元素的数组，如图 1 所示：

图1：一维数组存储结构示意图

二维数组，指的存储一维数组的一维数组，如图 2 所示：

图2：二维数组示意图
n维数组，指的是存储n-1维数组的一维数组

注意：无论数组的维数是多少，数组中的数据类型都必须一致。

矩阵（稀疏矩阵）压缩存储（3种方式）

数据结构中提供针对某些特殊矩阵的压缩存储结构，这里所说的特殊矩阵，主要分为以下两类:

1.含有大量相同元素的矩阵，比如对称矩阵
2.含有大量0元素的矩阵，比如稀疏矩阵、上（下）三角矩阵

针对以上两类矩阵，数据结构的压缩存储思想是：矩阵中的相同数据元素（包括元素 0）只存储一个。

对称矩阵

数据元素沿主对角线对应相等，这类矩阵称为对称矩阵。

图3：对称矩阵示意图

矩阵中有两条对角线，其中图 1 中的对角线称为主对角线，另一条从左下角到右上角的对角线为副对角线。对称矩阵指的是各数据元素沿主对角线对称的矩阵。

我们可以使用一维数组存储对称矩阵。由于矩阵中沿对角线两侧的数据相等，因此数组中只需存储对角线一侧（包含对角线）的数据即可。

对称矩阵的实现过程是，若存储下三角中的元素，只需将各元素所在的行标 i 和列标 j 代入下面的公式：

图4：下三角矩阵存储位置计算

存储上三角的元素要将各元素的行标 i 和列标 j 代入另一个公式：

图5：上三角矩阵存储位置计算

最终求得的 k 值即为该元素存储到数组中的位置（矩阵中元素的行标和列标都从 1 开始）。

例如，在数组 skr[6] 中存储图 1 中的对称矩阵，则矩阵的压缩存储状态如图 6 所示（存储上三角和下三角的结果相同）：

图6 对称矩阵压缩示意图

注意，以上两个公式既是用来存储矩阵中元素的，也用来从数组中提取矩阵相应位置的元素。例如，如果想从图 6 中的数组提取矩阵中位于 (3,1) 处的元素，由于该元素位于下三角，需用下三角公式获取元素在数组中的位置，即：

图7：元素对应位置计算

结合图 6，数组下标为 3 的位置存储的是元素 3，与图 3 对应。

上(下)三角矩阵

图8：上下三角矩阵

主对角线下的数据元素全部为0的矩阵为上三角矩阵（图 4a)），主对角线上元素全部为0的矩阵为下三角矩阵（图 4b)）。上(下)三角矩阵存储元素和提取元素的过程和对称矩阵相同。

稀疏矩阵

图9：稀疏矩阵示意图

压缩存储稀疏矩阵的方法是：只存储矩阵中的非 0 元素，与前面的存储方法不同，稀疏矩阵非 0 元素的存储需同时存储该元素所在矩阵中的行标和列标。

例如，存储图 9 中的稀疏矩阵，需存储以下信息：

(1,1,1)：数据元素为 1，在矩阵中的位置为 (1,1)；
(3,3,1)：数据元素为 3，在矩阵中的位置为 (3,1)；
(5,2,3)：数据元素为 5，在矩阵中的位置为 (2,3)；
除此之外，还要存储矩阵的行数 3 和列数 3；

由此，可以成功存储一个稀疏矩阵。

矩阵压缩存储的3种方式

对于以上 3 种特殊的矩阵，对称矩阵和上下三角矩阵的实现方法是相同的，且实现过程比较容易，仅需套用上面给出的公式即可。

稀疏矩阵的压缩存储，数据结构提供有3种具体实现方式：

1.三元组顺序表
2.行逻辑链接的顺序表
3.十字链表

三元组顺序表

图 9 是一个稀疏矩阵，若对其进行压缩存储，矩阵中各非 0 元素的存储状态如图 10 所示：

图10 稀疏矩阵压缩存储示意图

图10存储的是三元组（即由 3 部分数据组成的集合），组中数据分别表示（行标，列标，元素值）。

public class Triple {
    int i; //行标i
    int j; //列标j
    int data;   //元素值
}

public class TSMatrix{
    int n; // 矩阵行数
    int m; // 矩阵列数
    int num; // 矩阵有效数据数量
    Triple[] triple = new Triple[num]；//矩阵3元组元素
}

行逻辑链接顺序表

三元组顺序表每次提取指定元素都需要遍历整个数组，运行效率很低。
行逻辑链接的顺序表。它可以看作是三元组顺序表的升级版，即在三元组顺序表的基础上改善了提取数据的效率。

图11：稀疏矩阵示意图

图 11 是一个稀疏矩阵，当使用行逻辑链接的顺序表对其进行压缩存储时，需要做以下两个工作：

将矩阵中的非 0 元素采用三元组的形式存储到一维数组 data 中，如图 2 所示（和三元组顺序表一样）：

图12：三元组存储稀疏矩阵

使用数组 rpos 记录矩阵中每行第一个非 0 元素在一维数组中的存储位置。如图 13 所示:

图13：存储各行首个非0元素在[图11]数组中的位置

通过以上两步操作，即实现了使用行逻辑链接的顺序表存储稀疏矩阵。
此时，如果想从行逻辑链接的顺序表中提取元素，则可以借助 rpos 数组提高遍历数组的效率。

例如，提取图 11 稀疏矩阵中的元素 2 的过程如下：

由 rpos 数组可知，第一行首个非 0 元素位于data[1]，因此在遍历此行时，可以直接从第 data[1] 的位置开始，一直遍历到下一行首个非 0 元素所在的位置（data[3]）之前

十字链表法

对于压缩存储稀疏矩阵，无论是使用三元组顺序表还是使用行逻辑链接的顺序表，归根结底是使用数组存储稀疏矩阵。介于数组 "不利于插入和删除数据" 的特点，以上两种压缩存储方式都不适合解决类似 "向矩阵中添加或删除非 0 元素" 的问题。

十字链表法存储稀疏矩阵，该存储方式采用的是 "链表+数组" 结构，如图14所示：

图14：十字链表示意图

可以看到，使用十字链表压缩存储稀疏矩阵时，矩阵中的各行各列都各用一各链表存储，与此同时，所有行链表的表头存储到一个数组（rhead），所有列链表的表头存储到另一个数组（chead）中。

因此，各个链表中节点的结构应如图15 所示:

图15：十字链表节点结构

两个指针域分别用于链接所在行的下一个元素以及所在列的下一个元素。

矩阵（稀疏矩阵）的转置算法

矩阵的转置，即互换矩阵中所有元素的行标和列标，如图16所示：

图16：矩阵转置示意图

但如果想通过程序实现矩阵的转置，互换行标和列标只是第一步。因为实现矩阵转置的前提是将矩阵存储起来，数据结构中提供了 3 种存储矩阵的结构，分别是三元组顺序表、行逻辑链接的顺序表、十字链表。如果采用前两种结构，矩阵的转置过程会涉及三元组表也跟着改变的问题，如图 2 所示：

图17：三元组表的变化

图 2a) 表示的是图 1 中转置之前矩阵的三元组表，2b) 表示的是图 1 中矩阵转置后对应的三元组表。由此发现，三元组顺序表中数组的位置发生了变化。
不仅如此，如果矩阵的行数和列数不等，也需要将它们互换。

因此通过以上分析，矩阵转置的实现过程需完成以下 3 步：

1.将矩阵的行数和列数互换
2.将三元组表（存储矩阵）中的 i 列和 j 列互换，实现矩阵的转置
3.以 j 为序列，重新排列三元组表中存储各三元组的先后顺序

此 3 步中，前两步比较简单，关键在于最后一步的实现。

矩阵转置的实现思路是：不断遍历存储矩阵的三元组表，每次都取出表中 j 列最小的那一个三元组，互换行标和列标的值，并按次序存储到一个新三元组表中。

例如，将图 2a) 三元组表存储的矩阵进行转置的过程为：

1.新建一个三元组表（用于存储转置矩阵），并将原矩阵的行数和列数互换赋值给新三元组；
2.遍历三元组表，找到表中 j 列最小值 1 所在的三元组 (3,1,6)，然后将其行标和列标互换后添加到一个新的三元组表中，如图 18 所示：

图18：矩阵转置的第一个过程
3.继续遍历三元组表，找到表中 j 列次小值为 2 的三元组，分别为 (1,2,1)、(2,2,3) 和 (3,2,5)，根据找到它们的先后次序将各自的行标和列标互换后添加到新三元组表中，如图 19 所示：

图19：矩阵转置的第二个过程

对比图 19 和图 2b) 可以看到，矩阵被成功地转置。
由于此算法中需要嵌套使用了两个 for 循环，时间复杂度为 O(n²)。

稀疏矩阵的快速转置算法

稀疏矩阵快速转置算法和普通算法的区别仅在于第 3 步，快速转置能够做到遍历一次三元组表即可完成第 3 步的工作。
稀疏矩阵的快速转置是这样的，在普通算法的基础上增设两个数组（假
设分别为 array 和 copt）：

array 数组负责记录原矩阵每一列非 0 元素的个数。以图 1 为例，则对应的 array 数组如图 20 所示：
图20：每一列非0元素的个数
图 2 中 array 数组表示，原稀疏矩阵中第一列有 1 个非 0 元素，第二列有 2 个非 0 元素。
copt 数组用于计算稀疏矩阵中每列第一个非 0 元素在新三元组表中存放的位置。
我们通常默认第一列首个非 0 元素存放到新三元组表中的位置为 1，然后通过 cpot[col] = cpot[col-1] + array[col-1] 公式可计算出后续各列首个非 0 元素存放到新三元组表的位置。拿图 1 中的稀疏矩阵来说，它对应的 copt 数组如图 21 所示：

图21：copt数组示意图

图 21 中的 copt 数组表示，原稀疏矩阵中第 2 列首个非 0 元素存放到新三元组表的位置为 2。

注意，cpot[col] = cpot[col-1] + array[col-1] 的意思是，后一列首个非 0 元素存放的位置等于前一列首个非 0 元素的存放位置,加上该列非 0 元素的个数。由此可以看出，copt 数组才是最终想要的，而 array 数组的设立只是为了帮助我们得到 copt 数组。

//具体代码省略

稀疏矩阵快速转置算法的时间复杂度为 O(n)。即使在最坏的情况下（矩阵中全部都是非 0 元素），该算法的时间复杂度也才为 O(n²)。

矩阵乘法

矩阵相乘的前提条件是：乘号前的矩阵的列数要和乘号后的矩阵的行数相等。且矩阵的乘法运算没有交换律，即 AB 和 BA 是不一样的。假设下面是矩阵A：

3	0	0	5
0	-1	0	0
2	0	0	0

下面是矩阵B：

0	2
1	0
-2	4
0	0

由于矩阵 A 的列数和矩阵 B 的行数相等，可以进行 AB 运算（不能进行 BA 运算）。计算方法是：用矩阵 A 的第 i 行和矩阵 B 中的每一列 j 对应的数值做乘法运算，乘积一一相加，所得结果即为矩阵 C 中第 i 行第 j 列的值。

例如：C12 = 6 是因为：A11B12 + A12B22 + A13B32 + A14B42，即 32 + 00 + 04 + 50 = 6 ，因为这是 A 的第 1 行和 B的第 2 列的乘积和，所以结果放在 C 的第 1 行第 2 列的位置。

结果矩阵C为：

0	6
-1	0
0	4

例如，A 是 m1n1 矩阵，B 是 m2n2 矩阵(前提必须是 n1 == m2 )：
普通算法的时间复杂度为 O(m1*n2*n1)

基于行逻辑链接的顺序表的矩阵乘法

具体过程不描述，请自行百度，这里只说结论。

当稀疏矩阵 Amn 和稀疏矩阵 Bnp 采用行逻辑链接的顺序表做乘法运算时，在矩阵 A 的列数（矩阵 B 的行数） n 不是很大的情况下，算法的时间复杂度相当于 O(m*p)，比普通算法要快很多

矩阵加法

矩阵之间能够进行加法运算的前提条件是：各矩阵的行数和列数必须相等。

在行数和列数都相等的情况下，矩阵相加的结果就是矩阵中对应位置的值相加所组成的矩阵，例如：

图22：矩阵相加

十字链表法
过程有点复杂，具体请自行百度，这里只说结论
使用十字链表法解决稀疏矩阵的压缩存储的同时，在解决矩阵相加的问题中，对于某个单独的结点来说，算法的时间复杂度为一个常数（全部为选择结构），算法的整体的时间复杂度取决于两矩阵中非 0 元素的个数。

广义表

数组即可以存储不可再分的数据元素（如数字 5、字符 'a'），也可以继续存储数组（即 n 维数组）。

但需要注意的是，以上两种数据存储形式绝不会出现在同一个数组中。例如，我们可以创建一个整形数组去存储 {1,2,3}，我们也可以创建一个二维整形数组去存储 {{1,2,3},{4,5,6}}，但数组不适合用来存储类似 {1,{1,2,3}} 这样的数据。

有人可能会说，创建一个二维数组来存储{1,{1,2,3}}。在存储上确实可以实现，但无疑会造成存储空间的浪费。

对于存储 {1,{1,2,3}} 这样的数据，更适合用广义表结构来存储。
广义表，又称列表，也是一种线性存储结构。

同数组类似，广义表中既可以存储不可再分的元素，也可以存储广义表，记作：

LS = (a₁,a₂,…,a_n)

其中，LS 代表广义表的名称，a_n 表示广义表存储的数据。广义表中每个 a_i 既可以代表单个元素，也可以代表另一个广义表。

原子和子表

通常，广义表中存储的单个元素称为 "原子"，而存储的广义表称为 "子表"。

以下是广义表存储数据的一些常用形式：

A = ()：A 表示一个广义表，只不过表是空的。
B = (e)：广义表 B 中只有一个原子 e。
C = (a,(b,c,d)) ：广义表 C 中有两个元素，原子 a 和子表 (b,c,d)。
D = (A,B,C)：广义表 D 中存有 3 个子表，分别是A、B和C。这种表示方式等同于 D = ((),(e),(b,c,d)) 。
E = (a,E)：广义表 E 中有两个元素，原子 a 和它本身。这是一个递归广义表，等同于：E = (a,(a,(a,…)))。

注意，A = () 和 A = (()) 是不一样的。前者是空表，而后者是包含一个子表的广义表，只不过这个子表是空表。

广义表的表头和表尾

当广义表不是空表时，称第一个数据（原子或子表）为"表头"，剩下的数据构成的新广义表为"表尾"。

强调一下，除非广义表为空表，否则广义表一定具有表头和表尾，且广义表的表尾一定是一个广义表。

例如在广义表中 LS={1,{1,2,3},5} 中，表头为原子 1，表尾为子表 {1,2,3} 和原子 5 构成的广义表，即 {{1,2,3},5}。

再比如，在广义表 LS = {1} 中，表头为原子 1 ，但由于广义表中无表尾元素，因此该表的表尾是一个空表，用 {} 表示。

广义表的存储结构

由于广义表中既可存储原子（不可再分的数据元素），也可以存储子表，因此很难使用顺序存储结构表示，通常情况下广义表结构采用链表实现。

使用链表存储广义表，首先需要确定链表中节点的结构。由于广义表中可同时存储原子和子表两种形式的数据，因此链表节点的结构也有两种，如图23 所示：

图23：广义表节点的两种类型

如图 23所示，表示原子的节点由两部分构成，分别是 tag 标记位和原子的值，表示子表的节点由三部分构成，分别是 tag 标记位、hp 指针和 tp 指针。

tag 标记位用于区分此节点是原子还是子表，通常原子的 tag 值为 0，子表的 tag 值为 1。子表节点中的 hp 指针用于连接本子表中存储的原子或子表，tp 指针用于连接广义表中下一个原子或子表。

例如，广义表 {a,{b,c,d}} 是由一个原子 a 和子表 {b,c,d} 构成，而子表 {b,c,d} 又是由原子 b、c 和 d 构成，用链表存储该广义表如图 24 所示：

图24:广义表{a,{b,c,d}}的结构示意图

另一种广义表存储结构

如果你觉得图 24 这种存储广义表的方式不合理，可以使用另一套表示广义表中原子和子表结构的节点，如图 25 所示：

图25：广义表的另一套节点结构

采用图 25 中的节点结构存储广义表 {a,{b,c,d}} 的示意图如图 26 所示：

图26：广义表{a,{b,c,d}}的结构示意图

广义表的深度和长度

广义表的长度

由于广义表中可以同时存储原子和子表两种类型的数据，因此在计算广义表的长度时规定，广义表中存储的每个原子算作一个数据，同样每个子表也只算作是一个数据。

前面我们用 LS={a1,a2,...,an} 来表示一个广义表，其中每个 ai 都可用来表示一个原子或子表，其实它还可以表示广义表 LS 的长度为 n。

广义表规定，空表 {} 的长度为 0

广义表的存储使用的是链表结构，且有以下两种方式（如图 1 所示）：

图27：广义表存储{a,{b,c,d}}的两种方式

对于图 a) 来说，只需计算最顶层（红色标注）含有的节点数量，即可求的广义表的长度。

对于图 b) 来说，由于其最顶层（蓝色标注）表示的此广义表，而第二层（红色标注）表示的才是该广义表中包含的数据元素，因此可以通过计算第二层中包含的节点数量，即可求得广义表的长度。

广义表的深度

广义表的深度，可以通过观察该表中所包含括号的层数间接得到。

图28：广义表示意图

从图 28 中可以看到，此广义表从左往右数有两层左括号（从右往左数也是如此），因此该广义表的深度为 2。

编写程序计算广义表的深度时，可以采用递归的方式：

1.依次遍历广义表 C 的每个节点，若当前节点为原子（tag 值为 0），则返回 0；若为空表，则返回 1；反之，则继续遍历该子表中的数据元素。
2.设置一个初始值为 0 的整形变量 max，每次递归过程返回时，令 max 与返回值进行比较，并取较大值。这样，当整个广义表递归结束时，max+1 就是广义表的深度。

广义表的复制

对于任意一个非空广义表来说，都是由两部分组成：表头和表尾。反之，只要确定的一个广义表的表头和表尾，那么这个广义表就可以唯一确定下来。

复制一个广义表，也是不断的复制表头和表尾的过程。如果表头或者表尾同样是一个广义表，依旧复制其表头和表尾。

所以，复制广义表的过程，其实就是不断的递归，复制广义表中表头和表尾的过程。