数据结构与算法 －数组

数组可看成是一种特殊的线性表，其特殊在于表中的数组元素本身也是一种线性表。

数组的逻辑结构和运算

数组它是线性表的推广，其每个元素由一个值和一 组下标组成，其中下标个数称为数组的维数。

数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯 一可供使用的数据类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单，多维数组也是线性表的一种延伸。

上图所示的二维数组a[m][n]可以看成是由m个行向量组成的向量， 也可以看成是n个列向量组成的向量。

数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组通常只有两种基本运算：

1. 读，给定一组下标，读取相应的数据元素。

2. 写，给定一组下标，修改相应的数据元素。

 

数组的存储结构和寻址公式

1. 存储结构

由于计算机的内存结构是一维的，因此用一维内存来表示多维数组， 就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。

又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立， 结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采 用 顺序存储 的方法来表示数组。

2. 寻址公式

如上图中，二维数组a[m][n]按 “行优先顺序” 存储在内存中，假设每个元素占用k个存储单元。 元素 a[i][j] 的存储地址应是数组的基地址加上排在 a[i][j] 前面的元 素所占用的单元数。因为 a[i][j] 位于第i行、第j列，前面i行一共有 i×n 个元素，第i行上 a[i][j] 前面又有j个元素，故它前面一共有 i×n+j 个元素，因此，a[i][j] 的地址计算函数为：LOC(a[i][j])=LOC(a[0][0])+(i*n+j)*k

 

数组矩阵的压缩存储

为了节省存储空间， 我们可以对一些特殊的数组矩阵进行压缩存储，特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，在存储时可以为为多个相同的非零元素只分配一个存储空间，而对零元素不分配空间。下面我们讨论几种特殊矩阵的压缩存储。

1. 对称矩阵

在一个n阶方阵a中，若元素满足下述性质： a[i][j]=a[j][i]，并且 0≤i，j≤n-1，则称a为对称矩阵。如下图便是一个5阶对称矩阵。

对称矩阵中的元素在主对角线上是对称关系，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样能节约近一半的存储空间。我们按“行优先顺序”存储主对角线（包括对角线）以下的元素，其存储形式如图所示：

在这个下三角矩阵中，第i行恰有i个元素，元素总数为： ∑(i)=n(n+1)/2。因此，我们可以按图中箭头所指的次序将这些元素存放在一个 一维数组s[1...n(n+1)/2]中，为了便于访问对称矩阵a中的元素 ，我们必须在 a[i][j] 和 s[k] 之间找一个对应关系，即下标变换公式。

(1). 若i≥j，则a[i][j] 在下三角形中。a[i][j]之前的i行（从第0 行到第i-1行）一共有1+2+…+i=i(i+1)/2个元素，在第i行上， a[i][j]之前恰有j 个元素（a[i][0],a[i][1],a[i][2]…a[i][j-1]）, 因此，a[i][j] = s[i*(i+1)/2+j ]

(2). 若i<j，则a[i][j] 是在上三角矩阵中。因为a[i][j] =a[j][i] ，所以只 要交换上述对应关系式中的i和j即可得到：a[i][j] = s[j*(j+1)/2+i ]

所以，令 I=max(i,j)， J=min(i,j)，则k和 i, j的对应关系可统一为： k=I*(I-1)/2+J，0≤k＜n(n+1)/2 -1

有了上述的下标交换关系，对于任意给定一组下标(i,j)， 均可在s[k]中找到矩阵元素a[i][j]，反之，对所有的 k=0,1,2,3,…n(n+1)/2-1，都能确定s[k]中的元素在矩阵中的 位置(i,j)。由此，称s[n(n+1)/2]为对称矩阵a 的压缩存储。

 

2. 三角矩阵

以主对角线划分，三角矩阵有上三角和下三角两种。 上三角矩阵如图所示，它的下三角（不包括主对角线） 中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数。在大多数情况下，三角矩阵常数为零。

三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量s[0..n(n+1)/2]中，其中c存放在向量的最后一个分 量中。

上三角矩阵中，主对角线之上的第p行(0≤p<n)恰有n-p个元素，按行优先顺序存放上三角矩阵中的元素a[i][j]时，a[i][j]之前的i 行一共有 (n-p)=i(2n-i+1)/2个元素，在第i行上，a[i][j]前恰好有 j-i个元素，因此，s[k]和a[i][j]的对应关系是：

下三角矩阵的存储和对称矩阵类似，s[k]和a[i][j]对应关系是：

 

3. 稀疏矩阵

什么是稀疏矩阵？简单说，设矩阵a中有s个非零元素， 若s远远小于矩阵元素的总数，则称a为稀疏矩阵。

稀疏矩阵的压缩存储只存储稀疏矩阵中的非零元素。

由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的行和列的位置 (i,j)，所以，我们可以用一个三元组(i,j,a[i][j])唯一确定矩阵a的一个非零元素。

例如，下列三元组表

( (0,1,12)，(0,2,9)，(2,0,- 3)，(2,5,14)，(3,2,24), (4,1,18)，(5,0,15)，(5,3,-7) )，加上(6,7)这一对行、列值便可作为下列矩阵M的另一 种描述，我们称之为稀疏矩阵的三元组顺序表表示法。

三元组顺序表表示法的定义。

const int maxnum=10;
// 定义三元组
typedef struct node{
    // 非零元素的行下标和列下标
    int i, j; 
    // 非零元素的值
    DataType v; 
}NODE;


// 稀疏矩阵三元组表存储类型
typedef struct spmatrix{
    // 非零元三元组表
    NODE data[maxnum]; 
    // 矩阵的行数、列数和非零元个数
    int mu,nu,tu; 
}SpMtx;

设：SpMtrx M ; 则下图（左）图所示的稀疏矩阵的三元组的表示如下图（右）所示：