数组和矩阵

数组

多维数组的存储和寻址：

• 已知数组A[a][b][c][d],每个元素占C个存储单元
• 数组元素A[i] j][k][l]的存储地址：
  • 行优先:Loc(A)+( i*b*c*d + j*b*d + k*d + l )*C
  • 列优先:Loc(A)+( i + j*a + k*a*b + l*a*b*c )*C

矩阵

矩阵的压缩存储

• 压缩存储需考虑2个问题
  • 需要多大存储空间：数组d[ ]需要多少元素
  • 地址映射：矩阵的任意元素M(i, j)在一维数组d[ ]中的位置（下标）， 即把矩阵元素的下标映射到数组d的下标

1. 对角矩阵的压缩存储

   1. 对于一个n*n的对角矩阵，至多只有n个非0元素，因此只需存储n个对角元素
   2. M( i , i ) -> d[ i ]

2. (下）三角矩阵的压缩存储

   1. 以按行优先方式压缩存放在一维数组d，d需要n(n+1)/2个元素
   2. M(i, j)= d[k]=d[i(i−1)/2 + (j−1)]

3. 对称矩阵M的压缩存储

   1. 对称矩阵中M(i, j)与M(j, i)的信息相同，只需存储M的下三角部分的元素信息。
   2. 对于对称矩阵中的下三角元素M(i, j) (i>=j) :
      1. i < j，M(i, j)=d[k]，k = i(i−1)/2 + (j−1)
   3. 对于上三角元素M(i, j) (i<j):元素值与下三角矩阵中的 元素M(j,i)相同
      1. i < j, M(i, j)=M(j, i)=d[q]， q= j(j−1)/2 + (i−1)

4. 三对角矩阵M的压缩存储

   1. 方阵Mn*n中任意元素M(i, j)，当| i - j | >1时，有M(i, j) =0， 则 M称为三对角矩阵。
   2. 需要3*n-2个存储单位
   3. 对于非零元素：即| i-j | <=1, M(i,j) = d[2*i + j - 3]

5. 稀疏矩阵的压缩存储

   1. 非零元素的个数远小于零元素的个数

   2. 三元组结点来存储矩阵的每个非零元素aij，其中i和j为元素的行号和列号，即node(i,j,aij)

      struct Triple{
          int row;
          int col;
          int value;
       };
      
       Triple Array[100];
      

      • 对于三元组有一个需要注意的算法：稀疏矩阵的快速转置。
      • 预先确定矩阵M中每一列（即T中每一行）的第一个非零元的位置
      • 求出每行非零元素个数，然后利用cpot[col]=copt[col-1]+num[col-1]，求出位置

   3. 十字链表:数据,该结点所在行 ,该结点所在列 ,指向左侧相邻非零元素的指针 ,指向上方相邻非零元素的指针,即node(row,col,value,left,up)

       struct ListNode{
          int row; //节点所在行
          int col; //节点所在列
          int value; //数据
          ListNode* left;//指向左侧相邻非零元素的指针
          ListNode* up; //指向上方相邻非零元素的指针
       };
      

1. 双向十字链表：在十字链表的基础上增加双方向的指针，并有循环链表的特点

    struct ListNode{
       int row; //节点所在行
       int col; //节点所在列
       int value; //数据
       ListNode* left;//指向左侧相邻非零元素的指针
       ListNode* up; //指向上方相邻非零元素的指针
       ListNode* right; //指向右侧相邻非零元素的指针
       ListNode* down;  //指向下方相邻非零元素的指针
    };