2.4 数 组

2.4  数  组

2.4.1要点

   1.数组与线性表

    数组可以理解为线性表的推广形式，在这里主要讨论二维数组，也即是矩阵。如一个

m×n的二维数组，可以看作一个由m个行向量构成的长度为n的线性表；也可以看作一个由n个列向量组成的长度为m的线性表。因此数组是一个复杂的线性表。

2.数组的存储方式

由于数组是长度固定的线性表，因此它的存储方式通常是采用顺序存储。但由于二维以上数组其元素地址是由多个下标构成，它与一维的存储空间可以有多种映射关系，如二维数组的存放方式可以有按行存放与按列存放两种。但当数组中绝大部分元素值为零时，采用上述存储方式，将会造成大量存储空间的浪费，必须采用相应的压缩存储方式，这里主要讨论希疏矩阵的存储方式。

3.数组的运算

数组的运算主要有：

（1）给定一组下标，找到与之相对应的数组元素。

（2）给定一组下标，存取或修改与之相对应的数组元素。

2.4.2 稀疏矩阵的顺序存储结构

用顺序存储方式存放稀疏矩阵，适用于矩阵元素个数在运算前后没有变化的情况，例如访问矩阵元素、矩阵专置等。最常用的为三元组表示和辅助向量的三元组表示。

   1. 三元组表示

用顺序表表示稀疏矩阵，顺序表中每一个元素三个数据项组成，它们分别表示稀疏矩阵中每一个非零元素在矩阵中的行、列位置及元素值。

若一个m×n稀疏矩阵，共有t 个非零元素，采用三元组表示，假设其行、列和元素值各占一个单位存储空间，那么共占3 t个空间。而用一般的存储方式则需m×n个空间。因此只有当3 t<m×n时采用三个元组表示方式才能节省存储空间。

例2.17 已知（m×n）稀疏矩阵A为：

    A= 

用三元组表示为：

       序号  1    2   3    4    5    6

在三元组中若要查找矩阵元素A[3，2]时，应先从三元组的行数据项查得相应的行值，再查找对应值下的列值，然后得到相应的元素。

    2.带辅助向量的三元组表示

为便于对三元组表示的稀疏矩阵元素的访问，通常还需附设两个辅助向量POS和NUM，它们的大小与稀疏矩阵的行数相当。其中POS[i]表示稀疏矩阵中第i行第1非零元素在三元组中的序号；NUM[i]表示稀疏矩阵在第i行中的非零元素个数。对应上述稀疏矩阵A的POS和NUM向量为：

序号  1    2   3    4    5   

有了辅助向量以后，在查找矩阵元素时，可以增加查找速度。例如要查找矩阵元素A[3，2]时，先按行号取出POS[3]=4,得知矩阵第3行的第1个非零元素在三元组中的序号为4，又从NUM[3]中得知第3行中非零元素的个数为2，从而可以高效地访问稀疏矩阵元素A[3，2]。

2.4.3数组的链式结构—十字链表

  十字链表是数组的动态存储结构，可以看作是线性链表的扩展。在这种结构中，稀疏矩阵中的每一个非零元素对应一个结点，每个结点有5个域组成，其中3个数据域分别存放结点的行、列及元素值，2个指针域存放向下的指针(down)与向右的指针（right）如图2.20所示。由于这种结点链接成的链表称为十字链表。

    用十字链表表示稀疏矩阵的特点为：

   （1）稀疏矩阵每一行和每一列的结点均用代表投结点的循环链表表示;

（2）表头结点中行、列域中的值均置为0；

（3）行、列链表的表头结点合用，并且这些表头结点通过结点中的值域相连接，再用一个结点作为它们总的表头结点H，这个结点中的行、列域中分别存放稀疏矩阵的行数和列数。由此可以看出，只要给出指向头结点H 头指针h，就可以扫描到稀疏矩阵中任意一个非零元素。

用十字链表表示稀疏矩阵适用于对矩阵进行运算后会改变稀疏矩阵的稀疏程度的运算，例如矩阵的相加、相乘等。