多维数组
多维数组和广义表是一种复杂的非线性结构，它们的逻辑特征是：一个数据元素可能有多个直接前驱和多个直接后继。
多维数组
1、数组（向量）——常用数据类型
    　一维数组（向量）是存储于计算机的连续存储空间中的多个具有统一类型的数据元素。
    　同一数组的不同元素通过不同的下标标识。
      （a1,a2,…,an)
2、二维数组
    　二维数组Amn可视为由m个行向量组成的向量，或由n个列向量组成的向量。     
    　二维数组中的每个元素aij既属于第i行的行向量，又属于第j列的列向量。
3、多维数组
    　三维数组Amnp可视为以二维数组为数据元素的向量。四维数组可视为以三维数组为数据元素的向量……
    　三维数组中的每个元素aijk都属于三个向量。四维数组中的每个元素都属于四个向量……
4、数组的顺序存储方式
    　由于计算机内存是一维的，多维数组的元素应排成线性序列后存人存储器。
    　数组一般不做插入和删除操作，即结构中元素个数和元素间关系不变化。一般采用顺序存储方法表示数组。
（1）行优先顺序
    　将数组元素按行向量排列，第i+1个行向量紧接在第i个行向量后面。
  【例】二维数组Amn的按行优先存储的线性序列为：
    a11,a12,…,a1n,a21,a22,…,a2n,……，am1,am2,…，amn
  注意：
    　①PASCAL和C语言中，数组按行优先顺序存储。
    　②行优先顺序推广到多维数组，可规定为先排最右的下标。
（2）列优先顺序
    　将数组元素按列向量排列，第i+1个列向量紧接在第i个列向量后面。
  【例】二维数组Amn的按列优先存储的线性序列为：
    a11,a21,…,am1,a12,a22,…,am2,……，a1n,a2n,…，amn
  注意：
    　①FORTRAN语言中，数组按列优先顺序存储。
    　②列优先顺序推广到多维数组，可规定为先排最左的下标。
5、数组元素的地址计算公式
（1）按行优先顺序存储的二维数组Amn地址计算公式
        LOC(aij)=LOC(a11)+[(i-1)×n+j-1]×d
    其中：
  ①LOC(a11)是开始结点的存放地址（即基地址）
  ②d为每个元素所占的存储单元数
  ③由地址计算公式可得，数组中任一元素可通过地址公式在相同时间内存取。即顺序存储的数组是随机存取结构。
（2）按列优先顺序存储的二维数组Amn地址计算公式
          LOC(aij)=LOC(a11)+[(j-1)×m+i-1]×d
（3）按行优先顺序存储的三维数组Amnp地址计算公式
      LOC(aijk)=LOC(a111)+[(i-1)×n×p+(j-1)×p+k-1]×d
（4）下界不为1的二维数组的地址计算公式
  ①二维数组A[c1..d1,c2..d2]的地址计算公式：
      LOC(aij)=LOC(ac1c2)+[(i-c1)×(d2-c2+1)+j-c2]×d
 　②下界为0的二维数组的地址计算公式（C语言中使用）
      LOC(aij)=LOC(a00)+[i×(d2+1)+j]×d
  注意：
    　以下讨论的数组存储结构都以C语言下标表示。
矩阵的压缩存储
矩阵是科学与工程计算问题中常用的数学对象之一。
矩阵的存储
1、矩阵的二维数组描述
    　矩阵用二维数组描述时，存储的密度为1。可以对其元素进行随机存取，各种矩阵运算也非常简单。
2、矩阵的压缩存储
   　 矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，为了节省存储空间，我们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。
特殊矩阵
    　所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。常见的有对称矩阵、三角矩阵和对角矩阵等。
1．对称矩阵
（1）对称矩阵
    　在一个n阶方阵A中，若元素满足下述性质： 
      aij=aji 0≤i，j≤n-1
则称A为对称矩阵。
【例】下图便是一个5阶对称矩阵。                   
（2）对称矩阵的压缩存储
    对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每
两个对称的元素共享一个存储空间。这样，能节约近一半的存储空间。
①按"行优先顺序"存储主对角线(包括对角线)以下的元素          
    即按a00,a10,a11,……，an-1,0,an-1,1…，an-1,n-1次序存放在一个向量sa[0．．n(n+1)／2-1]中（下三角矩阵中，元素总数为n(n+1)／2）。
    其中：
        sa[0]= a00 ,
        sa[1] = a10 ,
        ……，
        sa[n(n+1)／2-1]= an-1,n-1
②元素aij的存放位置
    aij元素前有i行(从第0行到第i-1行)，一共有：
        1+2+…+i=i×(i+1)／2个元素；
    在第i行上，aij之前恰有j个元素(即ai0，ail，…，ai,j-1)，因此有：
          sa[i×(i+1)／2+j]= aij 
③aij和sa[k]之间的对应关系：
    若i≥j，k=i×(i+1)／2+j  0≤k<n(n+1)／2
    若i＜j，k=j×(j+1)／2+i  0≤k<n(n+1)／2
    令I=max(i，j)，J=min(i，j)，则k和i，j的对应关系可统一为：
        k=i×(i+1)／2+j 0≤k<n(n+1)／2 
（3）对称矩阵的地址计算公式
  LOC(aij)=LOC(sa[k])
          =LOC(sa[0])+k×d=LOC(sa[0])+[I×(I+1)／2+J]×d
    通过下标变换公式，能立即到矩阵元素aij在其压缩存储表示sa中的对应位置k。因此是随机存取结构。
  【例】a21和a12均存储在sa[4]中，这是因为
          k=I×(I+1)／2+J=2×(2+1)／2+1=4
2、三角矩阵 
（1）三角矩阵的划分
    　以主对角线划分，三角矩阵有上三角矩阵和下三角矩阵两种。
①上三角矩阵
    　如下图(a)所示，它的下三角(不包括主角线)中的元素均为常数c。
②下三角矩阵
    　与上三角矩阵相反，它的主对角线上方均为常数c，如下图(b)所示。
  注意：
　    在多数情况下，三角矩阵的常数c为零。
（2）三角矩阵的压缩存储
    三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n×(n+1)／2个，因此，三角矩阵可压缩存储到向量sa[0．．n(n+1)／2]中，其中c存放在向量的最后一个分量中。 
① 上三角矩阵中aij和sa[k]之间的对应关系
    　上三角矩阵中，主对角线之上的第p行(0≤p<n)恰有n-p个元素，按行优先顺序存放上三角矩阵中的元素aij时：
    aij元素前有i行(从第0行到第i-1行)，一共有：
        (n-0)+(n-1)+(n-2)+…+(n-i)=i×(2n-i+1)／2个元素；
    　在第i行上，aij之前恰有j-i个元素(即aij，ai,j+l，…，ai,j-1)，因此有：
          sa[i×(2n-i+1)／2+j-i]= aij 
所以：
   　 ┌i×(2n-i+1)／2+j-i 当i≤j
  　k=│
      └n×(n+1)/2 当i＞j
②下三角矩阵中aij和sa[k]之间的对应关系
  　  ┌i×(i+1)／2+j 当i≥j
　  k=│
    　 └n×(n+1)/2 当i＜j
  注意：
    　三角矩阵的压缩存储结构是随机存取结构。
3．对角矩阵
    　所有的非零元素集中在以主对角线为中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零的矩阵为对角矩阵。
  【例】下图给出了一个三对角矩阵。           
    其中：
    非零元素仅出现在主对角上(aii，0≤i≤n-1)，紧邻主对角线上面的那条对角线上(ai，i+1 ，0≤i≤n-2)和紧邻主对角线下面的那条对角线上(a i+1，i，0≤i≤n-2)。当|i-j|>1时，元素aij=0。
    　由此可知，一个k对角线矩阵(k为奇数)A是满足下述条件的矩阵：
            若|i-j|>(k-1)／2，则元素aij=0。
    　对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能到每个非零元素和向量下标的对应关系。具体【参见练习】
稀疏矩阵
    　设矩阵Amn中有s个非零元素，若s远远小于矩阵元素的总数(即s<<m×n)，则称A为稀疏矩阵。
1、稀疏矩阵的压缩存储
    　为了节省存储单元，可只存储非零元素。由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须存储非零元素所在的行号、列号，才能迅速确定一个非零元素是矩阵中的哪一个元素。稀疏矩阵的压缩存储会失去随机存取功能。
    　其中每一个非零元素所在的行号、列号和值组成一个三元组(i，j，aij)，并由此三元组惟一确定。
    　稀疏矩阵进行压缩存储通常有两类方法：顺序存储和链式存储。链式存储方法【参见参考书目】。
2、三元组表
    　将表示稀疏矩阵的非零元素的三元组按行优先(或列优先)的顺序排列(跳过零元素)，并依次存放在向量中，这种稀疏矩阵的顺序存储结构称为三元组表。
  注意：
　    以下的讨论中，均假定三元组是按行优先顺序排列的。
【例】下图(a)所示的稀疏矩阵A的三元组表表示见图(b)     
（1）三元组表的类型说明
　    为了运算方便，将矩阵的总行数、总列数及非零元素的总数均作为三元组表的属性进行描述。其类型描述为：
  #define MaxSize 10000 //由用户定义
  typedef int DataType； //由用户定义
  typedef struct { //三元组
    int i，j；//非零元的行、列号
    DataType v； //非零元的值
  }TriTupleNode；
  typedef struct{ //三元组表
    TriTupleNode data[MaxSize]； //三元组表空间
    int m,n，t； //矩阵的行数、列数及非零元个数
  }TriTupleTable；     
(2) 压缩存储结构上矩阵的转置运算
    一个m二维数组下标怎么理解×n的矩阵A，它的转置矩阵B是一个n×m的矩阵，且：
        A[i][j]=B[j][i]，0≤i<m，0≤j<n，
    即A的行是B的列，A的列是B的行。
【例】下图中的B和上图中的A互为转置矩阵。    
①三元组表表示的矩阵转置的思想方法
  第一步：根据A矩阵的行数、列数和非零元总数确定B矩阵的列数、行数和非零元总数。
  第二步：当三元组表非空（A矩阵的非零元不为0）时，根据A矩阵三元组表的结点空间data（以下简称为三元组表），将A的三元组表a->data置换为B的三元组表b->data。
②三元组表的转置
    　方法一:简单地交换a->data中i和j中的内容，得到按列优先顺序存储倒b->data;再将b->data重排成按行优先顺序的三元组表。
    　方法二:由于A的列是B的行，因此，按a->data的列序转置，所得到的转置矩阵B的三元组表b->data必定是按行优先存放的。
    　按这种方法设计的算法，其基本思想是：对A中的每一列col(0≤col≤a->n-1)，通过从头至尾扫描三元组表a->data，出所有列号等于col的那些三元组，将它们的行号和列号互换后依次放人b->data中，即可得到B的按行优先的压缩存贮表示。具体实现参见【动画演示】
③具体算法：
void TransMatrix(TriTupleTable *b，TriTupleTable *a)
{//*a，*b是矩阵A、B的三元组表表示，求A转置为B
  int p，q，col；
  b->m=a->n； b->n=a->m； //A和B的行列总数互换
  b->t=a->t； //非零元总数
  if(b->t<=0)
      Error("A=0")； //A中无非零元，退出
  q=0；
  for(col=0；col<a->n；col++) //对A的每一列
    for(p=0；p<a->t；p++) //扫描A的三元组表
      if(a->data[p]．j==col){ //列号为col的三元组
        b->data[q)．i=a->data[p].j；
        b->data[q]．j=a->data[p].i；
        b->data[q]．v=a->data[p].v；
        q++；
      }
 } //TransMatrix
④算法分析
  该算法的时间主要耗费在col和p的二重循环上：
    　若A的列数为n，非零元素个数t，则执行时间为O(n×t)，即与A的列数和非零元素个数的乘积成正比。
  通常用二维数组表示矩阵时，其转置算法的执行时间是O(m×n)，它正比于行数和列数的乘积。
    由于非零元素个数一般远远大于行数，因此上述稀疏矩阵转置算法的时间大于通常的转置算法的时间。
3、带行表的三元组表
    　为了方便某些矩阵运算，在按行优先存储的三元组表中，加入一个行表来记录稀疏矩阵中每行的非零元素在三元组表中的起始位置。这就是带行表的三元组表。
（1）类型描述
    #define MaxRow l00 //在三元组表定义前加入此最大行定义
    typedef struct {
      TriTupleNode data[MaxSize]；
      int RowTab[MaxRow]；//行表，应保证m≤MaxRow
      int m，n，t;
    }RTriTupleTable；

(2)带行表的三元组表的操作
① 对于任给行号i(0≤i≤m-1)，能迅速地确定该行的第一个非零元在三元组表中的存储位置为RowTab[i]
② RowTab[i](0≤i≤m-1)表示第i行之前的所有行的非零元数。
③ 第i行上的非零元数目为RowTab[i+1]-RowTab[i](0≤i≤m-2)
④ 最后一行(即第m-l行)的非零元数目为t-RowTab[m-1](t为矩阵的非零元总数)
  注意：
    　若在行表中令RowTab[m]=t（要求MaxRow>m）会更方便 些，且t可省略。
    　带行表的三元组表可改进矩阵的转置算法，具体【参阅其它参考书】。
4．稀疏矩阵压缩存储方式分析
（1） 三元组表和带行表的三元组表的特点
    　相应的算法描述较为简单，但这类顺序存储方式对于非零元的位置或个数经常发生变化的矩阵运算就显得不太适合。
  【例】执行将矩阵B相加到矩阵A上的运算时，某位置上的结果可能会由非零元变为零元，但也可能由零元变为非零元，这就会引起在A的三元组表中进行删除和插人操作，从而导致
大量结点的移动。对此类运算采用链式存储结构为宜。
（2）稀疏矩阵的链式结构
    　稀疏矩阵的链式结构有十字链表等方法，适用于非零元变化大的场合， 比较复杂，可【参阅其它参考书】。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。